こんにちはお世話になります。
私はネットワークに興味があるオジサンです。
先日、データリンク層のプロトコル群を勉強していたとき、誤り訂正でCRCが出てきました。誤り訂正ではパリティーチェックやチェックサム等は聞き覚えがありましたが、CRCは始めて見たので興味を持ち少し調べてみようと思いました。
それが間違いの元でした。
インターネットでCRCの構造を詳しく解説するサイトが少なく、その解説は難しすぎて手におえません。
数学にはめっぽう弱い私には、多項式同士の加減乗除算などは頭痛の肥やしにしかなりません。
今ではCRCが気になって勉強に集中できない状態です。
そこで、表題にもあるCRCのアルゴリズムを、何方か分かり易く教えてくださいませんか。もしくは、CRCのアルゴリズムを簡単に解説している書籍をご存知でしたら教えてください。
カテゴリー(本来は数学系?)が違うかもしれませんが、何卒よろしくお願い申し上げます。
No.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 なら偶数パリティと同じなのかとか、生成多項式をどう選
べばいいかとかについては、符号理論の勉強が必要です。前者はそ
れほど難しくはないですが。
丁寧な回答ありがとうございます。
パリティティーチェックで1ビットだったパリティーが、CRCでは多項式で多ビットに置き換えたのですね。理解しました(^_^;)。
ご指導の通り計算してみました。最初は「特殊な二進数の世界」に戸惑ってしまいましたが、めでたく計算できました。
ビット列を高次元に表すことは、アドレスからデータ範囲までチェックするために必要だったんですね(ホンマかいな)、と勝手に納得しています。
おっしゃる通り符号理論の勉強が必要なようです(頭が痛い)。
punchan_jpさんの回答で多項式の符号化計算まで理解(ほんの少しですが)できるとは思っていませんでした。とても得した気分です。
punchan_jpさんには貴重な時間を割いていただき、大変感謝しております。
これからもよろしくお願い申し上げます。
ありがとうございました。
No.1
- 回答日時:
凄い難しい事ですね。
CRCの計算方法だけでも結構な厚さの本が出来てしまうので、ここでは、簡潔に書きます。----ここから
CRCは、データ列を高次の多項式と考えて、その多項式をあらかじめ定められた生成多項式で割る。その余りをBCCとしてデータの後ろに付加して送信する。
また、受信側では同じ生成多項式で割り算を行い、余りがなけば転送データに誤りがないと判断する。
-----
こんな感じでですが....どうでしょうか?
もし勉強に集中出来ないって事なら、CRCはチェックサムのやり方(計算方法)って覚えると良いでしょう。
具体的な計算方法が判らなくても、何をする物なのか理解出来ればそれほど大きな問題になるとは思えません。
詳しく知りたい場合には、通信プロトコル関係の書籍を呼んで下さい。説明が詳しく書かれています。
早速の回答ありがとうございます。
要点を易しく解説していただき、ウニ状態の頭の中もようやく整理できました。
CRCはエラーチェックだと軽くCRCを流したかったのですが、データリンク層に使われているからには何か理由があるのかと思い込み、調べ始めたのが運のつきでした。オヤジの冷や水、数学はもうこりごりです。
mnabeさんには当質問で貴重な時間を割いていただき、大変感謝しております。
これからもよろしくお願い申し上げます。
ありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 高校 勉強ができない。 4 2022/07/03 08:13
- 国家公務員・地方公務員 公務員試験の数的処理で苦戦しています。 1 2023/01/30 08:56
- 輸入バイク 錆止めオイルについえ 3 2023/03/02 23:52
- 高校 有効数字計算 確定した値を含む 2 2023/01/18 06:03
- 統計学 統計学を独学で勉強してます。 ページ左上に誤差分散の推定量の指揮があると思いますが(青いペン) 例題 2 2023/02/12 12:34
- 統計学 統計学を独学で勉強してます。 ページ左上に誤差分散の推定量の指揮があると思いますが(青いペン) 例題 5 2023/02/12 15:39
- その他(悩み相談・人生相談) 自分の頭が悪すぎて恥ずかしいですごめんなさい。 なるべく多くの人に答えてもらえたら嬉しいです。 小学 6 2022/03/28 03:17
- 工学 【呉工業製品についての工学的な質問です】ギアの小歯車に呉工業のグリスメイトを吹き掛けた 2 2023/03/12 14:23
- その他(学校・勉強) 教養があれば世の中の見方が変わってきてそこから興味のある分野の本を読んだり調べたりでまた人生の愉しみ 5 2023/01/07 19:25
- 発達障害・ダウン症・自閉症 中学の時にIQ82の境界知能と診断されました。 今の私も、やはり境界知能でしょうか? そしてこれは、 3 2023/02/19 00:37
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
まあべつにいいけど
-
arcsinのマクローリン展開について
-
(x-1)(x-2)(x-3)の展開の...
-
多項式について質問です。 エク...
-
斉次とは?(漢字と意味)
-
パデ近似の利点について教えて...
-
余次元って何?
-
単項式と分数式の違いについて
-
e^sinXの展開式について。。。
-
データのノイズ除去法 - Savitz...
-
等差×等比 型の数列の和を求め...
-
(1+x)^n=1+nxについて
-
約数と因数の違い(∈N)
-
組立除法 1次式 ax-k の係数...
-
deg f?
-
原始多項式の求め方
-
Qバー={α⊂C| αがQ上代数的...
-
M系列の生成多項式と原始多項式...
-
CRCチェック 多項式の選び方
-
ローラン展開の問題についての...
おすすめ情報