第4章離散的通信路符号化(5くらい?)

復習

線形符号

チェックビットが符号ビットのex-OR演算で求められる

例えば(7,4)だと
c1=x1⊕x2⊕x4
c2=x1⊕x3⊕x4
c3=x2⊕x3⊕x4
検査行列Hは
$H=\begin{bmatrix} 1 & 1 & 0 & 1 & \vdots & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & \vdots & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & \vdots & 0 & 0 & 1 \end{bmatrix}$
生成行列Gは
$G=\begin{bmatrix} 1 & 0 & 0 & 0 & \vdots & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & \vdots & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & \vdots & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & \vdots & 1 & 1 & 1 \end{bmatrix}$

最小重みを考えれば誤り訂正能力とか考えられるから無問題

ハミング符号
単一誤り訂正能力を持つ最も効率のよい符号
長さn=2^(m)-1となるハミング符号を構成することができる。

ハミング符号に対し、H行列の横方向に偶数パリティ・縦方向に奇数パリティを付加すると最小距離dmin=4の符号ができる。

巡回符号

W=(Wn-1,Wn-2, ... ,W0) 符号語
$W(x)=W_{n-1}x^{n-1} + W_{n-2}x^{n-2} + \cdots + W_1x + W_0$
$W(x)=G(x)Q(x)$
G(x)はm次多項式、Q(x)はn-m-1次以下、符号語はG(x)で割り切れる2^(n-m)個
G(x)はx^n-1の因数多項式で、Q(x)が符号多項式

連続するm以下の誤りを検出することができる。