応用情報技術者試験過去問を解いてみた R6年度春期問4 ハミング符号

1 はじめに
2 問題(R6年度応用情報技術者試験春期午前問4)
3 解答
4 解説
- 4.1 C₀, C₁, C₂ の計算
- 4.2 i の計算
- 4.3 訂正
5 問題の用語解説
6 体系的位置づけ
7 さらに理解を深めよう：ハミング符号
- 7.1 受信データが「正しい」か「間違っている」か、どうやって判断する？
- 7.2 どうしてその計算方法で誤り位置が特定できるの？
- 7.3 2ビット分誤りがあるとどうなるの？
- 7.4 C₀, C₁, C₂ の計算式の理由
- 7.5 最後に：パリティとは何か？
- 7.6 小まとめ
8 もっと解説：そもそも誤り訂正はなぜ必要なのか
9 受信した符号が誤っているかどうかは、どう判断するのか
10 パリティとは何か(もう一度)
11 今回の問題の場合(符号長7、情報ビット数4の場合)
12 今回の問題でパリティビットが3個である理由
13 ハミング符号とパリティの関係
14 なぜハミング符号では誤っている場所まで特定できるのか
15 パリティ3個で8通りあるのに、なぜ7ビット分しか使わないのか
16 もしパリティが4個なら15ビットまで扱えるのか？
17 データ長が8〜14ビットの場合は使えるのか
18 実際の通信の世界で使われているのか
19 もう少し解説：情報の伝達イメージ
- 19.1 情報と情報の切れ目はどう表現するのか
- 19.2 0と1は電気信号にどう乗せているのか
20 最後に
21 参考情報

はじめに

今回も、応用情報技術者試験の過去問を解いていきます。
今回は「ハミング符号による誤り訂正」の問題です。
通信の安定性やデータの信頼性を支える重要な技術なので、しっかり理解していきます。

ただ、正直この問題よくわからない…

問題(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

※「mod2で計算」とは、「2で割った余りを計算する」という意味です

なので、例えば3に対しmod2で計算すると

3 ÷ 2 = 1余り1

したがって、計算結果は1となります。

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ビット誤りが起きると：
(＝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ビット以上の誤りは対応外

もっと解説：そもそも誤り訂正はなぜ必要なのか

データ通信では、送信した情報がそのまま相手に届くとは限りません。
コンピュータの中では情報は0と1で扱われていますが、その0と1は電気信号や電波にのって送受しています。

そのため、次のような影響でビットが変化します。

電磁ノイズ
温度変化
回路の揺らぎ
タイミングのズレ

上記の影響を受けると、送信側と受信側で数字の並びがずれてしまうことがあります。

$\text{送信：}1010101 \quad \rightarrow \quad \text{受信：}1000101$

そうなると、正しい情報のやりとりができません。

そこで、このような誤りを検出・訂正するために、パリティやハミング符号が必要になります。

受信した符号が誤っているかどうかは、どう判断するのか

誤りを検出するためには、データに「チェック用の情報」を付加します。
これがパリティです。

送信側と受信側で同じ計算を行い、結果を比較します。

一致 → 正常
不一致 → 誤りあり

ハミング符号ではさらに、

誤りの有無
誤りの場所

の両方を特定できます。

パリティとは何か(もう一度)

パリティとは、誤り検出のためのチェックビットです。
ざっくり言えば、誤りを検出するための「数字」のことです。

例えば、下記の情報があったとします。

「1011（1の個数=3）」

これに対し、誤り検出のために、最後尾に1を追加したとします。

⇒10111

この時付け加えた１が「パリティ」です。

この時のケースでは、受信側では1の個数を再度数え、

偶数 → 正常
奇数 → 誤り

と判断します。

今回の問題の場合(符号長7、情報ビット数4の場合)

今回の問題は、符号長7、情報ビット数4ビットとなっています。

これは7ビットの数字(例えば1010101)の中で、

4つが情報として使われ、

残り3つが誤り位置を特定するために使われる、ということです。

また、パリティビットは、左から、1、2、4番目の位置に設置されます
(下記の赤文字部分)

1010101

今回の問題でパリティビットが3個である理由

ハミング符号では次の関係を満たします(満たす必要があります)。

$2^r \geq n + 1$

r：パリティの数

n：符号長

今回： $n = 7$

なので

$2^3 = 8 \geq 7 + 1 = 8$

👉 よって パリティは3個必要、ということになります。

ハミング符号とパリティの関係

念のため解説しておくと、

ハミング符号は複数のパリティから構成されます。

つまり、パリティの特定の組み合わせによって、ハミング符号はできています。

これが、ハミング符号とパリティの関係性です。

なぜハミング符号では誤っている場所まで特定できるのか

各ビットには固有のチェックパターン（ID）が割り当てられています。

ビット位置	ID（c₂ c₁ c₀）
1	001
2	010
3	011
4	100
5	101
6	110
7	111

誤りがあると、 $(c_2\ c_1\ c_0) = 011 \Rightarrow 3$

👉 3ビット目が誤り

パリティ3個で8通りあるのに、なぜ7ビット分しか使わないのか

ここで生じうる疑問として、

3つのパリティの組み合わせは

$2^3 = 8$

つまり、8つの組み合わせが存在します。

しかし、今回の問題の場合、7つのパターンを識別に用いているだけで、1つ余っているように感じます。

この1つの余りはどこにいったのでしょうか。

結論から言うと、その一つは「正常」の場合を示すために用いられます。

つまり、

000 → 正常
001〜111 → エラー位置

ということで、すべての組み合わせを使っているということになります。

👉 1つは正常用として使う

もしパリティが4個なら15ビットまで扱えるのか？

結論として、その通りです。

$2^4 = 16$

0000 → 正常
その他 → エラー位置（15通り）

👉 最大15ビットまで対応可能

データ長が8〜14ビットの場合は使えるのか

これまでの話で

7ビットまでの情報：3つのパリティ

15ビットまでの情報：4つのパリティ

これで誤り訂正ができるということがわかりました。

では、7から15の間、例えば10ビットの長さを誤り訂正することはできるのか？

という疑問がわいてきます。

これもできます。

この場合、パリティは4つ使います。

ただし、10ビットの情報しかないので、

$2^4 = 16$

16個の組み合わせの内、

10個の組み合わせだけ使用し、残り5つは使用しないという形で運用します。
(※残り1つは正常用)

このような運用方法であれば、10ビットの情報であっても。ハミング符号は使用可能です。

実際の通信の世界で使われているのか

実際はもっと複雑な技術で、誤り訂正を行っています。

しかし、その技術の基礎的な部分は、ハミング符号になっています。

だからこそ、応用情報技術者試験で出題されているのです。

技術	用途
パリティ	軽いチェック
ハミング符号	ECCメモリ
LDPC	高速通信

もう少し解説：情報の伝達イメージ

情報と情報の切れ目はどう表現するのか

情報は0と1の形で伝達されると説明しました。
そうすると、次のような疑問がわくかもしれません

「0と1の並びから、どこまでの範囲が情報なのか、どうやって区別するのだろう？」

どういうことかというと例えば次の情報があったとします。

0100111100000110101…

この中で、下記の赤色の部分が情報で、青色がパリティビットだとします。