復号手法
長さ n {\displaystyle n} で最小ハミング距離 d {\displaystyle d} の符号 C ⊂ F 2 n {\displaystyle C\subset \mathbb {F} _{2}^{n}} は、最小距離復号により t = ⌊ d − 1 2 ⌋ {\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor } 個以下の通信路で発生した誤りを訂正できる。シンドローム復号(Syndrome Decoding)は、線型符号のために最小距離復号を高効率に行う復号手法である。シンドローム復号は符号の線型性を利用して小さなルックアップテーブルを使うことで復号を可能にする。以下ではその方法を説明する。
符号語 y ∈ F 2 n {\displaystyle y\in \mathbb {F} _{2}^{n}} を通信する際、誤りパターン e ∈ F 2 n {\displaystyle e\in \mathbb {F} _{2}^{n}} が発生したとする。すると受信されるメッセージは x = y + e {\displaystyle x=y+e} となる。
シンドローム復号では、与えられた符号のパリティ検査行列 H ∈ F 2 ( n − k ) × n {\displaystyle H\in \mathbb {F} _{2}^{(n-k)\times n}} を用いて受信したメッセージ x {\displaystyle x} のシンドローム H x {\displaystyle Hx} を計算する。ここで k {\displaystyle k} は符号語のなす部分空間の次元である。パリティ検査行列 H {\displaystyle H} は全ての x ∈ C {\displaystyle x\in C} について H x = 0 {\displaystyle Hx=0} となる性質を持つため
H x = H ( y + e ) = H y + H e = 0 + H e = H e {\displaystyle Hx=H(y+e)=Hy+He=0+He=He}
が成立する。 t {\displaystyle t} 個を超える誤りが発生しない前提で全ての誤りパターン e ∈ F 2 n {\displaystyle e\in \mathbb {F} _{2}^{n}} について値 H e {\displaystyle He} を事前に求めておきルックアップテーブルを作成しておけば、 x {\displaystyle x} のシンドロームから誤りパターン e {\displaystyle e} を得ることができる。
メッセージ x ∈ F 2 n {\displaystyle x\in \mathbb {F} _{2}^{n}} を受信したとき、最尤復号(Maximum Likelihood Decoding)では、
P ( x received ∣ y sent ) {\displaystyle \mathbb {P} (x{\mbox{ received}}\mid y{\mbox{ sent}})}
が最大となるような符号語 y ∈ C {\displaystyle y\in C} を選択する。すなわち、 x {\displaystyle x} を受信したときの条件付き確率の最も高い符号語 y {\displaystyle y} を選択する。なお、全ての符号語の出現確率が同じである場合、これは「最適復号」と等価である。