BCH符号

BCH符号（BCHふごう、英: BCH code）は、パラメータ化された誤り訂正符号の一種で、最もよく研究されている符号の1つである。1959年 Alexis Hocquenghem が、それとは別に1960年には Raj Chandra Bose と D. K. Ray-Chaudhuri が考案した^[1]。BCH とは、この3人のイニシャルである。

BCH符号は、シンドローム復号という簡潔な代数学的手法で容易に復号できる点を特徴とする。そのための電子回路は非常に単純でコンピュータを使う必要もなく、低電力で小型の機器で復号可能である。符号としても非常に柔軟性があり、ブロック長や誤り訂正能力を自由に設定でき、目的に応じてカスタマイズされた符号を設計できる。

BCH符号は、マルチレベル/巡回/誤り訂正/可変長デジタル符号であり、複数の無作為誤りパターンを訂正できる。BCH符号は、レベル数が素数または素数のべき乗であるようなマルチレベルの位相偏移変調でも使われる。11レベルのBCH符号を使って、十進数の10個の数字と符号を表す場合もある^[2]。

目次

• 
  1 構築
  
  
  
  • 
    1.1 単純化したBCH符号
    
    
    
    • 
      1.1.1 例
      
    
    
    
    
  
  
  • 
    1.2 一般のBCH符号
    
  
  
  • 
    1.3 特性
    
  
  
  • 
    1.4 特殊ケース
    
  
  
  
  


• 
  2 復号
  
  
  
  • 
    2.1 PGZアルゴリズム
    
  
  
  • 
    2.2 誤り位置多項式の因数分解
    
  
  
  • 
    2.3 誤り訂正
    
  
  
  
  


• 
  3 脚注
  


• 
  4 参考文献
  

構築

BCH符号は、有限体上の特定の生成多項式を使った多項式符号である。また、同時に巡回符号でもある。

単純化したBCH符号

まず説明を簡単にするため、特殊なBCH符号を例とする。一般のBCH符号は次節で説明する。

有限体 GF(q){displaystyle GF(q)}（q{displaystyle q} は素数冪）を定める。そして、n=qm−1{displaystyle n=q^{m}-1} および 2≤d≤n{displaystyle 2leq dleq n} となるように正の整数 m{displaystyle m}, n{displaystyle n}, d{displaystyle d} を定める。これらから、GF(q){displaystyle GF(q)} 上で符号語長 n{displaystyle n}、最小ハミング距離 d{displaystyle d} 以上の多項式符号を構築する。さらに定めるべきは、その符号の生成多項式である。

GF(qm){displaystyle GF(q^{m})} の1のn乗根を α{displaystyle alpha } とする。全ての i{displaystyle i} について αi{displaystyle alpha ^{i}} の GF(q){displaystyle GF(q)} 上の原始多項式を mi(x){displaystyle m_{i}(x)} とする。BCH符号の生成多項式は最小公倍数 g(x)=lcm(m1(x),…,md−1(x)){displaystyle g(x)={rm {lcm}}(m_{1}(x),ldots ,m_{d-1}(x))} で定義される。

例

q=2{displaystyle q=2} 、 m=4{displaystyle m=4} とする（従って n = 15 ）。 d{displaystyle d} についてはいくつかの値を検討する。まず、

α4+α+1=0{displaystyle alpha ^{4}+alpha +1=0} (1);

を満たす1の冪根 α∈GF(16){displaystyle alpha in GF(16)} が存在し、GF(2){displaystyle GF(2)} 上の原始多項式は

m1(x)=x4+x+1{displaystyle m_{1}(x)=x^{4}+x+1}

である。なお、GF(2){displaystyle GF(2)} においては (a+b)2=a2+2ab+b2=a2+b2{displaystyle (a+b)^{2}=a^{2}+2ab+b^{2}=a^{2}+b^{2}} が成り立つので、m1(α2)=m1(α)2=0{displaystyle m_{1}(alpha ^{2})=m_{1}(alpha )^{2}=0} となる。従って α2{displaystyle alpha ^{2}} は m1(x){displaystyle m_{1}(x)} の根であり、

m2(x)=m1(x)=x4+x+1{displaystyle m_{2}(x)=m_{1}(x)=x^{4}+x+1}

となる。m3(x){displaystyle m_{3}(x)} を求めるため、(1)を繰り返し適用して以下の線型関係式を得る。

• 1=0α3+0α2+0α+1{displaystyle 1=0alpha ^{3}+0alpha ^{2}+0alpha +1}


• α3=1α3+0α2+0α+0{displaystyle alpha ^{3}=1alpha ^{3}+0alpha ^{2}+0alpha +0}


• α6=1α3+1α2+0α+0{displaystyle alpha ^{6}=1alpha ^{3}+1alpha ^{2}+0alpha +0}


• α9=1α3+0α2+1α+0{displaystyle alpha ^{9}=1alpha ^{3}+0alpha ^{2}+1alpha +0}


• α12=1α3+1α2+1α+1{displaystyle alpha ^{12}=1alpha ^{3}+1alpha ^{2}+1alpha +1}

これらの右辺は線型従属でなければならず、そこから線型従属式 α12+α9+α6+α3+1=0{displaystyle alpha ^{12}+alpha ^{9}+alpha ^{6}+alpha ^{3}+1=0} が得られる。これには少なからぬ従属性があるので、α3{displaystyle alpha ^{3}} の原始多項式は

m3(x)=x4+x3+x2+x+1{displaystyle m_{3}(x)=x^{4}+x^{3}+x^{2}+x+1}

となる。同様の考え方で、以下のような式が得られる。

m4(x)=m2(x)=x4+x+1{displaystyle m_{4}(x)=m_{2}(x)=x^{4}+x+1,}

m5(x)=x2+x+1{displaystyle m_{5}(x)=x^{2}+x+1,}

m6(x)=m3(x)=x4+x3+x2+x+1{displaystyle m_{6}(x)=m_{3}(x)=x^{4}+x^{3}+x^{2}+x+1,}

m7(x)=x4+x3+1{displaystyle m_{7}(x)=x^{4}+x^{3}+1,}

d=1,2,3{displaystyle d=1,2,3} の場合のBCH符号の生成多項式は次のようになる。

d(x)=m1(x)=x4+x+1{displaystyle d(x)=m_{1}(x)=x^{4}+x+1,}

この場合の最小ハミング距離は3で、最大1つの誤りを訂正できる。生成多項式の次数が4なので、この符号はデータビットが11ビット、チェックサムビットが4ビットとなる。

d=4,5{displaystyle d=4,5} の場合のBCH符号の生成多項式は次のようになる。

d(x)=lcm(m1(x),m3(x))=(x4+x+1)(1+x+x2+x3+x4)=x8+x7+x6+x4+1{displaystyle d(x)={rm {lcm}}(m_{1}(x),m_{3}(x))=(x^{4}+x+1)(1+x+x^{2}+x^{3}+x^{4})=x^{8}+x^{7}+x^{6}+x^{4}+1,}

この場合の最小ハミング距離は5で、最大2つの誤りを訂正できる。生成多項式の次数が8なので、この符号はデータビットが7ビット、チェックサムビットが8ビットとなる。

d=6,7{displaystyle d=6,7} の場合のBCH符号の生成多項式は次のようになる。

d(x)=lcm(m1(x),m3(x),m5(x))=(x4+x+1)(1+x+x2+x3+x4)(x2+x+1)=x10+x8+x5+x4+x2+x+1{displaystyle {begin{aligned}d(x)&{}={rm {lcm}}(m_{1}(x),m_{3}(x),m_{5}(x))\&{}=(x^{4}+x+1)(1+x+x^{2}+x^{3}+x^{4})(x^{2}+x+1)\&{}=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1end{aligned}}}

最小ハミング距離は7で、3つまでの誤りを訂正できる。符号のデータビットは5ビット、チェックサムビットは10ビットとなる。

d=8{displaystyle d=8} 以上のBCH符号の生成多項式は、次の通りである。

d(x)=lcm(m1(x),m3(x),m5(x),m7(x))=(x4+x+1)(1+x+x2+x3+x4)(x2+x+1)(x4+x3+1)=x14+x13+x12+⋯+x2+x+1{displaystyle {begin{aligned}d(x)&{}={rm {lcm}}(m_{1}(x),m_{3}(x),m_{5}(x),m_{7}(x))\&{}=(x^{4}+x+1)(1+x+x^{2}+x^{3}+x^{4})(x^{2}+x+1)(x^{4}+x^{3}+1)\&{}=x^{14}+x^{13}+x^{12}+cdots +x^{2}+x+1end{aligned}}}

この符号の最小ハミング距離は15で、7つまでの誤りを訂正できる。この場合、データビットが1ビットで、チェックサムビットが14ビットになる。実際、この符号は2つの符号語（000000000000000 と 111111111111111）しか持たない。

一般のBCH符号

一般のBCH符号は、上述の解説と2つの面で異なる。第一に n=qm−1{displaystyle n=q^{m}-1} をより一般的条件にする。第二に生成多項式の一連の根として α,…,αd−1{displaystyle alpha ,ldots ,alpha ^{d-1}} ではなく αc,…,αc+d−2{displaystyle alpha ^{c},ldots ,alpha ^{c+d-2}} を採用する。

有限体 GF(q){displaystyle GF(q)}（q{displaystyle q} は素数冪）を定める。そして 2≤d≤n{displaystyle 2leq dleq n}、gcd(n,q)=1{displaystyle {rm {gcd}}(n,q)=1} が成り立ち、 n{displaystyle n} を法とする q{displaystyle q} の位数が m{displaystyle m} となるように、正の整数 m,n,d,c{displaystyle m,n,d,c} を選択する。

前節と同様、GF(qm){displaystyle GF(q^{m})} の1のn乗根を α{displaystyle alpha } とし、全ての i{displaystyle i} について αi{displaystyle alpha ^{i}} の GF(q){displaystyle GF(q)} 上の原始多項式を mi(x){displaystyle m_{i}(x)} とする。BCH符号の生成多項式は、最小公倍数 g(x)=lcm(mc(x),…,mc+d−2(x)){displaystyle g(x)={rm {lcm}}(m_{c}(x),ldots ,m_{c+d-2}(x))} で定義される。

単純化した例と同様に n=qm−1{displaystyle n=q^{m}-1} を条件にすると、gcd(n,q){displaystyle {rm {gcd}}(n,q)} は自動的に1となり、n{displaystyle n} を法とした q{displaystyle q} の位数は自動的に m{displaystyle m} となる。従って、単純化した定義は一般的定義の特殊ケースになっている。

特性

BCH符号の生成多項式の次数は最大で (d−1)m{displaystyle (d-1)m} である。さらに q=2{displaystyle q=2} かつ c=1{displaystyle c=1} の場合、生成多項式の次数は最大で dm/2{displaystyle dm/2} である。

証明: 各原始多項式 mi(x){displaystyle m_{i}(x)} の次数は最大で m{displaystyle m} である。したがって、それらの d−1{displaystyle d-1} の最小公倍数の次数は最大で (d−1)m{displaystyle (d-1)m} となる。さらに q=2{displaystyle q=2} の場合、全ての i{displaystyle i} について mi(x)=m2i(x){displaystyle m_{i}(x)=m_{2i}(x)} となる。したがって g(x){displaystyle g(x)} は、奇数インデックス i{displaystyle i} の原始多項式 mi(x){displaystyle m_{i}(x)}（最大でも d/2{displaystyle d/2} 個）の最小公倍数であり、それぞれの多項式の次数は最大でも m{displaystyle m} である。

BCH符号の最小ハミング距離は最小で d{displaystyle d} である。単純化した例で証明を示すが、一般の場合も同様に証明できる。符号語 p(x){displaystyle p(x)} にはゼロでない項が d{displaystyle d} 個未満存在するとする。すると、

p(x)=b1xj1+⋯+bd−1xjd−1, where j1<j2<⋯<jd−1{displaystyle p(x)=b_{1}x^{j_{1}}+cdots +b_{d-1}x^{j_{d-1}},{text{ where }}j_{1}<j_{2}<cdots <j_{d-1}}

と表せる。α1,…,αd−1{displaystyle alpha ^{1},ldots ,alpha ^{d-1}} は g(x){displaystyle g(x)} の根なので、p(x){displaystyle p(x)} にとっても根である。したがって b1,…,bd−1{displaystyle b_{1},ldots ,b_{d-1}} は i=1,…,d−1{displaystyle i=1,ldots ,d-1} について以下の式も満たす。

p(αi)=b1αij1+b2αij2+⋯+bd−1αijd−1=0{displaystyle p(alpha ^{i})=b_{1}alpha ^{ij_{1}}+b_{2}alpha ^{ij_{2}}+cdots +b_{d-1}alpha ^{ij_{d-1}}=0}

この式を αij1{displaystyle alpha ^{ij_{1}}} で割り、kl=jl−j1{displaystyle k_{l}=j_{l}-j_{1}} と記述すると、全ての i{displaystyle i} について

b1+b2αik2+⋯+bd−1αikd−1=0{displaystyle b_{1}+b_{2}alpha ^{ik_{2}}+cdots +b_{d-1}alpha ^{ik_{d-1}}=0}

という式が得られ、これと等価的に次が得られる。

[1αk2⋯αkd−11α2k2⋯α2kd−1⋮⋮⋮1α(d−1)k2⋯α(d−1)kd−1][b1b2⋮bd−1]=[00⋮0]{displaystyle {begin{bmatrix}1&alpha ^{k_{2}}&cdots &alpha ^{k_{d-1}}\1&alpha ^{2k_{2}}&cdots &alpha ^{2k_{d-1}}\vdots &vdots &&vdots \1&alpha ^{(d-1)k_{2}}&cdots &alpha ^{(d-1)k_{d-1}}\end{bmatrix}}{begin{bmatrix}b_{1}\b_{2}\vdots \b_{d-1}end{bmatrix}}={begin{bmatrix}0\0\vdots \0end{bmatrix}}}

この行列はヴァンデルモンド行列であり、その行列式は

det(V)=∏1≤i<j≤d−1(αkj−αki){displaystyle det(V)=prod _{1leq i<jleq d-1}(alpha ^{k_{j}}-alpha ^{k_{i}})}

となって、その値はゼロではない。したがって b1,…,bd−1=0{displaystyle b_{1},ldots ,b_{d-1}=0} となり、p(x)=0{displaystyle p(x)=0} となる。

BCH符号は巡回符号である。長さ n{displaystyle n} の多項式符号が巡回符号となるのは、生成多項式で xn−1{displaystyle x^{n}-1} を割り切れる場合のみである。g(x){displaystyle g(x)} は αc,…,αc+d−2{displaystyle alpha ^{c},ldots ,alpha ^{c+d-2}} を根とする原始多項式なので、αc,…,αc+d−2{displaystyle alpha ^{c},ldots ,alpha ^{c+d-2}} のそれぞれが xn−1{displaystyle x^{n}-1} の根であることを示せばよい。α{displaystyle alpha } は定義上1のn{displaystyle n}乗根なので、簡単に証明できる。

特殊ケース

• 
  c=1{displaystyle c=1} のBCH符号を「狭義BCH符号（narrow-sense BCH code）」と呼ぶ。


• 
  n=qm−1{displaystyle n=q^{m}-1} のBCH符号を「原始BCH符号（primitive BCH code）」と呼ぶ。

従って、本項目で単純化したBCH符号として解説したものは、原始・狭義BCH符号である。

• 
  n=q−1{displaystyle n=q-1} の狭義BCH符号をリード・ソロモン符号と呼ぶ。

復号

BCH符号の復号は、次の4段階で行われる。

1. 受信したベクトル R について 2t シンドローム値を計算する。


2. 誤り位置多項式を計算する。


3. その多項式の根を計算し、誤り位置を把握する。


4. 2元BCH符号でない場合、それらの誤り位置での誤りの値を計算する。

よく使われる復号アルゴリズムとしては、Peterson Gorenstein Zierler（PGZ）アルゴリズムと Berlekamp-Massy アルゴリズムがある。

PGZアルゴリズム

このアルゴリズムは上述の工程の第2段階、すなわち誤り位置多項式の計算を行う。誤り位置多項式（error locator polynomial）の係数をλ1,λ2,…,λt{displaystyle lambda _{1},lambda _{2},dots ,lambda _{t}} とすると、誤り位置多項式は Λ(x)=1+λ1x+λ2x2+⋯+λtxt{displaystyle Lambda (x)=1+lambda _{1}x+lambda _{2}x^{2}+cdots +lambda _{t}x^{t}} となる。

[t=dmin−12]{displaystyle [t={frac {d_{min}-1}{2}}]} 個の誤りを訂正できるよう設計された (n,k,dmin){displaystyle (n,k,d_{min})} BCH符号に対して、PGZアルゴリズムは次のように実施される。

• まず、2t{displaystyle 2t} シンドロームの行列を生成する。


• 次に、下記のようにシンドローム値を配置した St×t{displaystyle S_{ttimes t}} 行列を生成する。

St×t=[s1s2s3…sts2s3s4…st+1s3s4s5…st+2……………stst+1st+2…s2t−1]{displaystyle S_{ttimes t}={begin{bmatrix}s_{1}&s_{2}&s_{3}&dots &s_{t}\s_{2}&s_{3}&s_{4}&dots &s_{t+1}\s_{3}&s_{4}&s_{5}&dots &s_{t+2}\dots &dots &dots &dots &dots \s_{t}&s_{t+1}&s_{t+2}&dots &s_{2t-1}end{bmatrix}}}

• 下記のような ctx1{displaystyle c_{tx1}} 行列を生成する。

Ct×1=[st+1st+2⋮⋮s2t]{displaystyle C_{ttimes 1}={begin{bmatrix}s_{t+1}\s_{t+2}\vdots \vdots \s_{2t}end{bmatrix}}}

• 未知の多項式係数で示される Λ{displaystyle Lambda } を次のように記述する。

Λt×1=[λ1λ2λ3λ4⋮λt]{displaystyle Lambda _{ttimes 1}={begin{bmatrix}lambda _{1}\lambda _{2}\lambda _{3}\lambda _{4}\vdots \lambda _{t}end{bmatrix}}}

• 次の行列方程式を構成する。

St×tΛt×1=Ct×1{displaystyle S_{ttimes t}Lambda _{ttimes 1}=C_{ttimes 1,}}

• 行列St×t{displaystyle S_{ttimes t}}の行列式が存在する場合、行列の逆を見つけ、Λ{displaystyle Lambda } の値を求めることができる。


• 
  det(St×t)=0{displaystyle det(S_{ttimes t})=0} の場合、次の手順を実施する。

       if t=0{displaystyle t=0}

       then

             空の誤り位置多項式を宣言する。

             完了。

       end

       set t←t−1{displaystyle tleftarrow t-1}

       PGZアルゴリズムの先頭に戻る。

• 
  Λ{displaystyle Lambda } の値が定まると、誤り位置多項式が得られる。


• PGZアルゴリズムの完了。

誤り位置多項式の因数分解

Λ(x){displaystyle Lambda (x)} 多項式が得られると、チェンサーチのアルゴリズムを使って Λ(x)=(αix+1)(αjx+1)⋯(αkx+1){displaystyle Lambda (x)=(alpha ^{i}x+1)(alpha ^{j}x+1)cdots (alpha ^{k}x+1)} の根を求めることができる。α{displaystyle alpha } の次数が受信した符号語の誤り発生位置に対応する。そのため、誤り位置多項式と呼ばれている。

誤り訂正

2元BCH符号では、上述の誤り位置多項式を解くことで誤り位置がわかり、そのビット位置を反転させればよい。

脚注

1. 
   ^ Page 189, Reed, Irving, S.. Error-Control Coding for Data Networks. Kiuwer Academic Publishers. ISBN 0-7923-8528-4. 
   


2. 
   ^ Federal Standard 1037C, 1996.
   

参考文献

• S. Lin and D. Costello. Error Control Coding: Fundamentals and Applications. Prentice-Hall, Englewood Cliffs, NJ, 2004.


• W.J. Gilbert and W.K. Nicholson. Modern Algebra with Applications, 2nd edition. Wiley, 2004.


• R. Lidl and G. Pilz. Applied Abstract Algebra, 2nd edition. Wiley, 1999.

This page is only for reference, If you need detailed information, please check here