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

A 回答 (2件)

偶数パリティについておさらいすると、1 となるビットの個数が偶


数になるように、検査ビットを定めるというものですよね?で、検
査側では、1 の個数を数えて奇数だとエラーと判断するわけです。

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

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

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

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

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

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

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

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

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

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

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

お礼日時:2001/01/30 18:50

凄い難しい事ですね。

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

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

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

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

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

お礼日時:2001/01/30 18:20

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

今、見られている記事はコレ!

  • 心理学者が分析!なぜ女性は電話に出るときに声が高くなるのか

    ご家庭や職場などで、女性が電話で話しているのを聞いて、普段より声が高いなと思ったことはないだろうか? 電話応対となると、無意識なのか高めの声でハキハキと話す人が多い気がする。「教えて!goo」にも「なぜ...

  • 一人暮らしに最適なインターネット環境は?

    今や、生活に欠かせないインターネット。一人暮らしを始める際は、新たにインターネット環境を準備する必要がありますよね。しかし、準備の際について迷うことも多いようです。教えて!gooには、こんな相談が寄せら...

  • Wi-Fiと無線LANの言葉の違い、ご存知ですか?

    インターネットに関する用語は、なんとなく理解していても、本来の意味は知られていないこともあります。教えて!gooには、こんな質問が寄せられました。 「WiFiと無線LANの違いについて」 質問者は、以前は無線LA...

  • 勧誘電話のおもしろい?撃退方法を教えてください

    マンション投資やオレオレ詐欺など、どこかで個人情報が漏れたのか、迷惑電話がかかってくることも少なくありません。教えて!gooにもこんな相談が寄せられていました。 「勧誘電話のおもしろい?撃退方法教えて下...

  • これで撃退!?迷惑電話の切り方

    会社や自宅などに、迷惑電話がかかってくる事はありませんか?中には何度もかけてくる場合もありますが、できるだけスマートにお断りしたいものですよね。教えて!gooにはこんな相談が寄せられています。 「迷惑電...

おしトピ編集部からのゆる~い質問を出題中

お題をもっとみる

このQ&Aを見た人が検索しているワード


このQ&Aを見た人がよく見るQ&A

このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ