巡回冗長符号。誤り検出のための符号。

データを特定の定数で割り算し、その剰余を検査用の数値として用いる。単純なチェックサムで誤り検出を行なうよりも確実性があるため、厳密性を必要とする場面でよく使われる。

目次 CRCの種類 ビット幅 多項式 計算方法 一般的なスタイル 32ビット一括スタイル

CRCの種類

大きく、データの幅(ビット数)と多項式によって分類される。

ビット幅

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

• CRC-4
• CRC-5
• CRC-6
• CRC-7
• CRC-8
• CRC-11
• CRC-12
• CRC-16
• CRC-32
• CRC-64

このうち、17ビットの定数を用いて16ビットのCRCを求めるのがCRC-16、33ビットの定数を用いて32ビットのCRCを求めるCRC-32がよく使われる。

この定数は多項式と呼ばれ、多項式の違いにより、CRC-16やCRC-32には様々な種類が存在する。

多項式

多項式は様々な誤りに対し正常時と異なる値を算出できるものが求められる。

多項式は、規約性を持つ、すなわち素数である場合に、誤り検出能力が高い。そして、用いる多項式により誤り検出性能にも差が生じる。同じCRC-32でも、V.42やMPEG-2、zlib(zlibを用いるPNGなども含む)などで広く使われているCRC-32よりも、Intel SSE4.2のCRC32C命令で対応するCastagnoli CRCの方が検出性能が勝るとされている。

実際に様々な多項式が使われており統一はないが、次のような値が主に利用されている。

CRC-4 (ITU-T G.704/G.706)

10011 (x⁴+x¹+x⁰)

CRC-5 (USBトークンパケット)

100101 (x⁵+x²+x⁰)

CRC-5 (ITU G.704/G.706)

110101 (x⁵+x⁴+x²+x⁰)

CRC-6

1100001 (x⁶+x⁵+x⁰)

CRC-7

10001001 (x⁷+x³+x⁰)

CRC-8

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

CRC-11 (FlexRayのヘッダーCRC)

101110000101 (x¹¹+x⁹+x⁸+x⁷+x²+x⁰)

CRC-12

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

CRC-16 (SDLC、USB)

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

CRC-16/CRC-CCITT (X.25、PPP、IrDA、Bluetooth、XMODEM 128/CRC、XMODEM 1024/CRC、HDLC)

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

CRC-32 (V.42 、MPEG-2、zlib)

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

CRC-32 (Intel SSE4.2、Castagnoli CRC)

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

CRC-64 (ISO 3309、HDLC)

10000000000000000000000000000000000000000000000000000000000011011 (x⁶⁴+x⁴+x³+x¹+x⁰)

CRC-64 (ECMA-182、ISO/IEC 13421)

10100001011110000111000011110101110101001111010100011011010010011 (x⁶⁴+x⁶²+x⁵⁷+x⁵⁵+x⁵⁴+x⁵³+x⁵²+x⁴⁷+x⁴⁶+x⁴⁵+x⁴⁰+x³⁹+x³⁸+x³⁷+x³⁵+x³³+x³²+x³¹+x²⁹+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. 完成

32ビット一括スタイル

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. 完成

リンク

関連する用語
パリティ
チェックサム
ベリファイ

[再検索] [戻る]