誤り訂正符号の解説
完璧な通信路はありません。宇宙線はメモリのビットを反転させ、傷はディスクの一部を消し、無線信号は弱まります。デジタルシステムは運を天に任せるのではなく、巧妙なやり方で冗長性を加え、一部が誤って届いても送られた内容を受信側が割り出せるようにしています。1940年代後半に始まったこれらの符号の数学は、私たちが保存したり送ったりするほぼすべてのビットを静かに守っています。
パリティで誤りを検出する
最も単純な保護は、1つのパリティビットです。1の総数が偶数になるように1か0を加えます。途中で1つのビットが反転すると個数が奇数になり、受信側は何かがおかしいとわかります。パリティではどのビットが誤っているかはわからず、2回の反転は打ち消し合って気づかれませんが、コストが低いため、何十年にもわたってメモリやシリアル通信で使われてきました。とはいえ、誤りを検出するのは仕事の半分にすぎません。そのあとデータを送り直さなければならないからです。
繰り返しで訂正する
再送を求めずに誤りを訂正するには、受信側が多数決で誤りに勝てるだけの冗長性が必要です。各ビットを000または111のように3回ずつ送れば、受信側は多数決を取れます。3つ組の中の1回の反転は訂正されます。代償は大きく、データ1ビットにつき3ビットが必要なうえ、同じ3つ組の中で2回反転すると、やはり誤りのほうが勝ってしまいます。符号理論の出発点となった問いは、もっとうまくできないかというものでした。
ハミングの符号
1947年、リチャード・ハミングはベル研究所で、パンチカードからプログラムを読み込むリレー式計算機を使っていました。週末に誤りを見つけると計算機はただ停止し、ハミングは月曜日に戻ってきて無駄になった実行結果を目にすることになりました。機械が誤りを検出できるなら、なぜその場所を突き止めて訂正できないのか、と彼は問いました。1950年に発表された彼の答えは、4つのデータビットを7ビットとして送るものです。位置1、2、4にある3つのパリティビットは、それぞれ異なる重なり合った位置のグループを検査します。グループは、どの単一の誤りも固有の検査の組み合わせを失敗させるように選ばれています。
シンドローム
受信側は3つの検査を計算し直します。すべて合格なら、語はそのまま受け入れられます。いくつか失敗した場合、失敗した検査を検査4を最上位の桁とする2進数の桁として書くと、1から7までの数が得られます。これがシンドロームで、反転したビットの位置そのものです。そのビットを元に戻せば符号語が復元されます。このしかけがうまくいくのは、各位置の2進展開がその位置の属する検査を並べたものになるように番号が付けられているからです。この符号を重なり合う3つの円として描くととても整って見えるのはそのためです。
ハミング距離
2つの語のハミング距離とは、それらが異なる位置の数です。(7,4) 符号では、どの2つの符号語も少なくとも3離れています。誤りが1つある語は、送られた符号語からは距離1のままで、ほかのどの符号語からも少なくとも2離れているので、最も近い符号語に復号すれば訂正されます。一般に、符号語どうしが少なくとも d 離れている符号は、d − 1 個の誤りを検出し、(d − 1)/2 個(切り捨て)の誤りを訂正します。全体のパリティビットを加えると距離が4に上がり、1つの誤りを訂正して2つを検出する拡大符号になります。
シャノン限界
ハミングの論文の2年前の1948年、クロード・シャノンは驚くべき定理を証明しました。雑音のある通信路にはすべて容量があり、その容量を下回る速度なら、十分に長い符号を使うことで、誤りを望むだけ少なくしてデータを送ることができます。容量を上回ると、誤りは避けられません。シャノンはそのような符号が存在することを示しましたが、その作り方は示しませんでした。彼の限界に迫る実用的な符号を見つけるには、1960年のリード・ソロモン符号から1993年のターボ符号、そして低密度パリティ検査符号の再発見まで、半世紀を要しました。
身の回りにある符号
リード・ソロモン符号のおかげで、CD は傷があっても再生でき、QR コードはシンボルの最大30%が損傷していても読み取れます。サーバーのメモリは拡大ハミング符号を使い、宇宙線による1ビットの反転を修正しています。ボイジャーが撮影した外惑星の画像はゴレイ符号、のちにリード・ソロモン符号で守られ、5G や Wi-Fi の LDPC 符号とポーラ符号は通信路が許すほぼすべてのビットを引き出しています。本のバーコードや銀行口座番号の最後の桁でさえ、簡単な誤り検出符号です。
試してみよう
誤り訂正符号シミュレーターを開いて、任意の4つのデータビットをハミング (7,4) 符号で符号化し、円の中や行の中でビットをクリックして反転させ、復号器が修復する前に、失敗した円とシンドロームが誤りを指し示す様子を見てみましょう。追加のパリティビットをオンにすると二重誤りが検出される様子が見られ、メッセージを雑音のある通信路に送れば、符号ありと符号なしで届く内容を比べられます。
よくある質問
誤り検出と誤り訂正の違いは何ですか?
検出は受信側に何かがおかしいことを知らせるだけなので、受信側はデータの再送を求めなければなりません。パリティビットやチェックサムがこれを行います。訂正では、受信側が再送を求めずに元のデータを復元でき、そのためにはより多くの冗長性が必要です。数百万キロメートル離れた宇宙探査機や DVD のように再送を求められないシステムは、訂正に頼っています。
すべてを2回送ればよいのでは?
2つのコピーでは、誤りが起きたことはわかっても、どちらのコピーが正しいかはわからず、コストは2倍になります。3つのコピーなら多数決ができますが、コストは3倍です。ハミングの符号は2倍未満のビット数で7ビットのブロックごとに1つの誤りを訂正でき、より長い符号ははるかに優れています。
リチャード・ハミングとはどんな人ですか?
アメリカの数学者(1915〜1998年)で、マンハッタン計画に参加したのち、ベル研究所で30年間働きました。符号のほか、信号処理のハミング窓、ハミング距離、そして講演「You and Your Research(あなたとあなたの研究)」でも知られています。1968年にチューリング賞を受賞しました。
符号はいくつでも誤りを訂正できますか?
十分な冗長性がある場合に限ります。符号はブロックあたり最大 (d − 1)/2 個の誤りを訂正できます。ここで d は符号語間の最小距離で、検査ビットの多い長い符号ほど大きな d に達します。シャノンの定理が究極の限界を定めています。どんな符号も通信路の容量を超えることはできません。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
誤り訂正符号シミュレーターを開く