反転したビット
シンドローム
受信結果
送信1ビットあたりのデータビット

誤り訂正符号についてもっと見る

誤り訂正符号シミュレーター

電線や空気中、傷のついたディスクを通るメッセージには、必ず誤りが入り込みます。ビットが0から1に、また1から0に反転するのです。誤り訂正符号は、慎重に選んだ少数の余分なビットを加えることで、受信側が再送を求めずに損傷を見つけて修復できるようにします。4つのデータビットを入力し、リチャード・ハミングの符号がそれを7ビットに変える様子を見て、好きなビットを反転させ、重なり合う3つの円が誤りをまっすぐ指し示す様子を確かめましょう。そのあと、メッセージ全体を雑音のある通信路に送り、符号ありと符号なしで届く内容を比べてみてください。 1011 のような4つのデータビットを入力すると、アプリが3つのパリティビットを加えて7ビットのハミング符号語を作ります。円の中でも行の中でも、どれかのビットをクリックすると、ノイズのようにそのビットが反転します。もう一度クリックすると元に戻ります。各円の1の個数は偶数でなければなりません。検査に失敗した円が誤ったビットを指し示し、復号器がそれを元に戻します。追加のパリティビットをオンにすると、2つの誤りが誤って訂正されるのではなく検出される様子が見られます。下では、テキストを符号ありと符号なしで雑音のある通信路に送ることができます。

使い方

  1. 4つのデータビットを入力し、3つのパリティビットを含む7ビットの符号語を、円と1行のビットの両方で確認します。
  2. ビットをクリックして反転させ、どの円が検査に失敗するか、シンドロームがどこを指すか、復号器が語を修復するかを観察します。
  3. 追加のパリティビットをオンにしてから、メッセージを雑音のある通信路に送り、符号ありと符号なしの結果を比べます。

ハミング符号が誤りを見つける仕組み

7つのビットには1から7の番号が付いています。ビット1、2、4がパリティビットで、4つのデータビットは3、5、6、7にあります。パリティビット1は、位置1、3、5、7、つまり2進数の番号が1で終わる位置の中で1の個数を偶数にします。ビット2は位置2、3、6、7について、ビット4は位置4、5、6、7について同じことをします。重なり合う3つの円として描くと、各ビットはちょうどそれを検査する円の中に収まります。1つのビットが反転すると、それを含む円が奇数になります。失敗した検査を2進数、つまりシンドロームとして読むと、誤ったビットの位置が得られます。

1ビット追加して得られるもの

2つのビットが反転すると、シンドロームは無関係な3つ目のビットを指し、復号器は事態を悪化させてしまいます。語全体を偶数にする8番目のビットを加えると、これが解決します。誤りが1つなら全体のパリティが変わり、誤りが2つなら全体は偶数のままで、いくつかの円が検査に失敗します。単一誤り訂正・二重誤り検出を意味する SECDED と呼ばれるこの拡大符号は、1つの誤りを訂正し、2つの誤りを確実に検出するので、受信側はそのブロックの再送を求めることができます。サーバーの ECC メモリに使われているのがこの符号です。雑音のある通信路では、2つの反転が同じブロックに入ることがまれである限り、この符号は散らばった多数の誤りをわずかな数に減らします。

よくある質問

なぜパリティビットは位置1、2、4にあるのですか?

それらが2の累乗で、どれも2進数で1が1つだけだからです。パリティビット 2ᵏ は、2進数の番号の k の桁が1であるすべての位置を検査します。位置6(2進数で110)のビットが反転すると、2と4の検査が失敗し、1は影響を受けません。失敗した検査が綴る110は、その位置そのものです。

この保護にはどれだけのコストがかかりますか?

(7,4) 符号は4つのデータビットごとに7ビットを送るので、符号化率は 4/7、つまり75%の上乗せです。拡大符号は4ビットに対して8ビットを送るので2倍です。より長いハミング符号はもっと割安で、15ビットで11データビット、31ビットで26データビットを運びます。Wi-Fi や 5G で使われる LDPC 符号やポーラ符号などの現代の符号は、クロード・シャノンが1948年に可能だと証明した最良の符号化率にきわめて近づいています。

誤りが3つあるとどうなりますか?

通常のハミング符号は完全にだまされることがあります。どの2つの符号語も少なくとも3ビット異なるので、3回の反転で有効な符号語が別の有効な符号語に変わり、検査はひとつも失敗しません。アプリはこれを「誤りを見逃し」として表示します。実際のシステムでは、ノイズレベルに対して十分に強い符号を選ぶことで、こうしたケースをまれに抑えています。

誤り訂正符号はどこで使われていますか?

デジタルデータが伝送・保存されるほぼあらゆる場所です。ECC コンピュータメモリ、ハードディスクと SSD、CD、DVD、ブルーレイディスク、一部がちぎれても読み取れる QR コード、携帯電話と Wi-Fi、デジタルテレビ、そしていまも太陽系の外からデータを送り続けているボイジャーなどの宇宙探査機からのメッセージです。

メッセージはどこかに送信されますか?

いいえ。雑音のある通信路はブラウザ内でシミュレートされており、メッセージと設定はこのブラウザのローカルストレージに保存されます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ