６．通信路符号化・線形符号
公開状態にしてますが、編集中です。
間違いや表記ゆれがあります。
ハミング距離
ハミング距離は、二つの系列の違いを数値で表す手段。
これを代数的に捉える。
長さ$${n}$$の二つの系列
$${a=\{a_1,a_2 \cdot \cdot \cdot ,a_n\}}$$
$${b=\{b_1,b_2 \cdot \cdot \cdot ,b_n\}}$$
について考える。
$${a,b}$$に互いに対応する位置にあるシンボルで異なるものがハミング距離である。
$${d_H(a,b)=\displaystyle \sum_{i=1}^n \delta(a_i,b_i)}$$
クロネッカーのデルタを用いて、その距離を考える。
$${\delta(x,y) = \begin{cases} 0 & (x =y) \\ 1 & (x \ne y) \end{cases}}$$
2元系列系では、
01と$${x,y}$$関係から排他的論理和(XOR)を利用すれば良いので、
$${d_H(a,b)=\displaystyle \sum_{i=1}^n(a_i \oplus b_i)}$$
一方の系列（ここでは、$${a}$$とする）とすべてのシンボルが0である系列0との距離を$${a}$$の重みといい、この距離にハミング距離を用いたものをハミング重みという。
$${w_H(a)=d_H(a,0)=\displaystyle \sum_{i=1}^n \delta(a_i,0)}$$
以上から、二元系列系の両者の関係は、
$${d_H(a,b)=w_H(a \oplus b)}$$
例題
$${a=(0,0,0),b=(1,0,0)}$$の時、
ハミング距離と$${a}$$のハミング重みを求める。
$${d_H(a,b)=0\oplus1+0\oplus0+0\oplus0}$$
$${=1+0+0=1}$$
$${w(a)=0+1+1=2}$$
誤り検出
符号$${C}$$に含まれる異なる二つの符号語$${a_i,a_j}$$のハミング距離$${d_H(a_i,a_j)}$$の最小値
$${d_{\min}=\displaystyle\min_{i \ne j}d_H(a_i,a_j)}$$
これを符号$${C}$$の最小距離という。
図のように半径$${t}$$が、
$${d_{\min} \ge 2t+1}$$
を満足すれば、他の球と共通の系列を持たない。
さらに、
$${t'=d_{\min} - (2t+1)}$$は、他の球と共通の系列を持たない。
$${t+1}$$個以上$${t+t'}$$以下の誤りは、
訂正できないが、検出はできる。
訂正は、検出されることが基となるから、
訂正＞検出の関係性。
以上のことから、
$${t}$$個以下の誤り訂正、
$${t+t'}$$個以下の誤り検出が可能にするには、
$${d_{\min} \ge 2t+t'+1}$$
例題
$${a=(0,0,0),b=(1,1,1)}$$
の時、何個の誤りを訂正できるか？
ハミング距離は３。
$${3 \ge 2t+1}$$
$${t \le 1}$$
したがって、一個以下の誤り訂正が可能。
総括問題
(7,4)ハミング符号を使用して、通信路の送信側で情報ビットを符号化し、受信側で誤り訂正で行い復号する。
４つの情報ビットがすべて正しく得られる確率を求めよ。
(7,4)ハミング符号は、最小距離は３。
それ以下の組み合わせは存在しない。
画像で、後述する生成行列を示しているが、
３つの検査ビットの取り方$${2^3}$$通りの中でも、最小距離は３になる。
誤り訂正は、
$${3 \ge 2t+1}$$
$${t \le 1}$$
誤り検出は、
$${3 \ge (2t+1) +1}$$
$${t \le 2}$$
４つの情報ビットを全て正しく得るには、
１つ誤りの場合でも、訂正できるからOK。
２つ誤りがあると検出はできるが、訂正はできない。
何かしらの誤り源を想定して計算をする。
ここでは、加算的２元通信路を考える。
送信シンボル$${\{0,1\}}$$の定常確率が、
$${q_0=\displaystyle\frac{1}{3}}$$、$${q_1=\displaystyle\frac{2}{3}}$$
とする。
加算的２元通信路では、1が誤りになるから、
$${(q_0)^7+_7C_1(q_0)^7(q_1)\displaystyle\frac{64}{243}}$$
線形符号
伝送する系列情報ビット$${i}$$と
誤り検出・訂正のために付加する検査ビット$${p}$$を考える。
$${k}$$個のシンボルで構成される情報ビットと$${n-k}$$このシンボルで構成される検査ビットを付加した、
長さ$${n}$$の系列符号語とする符号を$${(n,k)}$$符号という。
そして、符号語$${a}$$の情報ビット$${i}$$、検査ビット$${p}$$は、
それぞれ行ベクトルで表される。
$${a=\{ \bold i,\bold p\}}$$
$${=\{i_1,i_2 \cdot \cdot \cdot i_k,p_1,p_2 \cdot \cdot \cdot p_{n-k}\}}$$
また、
$${\begin{pmatrix} p_1 \\ p_2 \\\cdot\\\cdot\\\cdot\\p_{n-k}\end{pmatrix}＝\bold P\begin{pmatrix} i_1 \\ i_2 \\\cdot\\\cdot\\\cdot\\i_{k}\end{pmatrix}}$$
$${p^{ \mathrm{ T }}=Pi^{ \mathrm{ T }}}$$
$${p=iP^{ \mathrm{ T }}}$$
2を法とした計算
要するに、合同式（$${\mod 2}$$）
modは、あまりの数に注目する。
$${2\times3 \equiv1 \mod 5}$$
$${2 \times 3}$$を5で割ると、1になる。
このとき、5を法とした計算という。
情報理論の世界は、$${0,1}$$なので、
乗算の場合は、
$${0\times 0=0,0\times 1=0 ,1\times 0=0,1\times 1=1}$$
加算の場合（重要）は、
$${0＋0=0,0+ 1=1 ,1+ 0=1,\bold {1+ 1=0}}$$
1+1=0は違和感がありますが、
２を法の場合は正しいです。
生成行列
生成行列は、符号語$${a}$$から定義する。
$${a=\{ \bold i,\bold p\}}$$
$${=\{ \bold i,\bold {ip^T}\}}$$
$${=\{ \bold {iI_k},\bold {ip^T}\}}$$（※$${I_k}$$は、$${k}$$次正方行列。）
$${=\bold i\{\bold {I_k},\bold {p^T}\}}$$
このとき、$${a=\{ \bold i,\bold G\}}$$とした、
$${\bold G=\{\bold {I_k},\bold {p^T}\}}$$を生成行列という。
情報ビット$${i}$$から、符号語$${a}$$を生成する行列という意味を成している。
検査行列
$${Pi^{ \mathrm{ T }}-p^{ \mathrm{ T }}=0^T}$$
2を法とする加算と減算は同じなので、
$${Pi^{ \mathrm{ T }}＋p^{ \mathrm{ T }}=0^T}$$
$${\begin{pmatrix} P , I_{n-k}\end{pmatrix}\begin{pmatrix} i^T \\ p^T\end{pmatrix}=0^T}$$
$${\begin{pmatrix} P , I_{n-k}\end{pmatrix}a^T=0^T}$$
検査行列$${H}$$は、
$${H=\begin{pmatrix} P , I_{n-k}\end{pmatrix}}$$
で示されて、
$${Ha^T=0^T}$$
$${aH^T=0}$$
この式から、受信側で誤り検査をすることができることを示している。
誤り検出・訂正
最小距離$${d_{\min}}$$を得ると、訂正可能な誤りの個数が分かる。
$${d_{\min}=d_H(a_1,a_2)=w_H(a_1,a_2)}$$
線形符号における誤り検出・訂正は、受信語$${\bold b}$$と検査行列$${\bold H}$$により、
$${\bold s=\bold {bH}^T}$$
$${\bold s}$$は、シンドロームといい、誤りの検出が可能となる。
$${ \bold s=\begin{cases} 0 & (誤りなし) \\ 1 & (誤りあり) \end{cases}}$$
パリティ検査符号
パリティ検査符号は、$${(k+1,k)}$$線形符号で、長さ1。
検査ビットは次式で計算できる。
$${p_1=i_1+i_2+…+i_k}$$
$${= \begin{cases} 0 & (情報ビットの1の個数が偶数) \\ 1 & (情報ビットの1の個数が奇数) \end{cases}}$$
符号語内の1の個数が必ず偶数となるものを偶数パリティ、
符号語内の1の個数が必ず奇数となるものを奇数パリティと呼ぶ。
例えば、情報ビットが$${101}$$の場合、
偶数パリティは$${101\bold 0}$$
奇数パリティは$${101\bold 1}$$
偶数・奇数どちらも最小距離は2。
誤り訂正は不可能だが、1個の誤り検出は可能。
原理的には、任意の奇数個の誤り検出、偶数個の復号。
巡回符号
ある符号語$${\bold{a}=[a_0,a_1…a_{n-1}] }$$を１つ右にずらす。
$${\bold{a'}=[a_{n-1},a_0,a_1…a_{n-2}] }$$
この操作を巡回シフトといい、
巡回符号は、任意の符号語の巡回シフトが再度符号語となる線形符号。
長さ$${n}$$の符号語$${\bold{a}=[a_0,a_1…a_{n-1}] }$$で、$${a_j}$$を$${x^j}$$の係数とする多項式を$${A(x)}$$とすると、
$${A(x)=a_0+a_1x^1+a_2x^2+…+a_{n-1}x^{n-1}}$$
を得る。この$${A(x)}$$を$${\bold{a}}$$の符号多項式という。
多項式の演算は法を2($${\mod 2}$$)で行う。
符号語$${\bold{a}=[0,1,0,1]}$$,$${\bold{b}=[1,1,1,1]}$$を符号多項式にして、四則演算せよ。
$${A(x)=0\times x^0+1\times x+0\times x^2+1\times x^3=x^3+x}$$
$${B(x)=1\times x^0+1\times x+1\times x^2+1\times x^3=x^3+x^2+x+1}$$
$${A(x)+B(x)=(1+1)x^3+(1+0)x^2+(1+1)x＋(1+0)=x^2+1}$$
$${A(x)-B(x)=A(x)+B(x)=x^2+1}$$
※+,-を入れ替えて計算しても分かる。
$${A(x)B(x)=(x^3+x)(x^3+x^2+x+1)=x^6+x^5+x^4+x^3+x^4+x^3+x^2+x=x^6+x^5++x^2+x}$$
$${\displaystyle \frac{B(x)}{A(x)}=\displaystyle \frac{x^3+x^2+x+1}{x^3+x}=1+\displaystyle \frac{x^2+1}{x^3+x}}$$
商は$${1}$$、剰余は$${x^2+1}$$。
多項式$${A(x)}$$で割り切れる$${x^n-1}$$の内で最小の$${n}$$の値を$${A(x)}$$の周期という。
また、$${m}$$次多項式には、周期が存在していて、$${2^m-1}$$となるものを原始多項式と呼ぶ。
$${1+x+x^2}$$,$${1+x+x^3}$$の周期を求めよ。
周期は、${x^n-1}$$で割り切れるものだから、
$${x^3-1=(1+x+x^2)(1+x)}$$
$${n=3}$$より、周期は3
$${x^7-1=(1+x+x^3)(1+x+x^2+x^4)}$$
$${n=7}$$より、周期は7