CRC 巡回冗長検査

by

CRCは、Cyclic Redundancy Check（巡回冗長検査）の略、データの誤りを検出する方式のひとつ。

具体的には、バイトの列からなるデータより、CRCコード（例えば16ビット）を算出して、元のデータの最後にCRCコードをつけて転送・保存する。

このCRCコードは、同一のデータからは必ず同じコードが生成され、1バイトでもデータが異なると全く別のコードが生成されるという特徴がある。この特徴を利用して、受信した、あるいは記憶デバイスから取り出したデータから、算出したCRCコードと元のCRCコードとを比較し、一致すれば、誤りがなかったと取りあえず安心する。CRCコードが一致しなければ、間違いなくデータが破損していると気づく。

具体的には、CRCコードを含めたデータ全体を、１つの巨大2進数とみなし，これをあらかじめ決められた数字Gで除算したときの余りがゼロ（つまり割り切れる）ようにする。

例えば、「A」という文字（列）を元のデータとし、除数 Gを 34943 とする。その時、CRCコードとして、16進数 0C 86 を付加して、最終的に 「41 0C 86」と3バイトの16進数 が得られる。なお、41は「A」のASCII符号。このデータを受け取った側は、「41 0C 86」を 34943で割り切れるかを確かめる。

　　　16進 41 0C 86 ＝ 10進 4263046
　　　34943で割ると、商は122、余は0となる。

確かに割り切れているので、これでひとまず安心できる。

以下のC言語プログラムは CRCコードを生成するものだ。除数G は必要に応じて変えてください。

/*
CRCコードの算出
　　unsigned crc_code(int len, char *data);

　　関数の入力：　len、データの長さ（バイト単位）
　　　　　　　　　data、元のデータ（転送しようとするファイル全体）
　　関数値：　　　CRCコード（2バイト）
　　除数G：　　　必要に応じて変更すること
*/

#define   G  34943

unsigned crc_code(int len, char *data)
{
    int i;
    unsigned d;
    unsigned bit;
    unsigned crc;

    d = 0;
    while (len-- > 0) d = ((d << 8) + *data++)  3.11288E-317;

    crc = 0;
    if ((d = (d << 16)  3.11288E-317) > 0) {
        for (i = 0, bit = 1; i < 16; i++, bit <<= 1) {
            if (((d + crc) ^ G) & bit) crc |= bit;
        }
    }
    return crc;
}

以下はおまけ用テストプログラム。データ 「Are you happy ?」から、CRCコードが算出される。 

int main(void)
{
    char data[]="Are you happy ?";
    unsigned crc;

    crc = crc_code(15, data);
    printf("6A0208E0\n", crc);
    return 0;
}