平成22年度 春期 午前 問11

✓ これが正解エハミング符号

解説

位置まで分かる冗長を持つのはハミング符号です。

誤りを見つける力と、見つけたうえで直す力は別のものです。検出だけなら、送る側と受け取る側で同じ計算をして食い違いが出るかを見れば足りますが、訂正するには、どのビットが化けたのかという位置まで分からなければなりません。設問は 2 ビットの誤りを検出し、さらに 1 ビットの誤りを訂正するところまで求めているので、位置を特定できる冗長を備えたものを選びます。正解はハミング符号です。検査のためのビットを 1、2、4、8 といった位置に置き、それぞれが重なり方の違う組を見張るように組み立てておくと、食い違いを知らせた検査ビットの位置を足し合わせた数が、そのまま化けたビットの番号になります。設問が挙げた 2 ビットの検出と 1 ビットの訂正という組合せは、この符号にパリティをもう 1 本足した形で実現され、ECC メモリではこの形が定番として使われています。訂正まで欲しければ、必ず位置の分かる冗長を持たせる必要がある、というのがこの問いの骨です。

ほかの選択肢はなぜ違うのか

• ア偶数パリティ：ビットの中で 1 が立っている個数を数え、偶奇をそろえておくだけの仕組みです。食い違いが起きたことは分かりますが、どのビットが化けたのかは示せないため、直すところまでは届きません。
• イ垂直パリティ：検査を掛ける向きを縦に決めただけで、数えて偶奇を見るという中身は変わりません。位置を絞り込む手掛かりが 1 方向ぶんしかないので、こちらも見つけるところで止まってしまいます。
• ウチェックサム：まとまった単位の値を足し合わせた結果を添えておき、受け取った側で同じ和になるかを照らす方法です。合わなければ誤りだと判断できますが、和の中のどこが崩れたのかまでは分かりません。