CRC
読み：スィーアースィー
外語：CRC: Cyclic Redundancy Checking
巡回冗長符号。誤り検出のための符号。
データ
を特定の
定数
で割り算し、その
剰余
を検査用の数値として用いる。単純な
チェックサム
で誤り検出を行なうよりも確実性があるため、厳密性を必要とする場面でよく使われる。
目次
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
4
+x
1
+x
0
)
CRC-5 (USBトークンパケット)
100101 (x
5
+x
2
+x
0
)
CRC-5 (ITU G.704/G.706)
110101 (x
5
+x
4
+x
2
+x
0
)
CRC-6
1100001 (x
6
+x
5
+x
0
)
CRC-7
10001001 (x
7
+x
3
+x
0
)
CRC-8
100000111 (x
8
+x
2
+x
1
+x
0
)
CRC-11 (
FlexRay
のヘッダーCRC)
101110000101 (x
11
+x
9
+x
8
+x
7
+x
2
+x
0
)
CRC-12
1100000001111 (x
12
+x
11
+x
3
+x
2
+x
1
+x
0
)
CRC-16 (SDLC、USB)
11000000000000101 (x
16
+x
15
+x
2
+x
0
)
CRC-16/CRC-CCITT (
X.25
、
PPP
、
IrDA
、
Bluetooth
、
XMODEM 128/CRC
、
XMODEM 1024/CRC
、HDLC)
10001000000100001 (x
16
+x
12
+x
5
+x
0
)
CRC-32 (
V.42
、
MPEG-2
、
zlib
)
100000100110000010001110110110111 (x
32
+x
26
+x
23
+x
22
+x
16
+x
12
+x
11
+x
10
+x
8
+x
7
+x
5
+x
4
+x
2
+x
1
+x
0
)
CRC-32 (
Intel SSE4.2
、Castagnoli CRC)
100011110110111000110111101000001 (x
32
+x
28
+x
27
+x
26
+x
25
+x
23
+x
22
+x
20
+x
19
+x
18
+x
14
+x
13
+x
11
+x
10
+x
9
+x
8
+x
6
+x
0
)
CRC-64 (ISO 3309、HDLC)
10000000000000000000000000000000000000000000000000000000000011011 (x
64
+x
4
+x
3
+x
1
+x
0
)
CRC-64 (ECMA-182、ISO/IEC 13421)
10100001011110000111000011110101110101001111010100011011010010011 (x
64
+x
62
+x
57
+x
55
+x
54
+x
53
+x
52
+x
47
+x
46
+x
45
+x
40
+x
39
+x
38
+x
37
+x
35
+x
33
+x
32
+x
31
+x
29
+x
27
+x
24
+x
23
+x
22
+x
21
+x
19
+x
17
+x
13
+x
12
+x
10
+x
9
+x
7
+x
4
+x
1
+x
0
)
計算方法
一般的なスタイル
大雑把な計算方法は、次のとおり。16ビットCRCを、
アセンブラー
で処理すると仮定し、16ビットのCRCを計算するとする。メモリーから1バイト(8ビットとする)を随時読み計算する方法を述べる。
CRC格納レジスターを0クリア
計算するメモリー長ループ
データを1バイト読む
8回ループ
データを1ビット左シフト (桁溢れ分は
キャリーフラグ
)
CRC格納レジスターを1ビット左ローテート (LSBには上のキャリーフラグを代入)
16ビットから桁溢れしたら、CRC格納レジスターを多項式でXORする。
完成
32ビット一括スタイル
CやC++で計算しやすいように、CRC格納レジスターが32ビットと仮定し、このレジスター一つで全ての演算をする例を紹介する。それ以外の条件は上と同じ。
CRC格納レジスターの構成は、[8ビット桁溢れ分][16ビットCRC][8ビットのデータ]、となっている。
CRC格納レジスターを0クリア
計算するメモリー長ループ
データを1バイト読む
CRC格納レジスターにOR代入
8回ループ
CRC格納レジスターを1ビット左シフト
16ビットから桁溢れしたら(ビット24をチェックする)、CRC格納レジスターを多項式(256倍したもの)でXORする。
CRC格納レジスターを右に8ビットシフトし、下位16ビットを取り出す。
完成
再検索