応用情報技術者 2024年春期午前2 問04

問題文

符号長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 解説】

要点まとめ

結論：受信符号語1000101の誤り訂正後は1010101（エ）となる。
根拠：パリティ検査式 $c_{0}, c_{1}, c_{2}$ を計算し、誤り位置 $i = c_{0} + 2 c_{1} + 4 c_{2}$ を特定し、そのビットを反転する。
差がつくポイント：パリティビットの計算と誤り位置の算出方法を正確に理解し、ビットの位置を間違えないことが重要。

正解の理由

受信符号語は

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

です。
パリティ検査式に代入すると、

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} + 2 c_{1} + 4 c_{2} = 1 + 2 \times 1 + 4 \times 0 = 3

。
3ビット目を反転すると、1000101 → 1010101（エ）となり、誤り訂正が完了します。

よくある誤解

パリティビットの計算でビット位置を間違えたり、

i

の計算式の重み付けを誤ることが多いです。
また、誤り位置が0の場合は誤りなしと判断する点も混同しやすいです。

解法ステップ

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

選択肢別の誤答解説

ア: 1000001
→ 3ビット目を反転していない。誤り位置の特定が誤っている。
イ: 1000101
→ 受信符号語のまま。誤り訂正がされていない。
ウ: 1001101
→ 5ビット目を反転した形。誤り位置の計算ミス。
エ: 1010101
→ 正しく3ビット目を反転し、誤り訂正が完了している。

補足コラム

ハミング符号は1ビットの誤り訂正が可能な符号で、パリティ検査ビットを用いて誤り位置を特定します。
符号長7ビット、情報ビット4ビットのハミング符号は

(7, 4)

符号と呼ばれ、教育や通信で広く使われています。

FAQ

Q: なぜ

i

の計算式は

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

なのですか？
A: それぞれのパリティ検査ビットが誤り位置の2進数の各ビットに対応しているため、重み付けして誤り位置を特定します。

Q: 誤りが複数ビットあった場合も訂正できますか？
A: ハミング符号は1ビット誤り訂正のみ対応しており、複数ビット誤りは検出できても訂正はできません。

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

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 2024年 春期 午前2 問04

問題文

選択肢