応用情報技術者試験 令和6年春 午前問4 解説付き過去問
問題
符号長7ビット、情報ビット数4ビットのハミング符号による誤り訂正の方法を、次のとおりとする。
受信した7ビットの符号語x1x2x3x4x5x6x7(xk＝0又は1)に対して
c0 ＝ x1 ＋x3 ＋x5 ＋x7
c1 ＝ x2＋x3 ＋x6＋x7
c2 ＝ x4＋x5＋x6＋x7
(いずれも mod 2 での計算)
を計算し、c0、c1、c2の中に少なくとも一つは0でないものがある場合には、
i＝c0＋c1×2＋c2×4
を求めて、左からi ビット目を反転することによって誤りを訂正する。
受信した符号語が1000101であった場合、誤り訂正後の符号語はどれか。
受信した7ビットの符号語x1x2x3x4x5x6x7(xk＝0又は1)に対して
c0 ＝ x1 ＋x3 ＋x5 ＋x7
c1 ＝ x2＋x3 ＋x6＋x7
c2 ＝ x4＋x5＋x6＋x7
(いずれも mod 2 での計算)
を計算し、c0、c1、c2の中に少なくとも一つは0でないものがある場合には、
i＝c0＋c1×2＋c2×4
を求めて、左からi ビット目を反転することによって誤りを訂正する。
受信した符号語が1000101であった場合、誤り訂正後の符号語はどれか。
正解
解説
ハミング符号は、誤り検出と訂正を可能にする誤り訂正符号の一種であり、ここでは7ビットの符号語に対して誤り訂正を行う。
- 誤り訂正の手順
受信した符号語が 1000101 であるため、与えられた計算式を用いて誤り位置を特定する。
各パリティビットの計算を行う。mod 2 での計算を行うため、1の個数が奇数なら1、偶数なら0となる。
c0 ＝ (1＋0＋1＋1) mod 2 ＝ 3 mod 2 ＝ 1
c1 ＝ (0＋0＋0＋1) mod 2 ＝ 1 mod 2 ＝ 1
c2 ＝ (0＋1＋0＋1) mod 2 ＝ 2 mod 2 ＝ 0
これらの値を使って誤り位置 i を求める。
i ＝ c0＋c1×2＋c2×4
＝ 1＋1×2＋0×4
＝ 3
- 誤り訂正
i＝3 であるため、左から3ビット目を反転する。
受信符号語 ：1000101
3ビット目を反転後：1010101 - 結論
誤り訂正後の符号語は 1010101 となる。