CRCによる誤り検出の条件

質問

現在、CRCについて学んでいます。
その中で、誤り検出が可能な条件として、
誤りの多項式E(X)が生成多項式G(X)で割り切れないこと
というのがあると思います。

そこで例えば、rビットのバースト誤りの際に、
E(X) = x^(i) + x^(i+1) + … + x^(i+r-1)
= x^i * {1 + x + … + x^(r-1)}
（ただ、この最後の式でx～x^(r-2)までは、誤りによってあったりなかったりする筈です）
と表すことが出来て、生成多項式G(X)の次数がrであるとき、
1. x^iは（G(X)が2項以上の多項式であるなら）G(X)で割り切れない
2. {1 + x + … + x^(r-1)}は（次数がr-1であるから）G(X)で割り切れない
3. 従ってE(X)もG(X)で割り切れない
よって生成多項式の次数がrの場合、rビット以下のバースト誤りは検出できるとなっていますが、、、
いくら1.や2.がG(X)で割り切れなくても、それらの積（=E(X)）がG(X)で割り切れてしまうことはあるじゃないですか。
具体的には、i=1のとき、もしG(X)がx * {1 + x + … + x^(r-1)}であれば、割り切れますし、、、

同様の話で、
http://laputa.cs.shinshu-u.ac.jp/~yizawa/InfSys1/advanced/crc/
こちらのページの、「4.　巡回符号の誤り検出」という部分でも、
「これらは、3次の生成多項式、例えば G(x) = x^3+x+1 で割り切れないことは明らかです。」
という記述に対して、「例えばG(X) = x^3+x^2+x^1であれば割り切れてしまうのでは」と反論したくなります。

もちろん、割り切れないようなG(X)を選べばいいと言われればそれまでですが、、、以上の様にG(X)の内容によっては「G(X)の次数r以下のバースト誤りが検出できる」のが自明とは思えません。
そもそもそれが答え、、、？
どなたかご説明お願いしますm(_ _)m

回答No.4

Tacosan · ベストアンサー

あ～, 「既約多項式」の方が通りがいいかな?

お礼

なるほどっ、下の方のWikipediaページの情報にもありますけど、やっぱり「生成多項式は既約多項式であるのが一般的」と考えて良さそうですね(*^□^*)
そう考えると、質問で挙げた、G(X)の候補x * {1 + x + … + x^(r-1)}についても、既約でないからダメってことになって、納得です！！

どうもありがとうございましたm(_ _)m

回答No.3

seednyan

CRCは用途に応じて使用する多項式が決まっているようですね。

参考URL：

http://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E5%86%97%E9%95%B7%E6%A4%9C%E6%9F%BB

お礼

うーん、、、規格みたいな感じで？既に決まっている多項式もあるんですね。
でもそれはそれで学習の観点からだと「覚えるだけ」って感じだなぁ、、、＞＜

、、、って「CRC多項式の設計」の節を見たら、

>>新たなCRC多項式を作成したり、既存のCRCを改良する場合、多項式が既約性を持つようにするのが一般的である。すなわち
>>・この場合の既約性とは、多項式が自分自身か1でしか割り切れないことを意味する。
>>・既約でない多項式も使えるが、誤り検出力が劣る。しかし、用途によっては既約でない多項式を使っている場合もある。

とありますね！！
Wikipediaっていうのが残念ですが、参考になりました！
ありがとうございます(≧ω≦)

回答No.2

Tacosan

普通, CRC で「生成多項式」といえば原始多項式に決まっています. だから G(x) = x^3 + x^2 + x^1 というのはそもそも考えません.
「2.2 生成多項式とは」のところで「ｋ次の特別な多項式 G（x)」と書いてあるよね.

補足

こちらもお早いお返事ありがとうございます！
なるほど、生成多項式と言えば原始多項式、という前提があるのですね！
いま「原始多項式」について検索したところ、係数の最大公約数が1である多項式と出たのですが、、、
G(x) = x^3 + x^2 + x^1は、係数の最大公約数が1だから原始多項式ではないんですか？
x^0の係数が0だから最大公約数が1でない、とするにしても、質問で載せたページにあるG(x) = x^3+x+1も、x^2の係数が0ですし、、、＞＜

回答No.1

seednyan

数学は苦手ですが、少しだけコンピュータをかじったことがあるので。。CRCにはいろんなパターンがあることと、扱う数字は、"1","0"の２個しかありません。このある意味、特殊な条件下でしか成り立たないと思うしかありません。
なんせ、”デジタル”の”データ”の話なんで。。

お礼

お早いお返事ありがとうございます！
うーーーーーん、、、、、思うしかないですか＞＜
なんとか納得できる説明が欲しいです(´・ω・`)