単一パリティ符号とハミング符号

お約束

これからエラー検出・訂正について考えていく訳ですがエラー検出・訂正をするからには何か入力があって、それをどこかに送るなり保存するなりして、受け取った、あるいは読みだしたら間違えているかもしれないからエラーがあるか検査して、その結果エラーがあれば訂正できるなら訂正するわけです。
このシステムは実際には、線でつながっているシリアル通信かもしれないし、衛星通信かもしれないし、CPUにつながっているメモリかもしれないし、はたまたハードディスクに対する読み書きかもしれません。
ただ、エラー検出・訂正についてのみ考えたいのでこれからは以下のような単純なモデルを考えてみます。

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

シリアル通信をイメージしている感じですが通信路をメモリやハードディスクと考えればコンピューターシステムでしょうし、電波だと考えれば無線システムと考えることができます。

単一パリティ符号

送信語の各ビットの中で1であるビットの数が偶数になるように検査ビットを付加する方法を偶数パリティ、1であるビットの数が奇数になるように検査ビットを付加する方法を奇数パリティといいます。 RS232Cで使用されているのがこの単一パリティ符号ですね。
偶数パリティとか奇数パリティと呼ばれているやつです。

偶数パリティであれば、送信符号の1のビット数を数えた結果が奇数であれば検査ビットとして1、偶数であれば検査ビットとして0を付加するだけです。符号語の1であるビット数は必ず偶数となります。奇数パリティなら符号語の1であるビットが奇数になるように検査ビットが付加されます。

受信側では受信符号の1の数を数えてこれが偶数であれば受信符号は正しいと認識し、1の数が奇数であれば間違えていると認識します。（厳密に言えば奇数個の誤りは検出できるが偶数個の誤りは検出できない、となるため偶数ビット誤った場合は正しいと認識してしまいます）
単一パリティ符号は送信語のビット数が何ビットでも構わない、という特徴があります。1のビット数を数えるだけなので送信語は何ビットでも構わないんですね。

ただ、間違ってることはわかってもどこのビットが間違えているのかは分かりません。どこのビットが間違えているのか分からないのだから訂正することもできません。（もし、どこのビットが間違えているのか分かるのならそのビットを反転（1だったら0に、0だったら1に）すれば訂正することができます）
まとめると単一パリティ符号は

奇数個の誤りを検出できる。
送信語のビット数に制約がない。
誤りの場所は分からない。

となります。

検査符号の計算方法

単一パリティ符号の検査符号は偶数パリティであれば、
- 送信語の1のビット数が奇数個であれば1。
- 送信語の1のビット数が偶数個であれば0。

でしたが、これを計算で求められるようにしておきましょう。

各ビットの値は0と1しかとりませんから送信語の各ビットを足していき、その合計が偶数か奇数かを判断すればよい訳です。合計を2進数で考えると最下位のビットが0なら偶数、1なら奇数ですから合計の最下位だけを取り出せば偶数パリティとなります。
最下位ビットしか必要でないのだから最下位ビット以外は捨てて足し算する、ということにすると計算のルールは以下のようになります。

$0+0=0 \\ 0+1=1 \\ 1+0=1 \\ 1+1=0$

2進数では $1 + 1 = 10$ となりますが最下位ビット以外は捨てる、としたので $1 + 1 = 0$ となります。他は普通の足し算ですね。
この計算ルールでパリティ符号を計算してみましょう。例として以下のような送信符号3ビット（ $D_{3}$ 、 $D_{2}$ 、 $D_{1}$ ）、検査符号1ビット（ $P_{1}$ ）の単一パリティ符号を考えます。

$D\ _ {3}、D\ _ {2}、D\ _ {1}、P\ _ {1}$

送信符号3ビット（ $D_{3}$ 、 $D_{2}$ 、 $D_{1}$ ）を全部足した値が検査符号となるのですから偶数パリティの検査符号 $P_{1}$ は

$P\ _ {1} = D\ _ {3} + D\ _ {2} + D\ _ {1}$

と表すことができます。
また、奇数パリティであれば

$P\ _ {1} = D\ _ {3} + D\ _ {2} + D\ _ {1} + 1$

となります。
奇数パリティの検査符号は
- 送信語の1のビット数が奇数個であれば0。
- 送信語の1のビット数が偶数個であれば1。
ですから偶数パリティとは逆になります。だから偶数パリティを反転させればよい→1を足せばよい、ということです。

送信符号が何ビットあっても各ビットをひたすら上記足し算ルールで足していった値が検査符号になる、ということですね。

単一パリティ符号からハミング符号へ

単一パリティ符号はどこかに１ビットの誤りがあればそれを検出できるが、その誤りがどのビットなのかはわからない、という符号です。誤りがどのビットなのかわからないのですから訂正することもできませんね。

そこで、複数のパリティ符号を付加して誤ったビットの位置を特定できるようにしたものがハミング符号となります。誤ったビットがわかるのですからそのビットを反転（0なら1、1なら0）してやれば訂正できたことになります。問題はどうやって誤ったビットの位置を特定するか、です。

以下の7ビットでハミング符号を構成してみます。

$b_{7}$ $b_{6}$ $b_{5}$ $b_{4}$ $b_{3}$ $b_{2}$ $b_{1}$

でも何故7ビット？8ビットのほうがきりが良いんじゃないの・・・

ハミング符号を8ビットで構成することはできますが、7ビットのハミング符号は符号理論の中ではきりの良いビット数になります。理由については後々、数学的考察を行った上で考えてみることにします。とりあえず、ここではそういうもんなんだ、ということにして先に進みます。

で、どうやって誤ったビット位置を特定するの？

1ビットのパリティでは誤ったビット位置を特定することはできませんが、複数のパリティを付加して誤ったビット位置を特定できるようにします。複数のパリティはそれぞれ異なる送信語の複数のビットを担当してもらいます。それぞれのパリティだけでは担当しているビットの何れかに誤りがある、ということしかわかりませんが複数のパリティの結果から誤りのビット位置を特定します。

では、ハミング符号の作り方、はじまりはじまり・・・

$P_{3}$ を配置する

$P_{3}$ は $D_{4}$ 、 $D_{3}$ 、 $D_{2}$ を担当してもらいます。 $D_{4}$ 、 $D_{3}$ 、 $D_{2}$ 、 $P_{3}$ の何れかが1ビット誤りを起こすと $P_{3}$ が1になります。

$b_{7}$	$b_{6}$	$b_{5}$	$b_{4}$	$b_{3}$	$b_{2}$	$b_{1}$
$D_{4}$	$D_{3}$	$D_{2}$	$P_{3}$

$P_{2}$ を配置する

$P_{2}$ は $D_{4}$ 、 $D_{3}$ 、 $D_{1}$ を担当してもらいます。 $P_{3}$ の隣に $D_{1}$ 、更にその隣に $P_{2}$ を配置します。 $D_{4}$ 、 $D_{3}$ 、 $D_{1}$ 、 $P_{2}$ の何れかが1ビット誤りを起こすと $P_{2}$ が1になります。

$b_{7}$	$b_{6}$	$b_{5}$	$b_{4}$	$b_{3}$	$b_{2}$	$b_{1}$
$D_{4}$	$D_{3}$			$D_{1}$	$P_{2}$

$P_{1}$ を配置する

$P_{1}$ は $D_{4}$ 、 $D_{2}$ 、 $D_{1}$ を担当してもらいます。 $P_{2}$ の隣に $P_{1}$ を配置します。 $D_{4}$ 、 $D_{2}$ 、 $D_{1}$ 、 $P_{1}$ の何れかが1ビット誤りを起こすと $P_{1}$ が1になります。

$b_{7}$	$b_{6}$	$b_{5}$	$b_{4}$	$b_{3}$	$b_{2}$	$b_{1}$
$D_{4}$		$D_{2}$		$D_{1}$		$P_{1}$

完成

まとめるとこうなります。

$b_{7}$	$b_{6}$	$b_{5}$	$b_{4}$	$b_{3}$	$b_{2}$	$b_{1}$
$D_{4}$	$D_{3}$	$D_{2}$	$P_{3}$	$D_{1}$	$P_{2}$	$P_{1}$

4ビットの送信語と3ビットのパリティで合計7ビットの符号語ができました。3ビットのパリティは以下の式により計算できます。

$P\ _ {3} = D\ _ {4} + D\ _ {3} + D\ _ {2} \\ P\ _ {2} = D\ _ {4} + D\ _ {3} + D\ _ {1} \\ P\ _ {1} = D\ _ {4} + D\ _ {2} + D\ _ {1} \\$

4ビットの送信語の組み合わせに対して生成されるパリティをすべて計算してみましょう。

$D_{4}$	$D_{3}$	$D_{2}$	$P_{3}$	$D_{1}$	$P_{2}$	$P_{1}$
0	0	0	0	0	0	0
0	0	0	0	1	1	1
0	0	1	1	0	0	1
0	0	1	1	1	1	0
0	1	0	1	0	1	0
0	1	0	1	1	0	1
0	1	1	0	0	1	1
0	1	1	0	1	0	0
1	0	0	1	0	1	1
1	0	0	1	1	0	0
1	0	1	0	0	1	0
1	0	1	0	1	0	1
1	1	0	0	0	0	1
1	1	0	0	1	1	0
1	1	1	1	0	0	0
1	1	1	1	1	1	1

試してみる

送信語が

$D\ _ {4} = 0、D\ _ {3} = 0、D\ _ {2} = 0、D\ _ {1} = 0$

のときに $D_{4}$ が誤って1になった以下のような受信語の場合を考えてみます。

$D\ _ {4} = 1、D\ _ {3} = 0、D\ _ {2} = 0、P\ _ {3} = 0、D\ _ {1} = 1、P\ _ {2} = 0、P\ _ {1} = 0$

復号器で計算するパリティを $P'_{3}$ 、 $P'_{2}$ 、 $P'_{1}$ とすると

$P'\ _ {3} = D\ _ {4} + D\ _ {3} + D\ _ {2} = 1 + 0 + 0 = 1\\ P'\ _ {2} = D\ _ {4} + D\ _ {3} + D\ _ {1} = 1 + 0 + 0 = 1 \\ P'\ _ {1} = D\ _ {4} + D\ _ {2} + D\ _ {1} = 1 + 0 + 0 = 1 \\$

となり、受信語のパリティ

$P\ _ {3} = 0\\ P\ _ {2} = 0\\ P\ _ {1} = 0\\$

とは異なっていますからどこかに誤りが発生した、ということがわかります。

$P_{3}$ を確認する

受信語の $P_{3}$ は0ですが復号器で計算した $P'_{3}$ は1です。ということは $P_{3}$ の担当しているビットに誤りがあった、ということですね。
$D_{4}$ 、 $D_{3}$ 、 $D_{2}$ の何れかに誤りがあるようで、少なくとも $D_{1}$ は誤っていない、とわかります。

$P_{2}$ を確認する

受信語の $P_{2}$ は0ですが復号器で計算した $P'_{2}$ は1です。ということは $P_{2}$ の担当しているビットも誤りがあった、ということですね。
$P_{2}$ の担当は $D_{4}$ 、 $D_{3}$ 、 $D_{1}$ ですからこのうちの何れかに誤りがあったということになりますが、 $P_{3}$ を確認したときに $D_{1}$ は誤っていない、とわかっていますから誤りは $D_{4}$ 、 $D_{3}$ の何れかとなります。更に $D_{2}$ は誤っていない、ということもわかります。

$P_{1}$ を確認する

受信語の $P_{1}$ は0ですが復号器で計算した $P'_{1}$ は1です。ということは $P_{1}$ の担当しているビットも誤りがあった、ということになります。
$P_{2}$ の担当は $D_{4}$ 、 $D_{2}$ 、 $D_{1}$ ですからこのうちの何れかに誤りがあったということになりますが、 $P_{3}$ を確認したときに $D_{1}$ は誤っていない、更に $P_{2}$ を確認したときに $D_{2}$ も誤っていないとわかっていますから誤りは $D_{4}$ である、ということがわかりました。

誤ったビット位置を簡単に特定する方法

パリティビットを順番に確認しながら誤ったビット位置を特定してきましたが、実は誤ったビット位置を特定する方法があります。受信語のパリティは

$P\ _ {3} = 0、P\ _ {2} = 0、P\ _ {1} = 0$

ですが復号器で計算したパリティは

$P'\ _ {3} = 1、P'\ _ {2} = 1、P'\ _ {1} = 1$

です。二つのパリティの異なっているビットを1としたビット列を作るとこのケースではすべてのパリティが異なっていますから $111$ というビット列が得られます。これを2進数として考えると10進数では7ですね。よって誤りがあったのはビット7である $b_{7}$ です。 $b_{7}$ は $D_{4}$ に対応していますから誤りがあったのは $D_{4}$ である、となります。

ただ、この方法はこうなるようにパリティ符号を構成したからであってパリティ符号すべてがこういう特徴を持っている訳ではありません。この辺も後々考えていきます。

でも、なんか信じられん・・・

ではもう少し試してみましょう。送信語が

$D\ _ {4} = 1、D\ _ {3} = 0、D\ _ {2} = 1、D\ _ {1} = 0$

のときに $D_{2}$ が誤って受信語が以下のようになった場合、

$D\ _ {4} = 1、D\ _ {3} = 0、D\ _ {2} = 0、P\ _ {3} = 0、D\ _ {1} = 0、P\ _ {2} = 1、P\ _ {1} = 0$

復号器で計算したパリティは

$P'\ _ {3} = D\ _ {4} + D\ _ {3} + D\ _ {2} = 1 + 0 + 0 = 1\\ P'\ _ {2} = D\ _ {4} + D\ _ {3} + D\ _ {1} = 1 + 0 + 0 = 1 \\ P'\ _ {1} = D\ _ {4} + D\ _ {2} + D\ _ {1} = 1 + 0 + 0 = 1 \\$

受信語のパリティは

$P\ _ {3} = 0\\ P\ _ {2} = 1\\ P\ _ {1} = 0\\$

二つのパリティの異なるビットを1としたビット列は $101$ であり10進数で表すと5。誤りはビット5であるから $b_{5}$ で $D_{2}$ が誤っているよ、ということで検出成功です。

いや、じゃぁパリティが誤ったら？

送信語が

$D\ _ {4} = 0、D\ _ {3} = 1、D\ _ {2} = 1、D\ _ {1} = 0$

のときに $P_{3}$ が誤って受信語が以下のようになった場合、

$D\ _ {4} = 0、D\ _ {3} = 1、D\ _ {2} = 1、P\ _ {3} = 1、D\ _ {1} = 0、P\ _ {2} = 1、P\ _ {1} = 1$

復号器で計算したパリティは

$P'\ _ {3} = D\ _ {4} + D\ _ {3} + D\ _ {2} = 0 + 1 + 1 = 0\\ P'\ _ {2} = D\ _ {4} + D\ _ {3} + D\ _ {1} = 0 + 1 + 0 = 1 \\ P'\ _ {1} = D\ _ {4} + D\ _ {2} + D\ _ {1} = 0 + 1 + 0 = 1 \\$

受信語のパリティは

$P\ _ {3} = 1\\ P\ _ {2} = 1\\ P\ _ {1} = 1\\$

二つのパリティの異なるビットを1としたビット列は $100$ であり10進数で表すと4。誤りはビット4であるから $b_{4}$ で $P_{3}$ が誤っているよ、となります。

2ビット間違えたらだめじゃね？

はい、ここまでの話はあくまで1ビット誤ったらその位置が特定できるよ、ということで2ビット間違えた時は考えていません。2ビット、あるいはそれ以上誤ったらどうなるのでしょうか？誤りが検出できる？訂正は可能？

つっこみどころは色々ありますが、今回の話はここまで。
次回は、ハミング距離を考えてみましょう。

Smile Engineering Blog

ジェイエスピーからTipsや技術特集、プロジェクト物語を発信します

The Continuing Story of Error Correction Code 2