パリティ検査行列と最小距離復号

受信語 x'とパリティ検査行列Hの積 x'Hのことを, 受信語 x'のシンドロームといい, 線形符号の誤り訂正で重要な 役割を果たす. 受信語 x'を, 未知の送信語 xと誤りベクトル eを用いて,

x'=x+e

と書くというのは前にも述べたが, これにHを作用させると,

s=x'H=xH+eH=eH

となることが分かる. したがって, 線形符号の誤り訂正は, x'のシンドローム sに対して, s=eHなる eを求めることができればよい, ということになる.

したがって, 最小距離dの線形符号を用いた通信における最小距離復号による 誤り訂正は, 受信語 x'のシンドローム sから, s=eHを満たす 重みが(d-1)/2以下の誤りベクトル eを求めることで遂行される. s=eHを満たす重み(d-1)/2以下の誤りベクトル eが, 存在すれば唯一つしかないことは, ブロック符号のときと全く同じである. したがって, 線形符号の誤り訂正については, 連立一次方程式 s=eHから $w({\mathbf e})\le (d-1)/2$となる解を求めるための効率のよいアルゴリズムを 確立することが主要な問題となる.