応用情報技術者 2011年秋期午前2 問03

問題文

符号長7ビット、情報ビット数4ビットのハミング符号による誤り訂正の方法を、次のとおりとする。　受信した7ビットの符号語

x_{1} x_{2} x_{3} x_{4} x_{5} x_{6} x_{7}

(

x_{k} = 0

又は1)に対して　　

c_{0} = x_{1} + x_{3} + x_{5} + x_{7}

c_{1} = x_{2} + x_{3} + x_{6} + x_{7}

c_{2} = x_{4} + x_{5} + x_{6} + x_{7}

　(いずれもmod2での計算) 　を計算し、

c_{0}, c_{1}, c_{2}

の中に少なくとも一つは0でないものがある場合には、　　

i = c_{0} + c_{1} \times 2 + c_{2} \times 4

　を求めて、左から

i

ビット目を反転することによって誤りを訂正する。　受信した符号語が1000101であった場合、誤り訂正後の符号語はどれか。

選択肢

ア：1000001

イ：1000101

ウ：1001101

エ：1010101（正解）

符号長7ビット・情報ビット数4ビットのハミング符号による誤り訂正【午前2 解説】

正解の理由

受信符号語は

x_{1} = 1, x_{2} = 0, x_{3} = 0, x_{4} = 0, x_{5} = 1, x_{6} = 0, x_{7} = 1

です。
パリティ検査ビットを計算すると、

c_{0} = x_{1} + x_{3} + x_{5} + x_{7} = 1 + 0 + 1 + 1 = 3 \equiv 1 (mod 2)

c_{1} = x_{2} + x_{3} + x_{6} + x_{7} = 0 + 0 + 0 + 1 = 1

c_{2} = x_{4} + x_{5} + x_{6} + x_{7} = 0 + 1 + 0 + 1 = 2 \equiv 0

よって、

i = c_{0} + c_{1} \times 2 + c_{2} \times 4 = 1 + 2 + 0 = 3

。
3ビット目を反転すると、

x_{3} = 0 \to 1

となり、訂正後は1010101（エ）となります。

解法ステップ

受信符号語の各ビット $x_{1}$ から $x_{7}$ を確認する。
指定されたパリティ検査式で $c_{0}, c_{1}, c_{2}$ をmod2で計算する。
$i = c_{0} + c_{1} \times 2 + c_{2} \times 4$ を求める。
$i = 0$ なら誤りなし、 $i \neq = 0$ なら $i$ ビット目を反転する。
反転後の符号語を答える。

選択肢別の誤答解説

ア: 1000001
3ビット目を0に反転する誤り訂正は誤り。正しくは0→1に反転。
イ: 1000101
受信符号語のまま。パリティ検査で誤りが検出されているため訂正不要ではない。
ウ: 1001101
5ビット目を反転しているが、誤り位置は3ビット目なので誤り。
エ: 1010101
3ビット目を正しく反転し、誤り訂正後の正しい符号語。

よくある誤解

パリティ計算の対象ビットを間違えたり、

i

の計算式の重み付けを誤ると誤り位置がずれます。
また、誤り位置が0の場合は訂正不要ですが、0以外なら必ず該当ビットを反転することを忘れがちです。

補足コラム

ハミング符号は1ビット誤りの検出と訂正が可能な符号で、パリティ検査ビットの位置と計算方法が鍵です。
今回の7,4ハミング符号は7ビット中4ビットが情報ビット、3ビットがパリティビットで構成されます。
誤り位置の計算はパリティ検査結果を2進数のビット位置として扱う点が特徴です。

FAQ

Q: なぜ誤り位置

i

は

c_{0} + c_{1} \times 2 + c_{2} \times 4

で計算するのですか？
A: それぞれの

c_{k}

はパリティ検査ビットの結果で、2進数の重み付けにより誤り位置を特定するためです。

Q: 誤り位置が0の場合はどうなりますか？
A: すべてのパリティ検査が0で誤りなしと判断し、訂正は不要です。

関連キーワード: ハミング符号、誤り訂正、パリティ検査、符号理論、ビット反転

← 前の問題へ次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！