CRCが合いません!!

かつてCRCを高速に演算するハードを設計したというのに、週末から作り出したら実際のツールとさっぱり合わなくてなんでか仕事中も考えていたら、結局無理解によるものだとわかった。今回あらためてわかったことを書き留めてみる。
 
  • CRCとはそもそもデータ列を長大なビット列として扱ったものを生成多項式で割り算した剰余である。したがってCRC値をシフトしてキャリーが立つ→CRC値が生成多項式より大きくなった→生成多項式 x1で割り算できるという意味でシフトとそのキャリー確認後にExORを行なうのが基本のアルゴリズムとなる。

  • 生成多項式の表現は x^16+x^15+ .. +x^2+1 とかなっているが、次数の小さいものがCRCをFIFOとしてみたときの入り口より。ただしどちらをCRCのMSBにもってくるかは方式に依存。+1がLSBのときは「左送り」、x^nがLSBのときは「右送り」。

  • 生成多項式の生成多項式をx^1+1にすると偶数パリティと同じになる。前述の原理より自明。つまり1での剰余。「CRC=パリティ」の記述は正しい。

  • 「CRC=チェックサム」は間違いで、たぶん後述の末尾にCRC値を用いたチェック方法を勘違いしている。

  • 現在のCRCと同じ値をデータ列として処理するとCRCの値が0になる(方向に注意)。また現在のCRCの1の補数(=ビット反転したもの)をデータ列として処理すると常にCRCが特定の値になる。0にしてしまうと次のキャリーが発生するまで0が続くので、エラー検出に使う場合はデータ末に1の補数を置く方法がよい。これを利用してエラーチェックができる。データの末尾に期待するCRC値かその補数を置くとCRCの値を固定的に確認するだけでよくなる。

  • CRCの初期値は全ビット0か1が多い。仕様によっては特定の値が指定されることもある。ソフトでは全部1、ハードでは全部0または指定の値をとる場合が多い気がする。全部0と全部1の差で誤り検出に差は無いが0が続く、またはCRC長と同じ1が続いた後の0は誤りとして検出できない。理由は後述による。

  • CRCを”更新”するとき、右シフトで詰める場合と左シフトで詰める場合がある。基本は左シフトだが、実際はものによる。

  • CRCを”更新”するとき、データをCRC先頭に押し込む場合と、CRC最後尾からシフトアウト(キャリー)してきたものとデータをExORしたものをCRC先頭に再度押し込む場合がある。(DOW CRC)
  • データを最後まで処理したらCRCをビット反転する場合(CRC32)や、CRCと同じ長さの0のデータ列を挿入することがある。(CRC16)

  • データはMSBから扱う場合とLSBから扱う場合がある。基本はMSBからだがファイルを扱う場合は通常LSBから。

  • データがファイルの場合は単純に先頭からバイト単位で扱う。ワードのエンディアンは考えない。

  • 処理結果をあらかじめ2^n個のテーブルに保存することでnビットの一括処理ができる。これは足し算同様、演算子のXORが順不同であるという事実による。(1+2+3=6、2+3+1=6と同じように12 xor 17 xor 21= 8、17 xor 21 xor 12 = 8)

適当に思いつくままわかったことを書き留めたらこんなかんじ。実際のコードとかは明日以降掲載予定。

右送り、左送りとか、意味わかんない。シフトしたいのか、ビットの処理順なのかどっちだ。
あと「CRCチェックサム」なんて言葉が出回ってること自体も気持ち悪い。せいぜい「CRCチェックバリュー」くらいにしておけばいいものを。

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中