はじめに
今回も、応用情報技術者試験の過去問を解いていきます。
今回は「ハミング符号による誤り訂正」の問題です。
通信の安定性やデータの信頼性を支える重要な技術なので、しっかり理解していきます。
問題(R6年度 応用情報技術者試験 春期 午前 問4)
符号長7ビット、情報ビット数4ビットのハミング符号による誤り訂正の方法を、
次のとおりとする。
受信した７ビットの符号語 x₁ x₂ x₃ x₄ x₅ x₆ x₇ (xₖ = 0 又は 1) に対して
- c₀ = x₁ + x₃ + x₅ + x₇
- c₁ = x₂ + x₃ + x₆ + x₇
- c₂ = x₄ + x₅ + x₆ + x₇
（すべて mod 2 で計算）
これらの c₀, c₁, c₂ の中に少なくとも1つでも 0 でないものがあれば：
- i = c₀ + c₁×2 + c₂×4
と求め、左から i ビット目を反転して誤りを訂正する。
受信した符号語が 1000101 のとき、訂正後の符号語はどれか。
【選択肢】
ア 1000001
イ 1000101
ウ 1001101
エ 1010101
解答
エ 1010101
解説
1ビットごとの値は：
| ビット位置 | xₖ の値 |
|---|---|
| x₁ | 1 |
| x₂ | 0 |
| x₃ | 0 |
| x₄ | 0 |
| x₅ | 1 |
| x₆ | 0 |
| x₇ | 1 |
C₀, C₁, C₂ の計算
c₀ = x₁ + x₃ + x₅ + x₇ = 1 + 0 + 1 + 1 = 3 → mod2 = 1
c₁ = x₂ + x₃ + x₆ + x₇ = 0 + 0 + 0 + 1 = 1 → mod2 = 1
c₂ = x₄ + x₅ + x₆ + x₇ = 0 + 1 + 0 + 1 = 2 → mod2 = 0
i の計算
i = c₀ + c₁×2 + c₂×4 = 1 + 1×2 + 0×4 = 1 + 2 + 0 = 3
訂正
i = 3 → 左から3ビット目 を反転。
受信時：1 0 0 0 1 0 1
訂正後：1 0 1 0 1 0 1
よって正解は エ になります。
問題の用語解説
| 用語 | 解説 |
|---|---|
| 符号長 | 符号語全体の長さ。今回は7ビット。 |
| 情報ビット数 | 伝えたい元のデータのビット数。今回は4ビット。 |
| ハミング符号 | 誤り訂正のための符号方式。1ビット誤りまで訂正できる。 |
| パリティビット | 誤りを検出・訂正するために加える余分なビット。 |
| 誤り訂正 | 誤ったデータを正しいものに戻す処理。 |
体系的位置づけ
ハミング符号 さらに理解を深めよう
受信データが「正しい」か「間違っている」か、どうやって判断する？
ハミング符号では、受信したデータが正しいかどうかを C₀, C₁, C₂ という3つのパリティ計算の結果で判定します。
| C₀, C₁, C₂ の結果 | 意味 |
|---|---|
| C₀ = 0, C₁ = 0, C₂ = 0 | 正しい符号語（誤りなし） |
| いずれかが 1 | 誤りあり（訂正が必要） |
受信側は、パリティ計算の結果がゼロで揃っていれば「正しい」、
1つでも1が出ていれば「誤りあり」と判断します。
なぜかというと、送信時に C₀, C₁, C₂ がゼロになるように符号語を設計しているからです。
途中でビット誤りが起きるとパリティにズレが生じ、それが C₀, C₁, C₂ に表れます。
どうしてその計算方法で誤り位置が特定できるの？
ハミング符号のポイントは：
- 誤りが起きた位置のビット番号を2進数で表現できる
- それを C₂（4の位）、C₁（2の位）、C₀（1の位）の形でチェックしている
つまり C₀, C₁, C₂ をそのまま「重みづけ」して i を求めれば：
i = C₀ + C₁ × 2 + C₂ × 4
これが 誤り位置の番号 そのものになります。
例えば：
| 誤り位置 | C₂ C₁ C₀ | i の値 |
|---|---|---|
| 3ビット目 | 0 1 1 | 3 |
| 5ビット目 | 1 0 1 | 5 |
このように、C₀, C₁, C₂ は 誤り位置を2進数で表現しているのです。
2ビット分誤りがあるとどうなるの？
(7,4) ハミング符号は 「1ビット誤り」用に設計されています。
2ビット誤りが起きると：
- C₀, C₁, C₂ の結果は「2つの誤りの合成」になる
- 本来の誤り位置とは一致しない 「ニセの位置」 が出てしまう
- そのため正しく特定できず、むしろ別の位置を訂正してしまうことがある
C₀, C₁, C₂ の計算式の理由
C₀, C₁, C₂ は下記の計算式で求めます。
- c₀ = x₁ + x₃ + x₅ + x₇
- c₁ = x₂ + x₃ + x₆ + x₇
- c₂ = x₄ + x₅ + x₆ + x₇
なぜC₀,はx₁ 、x₃、x₅、 x₇のみを足すのか、気になる方もいるかもしれません(最初、私はそう思いました)。その理由はというと、C₀, C₁, C₂ が どのビット（x₁〜x₇）をチェックする(＝計算式に入れる)のか は、ビット番号の2進数の桁に対応して決められているからです。
具体的に言うと：
- ビット番号1（x₁）は 2進数で 001 → C₀ のチェックに入る
- ビット番号2（x₂）は 010 → C₁ のチェックに入る
- ビット番号3（x₃）は 011 → C₀, C₁ 両方に入る
- ビット番号4（x₄）は 100 → C₂ のチェックに入る
- ビット番号5（x₅）は 101 → C₀, C₂ に入る
- ビット番号6（x₆）は 110 → C₁, C₂ に入る
- ビット番号7（x₇）は 111 → C₀, C₁, C₂ すべてに入る
つまり、ビット番号の2進数表現の「1の位=1」になると、計算に組み込まれるということです。
ちなみに表にまとめると下記の通りとなります。
| ビット番号 | ビット名 | 2進数 | C₂ に入る？ | C₁ に入る？ | C₀ に入る？ |
|---|---|---|---|---|---|
| 1 | x₁ | 001 | 0 | 0 | 1 |
| 2 | x₂ | 010 | 0 | 1 | 0 |
| 3 | x₃ | 011 | 0 | 1 | 1 |
| 4 | x₄ | 100 | 1 | 0 | 0 |
| 5 | x₅ | 101 | 1 | 0 | 1 |
| 6 | x₆ | 110 | 1 | 1 | 0 |
| 7 | x₇ | 111 | 1 | 1 | 1 |
上の表で1になる場合、計算に組み込むことになるので、それを再度C₀, C₁, C₂ に対して計算式にまとめると
- c₀ = x₁ + x₃ + x₅ + x₇
- c₁ = x₂ + x₃ + x₆ + x₇
- c₂ = x₄ + x₅ + x₆ + x₇
となります。
最後に：パリティとは何か？
パリティとは：
- データの「偶奇（even/odd）」をチェックするための 冗長なビット情報
- 通信エラーを発見・訂正するために利用される
たとえば：
- データの中の 1 の数が 偶数になるように 追加ビットをつける → 偶数パリティ
- または 奇数になるように する → 奇数パリティ
ハミング符号では 偶数パリティ を採用し、
C₀, C₁, C₂ を通じて「誤りがあれば偶奇が崩れる」ことを利用してエラーを見つけています。
まとめ
✅ ハミング符号では 1ビット誤りを必ず訂正できる
✅ パリティチェックの設計が「ビット番号の2進数」に基づいている
✅ i = c₀ + c₁×2 + c₂×4 の計算で誤り位置を特定できる
✅ 2ビット以上の誤りは対応外
参考情報
- IPA 応用情報技術者試験 過去問題：
https://www.ipa.go.jp/shiken/mondai-kaiotu/2024r06.html
コメント