CRCとは、巡回冗長検査といって、シリアル通信のデータチェックなどで良く用いられる手法です。CAN通信でも、このCRCが利用されています。
CRCについては、深堀すると、理論が深遠すぎて、よくわからないところもまだありますが、今回ちょっと何となくこんなものかという所まで、分かったようなきがするので、メモしときます。
基本は、割り算のあまりを考える
たとえば、27という数字をデータとして、送りたいとします。データ送信時に27を7で割ったあまりを検査ビットとして、6をつけておくります。
受信側は27を受け取り、自分であまりを求め、受信側からきたあまりと一致してるかどうかで、データの信頼性を判断します。
たとえば、間違って、データに28がきたら、受信側で計算したあまりは0になってしまうので、この時、ぬぬぬ、データ怪しいぞって判断することができます。
これは、ちょっとよさそうですが、いちいち10進数で演算するのも、非効率な気がします。
二進数の割り算
じゃあ、実際にデータは0と1の二進数で割り算をして、あまりをだせばいいんじゃないかとなります。
たとえば、27÷7の2進数の割り算は、0b11011 ÷ 0b111となり、あまりは、0b110になります。
上の計算で、問題は、引き算のときに繰り下がりが発生してしまうことです。もちろん、足し算では、繰り上がりが発生します。繰り上がり、繰り下がりが発生すると、自分のbit以外の計算が結果に影響をおよぼしてくるので、演算がちょっと面倒で嫌な感じがします。
多項式の割り算
多項式の係数を各ビットに割り当てて、多項式をつくっていみます。
たとえば 11011の場合、多項式は、x^4+x^3+x+1となります。111の場合は、多項式は、x^2+x+1となります。
これで多項式の割り算をすれば、繰り下がりが発生しなそうな気がします。
確かに引き算は簡単になりました。ただ、途中係数が-1になったり、2なったりして、0と1以外の係数を取りだしてるので、なにをやってるのかよく分からなくなってきました。これは、二進数の割り算では出なかった問題です。
うーん。繰り下がり、繰り上がりがなくて、しかも演算しても、係数が0と1以外でてこないスーパー都合のよい計算方法ってありますか？
モジュロ2の世界を考える
モジュロ2とは、2で割ったときのあまりの数たちのことです。これを構成する要素は、{0,1}しかありません。この数同士の四則演算を考えます。演算結果も当然、モジュロ２の世界の住人とみなすので、2で割ったあまりをとります。
まず、足し算と引き算を考えます。
足し算
０ + ０ ＝０
０＋ １ ＝ １
１＋ ０ ＝ １
１＋ １ ＝ ０
うん？って一瞬なりますが、答えの２を２で割ったあまりは０なので０です
よくみると、足す数と足される数のXNORをとれば、足し算の結果になっていることが分かります。次は、引き算です。代数学的には、加法の逆元（ある数を足したら単位元0になる数）みたいな言い方をしますが、難しいことは、考えないことにします。
引き算
０ － ０ ＝０
０ － １ ＝０ １＋ １ が ０なので
１ － ０ ＝０
１ － １ ＝０
すごいことがおきました。モジュロ2の世界では、足し算と引き算が同じ結果になります。つまり引き算したければ、足し算すればいいわけです。足し算は、XNORをとることと同値でした。つまり、割り算の途中で出てくる引き算は、単にXNORをとればいいことが分かりました。これがCRCの計算で、XNORの演算がでてくる理由です。
掛け算はどうでしょうか。
０ × ０ ＝ ０
０ × １ ＝ ０
１ × ０ ＝ ０
１ × １ ＝ １
普通の掛け算とおなじでした。
次に割り算ですが、割り算は0以外の要素にたいして、掛け算したら答えが1になるような数を考えます。つまり、逆数(これも本当は、積の逆元という)があるかどうかをみます。0以外の要素は1しかないので、1の逆数は1です。つまり、割り算はこうなります。
1 ÷ 1 = 1 × 1 = 1
0 ÷ 1 = 0 × 1 = 1
ちょっと要素数がすくなすぎて、逆にわかりにくいので、mod 5を考えてみます。mod5の元は{0,1,2,3,4}です。この逆数を考えます。
1の逆数 ： 1 簡単
2の逆数 ： 3 2×3 = 6 = 1 mod5 だから
3の逆数 ： 2 上におなじ
4の逆数 ： 4 4×4 = 16 = 1 mod5だから
mod5 でもすべての要素で逆数がもとまりました。これで割り算ができます。
例えば、
4 ÷ 4 = 4 × 4 = 1
4 ÷ 3 = 4 × 2 = 3
4 ÷ 2 = 4 × 3 = 2
4 ÷ 1 = 4 × 1 = 4
みたいにできます。mod5もそうですが、mod2の世界では、住人同士で、演算すると、答えもかならず、その世界の住人になり、演算が閉じています。これを代数学的には体とよぶらしいです。（体になる条件は、他にもありますが）
ちなみにmod 5も体ですが、mod 6 は体ではありません。実は、体にするには素数で割ったあまりである必要があります。
実数の世界も、体なので、これを実数体、mod 2の世界は、二元体などと表現します。ちなみに実数の元は無限個ありますが、二元体の元の数は二つしかありません。なので、こういうのを有限体というらしいです。GF(2)とかで表したりもします。
各ビットを多項式に置きかえた方法で割り算した時、計算のなかで0-1＝-1とかやってましたが、無意識に、演算を実数体上で取り扱ってたとも言えます。
じゃあ、mod 2 の世界でも、おれらなりの多項式あってもいいじゃんと主張してもよさそうな感じがしてきました。
モジュロ2を係数とした多項式を考える
そんな訳で、mod 2 の世界の多項式を考えます。かっこよく言うと、GF(2)上の多項式とよびます。多項式の係数はmod 2 なので、0と1しかとりません。係数同士の演算もmod 2のルールに従います。
つまり、例えば多項式の和は、
( x^2 + x + 1 ) + ( x + 1) = x^2 + (1 + 1) x + (1 + 1) = x^2
となります。
引き算は
(x^2 + x+ 1 ) – (x + 1) = x^2
となります。この結果から、やっぱり多項式でもmod２の世界では、足し算 = 引き算といえそうです。
モジュロ2を係数とした多項式の割り算
モジュロ2の多項式をつかって、割り算のあまりを求めてみます。
狙い通りの結果になりました。演算途中で係数が0と1以外をとることがなくなりました。
任意の多項式(ただし、係数はmod 2)に対して、x^2+x+1で割った時の余りを考えます。余りは割る多項式の次数より当然低いわけですから、{0, 1, x. x+1}のいづれかになります。これは2ビットで、{00, 01, 10, 11}として、すべての結果を2ビットでうまく表現できそうです。
さきに説明したとおり、素数で割った余りの集合は四則演算ができる有限体になりました。実は、多項式の世界でも同じことがいえます。多項式において、この素数にあたるのが既約多項式というものです。
ある数が素数かどうかは、約数が存在するかどうかでみれば、分かりますが、既約多項式の場合は、因数分解できるかどうかで考えます。
素数じゃない: 24 = 2 * 2 * 2 * 3
素数: 7 = ムリ！
既約多項式じゃない: x^2 + 2x + 1 = (x+1)(x+1)
既約多項式： x^2+1 = ムリ！
ただ、上の例みたく、実数体上では、x^2+1は因数分解できませんが、今回考えている多項式は、mod 2の世界の多項式なので、
x^2+1 は (x+1)(x+1) = x^2 +(1 + 1)x +1 = x^2 +1
みたいにx^2 +1 は因数分解できちゃいますので、注意が必要です。一方で、mod 2の世界でも、
x^2 + x + 1
は因数分解できません。これが、既約多項式になります。つまり、さっきの割り算の余り{0, 1, x, x+1}は、既約多項式のあまりの集合といえますので、体になっているはずです。実際に四則演算をして、確認してみます。
今回は、要素数が多いので、表にしました。下が足し算の結果です。
たとえば、 （x+1）+ (x +1) = ( 1 + 1) x + (1 + 1) = 0 のようになります。
どんな組み合わせでも答えは、{0, 1, x, x+1}以外でてこないので、演算は閉じています。引き算は足し算とおなじだったので、当然、同じ結果になるはずです。
次に掛け算の結果が下です。
そのままだと、黄色の箇所で、x^2 とか x^2 +1 とか、でてきてしまいますが、いまは、x^2+x+1で割った余りをかんがえているので、下のようにして、次数をおとします。
すると、下表のようになりました。
掛け算も、どんな組み合わせでも答えは、{0, 1, x, x+1}以外でてこないことがわかります。また、0以外のすべての要素が掛け算して答えが1になるような値(逆数）をもっているので、割り算も成立してそうです。
以上から、x^2+x+1のあまりの世界もmod 2 の世界と同じように体になっていることがわかりました。
拡大体
話の最初は、元が{0, 1}のmod 2 の世界を考えていて、次にこれを係数とした x^2 +x +1の割り算の余りの世界を考えたら、それも体になりました。しかも、元が拡大され、{0, 1, x, x+1}になりました。なので、これを拡大体と呼びます。また、既約多項式によって、新しい体が生成されたので、この多項式のことを生成多項式と呼びます。CRCで出てくる生成多項式がここでやっとでてきました。(実際は、ビット誤りの検出能力をあげるため、ちょっと補正がはいってたりする場合があります)
今回、生成多項式は2次式でした。その余りは、ax+bの形になります。mod 2では、aとbは0か1の2パターンのため、 拡大体の元の数は、2＾2 = 4個で、上の表の元の数と一致します。
ちなみに生成多項式がm次の場合は、2^m – 2 個になります。
CRCの検査方程式
以下、CRCに関する教科書の抜粋です。
・生成多項式G(x)の倍多項式すべての集合を符号Cとする
・CはW(x)=A(x)G(x)という形の符号多項式からなる符号
・符号多項式W(x)は、生成多項式G(x)で割り切れる つまり、W(x) mod G(x) = 0
実際の検査方法はこうです。
情報ビットを係数とする多項式X(x)を求めて、それを生成多項式で割り、剰余多項式C(x)もとめます。符号多項式をW(x)=X(x) + C(x) として、W(x)を生成多項式で割り切れることが確認できれば、データ問題なし、OKと判定します。
以上のようなことが、CRCの元になるような考え方です。なんとなく、なぜ、mod 2の多項式がでてきたのか、割り算途中で、XNORの演算がでてくるのか、その背景が分かった気がします。
CRCの実際の計算方法は、またどこかでまとめていきたいと思います。
CRCばんざい。
