通信路符号化(3) - 講義ノート

符号長n、情報ビットk、検査ビットm（n=k+m）のときη=k/nを符号の効率という。
訂正能力が高く効率のよい符号を見つけられるとうれしい

単一パリティ検査符号

符号語を各ビットのEx-ORを取った値が奇数もしくは偶数になるように構成する。
シンドローム *1は

1ビット誤りが生じた場合検出できる（0or1）
2ビット誤りが生じた場合は検出できない

単一パリティ検査符号は(k+1,k)符号であり、効率はη=k/(k+1)である。

線形符号

検査ビットが情報ビットの線形式（斉一次式）で表される符号
Cj=a1x1⊕a2x2⊕…⊕akxk ai∈{0,1}

特徴

2つの符号語の和は符号語

$w_1H^T=0$
$w_2H^T=0$
$(w_1+w_2)H^T=0$

符号語の定数倍は符号語
符号の最小距離は（全て0）以外の符号語の最小重み

符号語を（情報ビット）（検査ビット）の順で並べると
$H=\begin{bmatrix} a_{11} & a_{12} & \cdots &a_{1k} & 1 & 0 & \cdots & 0 \\ a_{21} & a_{22} & \cdots &a_{2k} & 0 & 1 & \cdots & 0 \\ \vdots & & & & & & & \vdots \\ a_{m1} & a_{m2} & \cdots &a_{mk} & 0 & 0 & \cdots & 1 \end{bmatrix}$
というように、パリティ検査行列Hは後ろmxm領域が単位行列となる。

シンドローム計算は
$Y=WH^T=EH^T$

誤り位置を探すには、シンドロームがH行列の縦方向のどれに一致しているかを探すことになる。その位置が誤り。

単一誤り訂正可能⇔{∀i hi≠0 , ∀ij hi≠hj (hi+hj≠h0) }

Hのどの異なるd-1個の列を加えても全零にならないが、あるd個の列を加えると全零になる⇔符号の最小距離=d

ハミング符号

d=3(単一誤り訂正可能)な符号を作成する

*1:受信符号を検査方程式に代入した値