[an error occurred while processing this directive] [an error occurred while processing this directive]

CRC の計算方法

ここでは厳密な定義には立ち入らず、CRC の計算がどのように進められるかを見てみます。

CRC のアイディア

CRC は、簡単にいうと「割り算の余り」です。
コンピューターが扱うデータは、0,1 がたくさん並んだものですが、これはとても大きな数値と見ることができます。 "01" なら 1 ですし、"1001" なら 9 、"10010100" は 148, "1001111011111011010010110101" なら 166704309 という風に、どんな長いデータでも、とても大きな数値と見なすことができます。 文書でも、デジカメで撮った画像ファイルでも、DVD の動画でも同じです。
CRC の原型は、この大きな数値をある素数 (P とします) で割った時の余りです。例えば P = 41 とすると、先の "10010100" (10進法で 148) を 41 で割ったあまりは 25 なので、25 が求める値になります。もしデータが化けていた場合は、この余りの値は元々の値と変わります。例えば "10010100" (10進法で 148) が "10011100" (10進法で 156) に化けてしまった場合、これを 41 で割ったあまりは 33 になり、元々の 25 と一致せず、エラーが分かります。
このとき、P が 2 でないとき、任意の 1 ビット誤りを検出できることが分かります。元々のデータが 1 ビット変化するというのは、元々のデータが 2n 変化するということです。ここで、2n は P で割り切れることは決してありません。よって、余りの値も変化してしまいます。

繰り下がりの問題

「素数 P で割った余り」は CRC の原型ですが、本物の CRC は、コンピュータで処理しやすくするため、もう少し工夫があります。
コンピュータの計算では、「繰り上がり」「繰り下がり」は厄介な問題です。 例えば、100000 を 101 で割る場合を考えてみます。二進法で書いていますが、割り算のルールは十進法と同じです。 
      ?
    +-------
101 | 100000
上のように割り算をするとき、? のところに 1 が立つのか立たないのか、割られる数の 1 を見ただけでは分かりません。 100 まで見て、はじめて ? には 0 が立つことが分かります。 
      0001
    +-------
101 | 100000
       101
      ------
       ?
さらに計算を進めて、引き算をするときにも問題があります。 ? のところに 0 が来るのか 1 が来るのかは、下の 2 桁を見ないと分かりません。この場合は 0 が来ます。
このように、繰り下がりがあると、割り算をするときに複数の桁を見る必要があります。 また、各桁を独立に処理することが出来ないため、ビット数が増えると、大きなボトルネックになります。

なお、現代のコンピュータでは、一回の割り算の処理は大したコストではありません。ただ、繰り上がりが存在のおかげで、割り算は and や or といったビット演算に比べて数倍遅くなります。エラー検出では大きなデータを扱うので、演算が軽い方がよい、という事情は変わりません。

繰り下がりのない割り算

そもそも、初めに "01" を 1 、"1001" を 9 みたいに数値に置き換えたところを、以下のように考え直してみます。 元々 n ビット目に 1 が立っていたら、xn を加えるだけです。
11
1001x3 + 1
10010100x7 + x4 + x2
つまり、任意の n ビットのビット列は { Σ a i xi | 0 ≤ i < n } ただし a i ∈ {0, 1} と表せます。

その上で、演算のルールを定めます。まず、足し算やかけ算は、通常の多項式演算のように定義します。
例えば
ただし、元々 xi の係数 (ai) は、各ビットを表していたので、0 または 1 でした。 なので、xi + xi = 2 xi としてしまうと、元のビット表現と対応しなくて少し困ります。
そこで、以下のように定めます。 こうすると、各桁の値は必ず 0 か 1 になって、元々のビット表現と対応できました。(めでたしめでたし)
さらに以下が導かれます。 足して 0 になるのだから、xi と -xi は等しいということになります。

このような演算系で、割り算を考えてみます。うれしいのは、各桁の演算を独立して取り扱えることです。
先ほどと同じ、100000 を 101 で割る場合を考えてみます。まず、100000 は x 5, 101 は x2+1 と書けます。 二進法で書いていますが、割り算のルールは十進法と同じです。 
         ?
       +-------
x2 + 1 | x5
上のように割り算をするとき、? のところに 1 が立つのか立たないのかは、割られる数の最上位の値、x2 を見るだけで十分です。この場合は x3 が立ちます。 因みに、さらに計算を続けると以下のようになります。 
         x3 + x
       +-------
x2 + 1 | x5
         x5 + x3
         -------
              x3
              x3 + x
              -------
                   x
よって、商が x3 + x、あまりが x になります。普通に演算が出来ていますね。
(Nagz さん、割り算の間違いを教えていただきありがとうございます!)

「繰り下がりのない割り算」を使った CRC の計算

先ほど説明した、「繰り下がりのない割り算」を用いて、CRC の計算をしてみます。 基本的には割り算をするだけですが、ポイントになるのは割る数です。 先ほど、割る数は大きな素数 P でした。 今回は各元は多項式 (12345 みたいな数ではなく、x3 + x2 + 1 みたいな式) なので、 素数に対応する概念としては、どんな多項式でも割り切れない式、既約多項式が適当です。 既約多項式の例としては、(x + 1), (x 2 + x + 1) など、色々作れます。 実際によく用いられる多項式としては、以下のようなものがあります。 これを、先ほどの例のように割り算していって、余りを求めます。この値を元々のビット表現に戻したのが、CRC の値です。
実用的によく用いられる CRC32 は次数が多くて大変なので、もう少し手軽な CRC5 を例にしてみます。 計算する元のビット列は、"10010100" (10 進数と見ると148)とします。 
              x2 + 1
            +-----------------------
x5 + x3 + 1 | x7          + x4     + x2
              x7    + x5           + x2
             ---------------------
                      x5 + x4
                      x5      + x3    + 1
                   ------------------
                           x4 + x3    + 1
「あまり」は x4 + x3 + 1 なので、11001、10 進数で見ると25 と求められます。
例えば、送りたいデータだった "10010100" が 10011100 と化けると、CRC の値は以下のように変わります。 
              x2 + 1
            +-----------------------
x5 + x3 + 1 | x7          + x4 + x3 + x2
              x7    + x5            + x2
             ---------------------
                      x5 + x4 + x3
                      x5      + x3      + x
                   ------------------
                           x4           + x
「あまり」は x4 + x なので、10010、10 進数で見ると 18 となり、先ほどの値と異なります。 元々の「割る数」(x5 + x3 + 1) は既約多項式なので、あまりの値がぴったり 一致するときは、その違いが (x5 + x3 + 1) * f(x) と表されるときだけです。 つまり、元々のデータとの差分が高々 4 次までの多項式の積で表されるときには、必ず誤りを 検出できることがわかります。

おまけ: なぜ突然、多項式が出てきたのか

CRC の計算で、方程式でもないのに多項式が出てくるのは少し唐突ですが、 これは、計算をなるべく自然なものにするために、あえて導入しています。
CRC の計算で用いるのは、GF(2n)の拡大体と呼ばれるものです。 この世界でも、数(元)は 101, 10010 のように、x を用いずに表すことも出来ます。 この場合の演算は、以下のようになります。 決して変わったことはしていないのですが、(!) がついたものは、 なじみのある足し算、かけ算とは違ってしまっています。
もともと、演算を各桁で完結できるように、 のかわりに というルールを決めて、あとは結合法則 に従えばよいのですが、演算のルールがはっきり見えてきません。

これに対し、x を導入し、各元を多項式として表すと、演算の規則を以下のようにすっきり表すことができます。 上から、以下の式が導かれます。 先ほど (!) で示した演算は、以下のようになります。 このように、x を用いることによって、なじみのある多項式の演算を用いた解析が出来るようになります。 もっと詳しい背景は、別項「CRC の数学」をご覧ください。
[an error occurred while processing this directive]