ハミング符号の原理（６） －巡回ハミング符号－

送信データに次のように目印（アドレス、シンドロームなど）を割り当てると、シフトレジスタを用いた簡単な回路で、符号化・復号化が行えるようになります。
　　　　 　(1**) (*1*) (**1)
101　a　　　a　　　　　　 a
111　b　　　b　　　b　　　b　
110　c　　　c　　　c　
011　d　　　　　　 d　　　d　
100　p1　　 p1　
010　p2　　　　　　p2　
001　p3　　　　　　　　　p3
--------------------------
　　　　　　　s1　　s2　　s3

s1 = a+b+c+p1
s2 = b+c+d+p2
s3 = a+b+d+p3

p1 = a+b+c
p2 = b+c+d
p3 = a+b+d

a=1 b=1 c=0 d=1
(a,b,c,d)=(1101)　のとき (p1,p2,p3)=(001)

送信データを
(a,b,c,d,p1,p2,p3)=(1101001)
として、
(a,b,c,d,p1,p2,p3)=(1100001)
が受信されたとします。

シンドローム計算回路は、次のとおりです。これは、R3、R2、R1 の３つのシフトレジスタと、２つの排他的論理和回路(+)からなる割り算回路です。

　　　　　　　　 　← ← ← ← ← ← ← ← ← ←
　　　　　　　　　↓　　　　　　↓　　　　　　　　　↑
受信データ　→(+)→ R3 →(+)→ R2 → R1 →

受信データ(a,b,c,d,p1,p2,p3)=(1100001)を次のように、入力すると、

　　　　　　　　　　　　　　　 ← ← ← ← ← ← ← ←
　　　　　　　　　　　　　　 ↓　　　　　↓　　　　　　　↑
　　　p3,p2,p1,d,c,b,a　→(+)→R3→(+)→R2→R1→

７ビットの受信データが入力された段階で、このシフトレジスタの内部状態がシンドロームとなります。

R3,R2,R1 　
--------
000　（初期状態）
100　（時刻ｔ１で a=1 がレジスタ R3 に入力された状態）
110　（時刻ｔ２で b=1 が入力された状態）
011　（時刻ｔ３で c=0 を入力）
111　（時刻ｔ４で d=0 を入力）
101　（時刻ｔ５で p1=0 を入力）
100　（時刻ｔ６で p2=0 を入力）
110　（時刻ｔ７で p3=1 を入力）

時刻ｔ７で、すべての受信データが入力された状態で、(R3,R2,R1)=(110) となります。
よって、シンドローム(s1,s2,s3)=(R1,R2,R3)=(011)
したがって、d の１ビット誤りであることがわかります。

数式で書くと
1100001÷1011=011
　（1100001を1011で割って余りが011の意味）
上記のシンドローム計算回路は、1011割り算回路になっています。


◆送信する符号化データの作成も同じ回路（割り算回路）で行うことができます。
(a,b,c,d,)=(1101)を送信するときには、

先ほどと同様に、
(a,b,c,d,p1,p2,p3)=(1101000)を入力すると、(R3,R2,R1)=(100)
となり、(p1,p2,p3)=(R1,R2,R3)=(001)となります。

数式で書くと、
1101000÷1011=001　（110100を1011で割って、余りが001の意味）

◆ちなみに、初期状態を (R3,R2,R1) = (100) として、下図の回路のシフト動作を行うと、シフトレジスタの内部状態 (R3,R2,R1) は、次のように変化します。

　　← ← ← ← ← ← ← ←
　↓　　　　↓　　　　 　　　↑
　　→R3→(+)→R2→R1→

上図の回路は、R3、R2、R1 の３つのシフトレジスタを用いて、R1の出力を、R3、R2にフィードバックしたものです。
R2＝R1+R3 として、フィードバックします。

R3,R2,R1 　
--------
100　
010　
001　
110　
011　
111　
101　
100

◆巡回符号とは
巡回符号の意味は、先ほどの送信データ、
(a,b,c,d,p1,p2,p3)=(1101001)

の最下位ビットを最上位ビットに移動し、他のビットを順次、右側に巡回シフト（巡回置換）した符号
(a,b,c,d,p1,p2,p3)=(1110100)
も、符号語になっています。
1110100÷1011＝0　（上記のシンドローム回路（割り算回路）に符号後の７ビットを入力した段階で、シフトレジスタの内部状態が000になる）

これをさらに、巡回シフトした符号
(a,b,c,d,p1,p2,p3)=(0111010)
も、符号語になっています。
0111010÷1011＝0

まとめて書くと、
(a,b,c,d,p1,p2,p3)=
(1101001)　
(1110100)　１回目の巡回シフト
(0111010)　２回目の巡回シフト
(0011101)　３回目
(1001110)　４回目
(0100111)　５回目
(1010011)　６回目
(1101001)　７回目

７回目の巡回シフトで元の符号に戻ります。

モジュロ２の算法による割り算　－１＝＋１

はじめに、符号に割り当てた、符号の目印は、ガロア拡大体の元です。
ガロア拡大体の元

参考文献：
誤り訂正符号とその応用，テレビジョン学会　編

ハミング符号の原理（１）
ハミング符号の原理（２）
ハミング符号の原理（３）
ハミング符号の原理（４）　－拡大ハミング符号－
ハミング符号の原理（５）　－グレイ・ハミング符号－
ハミング符号の原理（６）　－巡回ハミング符号－