ハミング距離 とは？

同じ長さのビット列を並べて、違っている位置の数を数えるんだ。たとえば1010と1001は、3番目と4番目が違うから距離は2。物理的な長さではなく、値の違いを数える距離だよ。

通信で使う有効な符号語同士を離しておくと、ビットの誤りを検出・訂正しやすくなるよ。すべての符号語の組で最小距離が3以上なら、1ビットの誤りの後も元の符号語が最も近いので、1ビット訂正ができる。距離が大きい2つのデータを用意するだけで、任意の誤りを直せるわけではないんだ。

QRコードも冗長な情報を加えて誤りを訂正するよ。ただし、使っているのはハミング符号ではなくReed–Solomon符号で、8ビットをまとめたコードワードを単位に扱う。ビットの距離を数える例と、QRの具体的な訂正方式は区別しよう。

同じ長さの文字列にも使えるよ。appleとapplyは最後の文字だけ違うので距離1。DNAの塩基の並びも、同じ長さで位置が対応していれば違う位置を数えられる。たとえばACGTとACGAなら距離1だね。

そのままのハミング距離では扱えないよ。挿入や削除も数えるなら編集距離などを考える。ハミング距離は同じ位置同士を比較するので、どの単位を比べるかと、長さ・位置の対応をそろえることが大切なんだ。