応用情報技術者 2018年 春期 午前2 問03
問題文
ハミング符号とは、データに冗長ビットを付加して、1ビットの誤りを訂正できるようにしたものである。ここでは、、、、の4ビットから成るデータに、3ビットの冗長ビット、、を付加したハミング符号を考える。
付加ビット、、は、それぞれ
となるように決める。ここで、⊕は排他的論理和を表す。
ハミング符号1110011には1ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。
選択肢
ア：0110011（正解）
イ：1010011
ウ：1100011
エ：1110111
ハミング符号の誤り訂正問題【午前2 解説】
要点まとめ
- 結論：誤り訂正はパリティ検査式を用いて誤り位置を特定し、誤ったビットを反転させることで行います。
- 根拠：ハミング符号は複数のパリティビットを使い、1ビットの誤りを検出・訂正可能な符号です。
- 差がつくポイント：パリティ検査式の計算順序と誤り位置の特定方法を正確に理解し、ビット位置の対応を間違えないことが重要です。
正解の理由
与えられたハミング符号1110011に対し、パリティ検査式を計算すると誤り位置が判明します。
:
:
:
これらの式に符号のビットを当てはめて計算すると、誤りは最上位ビット（）にあると判明し、ビットを反転すると0110011となり、選択肢アが正解です。
:
:
:
これらの式に符号のビットを当てはめて計算すると、誤りは最上位ビット（）にあると判明し、ビットを反転すると0110011となり、選択肢アが正解です。
よくある誤解
パリティビットの位置や計算式のビット対応を誤り、誤り位置の特定を間違えることが多いです。
また、誤り訂正ではなく誤り検出だけと混同し、訂正方法を理解していない場合があります。
また、誤り訂正ではなく誤り検出だけと混同し、訂正方法を理解していない場合があります。
解法ステップ
- ハミング符号のビット位置を確認し、との位置を把握する。
- 各パリティ検査式に符号のビットを代入し、排他的論理和（XOR）を計算する。
- パリティ検査式の結果から誤りビットの位置を2進数で特定する。
- 誤りビットを反転させて訂正した符号を求める。
- 訂正後の符号が選択肢のどれかを確認し、正解を選ぶ。
選択肢別の誤答解説
- イ: 誤り訂正の結果として誤り位置が異なるため不正解。
- ウ: 誤り位置の特定ミスにより誤ったビットを反転している。
- エ: パリティ計算を誤り、誤り位置を誤認している。
- ア: 正しく誤り位置を特定し、ビットを反転しているため正解。
補足コラム
ハミング符号は、（はデータビット数、はパリティビット数）を満たす最小のを用いて設計されます。今回の例では4ビットのデータに3ビットのパリティを付加し、1ビット誤り訂正が可能です。パリティビットは特定のビット位置のXORを取ることで誤り位置を2進数で示します。
FAQ
Q: ハミング符号は何ビットの誤りまで訂正可能ですか？
A: 基本的には1ビットの誤り訂正と2ビットの誤り検出が可能です。
A: 基本的には1ビットの誤り訂正と2ビットの誤り検出が可能です。
Q: パリティビットの位置はどのように決めますか？
A: パリティビットは2のべき乗の位置（1, 2, 4, 8…）に配置されます。
A: パリティビットは2のべき乗の位置（1, 2, 4, 8…）に配置されます。
関連キーワード: ハミング符号、誤り訂正、パリティビット、XOR, 冗長ビット、ビット誤り検出
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！