ハミング符号の誤り訂正
出典: 令和6年度 春期 応用情報技術者試験 午前 問4 (IPA)
符号長 7 ビット，情報ビット数 4 ビットのハミング符号による誤り訂正の方法を，次のとおりとする。
受信した 7 ビットの符号語 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₂ の中に少なくとも一つは 0 でないものがある場合には，
i ＝ c₀＋c₁×2＋c₂×4
を求めて，左から i ビット目を反転することによって誤りを訂正する。
受信した符号語が 1000101 であった場合，誤り訂正後の符号語はどれか。
- ア 1000001
- イ 1000101
- ウ 1001101
- エ 1010101
正解と解説を見る
正解: エ
- ア: 左から 3 ビット目ではなく 5 ビット目を反転した形です。i は 3 です。
- イ: 受信した符号語そのままで、訂正されていません。c₀ と c₁ が 1 なので誤りがあります。
- ウ: 左から 4 ビット目を反転した形です。i は 3 です。
- エ: 左から 3 ビット目 (0) を反転して 1 にした 1010101 です。正しい答えです。
ポイント
受信語 1000101 は x₁=1, x₂=0, x₃=0, x₄=0, x₅=1, x₆=0, x₇=1 です。
- c₀ = x₁+x₃+x₅+x₇ = 1+0+1+1 = 3 → mod 2 で 1
- c₁ = x₂+x₃+x₆+x₇ = 0+0+0+1 = 1 → 1
- c₂ = x₄+x₅+x₆+x₇ = 0+1+0+1 = 2 → 0
- i = 1 + 1×2 + 0×4 = 3。左から 3 ビット目を反転すると 1010101 になります。