応用情報技術者 2011年秋期午前2 問03

問題文

符号長7ビット、情報ビット数4ビットのハミング符号による誤り訂正の方法を、次のとおりとする。　受信した7ビットの符号語

x_{1} x_{2} x_{3} x_{4} x_{5} x_{6} x_{7}

(

x_{k} = 0

又は1)に対して　　

c_{0} = x_{1} + x_{3} + x_{5} + x_{7}

c_{1} = x_{2} + x_{3} + x_{6} + x_{7}

c_{2} = x_{4} + x_{5} + x_{6} + x_{7}

　(いずれもmod2での計算) 　を計算し、

c_{0}, c_{1}, c_{2}

の中に少なくとも一つは0でないものがある場合には、　　

i = c_{0} + c_{1} \times 2 + c_{2} \times 4

　を求めて、左から

i

ビット目を反転することによって誤りを訂正する。　受信した符号語が1000101であった場合、誤り訂正後の符号語はどれか。

🖊️ 解答を隠して解いてみる

選択肢

ア：1000001

イ：1000101

ウ：1001101

エ：1010101（正解）

🔒 解説は解答すると表示されます

ハミング符号の誤り位置検出【午前2解説】

正解の理由

受信語を左から1〜7ビット目を

x_{1} \dots x_{7}

とすると、受信語1000101は

x_{1} = 1, x_{2} = 0, x_{3} = 0, x_{4} = 0, x_{5} = 1, x_{6} = 0, x_{7} = 1

です。与えられた検査式を使ってパリティ検査値を計算すると

c_{0} = x_{1} + x_{3} + x_{5} + x_{7} = 1 + 0 + 1 + 1 = 3 \equiv 1 (mod 2)

、

c_{1} = x_{2} + x_{3} + x_{6} + x_{7} = 0 + 0 + 0 + 1 = 1

、

c_{2} = x_{4} + x_{5} + x_{6} + x_{7} = 0 + 1 + 0 + 1 = 2 \equiv 0 (mod 2)

となります。これより

i = c_{0} + c_{1} \times 2 + c_{2} \times 4 = 1 + 2 + 0 = 3

です。したがって左から3ビット目を反転すれば誤り訂正されます。受信語の3ビット目（0→1）を反転すると 1010101 になり、これが選択肢のエに一致します。よって正解はエです。

解法ステップ

受信語1000101をビット $x_{1} \dots x_{7}$ に割り当てる（左から順に1〜7）。
与えられた式で $c_{0}, c_{1}, c_{2}$ をそれぞれ mod2 で計算する：
- $c_{0} = x_{1} + x_{3} + x_{5} + x_{7}$
- $c_{1} = x_{2} + x_{3} + x_{6} + x_{7}$
- $c_{2} = x_{4} + x_{5} + x_{6} + x_{7}$
$i = c_{0} + c_{1} \times 2 + c_{2} \times 4$ を求める。
$i = 0$ なら誤りなし、 $i \neq = 0$ なら左から $i$ ビット目を反転する。今回 $i = 3$ なので3ビット目を反転して答えを得る。

選択肢別の誤答解説

ア: 1000001
受信語1000101と比べると、5ビット目が異なる（受信は $x_{5} = 1$ 、アは0）。すなわちアは「5ビット目を反転した語」ですが、計算上は3ビット目が誤りなので不正解です。
イ: 1000101
受信語と同一です。計算上 $c_{0}, c_{1}$ がともに1であり $i = 3$ と出ているため、何も変えないイは誤り訂正を行っていないため不正解です。
ウ: 1001101
受信語と比べると4ビット目が異なる（受信は $x_{4} = 0$ 、ウは1）。ウは「4ビット目を反転した語」ですが、正しい訂正位置は3ビット目なので不正解です。
エ: 1010101
受信語と比べると3ビット目が異なる（受信は $x_{3} = 0$ 、エは1）。計算で示した通り $i = 3$ なので3ビット目を反転した語が正しく、エが正解です。

よくある誤解

「ビット番号の向きを間違える」
左から何番目を反転するかが問題文で指定されている場合、右から数える癖があると位置がずれます。必ず設問のビット順（今回なら左から1〜7）を確認してください。
「シンドロームの重み割り当てを逆にする」
$i = c_{0} + c_{1} \times 2 + c_{2} \times 4$ のように、 $c_{0}$ を1の重み、 $c_{1}$ を2の重み、 $c_{2}$ を4の重みとする点を逆にしないこと。ビット順と重みの対応がズレると誤った位置を出します。
「mod2 の計算を忘れる（偶数を0にするのを忘れる）」
加算は常に mod2（偶奇）で行うため、合計が2や4でも0に戻すことを忘れないでください。

補足コラム

ハミング(7,4)符号は符号長7、情報ビット4の最小の正確な単一ビット訂正符号です。パリティ検査に用いる列（パリティビットがチェックする情報ビットの組）は、通常、列ベクトルを二進数で表すと1〜7の位置のビット表現になります。今回の式はその列の組合せによるシンドローム計算の具体形です。

簡単なPython例（受信語を与えて訂正する）：

def correct(received):
    x = list(map(int, received))
    c0 = (x[0] + x[2] + x[4] + x[6]) % 2
    c1 = (x[1] + x[2] + x[5] + x[6]) % 2
    c2 = (x[3] + x[4] + x[5] + x[6]) % 2
    i = c0 + c1*2 + c2*4
    if i != 0:
        idx = i - 1  # 左からiビット目はインデックスi-1
        x[idx] ^= 1
    return ''.join(map(str,x))

print(correct("1000101"))  # 出力: 1010101

FAQ

Q: シンドロームが0のときはどう判断する？
A:

i = 0

（すなわち

c_{0} = c_{1} = c_{2} = 0

）ならエラーなしと判断し、何もしません。

Q: 2ビット以上の誤りは訂正できる？
A: ハミング(7,4)は最小ハミング距離3で、単一ビット誤りは確実に訂正できます。2ビット誤りは検出（多くの場合シンドロームは0以外になる）できることが多いですが、確実に正しく訂正することはできません。単純なシンドロームデコードは単一誤りを前提としています。

Q: シンドロームのビット順を間違えた場合どうなる？
A: ビット順（

c_{0}

が1の重みなど）を逆にすると

i

の値が変わり、誤った位置を反転してしまいます。設問の式と重み対応を必ず確認してください。

関連キーワード: ハミング符号、シンドローム、単一ビット訂正、パリティ、符号長7、最小ハミング距離

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！