符号理論で重要なベクトルの重み， 符号の最小重みの定義を説明する． また，最尤復号の定義を説明し， 重みを使って最尤復号の意味付けについて説明する．
重みはベクトルに対して定義される量である． ベクトル $\vec{u}$ の重みとは $\vec{u}$ の成分のうち， 0 でないものの個数で，$wt(\vec{u})$ と書く． 例えば $\vec{u} = (1010000)$ であれば $wt(\vec{u}) = 2$ である． 2 元符号では 0 でないものは 1 しかないので 1 の個数が重みとなる．
要素が全て 1 である長さ $n$ のベクトルを $\vec{h} =(1,1,\ldots,1)$ と書く．長さ $n$ の $\vec{h}$ の重みは $n$ である．$h$ を 1 行 $n$ 列の行列として考えるとこれを生成行列として得られる符号は $[n,1]$ 繰り返し符号となる．例えば $n=3$ のとき，生成行列は \[ G=(1 1 1) \] であるから，この唯一の行を足さないとき（000），足すとき （111）の2つの符号語からなる符号を生成するので $[3,1]$ 3回繰り返し符号であることがわかる．
$C$ を生成行列が $\vec{h}$ である $[n, 1]$ 繰り返し符号とすると 前節の定理1を使って $C$ の検査行列を作ることができる．$\vec{h}$ は左端の $(1)$ を 1 行 1 列の単位行列 $I$，残りの $n$ 個の $(1,1,\ldots,1)$ を 1 行 $n-1$ 列の行列 $A$ と考えると $\vec{h} = (I,A)$ の形であるから標準形である．定理1により $(-A^T,I)$ が検査行列になる．これは \[ E_n=\left( \begin{array}{rrrrr} 1&1&0& \ldots &0\\ 1&0&1& \ldots &0\\ \vdots & \vdots & \vdots & \ddots &\vdots\\ 1&0&0& \ldots &1\\ \end{array} \right) \] となる．最も左の第1列が $n-1$ 行 $1$ 列の行列 $-A^T$ で， 残りが $n-1$ 行 $n-1$ 列の単位行列 $I$ である． $E_n$ は $C$ の検査行列であるから $[n,n-1]$ 符号 $C^\perp$ の生成行列である．この $C^\perp$ は 値が 1 である要素が偶数個あるベクトルの集合であり，偶パリティ符号 とよばれる．上の $G=(1 1 1)$ を生成行列とする例については検査行列は \[ E_3=\left( \begin{array}{rrr} 1&1&0\\ 1&0&1 \end{array} \right) \] となり，$E_3$ を生成行列とする符号は $\{000, 110, 101, 011\}$ である．1の個数が偶数個の 3 ビットの系列からなる符号であることがわかる．
最小重みは符号に対して定義される量である． 符号 $C$ の最小重みとは，$C$ の符号語のうち成分が全て0であるベクトル 以外の符号語の重みの最小値である．
最小重みは符号にとって重要なパラメータの一つで，慣例として 符号長を $n$，情報ビット数を $k$ で表すのと同様に最小重みは $d$ で表される．$[n, k]$ 符号という形式で $n, k$ の値を 記述するときは $d$ も加えて $[n, k, d]$ 符号と書かれることもある． 重みなのに何故 $d$ なのかについて説明すると， $d$ は最小重みというよりも符号語どうしの距離の 最小値という意味あいで使われることがほとんどだからである． ベクトルどうしの距離は後で定義するが，線形符号であれば 符号語どうしの距離の最小値と最小重みは一致することが知られている．
$E_n$ で生成される符号の最小重みは 2 である．これは それよりも重みの小さい全0以外のベクトルは 1 の個数が 1 個である，つまり 偶数個ではないのでそのような符号語は存在しない． また，重み 2 の符号語は生成行列の いずれかを選べばいいので存在することからいえる．
以下の標準形の $G$ を生成行列とする $[7, 4]$ ハミング符号の $d$ を考える． \[ G=\left( \begin{array}{rrrrrrr} 1&0&0&0&0&1&1\\ 0&1&0&0&1&0&1\\ 0&0&1&0&1&1&0\\ 0&0&0&1&1&1&1 \end{array} \right) \]
$2^4=16$ 個の全ての符号語を書き出すことで最小重み $d$ を みつけることはできるが，より組織的な方法でも発見することができる．
重要な事は符号語は生成行列の行の和で表せるもの全てである， ということである．$G$ の第1行はそれだけで符号語の一つであり， 重みが $3$ なので最小重みは $3$ 以下であることがわかる． あとは行の和によって重み $2$ のベクトルを作り得ないことが いえれば $d =3$ であるといえる．
$G$ の第1行を$\vec{g_1} =(1000011)$ とし，第 $2,3,4$ 行も それぞれ $\vec{g_2} =(0100101), \vec{g_3}=(0010110), \vec{g_4}=(0001111)$ とする．符号語は行を1個も足さない，1個足す，2個足す， 3個足す，4個足す，のいずれかで生成できる．4 個以上足すなら同じものを 2度以上足すことになり，同じもの 2 個の和は 0 ベクトルだから その 2 個の和を省略できるからである．
0個足す場合
全0の符号語が得られる．定義よりこれは最小重みにならない．
1個足す場合
$\vec{g_1},\vec{g_2},\vec{g_3},\vec{g_4}$ の 4 つである．
この場合の重みの最小値は $3$ である．
2個足す場合
$G$ は標準形で，前半は 4 行 4 列の単位行列
\[
I=\left(
\begin{array}{rrrr}
1&0&0&0\\
0&1&0&0\\
0&0&1&0\\
0&0&0&1
\end{array}
\right)
\]
である．
よって 4 列目まではどの行にも 1 が 1 個あり，場所が
互いに異なるのでどの 2 行を足しても 1 の個数は 2 個になる．
後半の 4 行 3 列の部分
\[
A=\left(
\begin{array}{rrrr}
0&1&1\\
1&0&1\\
1&1&0\\
1&1&1
\end{array}
\right)
\]
には同一な行は無い．つまりここから 2 個の和を作ると
全0にはならず，必ず 1 個は 1 が生成される．
以上のことから，1-4 列目に 2 個，5-7 列目に 1 個は
1 があるはずなので重みが 3 より小さい符号語は存在しない．
3個か4個足す場合
1-4列の単位行列部分から 3 または 4 個の 1 が生成されるので
重みが 3 より小さい符号は存在しない．
すべての場合において重みが 3 より小さい全0以外の 符号語は存在しないので$[7,4]$ハミング符号の最小重み $d$ が 3 であることがいえた．3つのパラメータを書く方式で書くと， このハミング符号は $[7,4,3]$ 符号と書ける．
符号の中に重みいくつの符号語が何個あるか，という分布を 重み分布といい，配列 $A_i$ で表す． $A_0$ は重み $0$ の符号語の個数， $A_1$ は重み $1$ の符号語の個数，... $A_i$ は重み $i$ の符号語の個数，... $A_n$ は重み $n$ の符号語の個数を示す．
線形符号は必ず全0のベクトルを符号語としてもつので常に $A_0=1$ である．
[7,4,3]ハミング符号の重み分布を求めてみる．もちろん 全ての符号語を書き出すことで求めることもできるが， $d=3$ であることを既に知っているので効率的に求めることが できる．
生成行列の全ての列の和をとると $\vec{h} = (1111111)$ が 符号語であることがわかる．一般に線形符号では零ベクトル $\vec{0}$ は必ず符号語であるが全1のベクトル $\vec{h}$ は 符号語であるとは限らない．$[7,4,3]$ ハミング符号は 全1ベクトル $\vec{h}$ を符号語としてもつタイプで，この場合は 重み分布の計算が簡単になる．
全1ベクトル $\vec{h}$ が符号語ということは，線形符号は 符号語と符号語の和は必ず符号語になるので全ての 符号語に対して全 1 ベクトル $\vec{h}$ との和も 符号語になる．ところで，全 1 ベクトル $\vec{h}$ との和はもとの 符号語の 0 と 1 を反転したものとなる． つまり，全ての符号語に対して 0 と 1 を反転させたベクトルも 必ず符号語として存在しているといえる．ビット反転の関係にある ベクトルの重みは対称関係がある．符号長は 7 なので 重み 0 のベクトルと反転関係にあるベクトルの重みは7， 重み 1 のベクトルと反転関係にあるベクトルの重みは6， 重み 2 のベクトルと反転関係にあるベクトルの重みは5， 重み 3 のベクトルと反転関係にあるベクトルの重みは4，... という関係になる． 重み $i$ の符号語があればとその反転関係にある符号語の重みは $7-i$ なので，重み分布は $A_0=A_7, A_1 = A_6, A_2 = A_5, A_3 = A_4$ という対称関係 になっているはずである．全0の符号語から$A_0=1$ であることを 知っているので $A_7=1$ もわかる．また $d=3$ であることも 知っているので $A_1=A_2=0$，対称性より $A_5=A_6 = 0$ であることもわかる．残るのは $A_3, A_4$ だけだが 対称性よりこれらは等しく，残りの符号語が 14 個であることから $A_3=A_4 = 7$ であると結論づけられる．重み分布を記述するときは 普通 $A_i = 0$ の要素は書かないので $[7,4,3]$ ハミング符号の 重み分布は $A_0=A_7=1$, $A_3=A_4=7$ と書く．
2つのベクトル $\vec{u}$ と $\vec{v}$ の距離 $d(\vec{u}, \vec{v})$ を，2つのベクトルで値が異なる要素の 場所の数として定義する．例えば $\vec{g_1}$ と $\vec{g_2}$ は 1,2,5,6 ビットめの 4 箇所が異なるので $d(\vec{g_1},\vec{g_2}) = 4$ である．
以下の式が成り立つことは簡単に理解できる． \[ d(\vec{u}, \vec{v})=wt(\vec{u}-\vec{v}) \] 2元符号では $-1 = 1$ なので $\vec{u}-\vec{v}=\vec{u}+\vec{v}$ である．
距離関数 $d$ はメトリック である．メトリックとは，$\vec{u},\vec{v},\vec{w}$ が空間 $V$ の 要素であるとき，以下の 3 つの条件を満たすものである．
最後の条件は三角不等式と呼ばれるものである．
最後の条件は背理法で証明できる．
$d(\vec{u},\vec{w}) > d(\vec{u},\vec{v})+d(\vec{v},\vec{w})$
と仮定する．距離関数 $d$ の定義より $\vec{u}$ の $d(\vec{u},\vec{v})$
箇所の成分を変更することで $\vec{v}$ が得られる．また
$\vec{v}$ の $d(\vec{v},\vec{w})$ 箇所の成分を変更することで
$\vec{w}$ が得られる．すなわち $\vec{u}$ から
$d(\vec{u},\vec{v})+d(\vec{v},\vec{w})$ 回の要素の変更で
$\vec{w}$ を得ることができる．これは仮定に矛盾するので
仮定は正しく無い，つまり
$d(\vec{u},\vec{w})\leq d(\vec{u},\vec{v})+d(\vec{v},\vec{w})$
であることがいえた．
距離や重みの概念を使って復号という問題を定式化する． 我々が受け取るのは $V$ の要素 $\vec{v}$ である． これは通信中に変更されてしまった可能性がある． 復号とは送信された $\vec{u} \in C$ を決定することである．
復号するための一つの方法は，全ての符号語をリストアップし， $\vec{v}$ との距離を求め，もっとも距離の小さい符号語 $\vec{u}$ に復号する，というものがある．このように 受信語を最も距離の近い符号語に復号することを 最尤復号という．
最尤復号は誤りベクトルと重みを使って 定義することもできる．$\vec{u}$ が送信され，$\vec{v}$ が受信されたとき，$\vec{e} = \vec{v}-\vec{u}$ で定義される $\vec{e}$ を誤りベクトルという．
例えば $\vec{u}=(1001)$ が送信され，$\vec{v}=(0001)$ が受信された場合は $\vec{e} = (1000)$ である．これは 最初のビットが通信途中で変わってしまったことを意味する．
誤りベクトルを使って最優符号を以下のように定義することができる
$\vec{v}$ を受信したとする．符号語 $\vec{u}$ に対して
$\vec{v} = \vec{e} +\vec{u}$ となる誤りベクトル $\vec{e}$ の
重みが最小になるような符号語 $\vec{u}$ に復号することで
最尤復号を行うことができる．
$\vec{u},\vec{v}$ が空間 $V$ の 要素であるとき，
を示せ．
授業の6日後までにメールで提出せよ．
メールの件名（サブジェクト）は CT05 とせよ．