MathcotさんのHomepageです

巡回符号・ハミング符号

Author: Mathcot

初版: 2007.8.12

Lastupdate: 2007.12.30


 
巡回符号CRC(Cyclic Redundancy Checking Code)
(1)線形符号の一種で、複数ビットの連続(バースト)誤り検出に強い符号
(2)デジタル通信や各種大量記憶媒体の誤り検出に広く利用されている。
xn-1 が生成多項式 G(x) で割り切れるとき、このG(x) から生成される符号語を巡回状にシフトしたもの
もまた符号語になっています。このような性質をもつ符号語を「巡回符号」という。
 

n=7
x7-1 = (x-1) (x6+x5+x4+x3+x2+x+1)
= (x-1) (x3 +x+1) (x3+x2-1)

巡回符号
(7, 3)符号
情報ビット3ビット、チェックビット4ビット、送受信符号ビット7ビットの線形符号。
(7, 4)符号
情報ビット4ビット、チェックビット3ビット、送受信符号ビット7ビットの線形符号。

伝送するm(=-k)個の情報ビット(p(m-1))を係数とする多項式を P(x)
P(x)=p0+p1x+p2x^2+…+pm-1x^(m-1)
 
符号多項式F(x)=P(x)x^(n-m)+R(x)

G(x):巡回符号の生成多項式とすると
F(x) = G(x) Q(x)から巡回符号をつくることができる。
符号ビットの特定箇所に情報ビットを対応させる。




組織符号(p0,p1,....,pk-1|c0,...,cn-k-1):n個

符号の多項式表現

u = ( u0, u1, ... , u(n-1) )

u(x) = u0 + u1 x + u2 + x^2 + ..... + u(n-1) x ^ (n-1)

巡回置換 x u(x) mod ( x^n - 1 )


情報多項式

g(x) = x^3 + x + 1

n= 7

情報多項式:P0 + P1 x + P2 x^2 + P3 x^3

(7,4)符号と同じ

伝えたい情報uを多項式とみなして、u(x)とする。(u0 + u1 x + u2 x^2 + ... )

ある関数g(x)をu(x)にかける。u'(x)をつたえる。y(x)=u'(x)+e(x)となり、y(x) mod g(x)とすると、あまりが0にならないときがエラーを含むときである。g(x)=x^3+x+1を選択すれば、一重誤り訂正可能の符号化になる。

生成行列(G)と検査行列(H)


ハミング符号

ある整数 m に対し、

符号長 :n = 2m − 1
情報数 :k = nm

で構成される。ここで情報数とは元のデータのビット数、符号長とは生成される符号のビット数である。 m = 3 の場合は n = 7、k = 4 となり、4ビットのビット列を7ビットの符号語に置き換えるハミング符号が形成される、この場合を(7,4)ハミング符号という。

ハミング符号は検査行列と生成行列と呼ばれる二つの行列を用いて処理が行われる。まず検査行列について述べる。この行列は m行 n列の行列で、全ての列要素がゼロではなく、かつ相違であるという条件がある。 (7,4)ハミング符号の検査行列 H の一例を以下に示す。

H=
[1 0 1 1 1 0 0]
[1 1 0 1 0 1 0]
[0 1 1 1 0 0 1]
=[A Im] : 組織符号
Aは任意の行列、Imはm行m列の単位行列
生成行列Gの計算が容易になる
HG~=GH~=0
G~はGの転置行列
組織符号の場合
G=[Ik A~]
上のHに対するG
G=
[1 0 0 0 1 1 0]
[0 1 0 0 0 1 1]
[0 0 1 0 1 0 1]
[0 0 0 1 1 1 1]

符号化

生成行列G
送信データX:m1…mk
符号化はGと送信データの行列計算を行い、加算はExORで行う。
G=
[1 0 0 0 1 1 0]
[0 1 0 0 0 1 1]
[0 0 1 0 1 0 1]
[0 0 0 1 1 1 1]

送信データX=[1 0 1 1]

符号行列
[1 0 1 1]・G=
[1 0 1 1 1 0 0]

復号化
(検査行列H)・(受信データY)

Yに誤りがない場合
Y=X・G (Xは符号化前のビット列

Y・H~=X・(G・H~)=0
=0でエラー無、≠0でエラー有

Yに1ビットのエラーがある場合
Y=X・G+ei
ei:誤りベクトル

Y・H~=(X・G+ei)・H~=X・(G・H~)+ei・H~
=ei・H~
この出力がHの何列目と一致するかで誤りの位置が検出され、
そのビットを反転させて誤り訂正ができる。


送信データ[1 0 1 1 1 0 0]
受信データ[1 1 1 1 1 0 0]


符号長7の二元巡回(7,4)の符号器を使用する。
この時、巡回符号の生成多項式を
g(x) = x^3 + x + 1

問題1
符号長n=7, 二元巡回(7,4)の符号器であるから、
情報ビットの桁数m=4=n-k=7-k
チェックビット数k=3
 
情報桁を表す多項式が x^2 + x +1  であるとき
符号器が出力する符号多項式はどのようなものか。

P(x)=x^2 + x +1
F(x)=g(x)Q(x)
P(x)x=Q(x)g(x)+R(x)

情報ベクトル:1110=1+x+x^2+0x^3=I(x)

問題2
この巡回符号のパリティ検査行列を求めよ。
H=
[0101100]
[0111010]
[1101001]

問題3
この巡回符号の符号語を送信したとき、
受信多項式 y(x) が x^5 + x^4 + x^3 + x^2 +1
であるとする。この受信多項式y(x)の誤りを訂正せよ。

P(x)=x^2 +x +1
F(x)=Q(x)g(x)=x^5P(x)+R(x)
x^5P(x)=x^7+x^6+X^5=g(x)Q(x)+R(x)
=(x^3 +x+1)(x^4+x^3+1) +x+1
Q(x)=x^4+x^3+1, R(x)=x+1
F(x)=x^7+x^6+X^5+x+1

問題1
>符号長7の二元巡回(7,4)
符号長n=7,情報ビット数m=4,n-m=3
>g(x) = x^3 + x + 1
>x^2 + x +1 =P(x)
P(x)x^3=x^6+x^5+x^4=g(x)Q(x)+R(x)
=(x^3+x+1)(x^3+x^2)+x^2
Q(x)=x^3+x^2, R(x)=x^2
巡回符号の符号多項式
F(x)=P(x)x^3+R(x)=x^6+x^5+x^4+x^2

問題2
パリティ検査行列Hは3行7列の行列で
全ての列が異なり、列の全ての要素がゼロでないこと。最後の3列は単位行列であること。これらの条件を満たす検査行列Hは次の通り。
H=
[1 0 1 1 1 0 0]
[1 1 0 1 0 1 0]
[0 1 1 1 0 0 1]

問題3
>受信多項式 y(x) が x^5 + x^4 + x^3 + x^2 +1
受信データY=[0111101]
誤りベクトル=Y・H~=[1 0 0]
これがH行列の前から5列目と一致する。
したがって受信データYの前から5ビット目がエラー。
5ビット目を反転させて誤り訂正する。
訂正後のY=[0111001]
正しい受信多項式はx^2の係数を反転させて
y(x)=x^5 + x^4 +x^3 + 1
となる。
 
参考URL
[1]巡回符号
[2]情報理論
[3]ハミング符号
[4]誤り検出方式−巡回符号−
[5]巡回符号
[6]
[7]


inserted by FC2 system