巡回冗長検査(CRC)のよくある実装の説明

巡回冗長検査(CRC)

計算方法

一言でいうと

特殊な剰余。

2進数のわり算

2進数のわり算の余りを考えてみよう。たとえば10011010 / 1010を考える。まずはじめの4ビット1001は1010より小さい。次の1ビットを追加して10011から1010を引く。結果は1001となる。次の1ビットを追加して10010から1010を引く。すると1000となる。同様に10001から1010を引いて111、さらに1110から1010を引いて100となる。

これは10進数で考えると154 / 10のあまりが4ということだ。

引き算のかわりにxorを

2進数での計算では「1ビットずらして引き算」をくりかえしていた。この「引き算」をxorとしてみよう。

上の例の10011010 / 1010では以下のようになる。1001と1010のxorで0011となる。2ビットずらして1110と1010のxorで0100となる。1ビットずらして1001と1010のxorで0011となる。1ビットずらして110が答えとなる。

    10011010
xor 1010
------------
    00111010
xor   1010
------------
    00010010
xor    1010
------------
    00000110

この計算をmodulo 2と呼ぶ。

すなおな実装

modulo 2の計算のすすめかたは以下のようになる。

1. わられる数の1となっている最上位のビットを探す
2. そのビットとわる数の最上位ビットの位置をあわせる
3. わられる数とわる数のそれぞれのビットについてxorをしたものでわられる数を更新
4. わる数とわられる数の最下位ビットの位置があっていれば終了
5. そうでなければ1へもどる

わる数の最上位ビットはいらない

わる数の最上位ビットは1だ。そしてxorをするときには必ずわられる数の対応する位置のビットも1だ。つまりxorした結果その位置のビットは必ず0となる。よってxorする必要はなく単に捨ててしまえば良い。これを考慮すると計算のしかたは以下のようになる。

ここでは「わる数'」を今まで考えてきた「わる数」の最上位ビットを捨てたものとする。

1. わられる数を最上位ビットbとその残りrにわける
2. bが0ならばrをわられる数とする
3. bが1ならばrとわる数'とを先頭をあわせてxorしたものをわられる数とする
4. 最下位ビットの位置がそろっていればわられる数を結果とする
5. そうでなければ1へもどる

持ちまわる値を小さく

実用的には「わられる数」は非常に大きな値となる。これを状態として持ちまわるのは非効率的だ。持ちまわる必要があるのは実際にはわる数'がnビットであるならば「わられる数」のうち先頭nビットだけでいい。「わられる数」の残りは必要に応じて読みこんでいく。

1. 先頭nビットを読みこむ
2. 先頭nビットを最上位ビットbと残りrにわける
3. わられる数から1ビット読みこみ残りrの最下位に追加しsとする
   1. ただし、読みこめなければ先頭nビットが結果となる
4. bが0ならばsを新しい先頭nビットとする
5. bが1ならばsとわる数'をxorしたものを新しい先頭nビットとする
6. 2へもどる

テーブルを使う

わる数'がnビットであり、わられる数をたとえば8ビットずつ読みこむとする。8ビット読みこんだところでわかるのは続くnビットがこの8ビットに対する操作によってどう変換されるか、だ。テーブルを作成するために0から255の256通りの8ビット値eに対して続くnビットに対して何をxorすることになるかを求める必要がある。続くnビットに対してxorする値をtとする。

1. はじめにtにeを代入する
2. 3から6を8回くりかえす
3. tを最上位ビットbと残りrにわける
4. rを左シフトする
5. bが0ならばrをtとする
6. bが1ならばrとわる数'とをxorしてtとする

テーブルが作れたら以下のようにする。

1. 8ビット読みだす
2. テーブルから対応する値を読みこみtに代入
3. tを先頭8ビットeと残りrにわける
4. rを8ビット左シフトする
5. 8ビット読みだしeとのxorをとりe'とする
6. e'に対応する値をテーブルから読みこみsとする
7. sとrとをxorしtに代入する
8. 3へもどる

上記では終了条件が省略されている。今までの計算と同じ結果とするにはわられる数の残りがnビットになった時点でtとその残りとをxorすることになる。

わられる数の末尾にnビットの0を追加

上記の終了条件よりも「読みこめなくなった時点でtを結果とする」のほうがコードがシンプルになる。このようにすると意味的にはわられる数の末尾にnビットの0を追加したのと同じことになる。

先頭nビットを補数にする

上記の手続きは以下のように単純化することができる。

1. tに0を代入する
2. tを先頭8ビットeと残りrにわける
3. rを8ビット左シフトする
4. 8ビット読みだしeとのxorをとりe'とする
5. e'に対応する値をテーブルから読みこみsとする
6. sとrとをxorしtに代入する
7. 2へもどる

ここでtの初期値を0ではなく2 ^ n - 1(つまりすべてのビットが1)とする。そうするとわられる数の先頭の0の個数によってチェックサムが変わってくる。データの先頭に0が追加または削除されてしまうといったエラーを検出可能となる。

この操作は数学的な意味としてはわられる数の先頭のnビットのそれぞれのビット値を反転(0 -> 1, 1 -> 0)するということになる。

リトルエンディアン

実際のCRCはリトルエンディアンで実装しやすい規格になっている。つまり今までは最上位ビットから計算していたのを、最下位ビットから順に計算していくようにすれば良い。