CRC (Cyclic Redundancy Check、巡回冗長検査)は通信の誤りとかを検知するために割とよく使われている手法だと思う。
他にもそのデータの1が立っている個数を数えて奇数・偶数などから判断するパリティ検出があるが、特定の数が化けると役に立たないなどの弱点がある。
CRCも当然計算結果が同じになるような入力はあるが、パリティと比較すると条件がバラけているため、より強い誤り検出法といえると思う。
今回、なんとなくどういうものかは知っていたが、計算方法までは具体的に知らなかったので、調べてみた。
参考:
ろぐれこーど | 巡回冗長検査(CRC, Cyclic Redundancy Check)の原理と実装あるデータに対してCRCをかける場合、以下のようなものが必要です。
初期値は一番初めにデータとXORするものです。
これは、一般的に0b0000または0b1111が用いられます。
0b0000の場合は、データが破損するなどしてすべてのビットが0になった場合に出力が0となります。
これが計算による0なのか、データが破損したことによる0なのかが判別できません。
このため、0b1111の方が計算が必ず入るので優れていると言えます。
生成多項式の係数がそのデータの割る数となります。
x^4+x+1は10011と表されます。
初期値: 0b1111
生成多項式: x^4+x+1 (0b10011)
データ: 0b00100011
の時の計算は以下のようになります。
一般に、CRCの計算結果の桁数だけデータの後ろ側をゼロ埋めします。
これは、データの値が割る数よりも小さい場合、データがそのまま出てくるのを防ぐ役割があります。
また、答え(XORをしていった後の余り)は常に割る数よりも1桁以上小さい数になります。
ここは、割り算の余りと同じ考えでOKだと思います。
次に、CRCを連続して行うケースを考えます。
先ほどの0b00100011のデータの次に0b10101000というデータが来たとします。
通信品質が特に問題になるケースでは、このように連続してCRCをかけ、そのCRCの答えが次のCRCのシード値になることがあります。
計算は以下のようになります。
この場合では、1度目の計算結果は0b1001であり、2度目の計算結果は0b0100となります。
こんな感じで、手計算については問題なく計算ができるようになりました。
実際は4桁のCRCではなく、もっと大きい桁の16桁や32桁の答えが出てくるようなCRCを行うケースが多くあると思われます。
よく使われるCRCのお話でした。
