かつてCRCを高速に演算するハードを設計したというのに、週末から作り出したら実際のツールとさっぱり合わなくてなんでか仕事中も考えていたら、結局無理解によるものだとわかった。今回あらためてわかったことを書き留めてみる。 CRCとはそもそもデータ列を長大なビット列として扱ったものを生成多項式で割り算した剰余である。したがってCRC値をシフトしてキャリーが立つ→CRC値が生成多項式より大きくなった→生成多項式 x1で割り算できるという意味でシフトとそのキャリー確認後にExORを行なうのが基本のアルゴリズムとなる。 生成多項式の表現は x^16+x^15+ .. +x^2+1 とかなっているが、次数の小さいものがCRCをFIFOとしてみたときの入り口より。ただしどちらをCRCのMSBにもってくるかは方式に依存。+1がLSBのときは「左送り」、x^nがLSBのときは「右送り」。 生成多項式の生成多項
![CRCが合いません!!](https://cdn-ak-scissors.b.st-hatena.com/image/square/8d71ff5111e05619a10d29bb40d7aebaa75c8fbc/height=288;version=1;width=512/https%3A%2F%2Fs0.wp.com%2Fi%2Fblank.jpg)