パリティとハミング符号の誤り訂正
反転した位置を検査式から求め、1ビット訂正の条件と2ビット誤りの限界を学びます。
説明
通信や保存の途中で0と1が反転することがあります。検出用の余分なビットを加えると、受け取った列が規則に反するか調べられます。検出できることと、元の位置を特定して訂正できることは別です。
偶数パリティで1ビットと2ビットの反転を試し、続いて4ビットのデータを7ビットにするハミング符号を作ります。検査結果のシンドロームから1ビットを訂正し、2ビットを1ビットと誤認して訂正すると何が起きるかまで確認します。
11の個数を偶数にする
データ1011は1が3個なので、パリティ1を付けて合計4個にします。
data = [1, 0, 1, 1]元の4ビット; parity = sum(data) % 2偶数にするパリティ; word = data + [parity]検査ビットを追加; word, sum(word) % 2符号語と検査符号語10111の検査結果は0です。偶数パリティでは、1の合計が偶数になるよう余分な1ビットを決めます。
2一つ反転すると検出できる
添字1を反転します。XORの1は0を1、1を0へ変えます。
one_error = word.copy()元を保持; one_error[1] ^= 11ビット反転; one_error, sum(one_error) % 2検出結果検査結果が1へ変わり、規則違反を検出できました。ただしパリティ一つだけでは、どの位置が反転したかは分かりません。
3二つ反転すると検出を逃す
さらに別の添字2も反転します。反転数が偶数だと1の個数の偶奇が元へ戻ります。
two_errors = one_error.copy()1ビット誤りから開始; two_errors[2] ^= 1別の1ビットも反転; two_errors, sum(two_errors) % 2, two_errors == word検査成功とデータ一致は別検査0でも元とは一致しません。偶数パリティは奇数個の反転を検出できますが、偶数個の反転は見逃します。
47ビットにデータと検査ビットを配置する
ハミング(7,4)では位置1・2・4を検査用、3・5・6・7をデータ用にします。位置番号をそのまま添字にするため、添字0は使いません。
code = [0]*8; positions = [3, 5, 6, 7]1始まりの領域とデータ位置; code[3], code[5], code[6], code[7] = dataデータ1011を配置; [(i, format(i, '03b'), code[i]) for i in range(1, 8)]位置・2進位置・値位置番号の2進表記で、最下位が1の位置を検査1、次が1を検査2、その次が1を検査4の対象にします。各データ位置が異なる検査の組に含まれます。
5三つの偶数パリティを作る
検査1は3・5・7、検査2は3・6・7、検査4は5・6・7から決めます。各検査自身を含めた合計が偶数になります。
code[1] = code[3]^code[5]^code[7]検査1; code[2] = code[3]^code[6]^code[7]検査2; code[4] = code[5]^code[6]^code[7]検査4; ''.join(map(str, code[1:]))7ビットの符号語符号語は0110011です。データ4ビットに検査3ビットを加え、1ビットの反転位置を特定する情報を持たせました。
6検査結果を位置番号にする
各検査対象の1の個数を2で割った余りが検査ビットです。重み1・2・4を掛けて足すとシンドロームになります。
syndrome = lambda bits:検査結果を求める関数 sum(p*(sum(bits[i] for i in range(1, 8) if i & p) % 2) for p in [1, 2, 4])各検査の重み付き和; syndrome(code)正常な符号語を検査正しい符号語のシンドロームは0です。1ビットだけが反転すると、その位置番号の各ビットに対応する検査だけが反転し、位置番号が得られます。
7位置5の誤りを訂正
位置5を反転すると、検査1と4が反応してシンドローム5になります。その位置を反転して戻します。
received = code.copy(); received[5] ^= 1位置5を反転; location = syndrome(received)誤り位置を計算; print(location, received[1:])位置と受信列; received[location] ^= 1そのビットを訂正; received == code, [received[i] for i in positions]符号語と復元データを照合シンドローム5で位置が特定され、訂正後は元の1011に戻ります。この訂正の判断は誤りが高々1ビットという条件に依存します。
8二つの誤りを一つと誤認する
位置3と5を反転するとシンドロームは3 XOR 5で6です。位置6が誤りだとみなして訂正してみます。
double = code.copy(); double[3] ^= 1; double[5] ^= 1二位置を反転; guessed = syndrome(double)単一誤りと仮定した位置; double[guessed] ^= 1誤った訂正; guessed, syndrome(double), double == code, [double[i] for i in positions]検査0でも元へ戻らない位置6を変えるとシンドロームは0になりますが、元の符号語とは一致しません。二つの誤りにさらに一つ加え、別の有効な符号語へ変えてしまいました。ハミング(7,4)の1ビット訂正だけでは2ビット誤りと見分けられません。
9全体パリティを追加する
元の7ビット全体にも偶数パリティを付けます。1ビット誤りは全体パリティを変え、2ビット誤りは変えません。
overall = sum(code[1:]) % 2全体パリティ; single = code.copy(); single[5] ^= 1単一誤り; pair = code.copy(); pair[3] ^= 1; pair[5] ^= 1二重誤り; [(syndrome(bits), (sum(bits[1:])+overall) % 2) for bits in [code, single, pair]]シンドロームと全体検査正常は(0,0)、1ビット誤りは(5,1)、2ビット誤りは(6,0)です。追加した全体パリティにより、最大2ビット誤りという条件では1ビット訂正と2ビット検出を分けられます。全体パリティだけの反転は(0,1)となります。3ビット以上にも同じ保証があるわけではありません。
まとめ
偶数パリティは奇数個の反転を検出しますが、位置の特定や偶数個の検出はできません。
ハミング(7,4)では複数の検査を組み合わせ、高々1ビットの誤りを訂正できます。
2ビットを単一誤りと扱うと誤訂正になります。全体パリティの追加で保証できる範囲が変わります。
操作履歴と解説を振り返れます。
Python 3
data = [1, 0, 1, 1]; parity = sum(data) % 2; word = data + [parity]; word, sum(word) % 2([1, 0, 1, 1, 1], 0)
one_error = word.copy(); one_error[1] ^= 1; one_error, sum(one_error) % 2([1, 1, 1, 1, 1], 1)
two_errors = one_error.copy(); two_errors[2] ^= 1; two_errors, sum(two_errors) % 2, two_errors == word([1, 1, 0, 1, 1], 0, False)
code = [0]*8; positions = [3, 5, 6, 7]; code[3], code[5], code[6], code[7] = data; [(i, format(i, '03b'), code[i]) for i in range(1, 8)][(1, '001', 0), (2, '010', 0), (3, '011', 1), (4, '100', 0), (5, '101', 0), (6, '110', 1), (7, '111', 1)]
code[1] = code[3]^code[5]^code[7]; code[2] = code[3]^code[6]^code[7]; code[4] = code[5]^code[6]^code[7]; ''.join(map(str, code[1:]))'0110011'
syndrome = lambda bits: sum(p*(sum(bits[i] for i in range(1, 8) if i & p) % 2) for p in [1, 2, 4]); syndrome(code)0
received = code.copy(); received[5] ^= 1; location = syndrome(received); print(location, received[1:]); received[location] ^= 1; received == code, [received[i] for i in positions]5 [0, 1, 1, 0, 1, 1, 1] (True, [1, 0, 1, 1])
double = code.copy(); double[3] ^= 1; double[5] ^= 1; guessed = syndrome(double); double[guessed] ^= 1; guessed, syndrome(double), double == code, [double[i] for i in positions](6, 0, False, [0, 1, 0, 1])
overall = sum(code[1:]) % 2; single = code.copy(); single[5] ^= 1; pair = code.copy(); pair[3] ^= 1; pair[5] ^= 1; [(syndrome(bits), (sum(bits[1:])+overall) % 2) for bits in [code, single, pair]][(0, 0), (5, 1), (6, 0)]
演習完了