巡回符号

巡回符号の定義は以下の通りである。

n個のシンボルで構成されるある線形符号の符号語として (c₀ , c₁ , ... , c_n-2 , c_n-1 ) があるとする。この符号語を巡回シフトさせたもの(c_n-1 , c₀ , c₁ , ... , c_n-2 ) が、やはりその線形符号の符号語である場合、その線形符号を巡回符号という。

巡回符号は一般に符号語を符号語多項式で表す。これは例えば上記の符号語を

${\displaystyle C(x)=c_{n-1}x^{n-1}+c_{n-2}x^{n-2}+\cdots +c_{1}x+c_{0}}$

というように符号語を (n-1)次の多項式で表現する方法である。なおこの式は加算を排他的論理和で表す GF(2^n-1)の拡張ガロア体上の多項式である事に注意する。特に a + b と a - b は基本的に同じ事を意味する。

巡回符号は以下のようにして作成される。まず n > m であり、 xⁿ - 1 を割り切ることのできる m次の多項式

${\displaystyle G(x)=x^{m}+g_{m-1}x^{m-1}+\cdots +g_{1}x+g_{0}}$

を考える。このとき、(n-m-1) シンボルの情報を符号語多項式で表したものを I(x) と置いて G(x) と I(x) の積で表される n-1次の多項式

${\displaystyle C(x)=I(x)\times G(x)}$

を符号語とする。この C(x)は必ず巡回符号の定義を満たすことが知られている。これは以下のように証明できる。

まず定義より xⁿ - 1 は G(x)で割り切れるので

${\displaystyle x^{n}-1=G(x)\times P(x)}$

で表すことが出来る。今 C(x)の多項式を

${\displaystyle C(x)=c_{n-1}x^{n-1}+c_{n-2}x^{n-2}+\cdots +c_{1}x+c_{0}}$

で表すとする。このときこの多項式を巡回シフトさせた多項式 C'(x) を考えると、

${\displaystyle C'(x)=c_{n-2}x^{n-1}+c_{n-3}x^{n-2}+\cdots +c_{1}x^{2}+c_{0}x+c_{n-1}}$

で表される。この式を C(x) との関係で表すと、

${\displaystyle C'(x)=x\times C(x)+c_{n-1}-c_{n-1}x^{n}=x\times C(x)-c_{n-1}(x^{n}-1)}$

となる。 ここで C(x) = I(x) × G(x) である事と xⁿ - 1 と G(x)との関係式より上記の式は

${\displaystyle C'(x)=x\times C(x)-c_{n-1}(x^{n}-1)=(x\cdot I(x)-c_{n-1}P(x))\times G(x)}$

となり、この式も最初に定義した C(x) と同様の式で表すことが出来る。すなわちこの符号化は巡回符号であることが分かる。このときこの G(x) は生成多項式と呼ばれる。巡回符号の定義から、もとの符号語多項式を n 回巡回シフトした場合、もとの符号語多項式に戻ることは自明である。このとき元に戻るまでに n-1 個の符号語が現れることになるが、この符号語が全て相違になるような符号を生成する生成多項式を特に原始多項式と呼ぶ。

このようにして、巡回符号は単純な多項式同士の積で表すことができるが、この場合 C(x)は必ずしも組織符号（符号語の前半部分の係数が I(x) の係数と一致する符号）であるとは限らない。そこで一般には以下のような方法で符号化される。まず情報多項式 I(x) と x^n-m との積を求める。この式を 生成多項式 G(x)で割った商を Q(x)、余りを R(x) と置けば、

${\displaystyle I(x)\times x^{n-m}=Q(x)\times G(x)+R(x)}$

で表すことが出来る。よって

${\displaystyle C(x)=Q(x)\times G(x)=I(x)\times x^{n-m}+R(x)}$

とすることで、I(x) の組織符号となる巡回符号を定義することが出来る。

巡回符号の最大の利点は、単純なシフトレジスタ回路を用いて符号化が可能な事である。例えばハミング符号では符号語は情報ベクトルと生成行列の積で表されるが、この場合は符号長が長くなるにつれ回路の規模が加速度的に大きくなる。それに対し、上記の組織符号を満たす巡回符号の場合はI(x) × x^n-m（これは実際には I(x) をシフトするだけである）を G(x) で割った余りを求める除算回路を1つ用意し、その結果を I(x) の後ろに添付するだけで実装することができる。