なんかやってると「多項式」というものに突き当たることがある。
CRCとか。
いつも、適当にネットで調べて、実装だけ持ってくることが多いのだけど、そろそろ理解した方がいいんじゃないか、と思うようになった。
というよりも、多項式、という言葉が出てくるたびに思考停止に陥るのが嫌になっただけだ。
多項式 - Wikipedia
和と積から成るということは、四則演算からできあがる式ってことらしい。
『C言語による最新アルゴリズム事典』
いきなりこの本が出てきたのがなぜかというと、手元に持っている本でアルゴリズムのようなものを説明しているのが唯一これだけだからだ(持っているのは21刷)。
こちらは、私が具体的に知りたい多項式の説明になる。
項目としては「多項式の計算」。
理屈は・・・まだ理解できていない。
私は、具体例がないとよくわからんのだ。
本に、CRC16のことが書かれているので、それから読み解こう。
CRC16(CCITT)はこうなるそうだ。
x^16 + x^12 + x^5 + 1
ここで、今までなら「で？」だったのだが、多項式のことを書く記事になったから、調べないといけない。
自分を追い詰めるというのは、こういうことだったのか。
元の多項式は、n番目の項の係数に、xのn乗を掛けたものを足していったものらしい。
n番目の係数をc[n]として、べき乗を^で表すと、
c[n] * x^n + c[n-1] * x^(n-1) + ・・・ + c[1] * x + c[0]
だそうだ。
c[z]の部分を、2進数の1とか0とかに置き換え、0を掛けたところを省いたのが、上記の式になるようだ。
c[16]と、c[12]と、c[5]とc[0]が1、つまり、10001000000100001、なのかな？
1 | 0001 | 0000 | 0010 | 0001
17bitあるやん！
何か間違っているのかと思ったが、本のCRC項目を読むと、CCITTのX.25では0x11021で割るということらしい。
だから、さっきの式は正しい。
ん、割る？
2進数で考えよう。
00 / 0 = (;_;)
00 / 1 = 0
01 / 0 = (;_;)
01 / 1 = 1
10 / 01 = 10 ... 00
10 / 10 = 01 ... 00
10 / 11 = 00 ... 10
11 / 01 = 11 ... 00
11 / 10 = 01 ... 01
11 / 11 = 01 ... 00
111 / 100 = 001 ... 011
1111 / 100 = 0011 ... 0011
11111 / 100 = 00111 ... 00011
111111 / 100 = 001111 ... 000011
1111 / 1000 = 0001 ... 0111
11111 / 1000 = 00011 ... 00111
111111 / 1000 = 000111 ... 000111
桁がxの最大な数字を、桁がyの最小の数字で割ると、割った値は(x - y + 1)桁になる。
だから、割る数がy桁なら、どんなにその数字が大きくても、結果が(x - y + 1)桁以上になることはないはず。
取りあえず2進数だけで考えると、そういう法則になる。なるはず。
本の説明では、割る数のビット数より1つ小さいビットだけ左シフトしてから割り、その余りがCRCになるとのこと。
割った結果が関係あるだろうと思って法則を見つけていたのだが、余りだとは・・・。
どんなに割られる数のビット数を増やしても、余りが割る数より大きくなることはない。
上記を見ればわかるように、割った余りの最大値はy-1ビットだ。
だから、17bitの値で割ったなら、その余りの最大は16bit。
CRC16は、だから16bitなのだ。
CRCの計算式はいろいろあるが、そこは高速化のためだから、もうよい。
多項式の理解というよりも、CRC計算の桁数の理解だけになったが、なんとなく満足した。
0 件のコメント:
コメントを投稿
コメントありがとうございます。
スパムかもしれない、と私が思ったら、
申し訳ないですが勝手に削除することもあります。
注: コメントを投稿できるのは、このブログのメンバーだけです。