シンドローム復号の正しさ

$C$ を $[n, k, d]_q$ 符号、$H$ を検査行列、$t = \lfloor (d-1)/2 \rfloor$ とする。

1. $S(\boldsymbol{y}) = S(\boldsymbol{y}') \iff \boldsymbol{y} - \boldsymbol{y}' \in C$。$S : \mathbb{F}_q^n \to \mathbb{F}_q^{\,n-k}$ は全射で、シンドロームと $C$ の剰余類は 1 対 1 に対応する。剰余類は $q^{n-k}$ 個ある。
2. 各シンドローム $\boldsymbol{s}$ に対し、対応する剰余類の代表元 $\boldsymbol{e}_{\boldsymbol{s}}$ を 1 つ選んでおく。受信語 $\boldsymbol{y}$ に対し $\hat{\boldsymbol{c}} = \boldsymbol{y} - \boldsymbol{e}_{S(\boldsymbol{y})}$ を出力する復号は最小距離復号である。すなわち $\hat{\boldsymbol{c}} \in C$ で、すべての $\boldsymbol{c}' \in C$ について $d(\hat{\boldsymbol{c}}, \boldsymbol{y}) \le d(\boldsymbol{c}', \boldsymbol{y})$。
3. 符号語 $\boldsymbol{c}$ を送り $\boldsymbol{y} = \boldsymbol{c} + \boldsymbol{e}$ を受け取ったとき、復号結果が $\boldsymbol{c}$ になることと、$\boldsymbol{e}$ が選んでおいた代表元の 1 つであることは同値である。$\mathrm{wt}(\boldsymbol{e}) \le t$ ならば $\boldsymbol{e}$ はその剰余類のただ 1 つの代表元で、復号結果は $\boldsymbol{c}$ になる。