CRC

用途に応じて、様々ある。一般的なものに、次のようなものがある。

• CRC-6
• CRC-8
• CRC-12
• CRC-16
• CRC-32
• CRC-CCITT

このうち、17ビットの定数を用いて16ビットのCRCを求めるCRC-CCITT、CRC-16と、33ビットの定数を用いて32ビットのCRCを求めるCRC-32がよく使われる。この定数は多項式と呼ばれる。

多項式は様々な誤りに対し正常時と異なる値を算出できるものが求められ、次のような値が主に利用されている。

CRC-6

1100001 (x⁶+x⁵+x⁰)

CRC-8

100000111 (x⁸+x²+x¹+x⁰)

CRC-12

1100000001111 (x¹²+x¹¹+x³+x²+x¹+x⁰)

CRC-16

11000000000000101 (x¹⁶+x¹⁵+x²+x⁰)

CRC-CCITT

10001000000100001 (x¹⁶+x¹²+x⁵+x⁰)

CRC-32

100000100110000010001110110110111 (x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x¹+x⁰)

大雑把な計算方法は、次のとおり。16ビットCRCを、アセンブラで処理すると仮定し、16ビットのCRCを計算するとする。メモリから1バイト(8ビットとする)を随時読み計算する方法を述べる。

1. CRC格納レジスタを0クリア
2. 計算するメモリ長ループ
   1. データを1バイト読む
   2. 8回ループ
      1. データを1ビット左シフト (桁溢れ分はキャリーフラグ)
      2. CRC格納レジスタを1ビット左ローテート (LSBには上のキャリーフラグを代入)
      3. 16ビットから桁溢れしたら、CRC格納レジスタを多項式でXORする。
3. 完成

CやC++で計算しやすいように、CRC格納レジスタが32ビットと仮定し、このレジスタ一つで全ての演算をする例を紹介する。それ以外の条件は上と同じ。

CRC格納レジスタの構成は、[8ビット桁溢れ分][16ビットCRC][8ビットのデータ]、となっている。

1. CRC格納レジスタを0クリア
2. 計算するメモリ長ループ
   1. データを1バイト読む
   2. CRC格納レジスタにOR代入
   3. 8回ループ
      1. CRC格納レジスタを1ビット左シフト
      2. 16ビットから桁溢れしたら(ビット24をチェックする)、CRC格納レジスタを多項式(256倍したもの)でXORする。
3. CRC格納レジスタを右に8ビットシフトし、下位16ビットを取り出す。
4. 完成