定理2で，符号の最小重みが $d$ のとき， 符号語を中心とした半径 $t = \lfloor(d-1)/2\rfloor$ の球は排他的， すなわちすべて互いに重ならないことを示した．一般に全空間 $V$ にはこれらのどの符号語の球にも属さないベクトルが存在する． このことは符号語を中心とした球に含まれるベクトルの個数を数える ことで調べることができる． \[ G =\left( \begin{array}{cccccc} 1 & 0 & 0 & 0 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 & 1 & 0 \end{array} \right) \] を生成行列とする$[6,3,3]$ 2元線形符号符号 $C$ を考える． $t = \lfloor(3-1)/2\rfloor = 1$ なのでこの符号の誤り訂正能力は 1 である．符号語を中心とした半径 $t = 1$ の球に所属する ベクトルの個数を求める．まず，符号語として全ゼロのベクトルを 考える．線形符号なので全ゼロのベクトルは必ず符号語である． 全ゼロの符号語を中心とした半径 $1$ の球には，中心の その符号語自身 1 個と，6 個の重み 1 のベクトル（符号語長が 6 だから） の合計 7 個のベクトルが所属している．注意すべきなのは 全ゼロ以外の符号語についても符号語を中心とする半径 1 の球には 同じ数のベクトルが含まれていることである． ある符号語 $\vec{c}$ を中心とする球に所属する符号語は， ゼロベクトルを中心とする球に所属する符号語を $\vec{c}$ に 足したものだからである． 符号 $C$ の符号語は $2^k = 2^3 = 8$ 個である．空間 $V$ の中に 重ならない $8$ 個の球があり，その $1$ つづつに $7$ 個の ベクトルが含まれるので，どれかの球に所属するベクトルは $7\cdot8=56$ 個ある．全空間 $V$ のベクトルの個数は $2^n=2^6=64$ 個だから，$8$ 個のベクトルがどの符号語を中心とする半径 $t=1$ の球にも含まれないことがわかる．
最小重み $d$ の符号 $C$ について， $V$ の全てのベクトルがどれかの符号語を中心とする半径 $t = \lfloor (d-1)/2 \rfloor$ の球に含まれるとき， $C$ は完全符号であるという．このとき， 球は空間を被覆するという．
完全符号は重み $t$ 以下の誤りパターンは全て正しく訂正できるが， それを超える重みの誤りはどれも正しく訂正されない．符号が 誤って復号される現象は確率的には符号語間のハミング距離が 最も小さいペアで起こることがほとんどなので， 誤って復号される確率は符号語間の距離の最小値でほぼ見積もることができる． 線形符号では符号語間の距離の最小値は符号の最小重みに等しいので 符号の最小重み $d$ が大きければ大きいほど信頼性の高い符号である ことを意味する．完全符号は与えられた $n$, $k$ に対して最大の 最小重みをもつので最良の符号であるといえる．また，完全符号は 数学的にも興味深い構造をもつので多くの人々が完全符号を探すことに 時間を費やした．この研究の結果を示す前に，いくつかの 完全符号についてそれが完全符号であることを説明する．
2元 $[7,4,3]$ ハミング符号は完全符号である．これも上で行なった 符号語を中心とする球に所属するベクトルの数え上げで確認できる． $d=3$ なので誤り訂正能力は $t=\lfloor (3-1)/2\rfloor = 1$ である．符号語を中心とする半径 $1$ の球には，中心の符号語 $1$ 個と，$n=7$ なので符号語からハミング距離が $1$ のベクトルは $7$ 個あるので合計 $8$ 個である．符号語の数は $2^k=2^4=16$ 個なのでどれかの球に所属するベクトルは $8\cdot16=128$ 個で， 符号語長 $7$ の全空間のベクトル数 $2^7=128$ に一致する． このことから 2元 $[7,4,3]$ ハミング符号が完全符号であるといえる． 他に完全符号であることが知られている 2つの符号は 2元 $[23,12,7]$ ゴレイ符号と 3元 $[11,6,5]$ ゴレイ符号である．
$V$ のベクトル全てを符号語とする符号や，符号語長が奇数の 繰り返し符号が完全符号であることは自明である（しかし実用的ではない）ので これらの符号を自明な完全符号という．
いくつかの方法で 2 元 $[7,4,3]$ ハミング符号が 単一誤り訂正符号である（ $t=1$である）ことを示した． ここでは別の方法で説明する． 2 元 $[7,4,3]$ ハミング符号の パリティ検査行列は以下のものである． \[ H =\left( \begin{array}{ccccccc} 0 & 1 & 1 & 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{array} \right) \] $H$の列（縦）をみると，全ての列（3ビット）は違うビットパターンに なっていることがわかる．3ビットのビットパターンは 8 個だから $H$ は全ゼロ以外のビットパターン全てで列ベクトルが 作られていることがわかる．シンドローム復号を行うことを 考える．送信した符号語が $\vec{x} \ \ (\in C)$ であり 重み 1 の誤り $\vec{e}$ がおこって $\vec{y} = \vec{x} + \vec{e}$ が受信されたとする．シンドロームは \[ \mbox{syn}(\vec{y})=H\vec{y}^T=H\vec{x}^T + \vec{e}^T=H\vec{e}^T \] である．つまり $H$ から $e$ の $1$ がある列と同じ位置の列だけを取り出した 列ベクトルがシンドロームとなる．$H$ の各列が全て異なっているので 1 ビットの誤りであればシンドロームを見れば何番目のビットが誤っていたか が特定できる．シンドロームが \[ \left( \begin{array}{c} 0\\ 0\\ 1 \end{array} \right) \] ならば 7 ビット目が誤り， \[ \left( \begin{array}{c} 0\\ 1\\ 0 \end{array} \right) \] ならば 6 ビット目が誤り， というように特定できる．誤りが無かった場合 はシンドロームはゼロベクトルになる．
$H$ をもっとわかりやすいように変形する．狙いは 3 ビットのビットパターンを 2 進表記で読むとちょうど ビット位置になるように配置することである． 生成行列もパリティ検査行列も，ある行（横）を 他の列との排他的論理和で置き換えても同じ符号の 生成行列，パリティ検査行列になる．これを基本行操作という． $H$ に対して第2行に第3行を排他的論理和で足し込むと \[ \left( \begin{array}{ccccccc} 0 & 1 & 1 & 1 & 1 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{array} \right) \] が得られる．この第1行に第2行を排他的論理和で足し込むと \[ \left( \begin{array}{ccccccc} 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{array} \right) \] が得られる．この第3行に第2行を排他的論理和で足し込むと \[ \left( \begin{array}{ccccccc} 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \end{array} \right) \] が得られる．この第3行に第1行を排他的論理和で足し込むと \[ H'=\left( \begin{array}{ccccccc} 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{array} \right) \] が得られる．$H'$ は基本行操作のみで得られたので $[7,4,3]$ハミング符号のパリティ検査行列であってその列は列番号の 2進表記に一致している．この $H'$ を使ってシンドロームを 計算すると，シンドロームを 2進数として読むとそのまま 誤りの位置になる．$H'$ の第1行を$\vec{a}$， 第2行を$\vec{b}$，1第3行を$\vec{c}$としたものがハミング復号で， $H'$ をパリティ検査行列としてシンドローム復号を行うことと 同じであることがわかる．
ここまでをまとめると， [7,4,3]ハミング符号は 1 ビット誤りに対してシンドロームを 2 進数として読むとそれが誤りビット位置になるように設計されていて， 1から7の2進表記を列ベクトルとする $H'$ をパリティ検査行列とする符号といえる．この符号では $H'$ を基本行操作だけでパリティ検査行列としての標準形の $H$ に変形することができるので， 定理1 を使うことで標準形の生成行列を得ることができる． 標準形の生成行列をもつので[7,4,3]ハミング符号は 生成行列の前半 4 列は単位行列である．この場合，4 ビットめまでは 入力ビットがそのまま出力されるので符号語の前半4ビットは 情報ビット，後半 3 ビットは誤り訂正のための冗長ビット というように 2 分できる．このような符号を組織符号 という．
この方法を一般化することで，単一誤り訂正可能な符号の族（集合の集合） を無限に作ることができる．$[7,4,3]$ ハミング符号は パリティ検査行列が $3$ 行のときの符号で，一般に $r$ 行のときの 符号を構成できる．これは一般化2元ハミング符号 とよばれ，$\mbox{Ham}(r,2)$ と記述される．$\mbox{Ham}(r,2)$ は $r$ ビットのゼロベクトル以外の全てのビットパターンを列ベクトルとする パリティ検査行列によって定義される符号である．$[7,4,3]$ハミング符号は $\mbox{Ham}(3,2)$ にあたる．$[7,4,5]$ハミング符号のときと同様に 列のビット列列番号の 2 進表記になるように並べると $[7,4,3]$ハミング符号で説明したハミング復号と同様に復号できる．
例10.1
$Ham(4,2)$のパリティ検査行列は $4$ ビットのゼロベクトル以外の
パターンなので以下のようになる．
\[
H=\left(
\begin{array}{ccccccccccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 &
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 1 & 1 & 1 & 1 &
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\
0 & 1 & 1 & 0 & 0 & 1 & 1 &
0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 &
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1
\end{array}
\right)
\]
1ビット誤りが起こった場合は受信後のシンドロームを計算し，
それをを2進表記の数値として読めば誤り位置になる．
重み1のベクトルのシンドロームは$H$の対応する列を 切り出した列ベクトルになる．これが全て異なることから $\mbox{Ham}(r,2)$ は全て単一ビット誤り訂正可能であることがわかる． $\mbox{Ham}(r,2)$ のパリティ検査行列は $r$ 行の行列であり， $r$ ビットのビット列でオールゼロ以外のものは $2^r-1$ 個あるから パリティ検査行列は $2^r-1$ 列である．このことから符号語長 $n = 2^r-1$ であることがわかる．一般に $[n,k]$ 線形符号の生成行列は $k$ 行 $n$ 列，パリティ検査行列は $n-k$ 行 $n$ 列であるから， $\mbox{Ham}(r,2)$ の生成行列は $n-r = 2^r - 1 -r$ 行 $n$ 列であることがわかる．$\mbox{Ham}(r,2)$ を $[n,k,d]$の符号パラメータの形で書くと $[2^r-1, 2^r-1-r, 3]$ 2元線形符号ということになる．
一般化ハミング符号 $\mbox{Ham}(r,2)$ の誤り訂正能力 $t$ が 1 であることがわかれば，完全符号で最小重みが $d=3$ であることがわかる．
一般化2元ハミング符号 $\mbox{Ham}(r,2)$ について以下の問に答えよ． メールで冪乗を書く場合は $a^b$ を a^b と書いてよい．
授業の6日後までにメールで提出せよ． メールの件名（サブジェクト）は CT10 とせよ．