| 03/11/03 | ファイルのCRC編−その３（実装編）[★★◎◎◎◎] | |||||||
アルゴリズムの最適化前回の最後はCRC32の計算はr=0; while (len--) r = ((r << 8) | *p++) ^ t[(r >> 24) & 0xFF]; と言うプログラムで行えることを示しました。 CRC32の計算の場合は、データの終端に32個の0をつけて計算することになり、ハードで計算するにしてもソフトで計算するにしてもちょっと面倒です。 そこで、このアルゴリズムをさらに最適化して行きます。 CRCを計算する対象のバイト列がレジスタに入ってきた時、値がどのように変化していくかを考えてみると、以下のようになります。
つまり、バイト列からレジスタに入ってきた値は4回テーブルの値でXORされ、レジスタから出て行くことになります。 ここで、やはりXORは計算順序に依存しないことを考えると、4回分のテーブルの値のXORをとった後にバイト列から入ってきた値とXORを取っても良さそうな気がします。 替わりにとりあえずレジスタが左シフトする時は0を右から入れておきます。 このようにすると、バイト列が終端に達した段階でレジスタに残っている値を考えると、レジスタに0が入ってきてそれに（位置に応じて回数は異なるが）何度かテーブルの値をXORした段階でストップします。 よって、「とりあえず0を入れておいて後でバイト列とXORを取る」という手段を利用するとわざわざ0を付け加えなくても0をつけたのと同じ結果が得られることになります。 図で表すと、今までの左の手法が右の手法に入れ替わることになります。
プログラムも対応して以下のように変わります。
バイト列の中身である*pの値がXORされる位置が移動しているのに注目です。 上ではrを8ビット左シフトした後最下位のバイトに*pが入ってきますが、下は何も入ってきてないので0で埋まります。 反射バイト列を扱うこれで、アルゴリズムがより最適化されました。しかしファイルのCRC計算にはまだ足りないものがあります。 ここで、ビット列が逆になることを「反射」(reflection)と名づけることにします。 例えば、1100を反射させると0011、1001010を反射させると0101001等のようになります。 反射の考えは一部のハードウェアで必要になります。 CRCの計算では上位ビット（２進数の上のケタ）から順にレジスタに入ってくることを想定していますが、ハードによっては通信時下位ビットから入ってくる場合があります。 この場合、8ビット入ってくるごとに反射させてCRCを求めてもいいですが、やはり余分な手間になります。 そこで手間を増やさずに、バイト列の各バイトを入力が反射した状態と仮定してCRCの計算をする手法を考えます。 （なお、ここでは8ビットごとに反射しているので、テーブルも8ビット、256エントリある必要があります） 計算は以下のように行います。
テーブルは中身を反射させておく必要があります。 例えば、もとのテーブルが 10101010 → 10010010010010010010010010010010 だったら、 01010101 → 01001001001001001001001001001001 として置きます。 また、レジスタの初期値が0でないならば反射させておきます。 あとは、シフトの方向が全て左だったものが右になっています。 ここで、入力バイトは反射させる必要はありません。（替わりにテーブルが逆になっている） 最後の結果のレジスタは本来の結果を反射したものになっているので、さらに反射すると正しい結果が返ってきます。 もし入力バイト列が8ビット分だけで「01010101」だったとします。 これは反射している状態なので、元々「10101010」を意図して送られてきています。
CRC計算のパラメータで、ようやくファイルのCRC計算です。CRCはここまでの段階で「割るための多項式」と、「入力バイト列の反射の有無」によってバリエーションが色々あることがわかると思います。 さらに、いくつかのパラメータによって最終的なCRCのアルゴリズムが決定されます。 重要なのがレジスタの初期値です。 ここまでレジスタの初期値は0にしてきましたが、入力バイト列が00 00 00・・・と00が続く場合、XORをとっても0になり、テーブルも0で引くと大抵0が返ってきてしまいます。 このようなblind spot(本文まま)を防ぐために初期値を入れることは意味が多少あるかもしれません。 後は同じような感じで最後になんか定数とXORをとる場合があります。 また、最後に出てくるCRCの値を反射させる場合があります。（ただし、反射は上の定数のXORの後に行う） 一般的なファイルのCRC32の計算では初期値をFFFFFFFFとし、最後にFFFFFFFFとXORをとるとしています。 このため、ファイルのなかみが「FF FF FF FF 00 00 ・・・」と最初の4バイトがFF、あとは00が任意の数続くような場合、レジスタの値と入力バイト列のXORを取ると常に00なので、FF FF FF FFの後はずっとレジスタの中身が0になり、最後にFFFFFFFFとXORをとるので、00の続くバイト数に関わらずCRC32はFFFFFFFFになります。 さて、これらのパラメータを考えると、ファイルのCRCに用いられるCRC16及びCRC32は以下のようになります。
これでCRC16・CRC32の計算を行う全ての情報がわかったことになります。 （圧縮方式であるLHAもファイルのCRC16を使っていますが、パラメータが違うので別の値になります） 一応CRC32の計算をVBで書いたものを載せておきます。 （テーブルの作成法は後述） バイト配列buf()のlバイトのデータが入力だとします。
初期値は定義通りFFFFFFFF、 右シフトの式がちょっと変な形をしていますが、あとは反射時のアルゴリズム while (len--) r = (r >> 8) ^ t[(r & 0xFF) ^ *p++]; と同じことをやっています。 (((lCRC And &H7FFFFF00) / 256) Or (&H800000 * -(lCRC < 0))) はVBではunsigned変数がないことと、ビットシフトがないのでムリヤリ右8ビットシフトをしているだけです。 入力がどこで反射しているかと言うのはここだけ見てもわかりにくいですが、実際はテーブルを作成しているときに反射させてしまうのでここでは必要がありません。 また、出力も反射させておくはずなのにここではしていません。 入力を反射するときのアルゴリズムは、そもそも出力が反射した状態で出てくるのでわざわざ余計に反射させる必要もないわけです。 で、最後にFFFFFFFFとのXORを取っています。 CRC16では最後に0000とのXORをとることになっていますが、これは何もしないのと同じなのでこの処理がなくなります。 テーブルの作成方法CRC32のテーブルのエントリを作って見ます。例えば入力が10101010(=170)の時のテーブルの値を計算してみます。 反射とかは気にせず、10000 0100 1100 0001 0001 1101 1011 0111(=0x104C11DB7)で割ってみます。 （多項式の0x04C11DB7は最高次の値を無視した表現なので、割り算は0x104C11DB7で行う） この値は、「その２」の方で既に行っていますね。
よって、テーブルのエントリは CRC32Table(170)=&HDEA580D8になるか・・・？ というとそうではありません。 それぞれの値をここで反射させます。 10101010(=170)を反射させると01010101(=85) 1101 1110 1010 0101 1000 0000 1101 1000(=0xDEA580D8)を反射させると0001 1011 0000 0001 1010 0101 0111 1011(=0x1B01A57B) なので、 CRC32Table(85)=&H1B01A57B となります。 これは、VB講座中のCRC32を求めるサンプルで実際に使っている値に一致します。 同様に256個のエントリを埋めると、上のプログラムで使っているCRC32Tableのテーブルが作成できます。 以上でCRCの計算は無事終了です。 以下のサイトを参考にしました。（国内だとテーブルをCRCを求めるコードはいくつかありましたがテーブルの作り方とかは見当たりませんでした・・・） Cyclic Redundancy Code Calculator Lab Report (Delphi用のソースの他、関連リンク集) A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS (実際の理論について詳しく説明) 特に下のサイトの構成にしたがってここでも解説しています。 以前VB講座中のCRC32を求めるサンプルでは、ビットシフトが重そうなので4つのバイト配列を使って計算していました。 しかし、unsignedもビットシフトもないとは言え、Long型1変数で行ったほうが3割ほど高速化したのでそちらで行いました。 また、同サンプルでは上のA PAINLESS〜〜に含まれるC言語のプログラムをコンパイルしたものを同梱しました。 （同梱したプログラムはpublic domainです） これは、上のパラメータ（多項式や初期値、反射の有無）を構造体で指定することで、様々なパラメータに対応するCRC値を計算できます。 ただし、テーブルは利用せずマジメに1ビットずつ計算しているので速度は遅いです。 テーブルを作成するプログラムもつけてあるので見てみるといいかもしれません。（出力はC言語ですがVBにも利用できるでしょう） | ||||||||
| 03/10/20 | ファイルのCRC編−その２（テーブル編）[★★◎◎◎◎] | |||||
|
前回の03/08/20のその１ではCRCの基本的な理論と計算方法について調べたと言うことで、今度はもっと効率の良い計算をする方法についての理論を考えることにしてみます。 割り算を実際にするのはかなり面倒ですが、後述のようにこの割り算の特性を理解することでビットシフトとXORだけで余りを求められることがわかります。 さらに計算を高速化する手段として、事前に計算したテーブルを利用する手法が一般的に使われているようです。 テーブルを使ったファイルのCRC16・CRC32の求め方はgoogle等で検索すると国内でもいくつか見つかります。 ただ、なんでそのテーブルを使うのか、そのテーブルはどっから出て来たかという情報が見つかりませんでした。 海外のサイトも探してみたところ、 A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS というサイトでこのテーブルについても触れています。 まぁ英語でも問題無い方は上のサイトで見てしまったほうが早いかもしれませんが、一応自分で理解したところを補足や例を交えつつ見ていきたいと思います。 CRCの計算は、「引き算の替わりにXORを用いて、割り算を行って余りを求める」と言うことになります。 ここで割り算を行うのは面倒な様に思えますが、実際はビットシフトとXORだけで行えると言うことを示したいと思います。 人間が割り算を筆算で行うときのことを考えてみたいと思います。 例えば、変な数ですが15000÷73の筆算を考えてみるといいと思います。 まぁ次のようになるでしょう。
上の「〜〜をもってきて」はなんか1ケタ下の数字をもってくるのでビットシフトっぽいし、引き算は既に述べたようにXORで置き換えられるような気がしてこないでしょうか？ ここで、本来は「15と73を比較する」場合は実際に数値を比較する必要があります。 ただ、今回は引き算をXORで代用することもあり、「桁数が一緒なら実際の数値は小さくでも割れる」ということになります。（繰り下がりの必要が無い） そこで、前回出てきた 011001010000 ÷ 10011 の余りをビットシフトとXORで求めてみたいと思います。 割る数は５ケタで、上の「桁数が一緒なら実際の数値は小さくでも割れる」という条件から、４ケタ分の領域を特別扱いして準備しておきたいと思います。（レジスタと呼ぶことにする）
011001010000 ÷ 10011 = 1101110 余り 0010 なので、この結果は正しいと言えますね。 このように人間の行う割り算の筆算と同じような考えかたを用いると、CRCの計算がビットシフトとXORだけで行うことができました。 この方法は形こそビットシフトとXORになっているものの、元々の理論通り割り算を行っています。 そのためCRCの理論とは直結していて理解はしやすいですが、ビットごとに計算を行っているためちょっと速度面で不安があります。 そもそもデータがバイト単位でやってくることが多いため、バイト単位ぐらいで計算ができるとありがたいですね。 と言うわけで、複数ケタ分の計算を事前にやっておいて結果を覚えておくと言うことが考えられます。 さっきの15000 ÷ 73の例を少し変えて、15000****・・・と15000に続いて他に数字が続いている場合での割り算を考えると、
これをみてわかるように、割り算では下のほうの数値が何であっても上には影響を及ぼさないことになります。 なので、下の値に関わらず、 「先頭が15000で始まる数値15000*****・・・を73で割ると計算の途中経過は35*****・・・になる」 よって、今後具体的に15000という数値が出てきたら割り算をしなくても35に置き換えてしまって構わないといえるでしょう。 この15000→35がテーブルになります。 同様に00000〜99999までについての余りを計算しておけば５ケタ分のテーブルができあがります。 まぁこれだとテーブルが100,000個も必要でちょっとおおすぎですが・・・ CRCの場合も同様にテーブル作成ができます。 別にテーブル作成は5ビットごとでも13ビットごとでもいいわけですが、通常バイト単位で処理できると便利だと言うことで8ビットを取ります。 テーブル項目数も256個でちょうどいいですね。 実際にCRC32で使われる場合のテーブルを１つ計算してみたいと思います。 CRC32では多項式は100000100110000010001110110110111です。 例えばビット列10101010(=170)に対するテーブル値を求めると、以下のようになります。
ここで、２進数でかつ繰り下がりを気にする必要が無いので、15000÷73で35余るようにあまることは無く、上8ビット分は必ず0になります。 で、このとき、割る数が33ケタなので最高後ろ32ケタに影響を及ぼすことになります。 なので、ここでは10101010に続く32ケタの********************************から何度か引き算が行われます。 ここで、********************************から３回なんか値を引かれた結果を@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@とおくと、薄い灰色である0を補うと以下のように表現できます。 ( ( (******************************** XOR 01100000100011101101101110000000) XOR 10011000001000111011011011100000) XOR 00100110000010001110110110111000) = @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ ちょっとわかりにくいので、16進法にしてみると、 ( ( (******** XOR 608EDB80) XOR 9823B6E0) XOR 2608EDB8) = @@@@@@@@ だいぶわかりやすくなってきました。 ここで、XORは足し算と一緒で演算の順番は気にしなくていいため、 ( ( (******** XOR 608EDB80) XOR 9823B6E0) XOR 2608EDB8) = ******** XOR (608EDB80 XOR 9823B6E0 XOR 2608EDB8) = ******** XOR DEA580D8 = @@@@@@@@ よって、10101010(=180)がレジスタから出て行くときには、レジスタにDEA580D8をXORを足せばいいことになります。 00000000〜11111111までのたった256個について同様に計算しておけば１バイト単位でXORするだけで計算できます。 先ほどのサイトから絵と式を持ってくると次のようになりますね。 レジスタは32bitのint変数rです。
これでだいぶいい感じになってきた気がします。 しかし、VB講座中のCRC32を求めるサンプルとテーブル、アルゴリズム共にちょっと異なっています。 例えば、CRC32用のテーブルの10101010(=170)に対応する値はDEA580D8ではなく36034AF6が入っています。 それに、XORやテーブルを引くタイミングも少しずれています。 そもそも、上のC言語の例では初期値が0になっているのに本来のCRC32を求める時はレジスタ初期値がFFFFFFFFが入っています。 XORやテーブルを引くタイミングが違うのは、上のC言語風のアルゴリズムではまだ無駄があるからです。 CRCでは最初にデータ列全体をシフトする必要がありました。 これは割る数に対応する式の次元（まぁ桁数-1なんですが）に対応するので、CRC32なら32bit、CRC16なら16bit分最後に0が付く必要があります。 これを処理するのは面倒です。 ハードで処理する場合はデータの終端を発見して32個0を加えたりしないと行けないし、ソフトの場合も32bit=4byte分後で余分にメモリを確保する必要が出てきたりします。 そこで、再びこのアルゴリズムの特性を利用して末尾の0の列を気にしなくてもいいように変形して行きます。 そこらへんは次回。 待ちきれない人は（いるかどうかわからないけど・・・）上のサイトを見るといいと思います。 | ||||||
| 03/09/28 | コンパイラ作ってみるかも編−その１（前準備編） | ||||
|
2年ほど前大学の授業の一貫でコンパイラを作ったことがありました。 ただ、目的のアーキテクチャも独自使用であり、言語も関数型言語だったと言うことで普通の手続き型言語のコンパイラを作る練習をしようと思い立ってみました。 ・・・ということで。 字句解析から何から全部やるのは厳しいし、アセンブラ吐き出してもリンカとかまで作るとなると相当面倒だな・・・ということで以下のアプローチを取ることにしました。
（ちなみに、現在VBで正規表現ルーチン及びLL文法解析ルーチンはできていて、lex/yaccに送るファイルを作成中） 最初あえてVBで字句解析などを行うのは、（2年前に途中まで作りかけたものがあったからというのがありますが）もともとVBネタばかりのページでCネタとかはどうなんだろうかということでVBです＾＾； ただ、どうしても木構造など扱う上でVBはポインタが使えないため非常に面倒です。 ということで実際のコンパイラはCで作成します。 最後に、EXEファイルを吐くにはx86のアーキテクチャを理解した上でEXEファイルの面倒な構造を理解しないと行けないことになります。 （自分の環境がWindows98なこともあって）ちょっとへんなEXE吐いて実行させたらOSが不安定・・・なんてのは面倒です。 一方Javaの場合、メモリ管理もVMまかせでいいうえ、エラーが起きてもVMがちゃんと守ってくれるのでOSには影響ないし、そもそもEXEファイルに比べてclassファイルの方が構造が簡単です。 また、コンパイラが完成したとして数値計算だけ行ってもつまんないし、練習のコンパイラの為にライブラリを用意するのも寄り道＆面倒です。 一方JavaだとprintlnとかdrawStringとかを普通に呼べばいいのでこの手間がだいぶ省けます。 作る言語としてはどうしてもCっぽいのが浮かんでしまうのですが、Javaに近いとつまらないのでVBに近い感じにしてみたいと思います。（まぁどっちもそれほど変わらないが・・・） んで、コンパイラをネット上だけの文章で勉強するのは大変なので、やはり本が欲しいと言うことになります。 コンパイラ本は高いですね。 薄めの本だと3000円程度ですが、ある程度のものだと5000円超えます。 幸い研究室にコンパイラの本があったので以下の本を使ってみたいと思います。 ドラゴンブックと呼ばれる本で内容が新しいとは言えないそうですが基本はしつこいぐらいしっかり押さえています。
次に、Javaのclassファイルを吐くのであれば、(Java言語自体の仕様はともかくとして）classファイルの構造やJavaのバイトコードのインストラクションセットの知識が必要となります。
これで資料に関してはコンパイラ・ターゲットとなるアーキテクチャとそろうことになりました。 最後に、目的となるコンパイラはWin+VCで作る予定です。 となると、flex/bisonのWindows版が必要となります。 これはコンパイラメーカーが作っているもののほか、Vector等にもありますが、比較的UnixやLinux版と挙動が近そうという（主観）ことで以下の2種類を挙げておきます。
FlexやBison、Lex・Yaccに関しては本もありますが、GNUのツールでもあるせいか結構細かいマニュアルがあります。
少しバージョンが古いですが大した問題では無いと思います。 なぜかbisonは検索すると大学内に日本語訳がいくつかありました・・・ GNUのマニュアルは必ずしもわかりやすいとは言えないので、flexやらbisonやらで検索すると大学のコンパイラ演習の授業のページや、個人でこれらを利用されている方のページがいくつも出てくるのでそちらを参考にするといいかと思います。 これで一通り資料・ソフト・マニュアルもそろったことになるので、次回はVBでムリヤリ簡単な正規表現のマッチを行うプログラムを書いてみたいと思います。 | |||||
| 03/08/20 | ファイルのCRC編−その１（CRC概要編）[★★◎◎◎◎] | ||||||||||||||||||||||||||||
|
従来から通信などの分野で、内容に（雑音などのエラーによる）誤りがないかをチェックする方法に対して様々な研究が行われてきました。 簡単な方法ではデータの数値の和を取るチェックサムや、1であるビット数が奇数もしくは偶数になるように冗長なビットをちょくちょく挟むことによるパリティビットなどが考えられます。 さらに誤っているビット位置を知るための情報をつける方法などが色々あります。 まぁこれはネットワークとか記録デバイスなどハード寄りのことをやる人はともかく、一般の使用者にはそこまで気にする必要はないかと思います。 ただ、現在ではインターネットなどでファイルをダウンロード・アップロードすることが多くなったわけですが、ダウンロード中に途中で接続が切れたりしてファイルの長さや内容が変になってしまうことはよくあるかと思います。（特にダイヤルアップだとね・・・） というわけで、最近では配布したファイルが正しいかどうかを示すために、ダウンロードするファイルのチェックサムのようなものを表記してある場合が増えてきました。 （まぁウイルスとかしこまれるとこのチェックサムも変化してしまうので、通信エラー以外にも改造版配布の防止にも役立つんでしょう） ここでチェックサムそのものが使われることはあまりないと思います。 よく使われるのは1方向性のハッシュ関数であるMD5、SHA、データ誤り訂正・検出に使われるCRCあたりだと思います。 （MD5はUnixのパスワード管理でも使われていたはず） MD5及びSHAは単なるハッシュ関数（と言ってもデータベースなどで使われるインデックス圧縮のようなものとは使用用途が違う）なのでとりあえずここは置いておいて・・・ CRC(Cyclic Redundant Check:巡回冗長検査)についての数学的(というか情報科学や通信工学？)の理論についてダラダラと触れてみたいと思います。 まぁCRCはネットで検索すると色々出てくるし、通信関連の本を読めば大抵書いてあるので、そっちをみた方がいいかもしれません。 日本語でも検索すると http://laputa.cs.shinshu-u.ac.jp/~yizawa/InfSys1/advanced/crc/ http://mailsrv.nara-edu.ac.jp/~asait/code.htm など、大学のレジュメやその他多くのサイトが見つかると思います。 CRCは簡単に言うと 「割り算のあまりを求める」 ということに他ならないということになります。 CRCでは、データを２進数表現し、それを多項式の係数とみなします。 例えばある１バイトの数値0x65は 0x65 = 01100101 = 0*x7+1*x6+1*x5+0*x4+0*x3+1*x2+0*x1+1*x0 = x6 + x5 + x2 + 1 とあらわすことができます。 で、これに対して割り算を行うわけですが、ここで、これから行う演算は2を法として行うことになります。 簡単に言えば、2で割った余りが等しい場合はその数値は等しいということになります。つまり、 ・・・ ≡ -6 ≡ -4 ≡ -2 ≡ 0 ≡ 2 ≡ 4 ≡ 6 ≡ ・・・ (mod 2) ・・・ ≡ -5 ≡ -3 ≡ -1 ≡ 1 ≡ 3 ≡ 5 ≡ 7 ≡ ・・・ (mod 2) となります。 よって、この世界では0と1があれば十分ということになります。 さらに、2つの数値の 足し算及び引き算、あとXORを考えると、
で、割り算を行うわけですが、先ほど出てきた多項式(0x65ならx6 + x5 + x2 + 1)を別の多項式で割ることになります。 例えば、10011=x4 + x + 1で割ることを考えます。
で、割り算をするわけですが、CRCの計算では単にx6 + x5 + x2 + 1をx4 + x + 1で割るわけではなく、割る式がこの場合4次式なので、割られる式にx4を掛けることになります。 また、これは元の0x65 = 01100101に対して、左4bitシフトして011001010000とすることと同じです。 これからx4 + x + 1で割るわけですが、この演算は単に011001010000 ÷ 10011で行うことになります。 ただ、ここで一つ重要となるのは、上に書いたように引き算で0-1=-1となっても、2を法とする演算では-1≡1となるため、上の位からの繰り下がりを考える必要がなくなります。 （多項式で考えてみれば、0*x3-1*x3 = -1*x3となったところで、別にx4から繰り下がりをしたりはしないですよね） まぁ色々書きましたが、結局すべき計算は 011001010000 ÷ 10011の余りを、引き算の代わりにXORを用いて求める ということになります。 計算の過程は省略しますが、結果は 011001010000 ÷ 10011 = 1101110 余り 0010 となります。よって、元のデータ0x65のCRCは0010となります。 ここで、5桁の数は10000-11111で16個あるわけだが、1〜1000000000000000(1<<14)をさらに4bit左シフトしたものをそれぞれもとの10011で割ってみると、
余りの値は0以外の15通り全ての値を取っていることがわかる。 ちなみに 10000000000000000000(1<<19) ÷ 10011 の余り ＝ 0011 であり、これは(1<< 4)を割った場合と同じ値になるが、これは(1<< 15)を10011を割ると余りが1になるので当然と言えば当然である。 先ほどのデータは 011001010000 ÷ 10011 = 1101110 余り 0010 であったが、もしもとのデータが1bit誤って01110101(0x75)になっていたとすると、CRCは 011101010000 ÷ 10011 = 1111101 余り 0111 であるが、この余りの差分を（やはりXORを用いて）取ると、0101となる。 これは(1<<8)を10011で割ったときの余りと等しい。 よって、4bit左シフトした後の値が(1<<8)だけずれていたことになる。 これによって、CRCは1bitの誤りを訂正することができる。 誤りが２個あった場合、i>jとすると、誤った分の差分はxi+xj = xj(xi-j+1) ((1<<(i-j)+1)<<j）となる。 割る数値はxで割りきれない(定数項1を含む)かつ（(xi-j+1)を割りきらない）ように選ぶことで、この誤りを検出できる。 上記で、(1<<15)を割ると余りは1になるので、(1<<15+1)は割りきれることになる。 よって、最大16bitまでの長さの数値に対して2bitの誤りを検出できる。 まぁ5bitの式は最上位を1に固定すると16通り考えられるので、それで16bitまでの長さとも考えられる。 さらに、CRCでは奇数bitの誤りを検出できる。 もし誤っているビットが奇数の場合、誤った分の値xi1 + xi1 + ・・・ + xin に対して、x=1を代入すると奇数個項があるので1になる。 よって、この式は(x+1)を因数に含まない（含むならば、1を代入すると(x+1)=0となって全体が0となり、矛盾する）。 そこで、割る数値自体を(x+1)を因数に持つものを選べばよい。 10011(x4 + x + 1)は引数にx+1を持たないので、その意味ではあまりいい式ではない。 さらに、もともとCRCはバースト誤りを検出するものである。 バースト誤りとは、あるビットからあるビットまでのうちいくつかが反転してしまっているものである。 先端の位置を xi+k-1、終端を xiとすると、この誤りは xi * (xk-1 + ・・・ + 1) とあらわすことができる。 （カッコ内はxk-1と1はなければならないが、xk-2 〜 x1 はあってもなくてもよい） この場合、長さkのバースト誤りと言える。 今回４次式を割る数値に使ったが、この場合k≦4であるようなバースト誤りは全て検出する。 四次式＝５ケタの数で割るのに、この場合カッコ内は最高でも３次式＝４ケタであり、最後に1が付いているのでうまく割りきれてしまうことがないからである。 もしk>4の場合、カッコ内がたまたまうまく割りきれてしまう可能性がある。 この確率は各ビットが半々の確率で都合いい方に誤るとして単純に(1/2)kである。よって、 5bitの誤りは1-(1/2)5=31/32 6bitの誤りは1-(1/2)6=63/64 7bitの誤りは1-(1/2)7=127/128 ・・・以下同様の確率で検出できる。 CRCの国際標準として、以下の値がある。
CRC-32だけなぜか(x+1)を因数に持たない気がするが・・・ CRCはこのように、比較的色んな誤りを検出できる。 また、割り算が必要とは言え足し算引き算がXORで、繰り上がり・繰り下がりを考えなくてもいいこともあって、シフトとXORで計算できるため、高速でかつパワーも必要としない。 そのため、通信時のチェックサム代わりなどで使われることになる。 ただ、この考えかたをそのままファイルのCRCには用いてもうまく行かない。 この理論であれば、データが0で埋まっているファイルは、どんな長さでも余りが0になるはずである。 （0をいくらビットシフトしたって0だし） そこで、これをさらに拡張したものが利用される。 詳しいことは次回。 | |||||||||||||||||||||||||||||