BCH符号

BCH符号（BCHふごう、）は、パラメータ化された誤り訂正符号の一種で、最もよく研究されている符号の1つである。1959年 Alexis Hocquenghem が、それとは別に1960年には Raj Chandra Bose と D. K. Ray-Chaudhuri が考案した。"BCH" とは、この3人のイニシャルである。
BCH符号は、シンドローム復号という簡潔な代数学的手法で容易に復号できる点を特徴とする。そのための電子回路は非常に単純でコンピュータを使う必要もなく、低電力で小型の機器で復号可能である。符号としても非常に柔軟性があり、ブロック長や誤り訂正能力を自由に設定でき、目的に応じてカスタマイズされた符号を設計できる。
BCH符号は、マルチレベル/巡回/誤り訂正/可変長デジタル符号であり、複数の無作為誤りパターンを訂正できる。BCH符号は、レベル数が素数または素数のべき乗であるようなマルチレベルの位相偏移変調でも使われる。11レベルのBCH符号を使って、十進数の10個の数字と符号を表す場合もある。
構築.
BCH符号は、有限体上の特定の生成多項式を使った多項式符号である。また、同時に巡回符号でもある。
単純化したBCH符号.
まず説明を簡単にするため、特殊なBCH符号を例とする。一般のBCH符号は次節で説明する。
有限体 formula_1（formula_2 は素数冪）を定める。そして、formula_3 および formula_4 となるように正の整数 formula_5, formula_6, formula_7 を定める。これらから、formula_1 上で符号語長 formula_6、最小ハミング距離 formula_7 以上の多項式符号を構築する。さらに定めるべきは、その符号の生成多項式である。
formula_11 の1のn乗根を formula_12 とする。全ての formula_13 について formula_14 の formula_1 上の原始多項式を formula_16 とする。BCH符号の生成多項式は最小公倍数 formula_17 で定義される。
例.
formula_18 、 formula_19 とする（従って n = 15 ）。 formula_7 についてはいくつかの値を検討する。まず、
を満たす1の冪根 formula_22 が存在し、formula_23 上の原始多項式は
である。なお、formula_23 においては formula_26 が成り立つので、formula_27 となる。従って formula_28 は formula_29 の根であり、
となる。formula_31 を求めるため、(1)を繰り返し適用して以下の線型関係式を得る。
これらの右辺は線型従属でなければならず、そこから線型従属式 formula_37 が得られる。これには少なからぬ従属性があるので、formula_38 の原始多項式は
となる。同様の考え方で、以下のような式が得られる。
formula_44 の場合のBCH符号の生成多項式は次のようになる。
この場合の最小ハミング距離は3で、最大1つの誤りを訂正できる。生成多項式の次数が4なので、この符号はデータビットが11ビット、チェックサムビットが4ビットとなる。
formula_46 の場合のBCH符号の生成多項式は次のようになる。
この場合の最小ハミング距離は5で、最大2つの誤りを訂正できる。生成多項式の次数が8なので、この符号はデータビットが7ビット、チェックサムビットが8ビットとなる。
formula_48 の場合のBCH符号の生成多項式は次のようになる。
最小ハミング距離は7で、3つまでの誤りを訂正できる。符号のデータビットは5ビット、チェックサムビットは10ビットとなる。
formula_50 以上のBCH符号の生成多項式は、次の通りである。
この符号の最小ハミング距離は15で、7つまでの誤りを訂正できる。この場合、データビットが1ビットで、チェックサムビットが14ビットになる。実際、この符号は2つの符号語（000000000000000 と 111111111111111）しか持たない。
一般のBCH符号.
一般のBCH符号は、上述の解説と2つの面で異なる。第一に formula_3 をより一般的条件にする。第二に生成多項式の一連の根として formula_53 ではなく formula_54 を採用する。
有限体 formula_1（formula_2 は素数冪）を定める。そして formula_57、formula_58 が成り立ち、 formula_6 を法とする formula_2 の位数が formula_5 となるように、正の整数 formula_62 を選択する。
前節と同様、formula_11 の1のn乗根を formula_12 とし、全ての formula_13 について formula_14 の formula_1 上の原始多項式を formula_16 とする。BCH符号の生成多項式は、最小公倍数 formula_69 で定義される。
単純化した例と同様に formula_3 を条件にすると、formula_71 は自動的に1となり、formula_6 を法とした formula_2 の位数は自動的に formula_5 となる。従って、単純化した定義は一般的定義の特殊ケースになっている。
特性.
BCH符号の生成多項式の次数は最大で formula_75 である。さらに formula_76 かつ formula_77 の場合、生成多項式の次数は最大で formula_78 である。
BCH符号の最小ハミング距離は最小で formula_7 である。単純化した例で証明を示すが、一般の場合も同様に証明できる。符号語 formula_92 にはゼロでない項が formula_7 個未満存在するとする。すると、
と表せる。formula_95 は formula_86 の根なので、formula_92 にとっても根である。したがって formula_98 は formula_99 について以下の式も満たす。
この式を formula_101 で割り、formula_102 と記述すると、全ての formula_13 について
という式が得られ、これと等価的に次が得られる。
この行列はヴァンデルモンド行列であり、その行列式は
となって、その値はゼロではない。したがって formula_107 となり、formula_108 となる。
BCH符号は巡回符号である。長さ formula_6 の多項式符号が巡回符号となるのは、生成多項式で formula_110 を割り切れる場合のみである。formula_86 は formula_54 を根とする原始多項式なので、formula_54 のそれぞれが formula_110 の根であることを示せばよい。formula_12 は定義上1のformula_6乗根なので、簡単に証明できる。
特殊ケース.
従って、本項目で単純化したBCH符号として解説したものは、原始・狭義BCH符号である。
復号.
BCH符号の復号は、次の4段階で行われる。
よく使われる復号アルゴリズムとしては、Peterson Gorenstein Zierler（PGZ）アルゴリズムと Berlekamp-Massy アルゴリズムがある。
PGZアルゴリズム.
このアルゴリズムは上述の工程の第2段階、すなわち誤り位置多項式の計算を行う。誤り位置多項式（error locator polynomial）の係数をformula_120 とすると、誤り位置多項式は formula_121 となる。
formula_122 個の誤りを訂正できるよう設計された formula_123 BCH符号に対して、PGZアルゴリズムは次のように実施される。
 if formula_135
 then
 空の誤り位置多項式を宣言する。
 完了。
 end
 set formula_136
 PGZアルゴリズムの先頭に戻る。
誤り位置多項式の因数分解.
formula_138 多項式が得られると、チェンサーチのアルゴリズムを使って formula_139 の根を求めることができる。formula_12 の次数が受信した符号語の誤り発生位置に対応する。そのため、誤り位置多項式と呼ばれている。
誤り訂正.
2元BCH符号では、上述の誤り位置多項式を解くことで誤り位置がわかり、そのビット位置を反転させればよい。