巡回符号
このようにして、巡回符号は単純な多項式同士の積で表すことができるが、この場合 C(x)は必ずしも組織符号(符号語の前半部分の係数が I(x) の係数と一致する符号)であるとは限らない。そこで一般には以下のような方法で符号化される。まず情報多項式 I(x) と x との積を求める。この式を 生成多項式 G(x)で割った商を Q(x)、余りを R(x) と置けば、
I ( x ) × x n − m = Q ( x ) × G ( x ) + R ( x ) {\displaystyle I(x)\times x^{n-m}=Q(x)\times G(x)+R(x)}
で表すことが出来る。よって
C ( x ) = Q ( x ) × G ( x ) = I ( x ) × x n − m + R ( x ) {\displaystyle C(x)=Q(x)\times G(x)=I(x)\times x^{n-m}+R(x)}
とすることで、I(x) の組織符号となる巡回符号を定義することが出来る。
巡回符号の最大の利点は、単純なシフトレジスタ回路を用いて符号化が可能な事である。例えばハミング符号では符号語は情報ベクトルと生成行列の積で表されるが、この場合は符号長が長くなるにつれ回路の規模が加速度的に大きくなる。それに対し、上記の組織符号を満たす巡回符号の場合はI(x) × x(これは実際には I(x) をシフトするだけである)を G(x) で割った余りを求める除算回路を1つ用意し、その結果を I(x) の後ろに添付するだけで実装することができる。
BCH符号は m次の原始多項式を1つ選び、その根を αとし、α を根とする多項式の内、最小の次数を持つものを Mi(x) で表したとき、 t個の誤りを訂正する生成多項式を
G ( x ) = L C M ( M l 0 ( x ) , M l 0 + 1 ( x ) , ... , M l 0 + 2 t − 2 ( x ) ) {\displaystyle G(x)=LCM\left(M_{l_{0}}(x),M_{l_{0}+1}(x),\dots ,M_{l_{0}+2t-2}(x)\right)}
で表す巡回符号である。ここで LCMは 最小公倍多項式を意味する。すなわち G(x) は Ml0(x) 〜 Ml0 + 2t - 2(x) で割り切れる最小の次数をもつ多項式である。
リード・ソロモン符号は生成多項式だけでなく多項式の係数にも拡張ガロア体を用いた特殊な BCH符号であるため、やはり巡回符号の一種である。同様にαを用いて tシンボルの誤りを訂正する生成多項式は以下のようになる。
G ( x ) = ∏ i = b 2 t − 1 + b ( x − α i ) {\displaystyle G(x)=\prod _{i=b}^{2t-1+b}(x-\alpha ^{i})}