巡回冗長検査
CRC は、巡回符号の理論に基づいた誤り検出符号の一種である。その計算は筆算による多項式の除算に似ており、送受信するデータを、あらかじめ決めておいた特定の数で割り、その余りをチェック用の値として使う。ただし、通常の算術による計算ではなく、有限体の計算を行う(繰り上がり・繰り下がりのない算術である点が通常の算術と異なる)。除算に使う特定の数を生成多項式という。余りの長さは常に除数の長さ以下であり、除数の長さによって結果の長さを決定できる。
CRCには多数のバリエーションがあり、主に出力結果のビット幅や生成多項式に違いがある。チェック用の値が n ビットになる CRC は CRC-n と表記される。規格によって生成多項式が異なることが多く、CRC-n XXX というように表記される(主な標準CRC)。
CRCは任意の有限体を使って構築できるが、一般に使われているCRCは位数2のGF(2)を使用している。
CRCがよく使われている重要な理由として、効率が保証されている点が挙げられる。nビットCRCは通常、nビット以下の連続する誤り(バースト誤り)を検出できる。言い換えれば、nビットの範囲内に1ビットの誤りが複数存在する場合を検出できる。また、それより長いバースト誤りも 1-2 の確率で検出する。データ通信での誤りも記憶装置での誤りも、誤りは無作為に出現するわけではなくバースト性がある。そのため、CRCの性質はそれらによく合っており、単にパリティチェックを複数行うよりも便利である。
最も単純な誤り検出であるパリティビットは、最も単純なCRCと見ることもできる(除数は2ビットの 11 である)。
このような除法のような計算方法を数学的に分析することで、よりよい誤り検出が可能な除数を選択する方法がわかる。このとき、ビット列の各桁をある変数 x の多項式の係数と見なす。この係数は有限体 GF(2) の元であり、一般的な意味での数ではない。多項式と見なすことで、ビット列は環の元と見なすことができるようになる。環は大まかに言えば、数にある意味で似た元の集合であり、それに対して加算に似た操作と乗算に似た操作を作用させることができる。これらの演算は一般的な算術と同様、交換法則、結合法則、分配法則が成り立つ。環では一般的な解析的手法が使えるため、多項式に見立てることで解析が容易になる。
nビットの2値CRCの計算方法は単純である。入力ビット列を一行に並べ、CRCの除数を表す (n+1) ビットのパターンをその下に左端を合わせるように書く。以下に3ビットCRCの計算の最初の様子を示す。
除数の左端のビットの上にある入力ビットが0なら、何もせず除数を右に1ビットずらす。除数の左端のビットの上にある入力ビットが1なら、除数と入力ビットをXOR演算する(つまり、除数のビット列のうち 1 になっている部分の上にあたる入力ビットを反転させる)。そして、除数を右に1ビットずらす。これを除数が入力ビット列の右端に到達するまで繰り返す。最終状態は以下の通りである。
除数の左端ビットは毎回入力ビットを0にしていくので、最終的には除数のビット数(nビット)の範囲にだけ1のビットが残ることになる。これが除算の余りであり、同時にCRC関数の値となる(CRC仕様によっては、さらなる後処理を要求する場合がある)。