誤り検出と誤り訂正

誤りを検出できる、そして誤りを訂正できる、というのはどういうことでしょうか？今回はこれについて考えてみましょう。

The Continuing Story of Error Correction Code 2 - Smile Engineering Blogの最初に書きましたが、言葉の定義を書いておきます。

送信語
送信者が送信したいデータのビット列。
符号器
送信語に誤り検出・訂正のための加工を施す装置。
符号語
符号器により送信語に誤り検出・訂正のための加工を施したビット列。
通信路
送信側から受信側へ符号語を送る経路。符号語は通信路を通過する際に誤りが加わる可能性がある。
受信語通信路を通って受信した符号語のビット列。
通信路でエラーが発生していなければ符号語と同一となる。

符号語のビット数が4ビットであれば16個の符号語を作ることができます。
この16個の符号語に送信語を割り当てる訳ですが、送信語が割り当てられた符号語どうしがとあるハミング距離となるように割り当てていきます。
この、とあるハミング距離を「最低ハミング距離」とします。
なぜ「最低」とするかというとすべての符号語間が同じハミング距離を保つようにできない場合があるためです。
送信語を最低ハミング距離を保って符号語に割り当てたのですから割り当てられる送信語は符号語の数（4ビットなら16個）よりも少なくなります。
そして、送信語が割り当てられていない符号語が存在することになります。
通信路で何も誤りが発生しなければ、送信語が割り当てられていない符号語が受信語になることはありません。

誤りを検出できる、ということ

受信語として送信語が割り当てられていない符号語だったら、それは誤りがあるということです。
各符号語間は最低ハミング距離があるのですから、1以上かつ最低ハミング距離未満のビット数の誤りが発生している、とわかります。

誤りを訂正できる、ということ

訂正可能な誤りのビット数をtとします。符号語からハミング距離tの領域が、他の符号語からハミング距離tの領域と重なっていなければ訂正可能です。

カルノー図で確認してみよう

最小ハミング距離が1

最小ハミング距離が1、ということは4ビットのうち1ビット異なると別の符号語になる、ということです。
だから、ハミング距離が1で送信語を符号語に割り振っていくと全ての符号語が送信語に割り当てられる、ということですね。
以下にカルノー図を示します。
$b_{3}b_{2}b_{1}b_{0} = 0000$ に着目してみるとハミング距離が1となる上下左右はすべて別の符号語になっています。
更に、その別の符号語の上下左右も別の符号語ですね。
1ビットでも間違えれば別の符号語になってしまうので最小ハミング距離が1では

誤り検出はできない
誤り訂正はできない

となります。着目した符号語
別の符号語

		$b_{1}b_{0}$
		$00$	$01$	$11$	$10$	$00$	$01$	$11$	$10$
$b_{3}b_{2}$	$00$	$0000$	$0001$	$0011$	$0010$	$0000$	$0001$	$0011$	$0010$
	$01$	$0100$	$0101$	$0111$	$0110$	$0100$	$0101$	$0111$	$0110$
	$11$	$1100$	$1101$	$1111$	$1110$	$1100$	$1101$	$1111$	$1110$
	$10$	$1000$	$1001$	$1011$	$1010$	$1000$	$1001$	$1011$	$1010$
	$00$	$0000$	$0001$	$0011$	$0010$	$0000$	$0001$	$0011$	$0010$
	$01$	$0100$	$0101$	$0111$	$0110$	$0100$	$0101$	$0111$	$0110$
	$11$	$1100$	$1101$	$1111$	$1110$	$1100$	$1101$	$1111$	$1110$
	$10$	$1000$	$1001$	$1011$	$1010$	$1000$	$1001$	$1011$	$1010$

最小ハミング距離が2

次は最小ハミング符号が2の場合。
最小ハミング符号を2として送信語を符号語に割り当てるとカルノー図上ではきれいな市松模様になります。
ここでも $b_{3}b_{2}b_{1}b_{0} = 0000$ に着目してみます。
$b_{3}b_{2}b_{1}b_{0} = 0000$ でハミング距離が1になるのは $b_{3}b_{2}b_{1}b_{0} = 0001$ 、 $b_{3}b_{2}b_{1}b_{0} = 0010$ 、 $b_{3}b_{2}b_{1}b_{0} = 0100$ 、 $b_{3}b_{2}b_{1}b_{0} = 1000$ の4種類になります。
この4つは全て別の符号語になっていませんよね。
このため、1ビット誤ったことは認識することができます。
しかし、2ビット誤ると別の符号語になってしまうので誤り検出は1ビットまでとなります。

では、誤り訂正はできるでしょうか？
$b_{3}b_{2}b_{1}b_{0} = 0000$ が1ビット誤って受信語が $b_{3}b_{2}b_{1}b_{0} = 0001$ になってしまった場合を考えてみます。
$b_{3}b_{2}b_{1}b_{0} = 0001$ という受信語は符号語 $b_{3}b_{2}b_{1}b_{0} = 0000$ が1ビット誤った受信語ですが $b_{3}b_{2}b_{1}b_{0} = 1001$ 、 $b_{3}b_{2}b_{1}b_{0} = 0101$ 、そして $b_{3}b_{2}b_{1}b_{0} = 0011$ が1ビット誤った受信語でもあります。
カルノー図の $b_{3}b_{2}b_{1}b_{0} = 0001$ の上下左右を見てくださいね。
誤った受信語 $b_{3}b_{2}b_{1}b_{0} = 0001$ は $b_{3}b_{2}b_{1}b_{0} = 0000$ 、 $b_{3}b_{2}b_{1}b_{0} = 1001$ 、 $b_{3}b_{2}b_{1}b_{0} = 0101$ 、そして $b_{3}b_{2}b_{1}b_{0} = 0011$ のどれに訂正したらよいのかわからないですね。
このため最小ハミング距離が2の場合

誤り検出は1ビットまで
誤り訂正はできない

となります。パリティ符号がこれに該当します。

着目した符号語
着目した符号語からハミング距離が1
別の符号語

		$b_{1}b_{0}$
		$00$	$01$	$11$	$10$	$00$	$01$	$11$	$10$
$b_{3}b_{2}$	$00$	$0000$	$0001$	$0011$	$0010$	$0000$	$0001$	$0011$	$0010$
	$01$	$0100$	$0101$	$0111$	$0110$	$0100$	$0101$	$0111$	$0110$
	$11$	$1100$	$1101$	$1111$	$1110$	$1100$	$1101$	$1111$	$1110$
	$10$	$1000$	$1001$	$1011$	$1010$	$1000$	$1001$	$1011$	$1010$
	$00$	$0000$	$0001$	$0011$	$0010$	$0000$	$0001$	$0011$	$0010$
	$01$	$0100$	$0101$	$0111$	$0110$	$0100$	$0101$	$0111$	$0110$
	$11$	$1100$	$1101$	$1111$	$1110$	$1100$	$1101$	$1111$	$1110$
	$10$	$1000$	$1001$	$1011$	$1010$	$1000$	$1001$	$1011$	$1010$

最小ハミング距離が3

次、最小ハミング距離が3の場合です。
符号語としてまずは $b_{3}b_{2}b_{1}b_{0} = 0000$ を割り当てて、ここからハミング距離が3となるものを選びます。
ここでは $b_{3}b_{2}b_{1}b_{0} = 1101$ を選びました。
もう一つ割り当てられないかな、と考えてみても $b_{3}b_{2}b_{1}b_{0} = 0000$ と $b_{3}b_{2}b_{1}b_{0} = 1101$ からハミング距離が3となる符号語はありません。
4ビットの符号語でハミング距離を3とすると、もう符号語は二つしか割り当てられないんですね。

では $b_{3}b_{2}b_{1}b_{0} = 0000$ に着目して誤り検出から考えていきましょう。
$b_{3}b_{2}b_{1}b_{0} = 0000$ で1ビット誤ったハミング距離が1の受信語（カルノー図の黄色のデータ）は当然別符号語にはなりません。
2ビット誤ったハミング距離が2の受信語（カルノー図のピンクのデータ）も別の符号語にはなりませんね。
最小ハミング距離を3とすると2ビットまでの誤り検出は可能となります。
$b_{3}b_{2}b_{1}b_{0} = 0000$ が3ビット誤った $b_{3}b_{2}b_{1}b_{0} = 1011$ 、 $b_{3}b_{2}b_{1}b_{0} = 1110$ 、 $b_{3}b_{2}b_{1}b_{0} = 0111$ も検出は可能ですが $b_{3}b_{2}b_{1}b_{0} = 1101$ に誤った場合、別の符号語になってしまうので誤り検出は2ビットまで、となります。

誤り訂正についても見てみましょう。
$b_{3}b_{2}b_{1}b_{0} = 0000$ が1ビット誤った上下左右のカルノー図の黄色のデータを見てください。
これら四つの受信語の更に上下左右を確認すると別の符号語が無いことがわかります。
もし、受信語がこの四つであれば、それは $b_{3}b_{2}b_{1}b_{0} = 0000$ が1ビット誤ったものと言えます。
とすれば、これら四つの受信語の何れかだった場合は無条件で $b_{3}b_{2}b_{1}b_{0} = 0000$ の符号語に置き換えることができます。
1ビットの誤りは訂正できる、ということですね。

では2ビット誤った、カルノー図のピンクの受信語の上下左右を確認してみましょう。
$b_{3}b_{2}b_{1}b_{0} = 0101$ 、 $b_{3}b_{2}b_{1}b_{0} = 1100$ 、そして $b_{3}b_{2}b_{1}b_{0} = 1001$ は別の符号語 $b_{3}b_{2}b_{1}b_{0} = 1101$ の1ビット誤り、ハミング距離が1になっています。
これでは $b_{3}b_{2}b_{1}b_{0} = 0000$ が2ビット誤ったのか、それとも $b_{3}b_{2}b_{1}b_{0} = 1101$ が1ビット誤ったのか判別がつきません。
ここから、最小ハミング距離が3の場合は1ビットまでの誤り訂正が可能、と言えそうです。

ということで、最小ハミング距離が3の場合

誤り検出は2ビットまで
誤り訂正は1ビットまで

となります。
ハミング符号がこれに該当します。

着目した符号語
着目した符号語からハミング距離が1
着目した符号語からハミング距離が2
別のコード

		$b_{1}b_{0}$
		$00$	$01$	$11$	$10$	$00$	$01$	$11$	$10$
$b_{3}b_{2}$	$00$	$0000$	$0001$	$0011$	$0010$	$0000$	$0001$	$0011$	$0010$
	$01$	$0100$	$0101$	$0111$	$0110$	$0100$	$0101$	$0111$	$0110$
	$11$	$1100$	$1101$	$1111$	$1110$	$1100$	$1101$	$1111$	$1110$
	$10$	$1000$	$1001$	$1011$	$1010$	$1000$	$1001$	$1011$	$1010$
	$00$	$0000$	$0001$	$0011$	$0010$	$0000$	$0001$	$0011$	$0010$
	$01$	$0100$	$0101$	$0111$	$0110$	$0100$	$0101$	$0111$	$0110$
	$11$	$1100$	$1101$	$1111$	$1110$	$1100$	$1101$	$1111$	$1110$
	$10$	$1000$	$1001$	$1011$	$1010$	$1000$	$1001$	$1011$	$1010$

最小ハミング距離が4、に行く前に・・・

前項で最小ハミング距離を3にすれば

誤り検出は2ビットまで
誤り訂正は1ビットまで

となる、としました。
なるほどなるほど、1ビットの誤りが訂正できて2ビット誤っていたらそれが検出できるんだな・・・
そう思いません？

$b_{3}b_{2}b_{1}b_{0} = 0101$ を受け取ったとしましょう。
1ビットの誤り訂正ができるので訂正します。
$b_{3}b_{2}b_{1}b_{0} = 0101$ の上下左右を見ると下に $b_{3}b_{2}b_{1}b_{0} = 1101$ という符号語があります。
これが1ビット誤ったんだな、ということで $b_{3}b_{2}b_{1}b_{0} = 1101$ に訂正しました。
残念、実は元の符号語は $b_{3}b_{2}b_{1}b_{0} = 0000$ で2ビット誤って $b_{3}b_{2}b_{1}b_{0} = 0101$ になっていたので誤訂正です。

いやいや、2ビットの誤り検出ができるんだから1ビット誤っていたら訂正、2ビット誤っていたら訂正せずに誤りとすれば？

$b_{3}b_{2}b_{1}b_{0} = 0101$ というデータ、1ビット誤りか、2ビット誤りか判別できるでしょうか？
前項の誤り訂正のところで
「これでは $b_{3}b_{2}b_{1}b_{0} = 0000$ が2ビット誤ったのか、それとも $b_{3}b_{2}b_{1}b_{0} = 1101$ が1ビット誤ったのか判別がつきません。」
としているとおり、判別はできません。

何がおかしいのか？

でも、確かに2ビットの誤りは検出できて、1ビットの誤りまでは訂正できるはずです。

実は2ビットまでの誤り検出を確実に行いたい場合、訂正を行ってはいけません。
誤りは1ビットか2ビットどちらかは分からないが誤っている、ということが検出できる、となります。

そして、1ビットの訂正を行う場合、誤訂正を行う可能性がある、となります。
確実に誤りを検出するか、誤訂正には目をつぶって1ビットの誤り訂正をするか、の2択です。

もし、送信側に誤りを通知して再送処理を行えるようなシステムなら2ビットまでの誤り検出を確実にしてくれたほうがいいですよね。
そして、誤りがランダムに発生するような状況で、誤る確率がとても低く4ビット程度の中に2ビットの誤りが発生する確率は恐ろしく低いような場合は1ビットの訂正をして、ごく稀なご訂正には目をつぶる、としたほうが良い場合もあると思います。
この辺はどのようなシステムの中で使用するか、ということに依存してきますが最小ハミング距離が3であるハミング符号を使う場合はこれらを頭に入れておく必要があります。

このような状況となる原因は異なる符号語間で1ビット誤りの領域と2ビット誤りの領域が被っていることにあります。
これを解決するためには1ビット誤りの領域と2ビット誤りの領域が被らないようにして、被るのは2ビット誤りの領域同志のみとすることです。
簡単に言えば最小ハミング距離を4にする、ということです。

最小ハミング距離が4

最後は満を持して登場（？）の最小ハミング距離が4の場合です。
符号語として $b_{3}b_{2}b_{1}b_{0} = 0000$ を割り当てると、ハミング距離が4になるのは $b_{3}b_{2}b_{1}b_{0} = 1111$ しかありません。
二つのコードの間でハミング距離が1の領域とハミング距離が2の領域が被っている個所はありません。
よって、最小ハミング距離が3の場合

誤り検出は2ビットまで
誤り訂正は1ビットまで

となります。
結論としては最小ハミング符号が3の場合と同じですが、こちらは上記二つが同時に実現できます。

拡張ハミング符号と呼ばれるSECDED（single error correction, double error detection）がこれに該当します。

着目したコード
着目したコードからハミング距離が1
着目したコードからハミング距離が2
別のコード

		$b_{1}b_{0}$
		$00$	$01$	$11$	$10$	$00$	$01$	$11$	$10$
$b_{3}b_{2}$	$00$	$0000$	$0001$	$0011$	$0010$	$0000$	$0001$	$0011$	$0010$
	$01$	$0100$	$0101$	$0111$	$0110$	$0100$	$0101$	$0111$	$0110$
	$11$	$1100$	$1101$	$1111$	$1110$	$1100$	$1101$	$1111$	$1110$
	$10$	$1000$	$1001$	$1011$	$1010$	$1000$	$1001$	$1011$	$1010$
	$00$	$0000$	$0001$	$0011$	$0010$	$0000$	$0001$	$0011$	$0010$
	$01$	$0100$	$0101$	$0111$	$0110$	$0100$	$0101$	$0111$	$0110$
	$11$	$1100$	$1101$	$1111$	$1110$	$1100$	$1101$	$1111$	$1110$
	$10$	$1000$	$1001$	$1011$	$1010$	$1000$	$1001$	$1011$	$1010$