CRCおぼえがき

（途中から調べずにイメージで書いています。たぶんどこか誤解しています。親切な方はご指摘ください）

• 送る側の処理
• D(X)・X^r = G(X)・Q(X) + R(X)　が基本の式
• CRC = R(X)を二進数で表したもの
• R(X)＝ (D(X) ・ X^r) ÷ G(X) の余り
• D(X)＝送信したいデータを多項式にしたもの
• r = G(X)の最高次数
• G(X)は生成多項式 (方式ごとに異なる。CRC-16やパリティなど)
• 送るデータはD(X)とR(X)をビット順でくっつけたもの
• つまり、D(X) ・ X^r + R(X)

多項式を２進数で表すことは、多項式が Σ^r_(i=0) b_i x^i という形で、係数の列 b_i が0か1だけからなるときに可能。b_iを多項式に対応する２進数のiビット目の数とする。つまり、多項式の最高次数はMSBの桁数となる。

• 受け取る側の処理
• 届いたデータをまるごと生成多項式G(X)で割る
• (D(X) ・ X^r + R(X)) ÷ G(X)
• 余りが０ならOK　（誤りが無い）
• D(X)・X^r = G(X)・Q(X) + R(X)　が元の定義
• D(X)・X^r  + R(X) = G(X)・Q(X) + 2R(X)
• 余りは 2R(X) になるの？
• 商は元のデータになる
• Q(X) = D(X)？