BCH符号のソースを表示

'''BCH符号'''（BCHふごう、{{lang-en-short|BCH code}}）は、パラメータ化された[[誤り検出訂正|誤り訂正符号]]の一種で、最もよく研究されている符号の1つである。1959年 {{仮リンク|Alexis Hocquenghem|en|Alexis Hocquenghem}} が、それとは別に1960年には {{仮リンク|Raj Chandra Bose|en|Raj Chandra Bose}} と {{仮リンク|D. K. Ray-Chaudhuri|en|Dijen K. Ray-Chaudhuri}} が考案した<ref>Page 189, {{cite book | last = Reed | first = Irving, S. | title = Error-Control Coding for Data Networks | publisher = Kiuwer Academic Publishers | isbn = 0-7923-8528-4 }}</ref>。''BCH'' とは、この3人のイニシャルである。

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

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

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

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

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

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

==== 例 ====
<math>q = 2</math> 、 <math>m = 4</math> とする（従って n = 15 ）。 <math>d</math> についてはいくつかの値を検討する。まず、
:<math>\alpha^4+\alpha+1=0</math> (1);

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

:<math>m_1(x) = x^4+x+1</math>

である。なお、<math>GF(2)</math> においては <math>(a+b)^2 = a^2 + 2ab + b^2 = a^2 + b^2</math> が成り立つので、<math>m_1(\alpha^2) = m_1(\alpha)^2 = 0</math> となる。従って <math>\alpha^2</math> は <math>m_1(x)</math> の根であり、

:<math>m_2(x) = m_1(x) = x^4+x+1</math>

となる。<math>m_3(x)</math> を求めるため、(1)を繰り返し適用して以下の線型関係式を得る。
* <math>1 = 0\alpha^3 + 0\alpha^2 + 0\alpha + 1</math>
* <math>\alpha^3 = 1\alpha^3 + 0\alpha^2 + 0\alpha + 0</math>
* <math>\alpha^6 = 1\alpha^3 + 1\alpha^2 + 0\alpha + 0</math>
* <math>\alpha^9 = 1\alpha^3 + 0\alpha^2 + 1\alpha + 0</math>
* <math>\alpha^{12} = 1\alpha^3 + 1\alpha^2 + 1\alpha + 1</math>

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

:<math>m_3(x) = x^4+x^3+x^2+x+1</math>

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

:<math>m_4(x) = m_2(x) = x^4+x+1\,</math>
:<math>m_5(x) = x^2+x+1\,</math>
:<math>m_6(x) = m_3(x) = x^4+x^3+x^2+x+1\,</math>
:<math>m_7(x) = x^4+x^3+1\,</math>

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

:<math>d(x) = m_1(x) = x^4+x+1\,</math>

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

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

:<math>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\,</math>

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

<math>d=6,7</math> の場合のBCH符号の生成多項式は次のようになる。

:<math>
\begin{align}
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{align}
</math>

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

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

:<math>
\begin{align}
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{align}
</math>

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

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

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

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

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

=== 特性 ===
BCH符号の生成多項式の次数は最大で <math>(d-1)m</math> である。さらに <math>q=2</math> かつ <math>c=1</math> の場合、生成多項式の次数は最大で <math>dm/2</math> である。
:証明: 各原始多項式 <math>m_i(x)</math> の次数は最大で <math>m</math> である。したがって、それらの <math>d-1</math> の最小公倍数の次数は最大で <math>(d-1)m</math> となる。さらに <math>q=2</math> の場合、全ての <math>i</math> について <math>m_i(x) = m_{2i}(x)</math> となる。したがって <math>g(x)</math> は、奇数インデックス <math>i</math> の原始多項式 <math>m_i(x)</math>（最大でも <math>d/2</math> 個）の最小公倍数であり、それぞれの多項式の次数は最大でも <math>m</math> である。

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

:<math>p(x) = b_1x^{j_1} + \cdots + b_{d-1}x^{j_{d-1}},\text{ where }j_1<j_2<\cdots<j_{d-1}</math> 

と表せる。<math>\alpha^1,\ldots,\alpha^{d-1}</math> は <math>g(x)</math> の根なので、<math>p(x)</math> にとっても根である。したがって <math>b_1,\ldots,b_{d-1}</math> は <math>i=1,\ldots,d-1</math> について以下の式も満たす。
:<math>p(\alpha^i) = b_1\alpha^{ij_1} + b_2\alpha^{ij_2} + \cdots + b_{d-1}\alpha^{ij_{d-1}} = 0</math>
この式を <math>\alpha^{ij_1}</math> で割り、<math>k_l = j_l - j_1</math> と記述すると、全ての <math>i</math> について
:<math>b_1 + b_2\alpha^{ik_2} + \cdots + b_{d-1}\alpha^{ik_{d-1}} = 0</math>
という式が得られ、これと等価的に次が得られる。
:<math>\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}
</math>
この行列は[[ヴァンデルモンド行列]]であり、その行列式は
:<math>\det(V) = \prod_{1\le i<j\le d-1} (\alpha^{k_j}-\alpha^{k_i})</math>
となって、その値はゼロではない。したがって <math>b_1,\ldots,b_{d-1}=0</math> となり、<math>p(x)=0</math> となる。

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

=== 特殊ケース ===
* <math>c=1</math> のBCH符号を「狭義BCH符号（narrow-sense BCH code）」と呼ぶ。
* <math>n=q^m-1</math> のBCH符号を「原始BCH符号（primitive BCH code）」と呼ぶ。

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

* <math>n=q-1</math> の狭義BCH符号を[[リード・ソロモン符号]]と呼ぶ。

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

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

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

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

* まず、<math>2t</math> シンドロームの行列を生成する。
* 次に、下記のようにシンドローム値を配置した <math>S_{t\times t}</math> 行列を生成する。
::<math>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}</math>
* 下記のような <math>c_{tx1}</math> 行列を生成する。
::<math>C_{t \times 1}=\begin{bmatrix}s_{t+1}\\
s_{t+2}\\
\vdots\\
\vdots\\
s_{2t}\end{bmatrix}
</math>
* 未知の多項式係数で示される <math>\Lambda</math> を次のように記述する。
::<math>\Lambda_{t \times 1} = \begin{bmatrix}\lambda_{1}\\
\lambda_{2}\\
\lambda_{3}\\
\lambda_{4}\\
\vdots\\
\lambda_{t}\end{bmatrix}
</math>
* 次の行列方程式を構成する。
::<math>S_{t \times t} \Lambda_{t \times 1}  = C_{t \times 1\,} </math>
* 行列<math>S_{t \times t}</math>の行列式が存在する場合、行列の逆を見つけ、<math>\Lambda</math> の値を求めることができる。
* <math> \det(S_{t \times t}) = 0 </math> の場合、次の手順を実施する。
        if <math>t = 0</math>
        then
              空の誤り位置多項式を宣言する。
              完了。
        end
        set <math> t \leftarrow t -1</math>
        PGZアルゴリズムの先頭に戻る。
 
* <math>\Lambda</math> の値が定まると、誤り位置多項式が得られる。
* PGZアルゴリズムの完了。

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

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

== 脚注 ==
{{Reflist}}

== 参考文献 ==
* 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.

{{DEFAULTSORT:BCHふこう}}

[[Category:誤り検出訂正]]
[[Category:数学に関する記事]]
[[Category:符号理論]]
[[Category:有限体]]