誤り訂正符号はどうやって失われたデータを戻すのか

スマートフォンでの動画視聴や、遠く離れた探査機からの宇宙写真の受信など、私たちは常にノイズが存在する環境でデジタルデータを受け取っています。電波の乱れや電子回路の熱、宇宙線などの物理的な影響によって、データの中の「0」が「1」に、あるいは「1」が「0」に反転してしまう事故は避けられません。

途中で壊れてしまったデータを、受信側はどうやって元の形に戻しているのでしょうか。

ここで扱う「失われたデータ」とは、回線混雑などでパケット自体が届かない「パケット喪失」や「消失」ではなく、受信機に届いた信号の0と1が反転してしまう「ビット反転誤り」を指します。

誤り訂正符号（ECC: Error-Correcting Code）は、失われたデータを魔法のように無から作り直すわけではありません。あらかじめ決められた計算規則に従う余分なビット（冗長検査ビット）を付加して送信し、受信したデータ列が正しい規則から外れたことを検知して、符号が保証する範囲内で誤り位置の特定や元の符号語の復元を行う技術です。

この仕組みがどのように組み立てられているのか、基本原理から見ていきましょう。

---

データを守る基本原理――「冗長性」と検出の第一歩

データが壊れても元に戻せる根本的な理由は、「冗長性（余分な情報）」にあります。

日常の言葉でも、メッセージに「こん〇ちは」と1文字欠落があっても前後の文脈から「こんにちは」だと分かります。言葉に文脈という冗長性が含まれているからです。しかし、最初から「あ」の1文字しか送られてこず、それがノイズで「い」に変わってしまったら、受け取った側は元の文字が「あ」だったのか最初から「い」だったのか区別できません。

デジタルデータも同様です。4ビットの情報をそのまま4ビットだけで送ると、途中で1ビットが反転しても、それが「壊れたデータ」なのか「もともと別のデータ」なのかを受信者は判別できません。誤りを捉えるためには、あらかじめ「余分なビット」を添えて送る必要があります。

最もシンプルな冗長性：単一パリティ検査

余分な情報を加える最も身近な方法が「パリティ検査（奇偶検査）」です。

例えば「偶数パリティ」では、データ全体の「1」の個数が常に偶数になるよう、末尾に1ビット（パリティビット）を追加します。

• 元データが 1010 の場合：1が2個（偶数）なので、パリティビット 0 を添えて 10100 として送信します。
• 元データが 1110 の場合：1が3個（奇数）なので、パリティビット 1 を添えて 11101 として送信します。

受信側は、届いた5ビット中の「1」の個数を数えます。偶数パリティで送ったのに奇数なら、奇数個のビット反転が起きたと分かります。ただし、これだけで反転がちょうど1ビットだったとは言えません。

誤りが見つかったときのシステムの対処

パリティ検査で誤りを検出した際、システムがどう動くかは用途によって異なります。単に「送信元へ再送を要求する（ARQ）」だけではありません。通信路の性質や制約に応じて、以下のような運用が選ばれます。

• 再送要求（ARQ）：TCP通信のように確実性が不可欠な場合、壊れたデータの再送を求めます。
• 破棄（ドロップ）：リアルタイムの音声通話や映像配信のように遅延を許容できない場合、壊れたフレームは破棄して次のデータを優先します。
• 上位層での回復：下位層では誤りの通知にとどめ、上位のアプリケーション層でデータの補間や修復を行います。
• 他方式との併用：誤り訂正符号と組み合わせ、軽微な誤りはその場で修復し、訂正しきれない重度の誤りだけを検出して上位へ伝えます。

身近な検出技術：チェックディジット

バーコード（JANコード）や書籍のISBNコード、クレジットカード番号の末尾にある「チェックディジット（検査数字）」も、パリティと同じ冗長性の原理です。あらかじめ定めた計算式で算出した数字を末尾に添えることで、入力ミスを防ぎます。

ただし、チェックディジットの方式（モジュラス10 ウェイト3、モジュラス11など）によって検出能力は異なります。1桁の入力ミスは確実に検出できても、隣り合う数字を入れ替えてしまう「転置誤り（例えば『35』を『53』と打つミス）」を検出できるかどうかは、アルゴリズムの設計に依存します。

パリティ検査の限界

単一パリティ検査には、2つの決定的な限界があります。

第一に、「どこかのビットが反転したこと」は分かっても、「どのビットが壊れたか」までは特定できません。壊れた位置が分からなければ、受信側が自力で元の値に戻す（訂正する）ことはできません。 第二に、同時に「2ビット」が反転すると1の個数の偶奇が元に戻るため、誤りが発生したこと自体を見落としてしまいます。

「誤りを検出するだけでなく、壊れた位置を割り出してその場で直すことはできないか」――この問いから生まれたのがハミング符号です。

---

壊れた位置を割り出す――ハミング(7,4)符号の幾何学的パズル

1940年代後半、ベル研究所のリチャード・ハミングは大型計算機を使っていました。当時はリレーの接触不良などでエラーが起きると、機械はパリティ検査によって計算を自動停止（ハルト）する仕様でした。金曜の夜に動かした計算が深夜早々に停止し、週末の無人運転が無駄になる事態に直面したハミングは、「エラー位置を機械自身が特定し、自動で直して計算を続ける仕組みが必要だ」と考えました。

そうして1950年に発表されたのが「ハミング符号」です。

7ビットの中に仕組まれた「二進数の名推理」

代表例である「ハミング(7,4)符号」は、送りたい4ビットのデータに3ビットの検査ビット（パリティ）を加え、計7ビットとして送信します。

なぜ3ビットのパリティだけで壊れた位置を特定できるのでしょうか。

ここでは、7ビットの受信語に誤りがないか、1ビットだけ反転したと仮定します。その範囲なら「誤りなし」1通りと、位置1〜7の単一誤り7通りの計8通りです。3ビットの検査結果は 2^3 = 8 通りを表し、単一誤りの位置を示せます。2ビット以上の誤りには同じ解釈を使えません。

ハミングは、7つのビット位置のうち2の累乗の位置（1, 2, 4）をパリティビットに割り当て、残りの位置（3, 5, 6, 7）に元のデータビットを配置しました。

各位置番号を二進数3桁で表すと、3つのパリティビットが監視すべき担当グループが自然に決まります。

• $P_1$（下一桁が1の位置を監視）：位置 1, 3, 5, 7 の4ビットについて、1の個数が偶数になるよう P_1 を決めます。
• $P_2$（中一桁が1の位置を監視）：位置 2, 3, 6, 7 の4ビットについて、1の個数が偶数になるよう P_2 を決めます。
• $P_3$（上一桁が1の位置を監視）：位置 4, 5, 6, 7 の4ビットについて、1の個数が偶数になるよう P_3 を決めます。

シンドローム（検査結果）が示す「犯人の居場所」

受信側では、届いた7ビットに対して3つのグループのパリティ検査を実行します。検査結果が合格（偶数）なら 0、異常（奇数）なら 1 と記録します。

• 検査1（グループ P_1）：結果 s_1（0 または 1）
• 検査2（グループ P_2）：結果 s_2（0 または 1）
• 検査3（グループ P_3）：結果 s_3（0 または 1）

3つの検査結果を (s_3, s_2, s_1) の順に並べたものがシンドロームです。誤りが0または1ビットという前提では、(0, 0, 0) は誤りなしを示します。ただし複数ビットの反転があれば、零でも見逃す組み合わせがあります。位置4の検査をP_4/s_4と呼ぶ表記もあり、本稿の第3検査P_3/s_3に対応します。

ここで、もし5番目のビットが反転したとします。5を二進数で表すと 101 です。

• 5は下一桁が1なので、P_1 の検査で異常 \rightarrow s_1 = 1
• 5は中一桁が0なので、P_2 の検査は正常 \rightarrow s_2 = 0
• 5は上一桁が1なので、P_3 の検査で異常 \rightarrow s_3 = 1

得られたシンドローム (s_3, s_2, s_1) は `(1, 0, 1)` となり、二進数の「5」に一致します。

位置1, 2, 4を偶数パリティビット、位置3, 5, 6, 7をデータビットとするハミング(7,4)符号において、3つのパリティ検査結果（シンドローム）の二進数表現は、反転したビットの位置番号と厳密に一致します（反転が0または1ビットの場合）。

誤りが0または1ビットという前提なら、検査結果が5番目を示したときそのビットを反転して元の符号語を復元できます。複数ビットが反転している場合は、同じ操作が誤訂正になることがあります。

---

【体験】シンドローム計算と単一誤りの復元

次の教材では、4ビットのデータに3ビットの検査情報を加える仕組みを試せます。まず本文の検査集合を確認し、どの位置を反転したときにどの検査結果が変わるかを比べてみてください。訂正の説明は、誤りが0または1ビットという前提に限ります。

ツールの見方と操作のポイント

1. データを選ぶ：4つの情報ビットを選びます。
2. 反転位置を選ぶ：受信までに1ビットだけ変わった例を考えます。
3. 検査結果を比べる：本文に示した三つの検査集合とシンドロームを照合します。
4. 訂正を確かめる：誤り位置の候補を反転し、元の情報ビットへ戻るか確認します。

ツールの保証範囲と重要な限界

本ツールを操作する上で理解しておくべき境界条件があります。

ハミング(7,4)符号が確実に訂正できるのは、1符号語あたり0または1ビットの反転を仮定した場合です。 図や操作ツールの表示だけで、複数誤りやパケット喪失まで訂正できるとは判断できません。

ちょうど2ビットが反転した場合、ハミング(7,4)符号の3検査のシンドロームは非零になります。ただし単一誤りの結果と区別できないため、単一誤りとして訂正を試みると誤訂正し得ます。3ビット以上では、組み合わせによってはシンドロームが (0, 0, 0) となり、誤りを見逃す場合もあります。

この限界が生じる理由は、符号が持つ「距離」という幾何学的な性質から説明できます。

---

「ハミング距離」が決定する検出と訂正の限界

誤り訂正の能力を数学的に測る物差しが「ハミング距離（Hamming Distance）」です。同じ長さの2つのビット列の間で「値が異なっている桁の数」を指します。

• 10100 と 10101 のハミング距離は 1（末尾の1桁のみ相違）
• 10100 と 10010 のハミング距離は 2（3桁目と4桁目の2箇所が相違）

最小ハミング距離と「安全圏」の幾何学

取り得るすべての正しい符号語のペアの中で、最も近いもの同士のハミング距離を「最小ハミング距離（$d_{\min}$）」と呼びます。この最小ハミング距離が、その符号が理論上保証できる誤り検出数や誤り訂正数の上限を決定します。

この関係を、空間に配置された「基地（正しい符号語）」としてイメージしてみましょう。

【最小ハミング距離 d_min の幾何学的イメージ】

● 基地A (正しい符号語)                ● 基地B (正しい符号語)
    │                                    │
    ├── 1ビット変化 (基地Aの勢力圏)      ├── 1ビット変化 (基地Bの勢力圏)
    │       │                                │       │
    │       ▼                                ▼       │
    │   [ 受信列X ]                      [ 受信列Y ] │
    │                                                │
    └────────────────── 距離 d_min ──────────────────┘

1. 冗長性がない場合（$d_{\min} = 1$）：基地同士が隣接している状態です。1ビット反転すると別の基地の位置に重なってしまうため、誤りがあったこと自体を検出できません。
2. 単一パリティ検査の場合（$d_{\min} = 2$）：基地同士の距離が2離れています。1ビット反転したデータはどの基地とも重ならない位置に落ちるため「誤り」と検出できます。しかし双方の基地から等距離（距離1）にあるため、どちらから来たのか判別できず訂正はできません。
3. ハミング(7,4)符号の場合（$d_{\min} = 3$）：基地同士が距離3離れています。各基地の周囲に「半径1の球体」を描いても互いに重なりません。1ビットの反転が起きてもデータは元の基地の球体内に留まるため、受信側は「最も近い基地」を選ぶことで元の符号語へ正しく復元できます。

訂正したい誤りのビット数を t とすると、単一誤り訂正（t=1）を保証するには d_{\min} \ge 2t + 1、すなわち $d_{\min} \ge 3$ が数学的に必須です。

2ビット誤りで起きる「誤訂正」の正体

ハミング(7,4)符号では、ちょうど2ビットの反転ならシンドロームは非零です。しかし、単一誤りとの区別はできません。3ビット以上の反転では検査結果が零になる組み合わせもあるため、「零なら常に誤りなし」とは言えません。

しかし、元の基地から距離2離れた位置は、隣の別の基地から見ると「距離1」の至近距離にあたります。受信側は「隣の基地から1ビット誤りで届いた」と誤認し、隣の基地へ引き戻す処理を行ってしまいます。これが誤訂正の正体です。

二重誤りを安全に検出する「SECDED」

誤訂正を起こさずに「2ビットの誤りが発生したため訂正不能である」と安全に検知するには、最小ハミング距離を $d_{\min} = 4$ に引き上げる必要があります。

ハミング(7,4)符号の7ビット全体に対して、さらにもう1ビット、全体を対象とした偶数パリティビットを追加して8ビットの符号を構成します（拡張ハミング符号）。

• 元の7ビットのどれか1ビットが反転：3検査のシンドロームは非零、追加した全体パリティも異常となり、その位置を訂正できます。
• 追加した全体パリティビットだけが反転：元の3検査は 000、全体パリティだけが異常となります。追加ビットの誤りとして区別できます。
• ちょうど2ビットが反転：全体パリティは正常でも、3検査は異常を示します。単一誤りとしての訂正を止め、検出した誤りを通知します。

この構成は SECDED（Single Error Correction, Double Error Detection: 単一誤り訂正・二重誤り検出） と呼ばれます。サーバー向けECCメモリなどの高信頼性ハードウェアにおいて、過剰な回路規模をかけずに二重誤りによるデータ破損を防ぐ代表的な構成例として広く普及しています。

---

実社会での応用と現代の誤り訂正技術

ハミング符号は基礎として優れていますが、現実の通信環境で発生するノイズは1ビットだけの独立した反転にとどまりません。

ランダム誤りとバースト誤り

ハミング符号が得意とするのは、たまに1ビットが独立して反転する「ランダム誤り」です。

一方、光ディスク表面の傷や電波の一時的な途切れなどでは、連続する多数のビットがまとめて破壊される「バースト誤り」が発生します。バースト誤りに対しては、ハミング符号単体では対処しきれません。

リード・ソロモン符号とインターリーブ

バースト誤りに強い代表格が、1960年に考案された「リード・ソロモン（Reed-Solomon）符号」です。

リード・ソロモン符号は、データを0と1のビット単位ではなく、8ビット（1バイト）などのまとまり（シンボル）単位で扱います。連続したビット列が壊れても「数シンボルの破損」として効率よく修復できるため、QRコードやCD・DVD・Blu-rayディスク、地上波デジタル放送などで広く利用されています。

さらに実際のシステムでは、「インターリーブ（並べ替え）」が併用されます。送信データをあらかじめ規則的に並べ替えて送信し、受信側で元の順序に戻す技術です。こうすることで、通信中に集中して生じたバースト誤りが、元の順序に戻した際にはデータ全体に分散され、まばらなランダム誤りへと変換されます。これをリード・ソロモン符号で訂正することで高い修復性能を発揮します。

深宇宙通信の現実――極限の通信路規格

誤り訂正の最高峰が見られるのが、探査機からの電波を受け取る深宇宙通信です。

一般に「宇宙通信はハミング符号で守られている」と単純化して語られることがありますが、ハミング(7,4)符号そのものが宇宙探査の実装規格として使われているわけではありません。太陽圏外を飛ぶボイジャーなどの探査機から届く電波は極めて微弱であり、宇宙空間の熱雑音にほぼ埋もれてしまいます。

NASAのディープスペースネットワーク（DSN）の設計ハンドブック（810-005）が示すように、実際の深宇宙通信では通信路の厳しさや伝送速度に応じて以下の符号が選定・併用されています。

• 畳み込み符号（Convolutional Codes）：データをブロックに区切らず、過去のデータ系列との関連性を保ちながら連続的に符号化する方式。ビタビ復号と組み合わせて広く使われました。
• 連接符号（Concatenated Codes）：内側に畳み込み符号、外側にリード・ソロモン符号を二重に配置し、双方の強みを掛け合わせて誤りを削ぎ落とす方式。
• ターボ符号（Turbo Codes）：1990年代に登場し、後述する理論的限界に極めて近い伝送性能を実証した符号。
• LDPC符号（低密度パリティ検査符号）：疎な行列演算を用いて巨大なブロックを高速・高精度に復元する符号で、現代の探査機や次世代光通信規格の主流となっています。

どの規格であっても、「決められた計算規則に従って余分な冗長ビットを付加し、受信空間の距離関係から最も確からしい符号語を導き出す」という根本原理は一貫しています。

---

よくある疑問（FAQ）

Q1. インターネットで動画が途切れるような「パケット喪失」も誤り訂正符号で直せるのか？

A. 仕組みは異なりますが、広義の誤り訂正技術（消失訂正）が応用されています。

本記事で扱ったハミング符号などは、データは届いたものの0と1が反転した「ビット反転誤り」を直す技術です。一方、ネットワーク混雑でパケット自体が抜け落ちる現象は「消失（erasure）」と呼ばれ、何番目のパケットが抜けたかがあらかじめ分かっているという特徴があります。

パケット喪失に対しては、TCPのように再送を要求する手法のほか、UDPを用いるリアルタイム配信などでは「消失訂正符号（Erasure Code）」が使われます。複数のパケットから冗長パケットを生成して送信することで、途中でパケットが数個欠落しても、残りのパケットから欠落部分を数学的に逆算して復元できます。

Q2. 冗長ビットを増やせば、どんなにノイズがひどくても100%データを元に戻せるのか？

A. 通信路容量という理論的限界（シャノン限界）があるため、無限には戻せません。

適切な符号設計では、冗長性を増やして誤りへの耐性を高められます。ただし、ビットを増やすだけで訂正能力が必ず上がるわけではありません。符号化率は符号語中の情報ビットの割合です。情報ビット数が同じなら冗長ビットを増やすほど下がりますが、実際の正味通信速度は伝送速度などにも依存します。

さらに、情報理論の創始者クロード・シャノンが1948年に証明した「通信路符号化定理」により、通信路にはノイズの強さや帯域幅によって定まる「通信路容量（C）」という物理的上限が存在します。データ送信速度がこの容量を下回っていれば、適切な符号化によって誤り率をいくらでもゼロに近づけられます。しかし、通信路容量を超える速度で誤りなくデータを伝送することは、どのような符号を用いても原理的に不可能です。

Q3. 「誤り訂正（ECC）」と「暗号化」や「ハッシュ関数」の違いは何か？

A. 防ごうとしている脅威と目的が異なります。

• 誤り訂正（ECC）：目的は「物理的ノイズからの復元」です。自然現象による偶発的なビット反転を修復し、元のデータを忠実に再現します。
• ハッシュ関数（SHA-256など）：データの照合値を作り、信頼できる値と比べて変更や破損の検出に使います。ただし異なる入力が同じ値になる可能性があり、あらゆる変更の検出を無条件に保証するものではありません。ハッシュ単体はデータの復元や送信者の認証を行いません。
• 暗号化（AESなど）：目的は「第三者に対する秘匿」です。通信途中でデータを盗み見られても内容を読み取られないように変換します。

現代のデジタル通信では、これらを組み合わせて「暗号化で秘匿し、物理層の誤り訂正でノイズから守り、届いた内容をハッシュ関数で検証する」という多層的な防御が行われています。

---

結び

デジタルデータは、決して傷つかない魔法の数字列ではありません。回路を走る電圧の乱れや微弱な電波の揺らぎなど、常に過酷な物理世界の中で運ばれています。

データには誤りが生じうるため、通信や保存では備えが必要です。誤り訂正符号は規則に従って冗長な情報を加え、定められた範囲の誤りを検出・訂正します。どこまで直せるかは符号の設計と誤りの数に依存します。

何気なく見ている画面の文字や画像も、見えない冗長性と幾何学的な計算によって正確に届けられているのです。

---