情報理論と符号の基礎
生成多項式の次数がr(検査ビットがrビット)で、定数項が1のCRCの性質として、正しいものはどれか。
- A1ビットの誤りなら、どのビットが誤ったかを特定して訂正することが、主な使い方である
- B長さがrビット以下のバースト誤り(連続した範囲に収まる誤り)は、すべて検出できる
- C生成多項式をうまく選べば、どのような誤りのパターンでも、すべて検出できる
答えと解説を見る
正解：B. 長さがrビット以下のバースト誤り(連続した範囲に収まる誤り)は、すべて検出できる
誤りのパターンを多項式 E(x) で表すと、CRCで検出できないのは、E(x) が生成多項式 G(x) で割り切れるときだけです。長さr以下のバースト誤りは x^i × B(x)(B(x) は次数がr − 1以下で、定数項が1)と書け、定数項が1のr次の G(x) では割り切れないので、必ず検出できます。一方、G(x) そのものの形の誤りのように、割り切れるパターンは検出できません。CRCは主に誤りの検出に使われ、誤りがあればデータを送り直してもらいます。
- A. CRCは主に誤りの検出に使い、誤りがあれば送り直してもらいます。訂正には、ハミング符号などの誤り訂正符号を使います。
- B. 正しい。長さr以下のバースト誤りは、生成多項式で割り切れないので、必ず検出できます。
- C. 誤りのパターンが生成多項式で割り切れると、余りが変わらないので検出できません。どの生成多項式にも、このようなパターンがあります。