CRC の計算

ランダムに生成された数値データに対し、誤りチェックのためのCRCを計算する例題です。

CRCでは、
（１）送信すべきビット列を２進数とみなし、
（２）検査用の２進数ビット列で割り算し、
（３）最後はあまりを出す。
という手順を取ります。

相手側には、送信すべきビット列と余りを送ります。
受信側でも同じ割り算を行い、余りが一致すれば正しく受信できたことになります。
（割り算と言っても「桁借り」の無い特殊な割り算です）

多項式：２進ビット列のビットは上に行くほど桁の重みが大きい。
　　　　そこで、重みを考慮した多項式表示（足し算の形）で表現します。

（例）１０１１１００１１１００１０１１ (16bit)
　　　最上位は2^15、最下位は2^0=1です。
　　　
　　　すると上のビット列は
　　　x^15 + x^13 + x^12 + x^11 + x^8 + x^7 + x^6 + x^3 + x + 1 (x=2)
　　　で表せます。

これが（送信すべきビット列の）多項式です。

生成多項式：検査用のビット列（割る数）も同じように多項式の形で表します。
　　　　　　（余りを生成するもとの式という意味で）生成多項式と呼びます。

例題では、多項式を用い直接計算する方式と（calculateCRC16）と、余剰テーブルを用いて高速化を図った方式（calculateCRC16t/calculateCRC32t）の２種類の計算を行っていますが、それぞれの結果は同じです。
配列のサイズが大きくなると計算量も大きくなるため、このような工夫が取られています。
また、検査用ビット数を16/32ビットとした計算の２種類用意しています。

生成された配列にCRCを付与した配列に対し、再度CRCを計算（CRCデータも含め）するとCRCが0になることを確認することにより、CRCの計算結果が正しいことが確認できます。

CRCを配列に格納する場合のバイトオーダーは、ビッグエンディアンで格納する必要があります。
ネットワークでやり取りされるデータは、通常ビッグエンディアンになりますので、ホスト内のバイトオーダーとは異なる点に注意が必要です。
例題では、htons/htonl 関数により、16/32 ビットのデータをビッグエンディアンに変更し格納しています。

ソース等をまとめたもの：DL

crc.h

crc.cpp

crcTest.cpp

実行結果