巡回符号
ハミング符号は必ずしも巡回符号ではないが、ある種のハミング符号は巡回符号の定義を満たすことが知られている。この符号のことを特に 巡回ハミング符号 と呼ぶ。巡回ハミング符号の生成行列を生成多項式で表した場合、 G(x) は m次の原始多項式であることが知られている。
巡回符号の定義は以下の通りである。
n個のシンボルで構成されるある線形符号の符号語として (c0 , c1 , ... , cn-2 , cn-1 ) があるとする。この符号語を巡回シフトさせたもの(cn-1 , c0 , c1 , ... , cn-2 ) が、やはりその線形符号の符号語である場合、その線形符号を巡回符号という。
巡回符号は一般に符号語を符号語多項式で表す。これは例えば上記の符号語を
C ( x ) = c n − 1 x n − 1 + c n − 2 x n − 2 + ⋯ + c 1 x + c 0 {\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)の拡張ガロア体上の多項式である事に注意する。特に a + b と a - b は基本的に同じ事を意味する。
巡回符号は以下のようにして作成される。まず n > m であり、 x - 1 を割り切ることのできる m次の多項式
G ( x ) = x m + g m − 1 x m − 1 + ⋯ + g 1 x + g 0 {\displaystyle G(x)=x^{m}+g_{m-1}x^{m-1}+\cdots +g_{1}x+g_{0}}
を考える。