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]。

構築

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

単純化したBCH符号

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

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

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

例

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

\alpha ^{4}+\alpha +1=0

(1);

を満たす1の冪根 $\alpha \in GF(16)$ が存在し、 $GF(2)$ 上の原始多項式は

m_{1}(x)=x^{4}+x+1

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

m_{2}(x)=m_{1}(x)=x^{4}+x+1

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

$1=0\alpha ^{3}+0\alpha ^{2}+0\alpha +1$
$\alpha ^{3}=1\alpha ^{3}+0\alpha ^{2}+0\alpha +0$
$\alpha ^{6}=1\alpha ^{3}+1\alpha ^{2}+0\alpha +0$
$\alpha ^{9}=1\alpha ^{3}+0\alpha ^{2}+1\alpha +0$
$\alpha ^{12}=1\alpha ^{3}+1\alpha ^{2}+1\alpha +1$

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

m_{3}(x)=x^{4}+x^{3}+x^{2}+x+1

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

m_{4}(x)=m_{2}(x)=x^{4}+x+1\,

m_{5}(x)=x^{2}+x+1\,

m_{6}(x)=m_{3}(x)=x^{4}+x^{3}+x^{2}+x+1\,

m_{7}(x)=x^{4}+x^{3}+1\,

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

d(x)=m_{1}(x)=x^{4}+x+1\,

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

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

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$ の場合のBCH符号の生成多項式は次のようになる。

{\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+1\end{aligned}}

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

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

{\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+1\end{aligned}}

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

一般のBCH符号

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

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

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

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

特性

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

証明: 各原始多項式

m_{i}(x)

の次数は最大で

m

である。したがって、それらの

d-1

の最小公倍数の次数は最大で

(d-1)m

となる。さらに

q=2

の場合、全ての

i

について

m_{i}(x)=m_{2i}(x)

となる。したがって

g(x)

は、奇数インデックス

i

の原始多項式

m_{i}(x)

（最大でも

d/2

個）の最小公倍数であり、それぞれの多項式の次数は最大でも

m

である。

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

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}

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

p(\alpha ^{i})=b_{1}\alpha ^{ij_{1}}+b_{2}\alpha ^{ij_{2}}+\cdots +b_{d-1}\alpha ^{ij_{d-1}}=0

この式を $\alpha ^{ij_{1}}$ で割り、 $k_{l}=j_{l}-j_{1}$ と記述すると、全ての $i$ について

b_{1}+b_{2}\alpha ^{ik_{2}}+\cdots +b_{d-1}\alpha ^{ik_{d-1}}=0

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

{\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 \\0\end{bmatrix}}

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

\det(V)=\prod _{1\leq i<j\leq d-1}(\alpha ^{k_{j}}-\alpha ^{k_{i}})

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

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

特殊ケース

$c=1$ のBCH符号を「狭義BCH符号（narrow-sense BCH code）」と呼ぶ。
$n=q^{m}-1$ のBCH符号を「原始BCH符号（primitive BCH code）」と呼ぶ。

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

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

復号

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

受信したベクトル R について 2t シンドローム値を計算する。
誤り位置多項式を計算する。
その多項式の根を計算し、誤り位置を把握する。
2元BCH符号でない場合、それらの誤り位置での誤りの値を計算する。

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

PGZアルゴリズム

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

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

まず、 $2t$ シンドロームの行列を生成する。
次に、下記のようにシンドローム値を配置した $S_{t\times t}$ 行列を生成する。

S_{t\times 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}}

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

C_{t\times 1}={\begin{bmatrix}s_{t+1}\\s_{t+2}\\\vdots \\\vdots \\s_{2t}\end{bmatrix}}

未知の多項式係数で示される $\Lambda$ を次のように記述する。

\Lambda _{t\times 1}={\begin{bmatrix}\lambda _{1}\\\lambda _{2}\\\lambda _{3}\\\lambda _{4}\\\vdots \\\lambda _{t}\end{bmatrix}}

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

S_{t\times t}\Lambda _{t\times 1}=C_{t\times 1\,}

行列 $S_{t\times t}$ の行列式が存在する場合、行列の逆を見つけ、 $\Lambda$ の値を求めることができる。
$\det(S_{t\times t})=0$ の場合、次の手順を実施する。

       if  $t=0$ 
       then
             空の誤り位置多項式を宣言する。
             完了。
       end
       set  $t\leftarrow t-1$ 
       PGZアルゴリズムの先頭に戻る。

$\Lambda$ の値が定まると、誤り位置多項式が得られる。
PGZアルゴリズムの完了。

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

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

誤り訂正

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

脚注

^ Page 189, Reed, Irving, S.. Error-Control Coding for Data Networks. Kiuwer Academic Publishers. ISBN 0-7923-8528-4
^ 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.

[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.

[1]

[2]