ハミング符号：位置を突き止めてビットを訂正する

一箇所反転を押してください。通信路でビット5が反転し、円1と円4に含まれる1の個数が奇数になります。円2は偶数のままです。したがって1 + 4 = 5。この結果になるように例を選んだわけではありません。円kは、位置番号を二進数で表したときにkを含む位置だけを検査します。そのため位置iのビットが誤ると、番号の和がiになる円だけが乱れます。図の中の位置が、そのままビットのアドレスなのです。ハミングが1950年に求めたのは、単一誤りの位置を示し、誤りがなければゼロになる「検査数」でした。三つの検査から得られる答えは八通り。七ビットの符号語に必要なのも、七つの位置と「誤りなし」を合わせた八通りです。余りはありません。128個ある七ビット語のうち16個が符号語で、残る112個は、それぞれただ一つの符号語から一箇所だけ反転したものです。グラフ下の表では、この112個をすべて正しく復号しています。パリティビットを位置1、2、4に置く理由も、仕組みがわかれば単純です。これらの位置は二進数で1を一つしか含まないため、各パリティビットは一つの円だけに属し、その検査だけで値を決められます。ハミング自身もこの理由を挙げています。

二箇所反転を押してください。ビット3とビット5が誤ります。円1には両方が含まれるので二度乱され、結局は偶数のままです。円2と円4は奇数になり、シンドロームは6を示します。実在する位置ですから、復号器は正しかったビット6を反転します。受信時には二つだったデータビットの誤りが、訂正後には三つになります。格子を見ると、どの組合せでも同じことが起きます。21組すべて、したがって16個のデータ語に対する336通りの二重反転が、フラグなしで誤ったデータを出力します。次にパリティビットのみを押してください。位置1と位置2はデータを含まず、データ自体は無傷で届いています。それでもシンドローム3に従い、復号器はd₁を壊します。今度は拡張符号・二箇所反転を押します。八番目のビットによって全体の1の個数が偶数になるため、一箇所の反転なら全体パリティは必ず奇数、二箇所なら必ず偶数です。シンドロームがゼロでないのに全体パリティが偶数なら、復号器は何も変更せず、符号語にフラグを立てます。448通りの二重反転すべてが検出されます。ただし訂正はできません。3と5を反転した場合も、1と7を反転した場合も、シンドロームは6になるからです。ハミングの出発点も検出でした。1950年の論文は、ベル研究所がアバディーン性能試験場向けに製作した二台のリレー式計算機の話から始まります。初期には8,900個のリレーのうち一日に二、三個ほどが故障しましたが、見逃しはありませんでした。その一方で、夜間や週末に無人運転すると、計算機はたびたび停止しました。

各ビットの二重送信も拡張符号も、四つのデータに八ビットを使います。二つのコピーが一致しなければ誤りが起きたことはわかりますが、どちらが正しいかは判断できません。受信側にできるのはブロックにフラグを立てることだけです。p = 0.01では、ブロックの7.69×10⁻²が検出されます。さらに、同じビットのコピーが両方とも反転した3.77×10⁻⁴は、誤ったまま通過します。拡張ハミング符号なら一箇所の反転をすべて訂正し、2.64×10⁻³を検出し、誤ったまま通過するのは5.34×10⁻⁵です。同じビット数で、フラグは29分の1、誤ったブロックは7分の1になります。破線と実線を見ると、pが0.066を超えるまで両方の指標で拡張符号が優位です。これは十五ビットに一つが反転する通信路に相当します。各ビットを三重送信すれば、スライダー上のどのpでも、ブロック単位では七ビット符号を上回ります。ここでは1.19×10⁻³に対して2.03×10⁻³です。ただし必要なのは12ビットで、七ビット符号は7ビット。だからこそ、公平なのは八ビット同士の比較です。