Chapter 06

誤り訂正の基礎 — ハミング距離と「どこまで直せるか」

この章で扱う問い. 通信路やディスクは必ず誤る。宇宙線でメモリのビットが反転し、傷でディスクの読み取りが化ける。それでもデータを守りたい——そのためにわざと冗長なビットを足しておくのが誤り訂正符号である。
ここで自然に湧く疑問が 3 つある。この章はそれに答える。
なぜ冗長を足すと直せるのか?（直感的には「同じものを 3 回送れば多数決できる」だが、その一般化は?）
何ビットまで直せるのか? その限界は何で決まるのか?
冗長はどれだけ必要か? 少なすぎると直せず、多すぎると無駄。最適はどこか?
答えの鍵はすべてハミング距離という 1 つの概念に集約される。

1. 符号とは — 「使ってよい語」を制限する

基本の枠組み

情報語 (message): 送りたい\(k\)ビットのデータ
符号語 (codeword): 冗長を加えた\(n\)ビット（\(n > k\)）
符号化: 情報語 → 符号語の対応付け
符号 \(C\): 符号語全体の集合。\(2^n\)通りの中の\(2^k\)個だけが「正規の語」

この符号を\((n, k)\)符号と呼び、\(R = k/n\)を符号化率という。

誤り検出・訂正の原理は、拍子抜けするほど単純である.
\(n\)ビットの空間には\(2^n\)通りのビット列がある。そのうち\(2^k\)個だけを「正しい語」に選んでおく。すると残りの\(2^n - 2^k\)個は「絶対に送られないはずの語」になる。
受信したものがその「あり得ない語」だったら → 誤りがあったと分かる（誤り検出）。さらに「あり得ない語」から見て一番近い正規の語を探せば → 元が復元できる（誤り訂正）。
つまり符号設計とは「正規の語どうしを、なるべく遠くに離して配置する」という配置問題である。遠く離れていれば、多少ずれても最寄りの語を取り違えない。

例: 3 回繰り返し符号 (3,1)

\(0 \to 000\)、\(1 \to 111\)。符号語は 2 個で、残る 6 通り（001, 010, ...）は非正規。

101 を受信したら → 正規語ではないので誤りと分かる。 111 からは 1 ビット違い、000 からは 2 ビット違いなので、111 が送られたと判断（多数決）。

2. ハミング距離とハミング重み

定義

ハミング距離 \(d(x,y)\): ビット列\(x, y\)が異なる位置の個数
ハミング重み \(w(x)\): \(x\)の中の 1 の個数（= \(d(x, 0)\)）

\(\mathrm{GF}(2)\)上では\(d(x,y) = w(x \oplus y)\)（XOR して 1 の個数を数える）。

例: \(x = 10110\)、\(y = 11010\) → \(x \oplus y = 01100\) → \(d = 2\)

距離の公理を満たすことの確認

\(d(x,y) \geq 0\)、\(d(x,y) = 0 \iff x = y\) ✓（明らか）
\(d(x,y) = d(y,x)\) ✓（XOR は対称）
三角不等式 \(d(x,z) \leq d(x,y) + d(y,z)\)

三角不等式の導出: 位置\(i\)で\(x_i \neq z_i\)なら、\(y_i\)がどちらの値であっても \(x_i \neq y_i\)または\(y_i \neq z_i\)の少なくとも一方が成り立つ（\(y_i\)が\(x_i\)と等しいなら\(z_i\)とは異なる、逆も同様）。よって左辺で数える位置は必ず右辺のどちらかで数えられている ∎

三角不等式が成り立つおかげで、「最も近い符号語を選ぶ」という判断が幾何的に意味を持つ。

最小距離

符号\(C\)の異なる 2 語の距離の最小値を最小距離\(d_{\min}\)という:

\[ d_{\min} = \min_{c_1 \neq c_2 \in C} d(c_1, c_2) \]

これが符号の性能を決める最重要のパラメータである。 \((n,k,d)\)符号のように 3 つ組で書くことも多い。

3. 検出能力と訂正能力（この章の中心定理）

定理

最小距離\(d_{\min}\)の符号は:

\[ \boxed{\text{誤り検出: } d_{\min} - 1 \text{ ビットまで}, \qquad \text{誤り訂正: } t = \left\lfloor \frac{d_{\min}-1}{2} \right\rfloor \text{ ビットまで}} \]

導出 1: 検出能力

\(e\)ビットの誤りが起きると、受信語は送信語から距離\(e\)の位置に移る。これが別の符号語に化けてしまうと、誤りに気づけない。別の符号語に到達するには最低\(d_{\min}\)ビット変える必要があるので、 \(e \leq d_{\min}-1\)なら絶対に別の符号語には届かない = 必ず検出できる ∎

導出 2: 訂正能力

各符号語を中心に半径\(t\)の球（距離\(t\)以内のビット列の集合）を考える。 訂正が正しく行えるのは、これらの球が互いに重ならないときである（重なると、その領域のビット列がどちらの符号語から来たか判定できない）。

2 つの符号語\(c_1, c_2\)の球が重ならない条件は、三角不等式より

\[ d(c_1, c_2) \geq 2t + 1 \]

（もし\(d \leq 2t\)なら、中間地点にある語が両方の球に入ってしまう。）これが全ペアで成り立つには\(d_{\min} \geq 2t+1\)、すなわち

\[ t \leq \frac{d_{\min}-1}{2} \qquad \blacksquare \]

数値例

\(d_{\min}\)	検出	訂正	例
2	1 ビット	0	単純パリティ
3	2 ビット	1 ビット	ハミング符号（08 章）
4	3 ビット	1 ビット	拡張ハミング（SECDED）
5	4 ビット	2 ビット	BCH 等
7	6 ビット	3 ビット	—

検出と訂正のトレードオフ. \(d_{\min}=4\)のとき、「3 ビット検出専用」と「1 ビット訂正 + 2 ビット検出」のどちらでも運用できる。訂正を狙うと、訂正に距離を使うぶん検出できる範囲が減る。 どちらを選ぶかは応用次第——通信では再送できるので検出重視、ディスクや宇宙探査機では再送できないので訂正重視、というのが典型である。

4. 符号の限界 — どこまで欲張れるか

「\(n\)を小さく、\(k\)を大きく、\(d\)を大きく」は全部同時には満たせない。その限界を与える定理を見る。

ハミング限界（球充填限界）

\(t\)ビット訂正符号では、各符号語の周りの半径\(t\)の球が重ならない。球 1 個に含まれるビット列の個数は

\[ V(n,t) = \sum_{i=0}^{t}\binom{n}{i} \]

（\(i\)ビット誤るパターンが\(\binom{n}{i}\)通り、それを\(i=0\)から\(t\)まで合計）。

球が重ならず全体\(2^n\)に収まる必要があるので:

\[ \boxed{2^k \sum_{i=0}^{t}\binom{n}{i} \leq 2^n} \]

等号が成立する符号を完全符号 (perfect code) という —— 空間に隙間なく球を詰められた状態。ハミング符号とゴレイ符号がその稀な例である（08 章）。

シングルトン限界

\[ \boxed{d_{\min} \leq n - k + 1} \]

導出: 符号語から最初の\(d_{\min}-1\)個の位置を削除する。 2 つの異なる符号語は少なくとも\(d_{\min}\)箇所で異なるので、 \(d_{\min}-1\)個消してもまだ最低 1 箇所は違う、つまり削除後も全部異なる。削除後の長さは\(n - d_{\min}+1\)ビットで、これが\(2^k\)個すべて異なるには

\[ 2^{n-d_{\min}+1} \geq 2^k \Longrightarrow n - d_{\min}+1 \geq k \Longrightarrow d_{\min} \leq n-k+1 \qquad \blacksquare \]

等号を達成する符号を MDS 符号 (Maximum Distance Separable) という。 リード・ソロモン符号は MDS である（11 章）——冗長を最大限に活かしきっている、という意味。

ギルバート・ヴァルシャモフ限界（存在保証）

上の 2 つは「これ以上は無理」という上界だったが、こちらは「これなら作れる」という下界:

\[ 2^k \sum_{i=0}^{d-2}\binom{n-1}{i} < 2^n \Longrightarrow \text{最小距離 } d \text{ の } (n,k) \text{ 符号が存在する} \]

5. シャノンの通信路符号化定理（理論的な最終目標）

定理（1948）: 通信路容量\(C\)より小さい任意の符号化率\(R < C\)に対し、符号長\(n\)を十分大きくすれば、誤り率をいくらでも 0 に近づけられる符号が存在する。

2 元対称通信路（各ビットが確率\(p\)で反転）の容量は

\[ C = 1 - H(p), \qquad H(p) = -p\log_2 p - (1-p)\log_2(1-p) \]

この定理の衝撃と、その後 50 年. シャノンは「誤り率ほぼ 0 で、しかも効率よく通信できる符号が存在する」ことを証明した。ところがその証明は存在を言うだけで、作り方を教えてくれない（ランダム符号による確率的議論）。
以来、符号理論は「シャノン限界にどこまで近づけるか」の歴史になった。
ハミング符号（1950）— 実用的だが限界からは遠い
リード・ソロモン（1960）— バースト誤りに強く、CD・QR で大成功
ターボ符号（1993）・LDPC（1962 再発見 1996）— 限界のコンマ数 dB まで到達
現代の 5G や Wi-Fi は LDPC を使っており、シャノンが 1948 年に示した限界に実質的に到達している。

6. 誤りのモデル

モデル	説明	有効な符号
ランダム誤り	各ビットが独立に反転	ハミング、BCH、LDPC
バースト誤り	連続する区間がまとめて壊れる（傷、フェージング）	リード・ソロモン、インターリーブ
消失 (erasure)	「どこが壊れたか」は分かるが値が不明	RS（訂正能力が 2 倍になる）

消失が有利な理由は 06 章の定理から即座に分かる. 通常の誤りは「位置」と「値」の 2 つが未知だが、消失は位置が既知。未知数が半分になるので、同じ\(d_{\min}\)で2 倍の個数を復元できる（\(d_{\min}-1\)個まで）。 RAID や分散ストレージが RS 符号を使うのは、ディスク故障が「どのディスクが死んだか分かる」= 消失だからである。

7. まとめ

概念	内容
\((n,k,d)\)符号	長さ\(n\)、情報\(k\)、最小距離\(d\)
ハミング距離	異なるビットの個数。\(d(x,y)=w(x\oplus y)\)
検出能力	\(d_{\min}-1\) ビット
訂正能力	\(\lfloor (d_{\min}-1)/2 \rfloor\) ビット
ハミング限界	球が重ならない条件。等号 → 完全符号
シングルトン限界	\(d \leq n-k+1\)。等号 → MDS（= RS 符号）
シャノン限界	理論的な究極目標

次章では、この「符号語の集合」に線形性という構造を入れて、実際に計算できる形にする。