BCH符号
この式を α i j 1 {\displaystyle \alpha ^{ij_{1}}} で割り、 k l = j l − j 1 {\displaystyle k_{l}=j_{l}-j_{1}} と記述すると、全ての i {\displaystyle i} について
b 1 + b 2 α i k 2 + ⋯ + b d − 1 α i k d − 1 = 0 {\displaystyle b_{1}+b_{2}\alpha ^{ik_{2}}+\cdots +b_{d-1}\alpha ^{ik_{d-1}}=0}
という式が得られ、これと等価的に次が得られる。
[ 1 α k 2 ⋯ α k d − 1 1 α 2 k 2 ⋯ α 2 k d − 1 ⋮ ⋮ ⋮ 1 α ( d − 1 ) k 2 ⋯ α ( d − 1 ) k d − 1 ] [ b 1 b 2 ⋮ b d − 1 ] = [ 0 0 ⋮ 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 \\0\end{bmatrix}}}
BCH符号の生成多項式の次数は最大で ( d − 1 ) m {\displaystyle (d-1)m} である。さらに q = 2 {\displaystyle q=2} かつ c = 1 {\displaystyle c=1} の場合、生成多項式の次数は最大で d m / 2 {\displaystyle dm/2} である。
証明: 各原始多項式 m i ( 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} について m i ( x ) = m 2 i ( x ) {\displaystyle m_{i}(x)=m_{2i}(x)} となる。したがって g ( x ) {\displaystyle g(x)} は、奇数インデックス i {\displaystyle i} の原始多項式 m i ( x ) {\displaystyle m_{i}(x)} (最大でも d / 2 {\displaystyle d/2} 個)の最小公倍数であり、それぞれの多項式の次数は最大でも m {\displaystyle m} である。
BCH符号の最小ハミング距離は最小で d {\displaystyle d} である。単純化した例で証明を示すが、一般の場合も同様に証明できる。
c = 1 {\displaystyle c=1} のBCH符号を「狭義BCH符号(narrow-sense BCH code)」と呼ぶ。
n = q m − 1 {\displaystyle n=q^{m}-1} のBCH符号を「原始BCH符号(primitive BCH code)」と呼ぶ。
従って、本項目で単純化したBCH符号として解説したものは、原始・狭義BCH符号である。
n = q − 1 {\displaystyle n=q-1} の狭義BCH符号をリード・ソロモン符号と呼ぶ。
d = 4 , 5 {\displaystyle d=4,5} の場合のBCH符号の生成多項式は次のようになる。
d ( x ) = l c m ( 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 {\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 ) = l c m ( 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 {\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+1\end{aligned}}}
さらに定めるべきは、その符号の生成多項式である。
G F ( q m ) {\displaystyle GF(q^{m})} の1のn乗根を α {\displaystyle \alpha } とする。全ての i {\displaystyle i} について α i {\displaystyle \alpha ^{i}} の G F ( q ) {\displaystyle GF(q)} 上の原始多項式を m i ( x ) {\displaystyle m_{i}(x)} とする。BCH符号の生成多項式は最小公倍数 g ( x ) = l c m ( m 1 ( x ) , ... , m d − 1 ( x ) ) {\displaystyle g(x)={\rm {lcm}}(m_{1}(x),\ldots ,m_{d-1}(x))} で定義される。