BCH符号は、有限体上の特定の生成多項式を使った多項式符号である。また、同時に巡回符号でもある。
単純化したBCH符号
編集
まず説明を簡単にするため、特殊なBCH符号を例とする。一般のBCH符号は次節で説明する。
有限体 ( は素数冪)を定める。そして、 および となるように正の整数 , , を定める。これらから、 上で符号語長 、最小ハミング距離 以上の多項式符号を構築する。さらに定めるべきは、その符号の生成多項式である。
の1のn乗根を とする。全ての について の 上の原始多項式を とする。BCH符号の生成多項式は最小公倍数 で定義される。
、 とする(従って n = 15 )。 についてはいくつかの値を検討する。まず、
- (1);
を満たす1の冪根 が存在し、 上の原始多項式は
-
である。なお、 においては が成り立つので、 となる。従って は の根であり、
-
となる。 を求めるため、(1)を繰り返し適用して以下の線型関係式を得る。
-
-
-
-
-
これらの右辺は線型従属でなければならず、そこから線型従属式 が得られる。これには少なからぬ従属性があるので、 の原始多項式は
-
となる。同様の考え方で、以下のような式が得られる。
-
-
-
-
の場合のBCH符号の生成多項式は次のようになる。
-
この場合の最小ハミング距離は3で、最大1つの誤りを訂正できる。生成多項式の次数が4なので、この符号はデータビットが11ビット、チェックサムビットが4ビットとなる。
の場合のBCH符号の生成多項式は次のようになる。
-
この場合の最小ハミング距離は5で、最大2つの誤りを訂正できる。生成多項式の次数が8なので、この符号はデータビットが7ビット、チェックサムビットが8ビットとなる。
の場合のBCH符号の生成多項式は次のようになる。
-
最小ハミング距離は7で、3つまでの誤りを訂正できる。符号のデータビットは5ビット、チェックサムビットは10ビットとなる。
以上のBCH符号の生成多項式は、次の通りである。
-
この符号の最小ハミング距離は15で、7つまでの誤りを訂正できる。この場合、データビットが1ビットで、チェックサムビットが14ビットになる。実際、この符号は2つの符号語(000000000000000 と 111111111111111)しか持たない。
一般のBCH符号
編集
一般のBCH符号は、上述の解説と2つの面で異なる。第一に をより一般的条件にする。第二に生成多項式の一連の根として ではなく を採用する。
有限体 ( は素数冪)を定める。そして 、 が成り立ち、 を法とする の位数が となるように、正の整数 を選択する。
前節と同様、 の1のn乗根を とし、全ての について の 上の原始多項式を とする。BCH符号の生成多項式は、最小公倍数 で定義される。
単純化した例と同様に を条件にすると、 は自動的に1となり、 を法とした の位数は自動的に となる。従って、単純化した定義は一般的定義の特殊ケースになっている。
BCH符号の生成多項式の次数は最大で である。さらに かつ の場合、生成多項式の次数は最大で である。
- 証明: 各原始多項式 の次数は最大で である。したがって、それらの の最小公倍数の次数は最大で となる。さらに の場合、全ての について となる。したがって は、奇数インデックス の原始多項式 (最大でも 個)の最小公倍数であり、それぞれの多項式の次数は最大でも である。
BCH符号の最小ハミング距離は最小で である。単純化した例で証明を示すが、一般の場合も同様に証明できる。符号語 にはゼロでない項が 個未満存在するとする。すると、
-
と表せる。 は の根なので、 にとっても根である。したがって は について以下の式も満たす。
-
この式を で割り、 と記述すると、全ての について
-
という式が得られ、これと等価的に次が得られる。
-
この行列はヴァンデルモンド行列であり、その行列式は
-
となって、その値はゼロではない。したがって となり、 となる。
BCH符号は巡回符号である。長さ の多項式符号が巡回符号となるのは、生成多項式で を割り切れる場合のみである。 は を根とする原始多項式なので、 のそれぞれが の根であることを示せばよい。 は定義上1の 乗根なので、簡単に証明できる。
特殊ケース
編集
- のBCH符号を「狭義BCH符号(narrow-sense BCH code)」と呼ぶ。
- のBCH符号を「原始BCH符号(primitive BCH code)」と呼ぶ。
従って、本項目で単純化したBCH符号として解説したものは、原始・狭義BCH符号である。
- の狭義BCH符号をリード・ソロモン符号と呼ぶ。