誤り訂正符号
パリティ・ハミング符号・CRC・リード・ソロモン符号で、通信路で反転したビットに気づいたり直したりする様子を見せます。ビットを押して壊し、ベン図や筆算、復号の手順で確かめられます。
ハミング (7,4)
4 ビットに 3 つの検査ビットを足します。3 つの検査の結果（シンドローム）が誤りの位置を 2 進で指すので、1 ビットの誤りを直せます。2 ビットの誤りは別の位置を指してしまいます。
データを 4 ビットずつのブロックに分け、それぞれを 7 ビットの符号語にして送ります（符号化率 4/7 = 57%）。
送る符号語と通信路
ビットを押すと、通信路でそのビットが反転したことにします。もう一度押すと元に戻ります。
- データのビット
- 検査用のビット
- 通信路で反転したビット
- 受け取った側が直したビット
受け取った側
| ブロック | 受け取った符号語 | 調べた結果 | 判定 | 取り出したデータ | 結果 |
|---|---|---|---|---|---|
| 1 | 0110111 | シンドローム 101（位置 5） | 訂正した | 1011 | 正しく受け取れた |
| 2 | 1100110 | シンドローム 000（誤りなし） | 誤りなし | 0110 | 正しく受け取れた |
ベン図で見るハミング符号
3 つの円は検査ビット p1・p2・p4 と、それぞれが受け持つデータビットです。円の中の 1 の数が偶数になるように検査ビットを決めるので、1 つのビットが反転すると、そのビットを含む円だけが「奇数」になります。失敗した円がすべて重なり、成功した円の外にある場所が誤りの位置です。
雑音のある通信路で比べる
4 ビットのデータを 20,000 回送り、各ビットが確率 p で反転する通信路（二元対称通信路）を通したときの結果を数えます。CRC-3 は 4 ビットに 3 ビットの余りを付けます。
| 方式 | 送るビット数 | 正しく受け取れた | 誤りに気づいた | 気づかず間違えた | 内訳 |
|---|---|---|---|---|---|
| 符号なし | 4 | 81.5% | 0.00% | 18.5% | |
| 3 回繰り返し | 12 | 97.2% | 0.00% | 2.8% | |
| パリティ | 5 | 77.9% | 20.0% | 2.0% | |
| ハミング (7,4) | 7 | 95.7% | 0.00% | 4.3% | |
| 拡張ハミング (8,4) | 8 | 94.1% | 5.2% | 0.64% | |
| CRC-3（検出だけ） | 7 | 69.9% | 30.0% | 0.05% |
- 正しく受け取れた
- 誤りに気づいた
- 気づかず間違えた
使い方
- 上のボタンで符号の種類を選びます。送るデータ（0 と 1 を 16 ビットまで、リード・ソロモン符号は文字列）を入力すると、検査用のビットを付けた符号語を表示します。
- 符号語のビット（バイト）を押すと、通信路でそこが反転したことにできます。「ランダムに反転」のボタンでも壊せます。受け取った側がどう判定し、どこを直したかが下に出ます。
- ハミング符号ではベン図で、CRC では筆算で、リード・ソロモン符号では復号の手順で、しくみを確かめられます。
- 一番下の表では、雑音のある通信路にたくさんのデータを送ったときの結果を方式ごとに比べます。
検出と訂正
誤り検出・訂正符号は、データに検査用のビットを足して、正しい符号語どうしをわざと「離して」おくしくみです。2 つの符号語で違うビットの数（ハミング距離）の最小値を d とすると、d − 1 個までの誤りに気づけ、(d − 1) / 2 個までの誤りを一番近い符号語に戻して直せます。パリティは d = 2、ハミング (7,4) と 3 回繰り返しは d = 3、拡張ハミング (8,4) は d = 4 です。
直せる数を超えた誤りは、別の符号語に「直して」しまうことがあります（誤訂正）。気づかずに間違ったデータを受け取るのが一番困るので、用途によって、直すことと気づくことのどちらを優先するかを選びます。送り直してもらえる通信では CRC のように検出だけを行い、送り直せない記録媒体や遠い宇宙からの通信では訂正できる符号を使います。
効率
データのビット数 k と符号語のビット数 n の比 k / n を符号化率と呼びます。3 回繰り返しは 1 ビットを直すのに 3 倍の量を送りますが、ハミング (7,4) は 1.75 倍で同じ 1 ビットの訂正ができます。リード・ソロモン符号は、検査用の記号を 2t 個足すだけで t 個の記号の誤りを直せ、この数は理論上の限界（シングルトン限界）に達しています。