はじめに

こんにちは、TechBulkです。 これまで「符号理論」シリーズとして、生成行列・検査行列の正体(vol.1)や、部分空間による誤り検出(vol.2)についてまとめてきました。

これまでの知識で、「誤りがあるかどうか（検出）」や「どのビットが間違ったか（訂正）」の計算方法は分かりました。 しかし、ふとこんな疑問が湧きませんか？

「そもそも、この符号は何ビットの誤りまでなら直せるの？」

今回は、その「訂正能力の限界」を決める最も重要な概念である「ハミング距離」と、それが「パリティ検査行列 $H$」とどう関係しているのかについて、講義で学んだ内容をアウトプットします。

1. 距離の定義：ハミング距離とハミング重み

まず、デジタルデータにおける「距離」を定義します。 我々が普段使うユークリッド距離（2点間の長さ）とは違い、ビットの世界では 「違いの数」を距離と呼びます。

ハミング距離 (Hamming Distance)

2つの同じ長さのベクトル $\boldsymbol{x}, \boldsymbol{y}$ があるとき、値が異なっているビットの個数を「ハミング距離」と呼び、$d_H(\boldsymbol{x}, \boldsymbol{y})$ と書きます。

例を見てみましょう。

$$\begin{aligned} \boldsymbol{x} &= (1, 0, 0, 1) \\ \boldsymbol{y} &= (0, 1, 1, 1) \end{aligned}$$

この2つを比べると、

• 1ビット目：$1 \neq 0$ (違う)
• 2ビット目：$0 \neq 1$ (違う)
• 3ビット目：$0 \neq 1$ (違う)
• 4ビット目：$1 = 1$ (同じ)

異なる場所は3箇所なので、ハミング距離は $d_H(\boldsymbol{x}, \boldsymbol{y}) = 3$ となります。

ハミング重み (Hamming Weight)

あるベクトル $\boldsymbol{x}$ の中で、「0ではない成分（つまり1）」の個数を「ハミング重み」と呼び、$w_H(\boldsymbol{x})$ と書きます。

$$\boldsymbol{x} = (0, 1, 1, 1, 0, 1)$$

この場合、1が4つあるので、ハミング重みは $w_H(\boldsymbol{x}) = 4$ です。

線形符号における重要な性質

ここで、線形代数（vol.2）の知識が活きてきます。 デジタルの世界（GF(2)）では、「引き算」と「足し算（XOR）」は同じ操作でした。 そのため、「2つのベクトルの距離」は「その差（和）のベクトルの重み」と等しくなります。

$$d_H(\boldsymbol{x}, \boldsymbol{y}) = w_H(\boldsymbol{x} - \boldsymbol{y}) = w_H(\boldsymbol{x} + \boldsymbol{y})$$

これは、「ある点から別の点への距離」を考えるときに、いちいち2点を比較しなくても、「原点からの距離（重み）」だけを見れば良いということを示唆しています。これが後で非常に効いてきます。

2. 最小距離 $d_{min}$ という「防御力」

符号の中に含まれるすべての符号語（正しいデータ）のペアの中で、最も小さいハミング距離を 「最小ハミング距離（または単に最小距離）」と呼び、$d_{min}$ と書きます。

$$d_{min} = \min_{\boldsymbol{x}, \boldsymbol{x}' \in C, \boldsymbol{x} \neq \boldsymbol{x}'} d_H(\boldsymbol{x}, \boldsymbol{x}')$$

符号語は必ず「ゼロベクトル $\boldsymbol{0}$」を含みます（線形部分空間だから）。 先ほどの「距離＝重み」の性質を使うと、結局のところ線形符号においては、以下のことが言えます。

最小距離 $d_{min}$ を求めることは、その符号語の中で（0以外で）最も小さい「ハミング重み」を見つけることと同じである。

つまり、一番「スカスカ（1が少ない）」な符号語の「1の数」が、その符号システム全体の防御力（$d_{min}$）になるのです。

3. パリティ検査行列 $H$ と $d_{min}$ の関係

さて、ここからが今回の講義のハイライトです。 実は、わざわざ全ての符号語を作って重みを数えなくても、パリティ検査行列 $H$ を見るだけで $d_{min}$ が分かってしまうのです。

$H$ の列ベクトルと線形独立性

パリティ検査行列 $H$ を、列ベクトル $\boldsymbol{h}_1, \boldsymbol{h}_2, \dots, \boldsymbol{h}_n$ の集まりとして見ます。

$$H = (\boldsymbol{h}_1, \boldsymbol{h}_2, \dots, \boldsymbol{h}_n)$$

符号理論には以下の美しい定理があります。

パリティ検査行列 $H$ の任意の $d-1$ 個の列が「線形独立」ならば、その符号の最小距離は $d_{min} \ge d$ である。

逆に言うと、「$H$ の列をいくつか足し合わせてゼロベクトルを作れる（線形従属になる）最小の列の数」が、そのまま最小距離 $d_{min}$ になります。

ハミング符号の例で確認

ハミング符号の検査行列 $H$ は以下のような形でした（列の順番は一例です）。

$$H = \begin{pmatrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}$$

1. 1本選ぶ: $H$ には「全て0の列」はありません。$\rightarrow$ 1本では線形従属にならない（$d_{min} > 1$）。
2. 2本選ぶ: $H$ のどの2本の列を見ても、同じものはありません。$\rightarrow$ 2本足しても0にはならない（$d_{min} > 2$）。
3. 3本選ぶ: 例えば、1列目、2列目、3列目（$(1,0,0)^T, (0,1,0)^T, (1,1,0)^T$）を足すと… $$\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} + \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} \quad (\text{mod } 2)$$ ゼロになりました！

3本の列で線形従属を作れたので、この符号の最小距離は $d_{min} = 3$ だと数学的に確定します。 行列を見るだけで符号の性能が分かるなんて、線形代数の力はすごいです。

4. なぜ $d_{min}=3$ だと誤りを1つ訂正できるのか？

最後に、なぜ「最小距離が3」だと「1ビットの誤り」を直せるのか、直感的に説明します。

「符号語」という島

情報の海の中に、「正しい符号語」という島がいくつか浮いていると想像してください。 $d_{min}=3$ というのは、「どの島と島の間も、最低3ステップ（3ビット分）離れている」ということです。

誤り訂正のメカニズム

1. 送信者が「島A」からデータを出航させます。
2. 途中でノイズ（誤り）が 1ビット 発生しました。
3. データは「島A」から1ステップ離れた場所に漂流します。

さて、受信者は漂流しているデータを見つけました。 この場所は、

• 「島A」からは 1ステップ の距離です。
• 隣の「島B」からは、最低でも 2ステップ（$3-1=2$）離れています。

受信者は「一番近い島が元のデータだろう」と推測します（最尤復号）。 距離が3離れていれば、「半径1の範囲」は互いに干渉しません。だから、迷わず「島A」に戻す（訂正する）ことができるのです。

一般式

一般に、最小距離 $d_{min}$ の符号が訂正できる誤りの数 $t$ は、以下の式で表されます。

$$t = \left\lfloor \frac{d_{min} - 1}{2} \right\rfloor$$

ハミング符号の場合、$d_{min}=3$ なので、

$$t = \lfloor (3-1)/2 \rfloor = 1$$

となり、1ビットの誤り訂正が可能であることが証明されます。

5. まとめ

今回の講義の要点は以下の3つです。

1. データの「違い」はハミング距離、「1の数」はハミング重みで表される。
2. 符号の性能（最小距離 $d_{min}$）は、行列 $H$ の列の線形独立性で決まる。
3. $d_{min}=3$ のハミング符号は、符号語同士が適度に離れているため、1ビットの誤りを確実に訂正できる。

「行列の列ベクトルが独立か従属か」という線形代数の純粋な数学の話が、「通信の信頼性」という物理的な性能に直結しているのが本当に面白い点だと感じました。

次回は、いよいよこれまでの知識を総動員して、具体的な計算演習か、あるいは「拡大体」などのより高度な代数構造の話に進むかもしれません。 引き続きアウトプットしていきます！