巡回符号

CRCの検査と能力
受信した符号をG(x)で割り、余りが0なら誤りなしと判断します。
生成多項式G(x)で生成した巡回符号は生成多項式の次数までの連続誤りを検出できます。

巡回符号の生成
送信したい符号（kビット）の多項式をP(x)とします。生成多項式をG(x)とし、xⁿ+1を割り切るものとします。
　F(x) = x^n-k・P(x) + R(x)
ここで、R(x)は x^n-k・P(x)をG(x)で割った余りとします。明らかに、F(x)はn次の多項式でG(x)で割り切ることができます。

生成多項式
xⁿ+1を割り切る多項式を生成多項式といいます。
例
n=5 ：x⁵ + 1=(x⁴ + x³ + x² + x + 1)(x+1)
n=7 :x⁷ + 1=(x³ + x² + 1)(x³ + x + 1)(x+1)

例
　　　　　　　　　　　　x2 + 1
　　　　　　　　　　　--------------------
x4 + x3 + x2 + 1 | x6 + x5 + x3 + 1
　　　　　　　　　　　　x6 + x5 + x4 + x2
　　　　　　　　　　　--------------------
　　　　　　　　　　　　　x4 + x3 + x2 + 1
　　　　　　　　　　　　　x4 + x3 + x2 + 1
　　　　　　　　　　　-------------------
　　　　　　　　　　　　　　　　　　　　　　　0

符号多項式
符号語に対し、次のように多項式を対応させます。
1001011.　1+x³+x⁵+x⁶　
多項式は、それ以下の次数の多項式で割り算することができます。

CRC16
実際に利用されている生成多項式を以下に示します（CCITT X25)。
　x¹⁶ + x¹² + x⁵ + 1

巡回符号
巡回符号は連続した誤りを検出可能で、チェック方法も簡単な符号です。

巡回符号
　生成多項式G(x)で割り切ることができる符号多項式を符号語とする符号を巡回（CRC）符号と呼びます。
　ある符号多項式をF(x)とすると、xF（x)もG(x)で割り切れるため、符号語になります。xF（x)は係数を一つシフトした符号ですから、巡回符号と呼びます。