2011年3月22日火曜日

CRC の計算

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

CRCでは、
(1)送信すべきビット列を2進数とみなし、
(2)検査用の2進数ビット列で割り算し、
(3)最後はあまりを出す。
という手順を取ります。

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

多項式:2進ビット列のビットは上に行くほど桁の重みが大きい。
    そこで、重みを考慮した多項式表示(足し算の形)で表現します。
(例)1011100111001011 (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)の2種類の計算を行っていますが、それぞれの結果は同じです。
配列のサイズが大きくなると計算量も大きくなるため、このような工夫が取られています。
また、検査用ビット数を16/32ビットとした計算の2種類用意しています。

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

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

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

crc.h

crc.cpp

crcTest.cpp

実行結果

0 件のコメント:

コメントを投稿