とにかく(実装からみた)CRCの実装方法から。
 
一般的な、シンプルなCRC
  1. CRCを保存する変数(以降CRCレジスタ)に初期値をセット。
  2. データから1ビットとってくる。(MSBから、またはLSBから)
  3. CRCレジスタにシフト代入。(右シフトまたは左シフト)
    シフト時にあふれるビットをキャリーとする。
  4. キャリーが 1のとき、CRCレジスタを生成多項式でExORし、結果をCRCレジスタに戻す。
回転シフトを使うCRC (DOW CRC ?)
  1. CRCを保存する変数(以降CRCレジスタ)に初期値をセット。
  2. データから1ビットとってくる。(MSBから、またはLSBから)
  3. CRCレジスタをシフト。(右シフトまたは左シフト)
    シフト時にあふれるビットをキャリーとする。
  4. キャリーとデータビットの ExOR が 1のとき、CRCレジスタを生成多項式でExORし、結果をCRCレジスタに戻す。

これが基本形。シフト方向の決定、データの先頭ビットは各実装で異なります。
あとはCRCの初期値の値、データ末後の処理手順(ビット反転するとか)を加えれば実際に使えるものになります。

実は、この二つの手順は等価で後者は前者の最適化されたアルゴリズムとなります。
厳密にはCRCがデータのビット列を生成多項式で割った余りだという解釈から前者の場合、
データの末尾にCRCレジスタと同じ長さの0を付け足す必要があります。
こうすると初期値が0ならば二つの手順から同じ結果が得られます。

ただし前者の手順を使いながらも末尾処理してないものが存在するため、一種のバリエーションと考えられます。
(例:IBM PC-DOS付属のCRCコマンド)

 

広告

コメントを残す

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

WordPress.com ロゴ

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

Twitter 画像

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

Facebook の写真

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

Google+ フォト

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

%s と連携中