HOME»応用情報技術者試験掲示板»CRCの理解のある方
投稿する
最初、そもそも割り算をする段階からなぜ？と始まったのかと思いました。まあ、MODゼロかそれ以外かの2択に絞れるのは除算以外ないからね、と・・・。
で、
CRCの原型は、大きな数値をある素数で割った時の余りがどうか、で決めているわけで、たとえばRSAなんかは素数を2つ用意していろいろやるわけですが、素数候補をポンポン出すにはどうやるか？といえば簡単で、0or1の乱数をビット数分用意してそれを数値に変換するわけです（ミラー・ラビン素数判定とかで判定するとかやるけど、そこは話がずれるので割愛）。
1001111011111011010010110101
なら166704309になりますけど、2^27×1+2^26×0・・・とかになっていく（ret = ret * 2 + bit）わけですから、多項式っちゅうのはこういうことって言い換えられますね。
このあたりは
www.seplus.jp/dokushuzemi/fe/fenavi/mastering_tech/crc/#!
基本情報でわかる CRC 「具体例を見て体験すれば仕組みがわかる」
にて
たとえばIEEE802.3なら
X^32+X^25+X^23+X^22+X^16+^X12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X+1
で32ビットのチェックビットを作った上で判定するとn-1ビット以下の長さの範囲内であれば、その中に複数のエラービットがあっても検出できる保証があるわけですが、それはなぜか？というと、
データをどのくらいの長さで区切った上で、どのような定数（素数）で割るかを決めるわけだから、セクションごとに誤りが出たら、複数の誤りがわかりますよね、って話ですよ。
[2873] CRCの理解のある方
tea_creatsさん(No.1)
CRC(巡回冗長検査)の理論がいまいちわかりません。
今わかっていることについて以下に述べますと、
・nBITCRCでは、最大nBITの連続したビット誤りを検出することができる。
・データの誤り訂正はできない。
・実データ部のうしろに、実データを多項式(?)で割り算をしたnBITのビット列を付加する。
わからないことを以下に述べますと、
・多項式で割り算をするという概念？理由がわからない
・この方法で複数ビットのデータ誤りを検出できている理由が分からない
・調べたところ、nBITずつ取り出して順々にXORでデータを取り出して行き最後に残ったnBITをCRCコード部としている、というものがあったがこれが多項式で割り算をしたというのに理解がつながらない
どなたか、CRCについてご教授願えませんか?
都合がよろしければ、解説サイト等でもご回答いただければ幸いです。
今わかっていることについて以下に述べますと、
・nBITCRCでは、最大nBITの連続したビット誤りを検出することができる。
・データの誤り訂正はできない。
・実データ部のうしろに、実データを多項式(?)で割り算をしたnBITのビット列を付加する。
わからないことを以下に述べますと、
・多項式で割り算をするという概念？理由がわからない
・この方法で複数ビットのデータ誤りを検出できている理由が分からない
・調べたところ、nBITずつ取り出して順々にXORでデータを取り出して行き最後に残ったnBITをCRCコード部としている、というものがあったがこれが多項式で割り算をしたというのに理解がつながらない
どなたか、CRCについてご教授願えませんか?
都合がよろしければ、解説サイト等でもご回答いただければ幸いです。
2021.09.19 21:03
GinSanaさん(No.2)
★AP プラチナマイスター
この投稿は投稿者により削除されました。(2021.09.19 23:34)
2021.09.19 23:34
GinSanaさん(No.3)
★AP プラチナマイスター
>多項式で割り算をするという概念？理由がわからない
>・調べたところ、nBITずつ取り出して順々にXORでデータを取り出して行き最後に残ったnBITをCRCコード部としている、というものがあったがこれが多項式で割り算をしたというのに理解がつながらない
最初、そもそも割り算をする段階からなぜ？と始まったのかと思いました。まあ、MODゼロかそれ以外かの2択に絞れるのは除算以外ないからね、と・・・。
で、
CRCの原型は、大きな数値をある素数で割った時の余りがどうか、で決めているわけで、たとえばRSAなんかは素数を2つ用意していろいろやるわけですが、素数候補をポンポン出すにはどうやるか？といえば簡単で、0or1の乱数をビット数分用意してそれを数値に変換するわけです（ミラー・ラビン素数判定とかで判定するとかやるけど、そこは話がずれるので割愛）。
1001111011111011010010110101
なら166704309になりますけど、2^27×1+2^26×0・・・とかになっていく（ret = ret * 2 + bit）わけですから、多項式っちゅうのはこういうことって言い換えられますね。
生成多項式で割る
と考えるからややこしいのであって生成多項式で得られた値で割る
にすればどうでしょうかね。このあたりは
www.seplus.jp/dokushuzemi/fe/fenavi/mastering_tech/crc/#!
基本情報でわかる CRC 「具体例を見て体験すれば仕組みがわかる」
にて
>・この方法で複数ビットのデータ誤りを検出できている理由が分からない
たとえばIEEE802.3なら
X^32+X^25+X^23+X^22+X^16+^X12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X+1
で32ビットのチェックビットを作った上で判定するとn-1ビット以下の長さの範囲内であれば、その中に複数のエラービットがあっても検出できる保証があるわけですが、それはなぜか？というと、
データをどのくらいの長さで区切った上で、どのような定数（素数）で割るかを決めるわけだから、セクションごとに誤りが出たら、複数の誤りがわかりますよね、って話ですよ。
2021.09.19 23:32