どんな符号にも適用できる復号法として， 符号語全てをリストアップする手法 を紹介した．この手法では全ての符号語と受信語との距離を比較し， 距離が最小の受信語に復号する方法で， 符号語の数が多くなるとこの方法は計算量の面で 現実的でない．別のアルゴリズムとして ハミング復号も紹介した． ハミング復号はハミング符号専用の復号アルゴリズムで非常に効率的に 実行できる．[7,4]ハミング符号に対してハミング復号では 3つのベクトルとの内積をとればいいだけなのに対して 符号語全てをリストアップする方法では 16 個のベクトルに対して 受信語との距離の比較を行わなければならない． メモリ使用量も大きく違う．リストアップ法では 16 個の符号語を 記憶しなければいけないのに対し，ハミング復号では $\vec{a},\vec{b},\vec{c}$ の3個のベクトルを記憶するだけでよい．
一般的に特定の符号だけに使える特殊な復号アルゴリズムは あらゆる符号に使用できる汎用的なアルゴリズムよりも効率的である．
この節で説明するシンドローム復号は全ての符号に適用できる復号法で ありながら，リストアップする手法よりも効率的に実行できる 優れた復号法である．もし研究者がある符号専用の特殊な高速復号 アルゴリズムを開発したと思ったらまずはシンドローム復号と 比較してそれよりも効率的かどうかを比較するべきである．
ここまでは符号$C$ は $n$項組の空間 $V$ のベクトル部分空間とみなしていた． しかし $V$ は加法に基づいたアーベル群とみて $C$ をその部分群と みることもできる．シンドローム復号を理解するには コセットを理解する必要がある．
コセットは符号とベクトルの組 に対して定義される．$C$ が $GF(q)$ 上の $[n,k]$ 符号で $\vec{a}$ が $V$ の要素であるとき， $\vec{a}$ による $C$ のコセットとは 集合 $\{\vec{a} + \vec{c}| \vec{c} \in C \}$ のことで， $\vec{a} + C$ と記述される．和の記号が使われているが 加算ではないことに注意する．$\vec{a}+C$ という記述全体で一つの 集合を表す．
例 7.1
\[
G =\left(
\begin{array}{cccc}
1 & 0 & 1 & 0\\
0 & 1 & 1 & 1
\end{array}
\right)
\]
を生成行列とする符号のコセットを考える．
この符号の符号語は $C = \{0000, 1010, 0111, 1101\}$ である．
コセットは符号と $V$ の任意の要素であるベクトル一つを指定すると決まる．
ベクトル $\vec{v_1} = 0011$ による $C$ のコセット $\vec{v_1} + C$ は
定義より集合 $\{0011 + \vec{c} | \vec{c} \in C \}$，つまり
集合 $C$ の要素それぞれに $0011$ を加えたものなので
$\vec{v_1} + C = \{0011, 1001, 0100, 1110\}$ となる．
同じ符号 $C$ の別のベクトルによるコセットを考える． $\vec{v_2} = 0000$ としてコセット $\vec{v_2} + C$ を求めると， 定義より各符号語に $0000$ を加えたものからなる集合なので， 符号そのものとなり， $\vec{v_2} + C = \{0000, 1010, 0111, 1101\}$ となる．
次に $\vec{v_3} = 1001$ のときのコセット $\vec{v_3} + C$ を求める． 各符号語に $1001$ を加えることで $\vec{v_3} + C = \{1001, 0011, 1110, 0100\}$ となる． 集合は要素の順番の記載順が異なっても同じ要素から構成されるなら 同じ集合なので，上の例 $\vec{v_1} + C$ と同じ集合であることがわかる． このように，一般に異なるベクトルによるコセットが 同じ集合になることがある．
（例終わり）
空間 $V$ のどの要素 $\vec{v}$ についても $\vec{v}$ を含む コセットが存在する．例えばコセット $\vec{v}+C$ は $v$ を含む． これは線形符号であれば全ゼロ系列は符号語なので， $\vec{v}$ に全ゼロ系列を加えたものがコセット $\vec{v}+C$ の要素になる ためである．
$\vec{a}$ が符号語であればコセット $\vec{a} +C$ は $C$ そのものになる（例7.1 の 2 番目の例）．定義により $\vec{a} +C$ は符号語と符号語の和となり，線形符号の 性質により符号語になるためである．
例 7.1 の 1 番目の例と 2 番目の例では同じコセット $\{0011, 1001, 0100, 1110\}$ が $\vec{v_1} + C$，$\vec{v_2} + C$ の 2 つの異なるベクトルによって 作られている．このように，コセットはその要素のどの ベクトルによっても作られる．このコセットの例であれば \[ 0011 + C = 1001 + C = 0100 + C = 1110 + C = \{0011, 1001, 0100, 1110\} \] である．これは $\vec{v_2}$ が $\vec{v_1} + C$ の要素であれば， 定義より $\vec{v_2}$ はある符号語 $\vec{c}$ と $\vec{v_1}$ の和である． このことから $\vec{v_2} + C = (\vec{v_1} + \vec{c}) + C$ となる． これは $\vec{v_1} + \vec{c}$ に符号語を加えたものからなる集合であるが 加算の結合性と線形符号の性質により $\vec{c}$ に符号語を加えた ものが符号語になることから $\vec{v_1}$ に符号語を加えたものからなる 集合に等しい．よって $\vec{v_1} + C = \vec{v_2} + C$ になる．
以下の 4 つはコセットの重要な性質である．
この 4 つを上の例 7.1 で説明する．例 7.1 ではまず $0011$ によるコセット $\{0011, 1001, 0100, 1110\}$ と $0000$ によるコセット $\{0000, 1010, 0111, 1101\}$ が得られた． $1001$ は $0011$ によるコセットの要素であるから $1001$ によるコセットは $0011$ によるコセットと同じになる． そこで既に作られたコセットにない系列 $0001$ によるコセット を求めると $\{0001, 1011, 0110, 1100\}$ が得られる． 同様に未出現の系列 $0010$ によるコセットを求めることで $\{0010, 1000, 0101, 1111\}$ が得られる． これで全ての 4 ビットのビットパターンが現れたので 全てのコセットが得られた．
上のコセットの性質の 1 番目は，全てのコセットの 要素数が 4 であることをいっている．
2 番目は 例えば同じコセット$\{0011, 1001, 0100, 1110\}$ の要素 $0011$，$1001$ によるコセットは完全に 同一の $\{0011, 1001, 0100, 1110\}$ になり，別のコセットに属する要素 $0011$， $0000$ によるコセットはそれぞれ $\{0011, 1001, 0100, 1110\}$ と $\{0000, 1010, 0111, 1101\}$ であり， 全く共通要素が無い．
3 番目は全ての 4 ビットパターンが，4 つのコセットのどれかの 要素となっていることをいっている．
4 番目は，$C$ の生成行列 $G$ が 2 行 4 列であることから $n=4, k=2$ であるのでコセットの個数が $2^{n-k}=2^2$ である ことをいっている．
\[ G =\left( \begin{array}{cccc} 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 \end{array} \right) \] を生成行列とする符号 $C$について，
授業の6日後までにメールで提出せよ． メールの件名（サブジェクト）は CT07 とせよ．