CRCのアルゴリズムって、どんな計算するんですか？

質問

こんにちはお世話になります。
私はネットワークに興味があるオジサンです。
先日、データリンク層のプロトコル群を勉強していたとき、誤り訂正でCRCが出てきました。誤り訂正ではパリティーチェックやチェックサム等は聞き覚えがありましたが、CRCは始めて見たので興味を持ち少し調べてみようと思いました。
それが間違いの元でした。
インターネットでCRCの構造を詳しく解説するサイトが少なく、その解説は難しすぎて手におえません。
数学にはめっぽう弱い私には、多項式同士の加減乗除算などは頭痛の肥やしにしかなりません。
今ではCRCが気になって勉強に集中できない状態です。
そこで、表題にもあるCRCのアルゴリズムを、何方か分かり易く教えてくださいませんか。もしくは、CRCのアルゴリズムを簡単に解説している書籍をご存知でしたら教えてください。
カテゴリー（本来は数学系？）が違うかもしれませんが、何卒よろしくお願い申し上げます。

回答No.2

punchan_jp · ベストアンサー

偶数パリティについておさらいすると、1 となるビットの個数が偶
数になるように、検査ビットを定めるというものですよね？で、検
査側では、1 の個数を数えて奇数だとエラーと判断するわけです。

実は、この偶数パリティというチェックのしかたは、CRC の一種な
んです。CRC では、ある特定の生成多項式を使いますが、CRC の生
成多項式として x + 1 を使ったものが偶数パリティです。

多項式の加減乗除で頭痛ということなら、ちょっと説明が厳しいの
ですが、2進数の加減乗除はできるでしょうか？これがだいじょう
ぶなら、1+1=0（つまり、0-1=1）という世界での2進数の加減乗除
を考えるということでも同じです。

この場合、x+1 という多項式は、11 と考えます。（xのi乗の係数
を第iビットの値とみなす）

例えば、10110 というデータに対して、11 という生成多項式で
CRC の検査ビットを求めるには、生成多項式の桁数－１＝１ビット
分データを左にシフトして、101100 を得ます。この値を、上の特
殊な2進数の世界で、生成多項式の 11 で割ります。そうすると、
商として 11011、余りとして 1 が得られます。試しにやってみて
ください。この余りを、101100 から引いて（特殊な2進数の世界で
は足すのと同じ）やると、101101 が出ます。これが送るべき符号
ということになります。実際、1の個数は偶数ですので、付け足し
たビットが偶数パリティとなっていることがわかります。

余りの分を引いたわけですから、このデータは 11 で割り切れるは
ずですので、検査側では 11 で割って、余りが 0 であることを確
認すればいいわけです。

この生成多項式の選び方で、検査の能力が変わってきます。やみく
もに選んだら、検査能力がまったくなくなります。通常の CRC は、
それを考慮してうまく多項式を作ってあるというだけのことです。

なぜ 11 なら偶数パリティと同じなのかとか、生成多項式をどう選
べばいいかとかについては、符号理論の勉強が必要です。前者はそ
れほど難しくはないですが。

お礼

丁寧な回答ありがとうございます。
パリティティーチェックで１ビットだったパリティーが、CRCでは多項式で多ビットに置き換えたのですね。理解しました(^_^;)。
ご指導の通り計算してみました。最初は「特殊な二進数の世界」に戸惑ってしまいましたが、めでたく計算できました。

ビット列を高次元に表すことは、アドレスからデータ範囲までチェックするために必要だったんですね（ホンマかいな）、と勝手に納得しています。
おっしゃる通り符号理論の勉強が必要なようです（頭が痛い）。

punchan_jpさんの回答で多項式の符号化計算まで理解（ほんの少しですが）できるとは思っていませんでした。とても得した気分です。

punchan_jpさんには貴重な時間を割いていただき、大変感謝しております。
これからもよろしくお願い申し上げます。
ありがとうございました。

回答No.1

mnabe

凄い難しい事ですね。CRCの計算方法だけでも結構な厚さの本が出来てしまうので、ここでは、簡潔に書きます。
----ここから
　CRCは、データ列を高次の多項式と考えて、その多項式をあらかじめ定められた生成多項式で割る。その余りをBCCとしてデータの後ろに付加して送信する。
　また、受信側では同じ生成多項式で割り算を行い、余りがなけば転送データに誤りがないと判断する。
-----
　こんな感じでですが....どうでしょうか？

　もし勉強に集中出来ないって事なら、CRCはチェックサムのやり方(計算方法)って覚えると良いでしょう。
　具体的な計算方法が判らなくても、何をする物なのか理解出来ればそれほど大きな問題になるとは思えません。

詳しく知りたい場合には、通信プロトコル関係の書籍を呼んで下さい。説明が詳しく書かれています。

お礼

早速の回答ありがとうございます。
要点を易しく解説していただき、ウニ状態の頭の中もようやく整理できました。
CRCはエラーチェックだと軽くCRCを流したかったのですが、データリンク層に使われているからには何か理由があるのかと思い込み、調べ始めたのが運のつきでした。オヤジの冷や水、数学はもうこりごりです。

mnabeさんには当質問で貴重な時間を割いていただき、大変感謝しております。
これからもよろしくお願い申し上げます。
ありがとうございました。