基本情報技術者 2010年 秋期 午前（科目A） 問04

生成多項式で割った余りを付加して送信する誤り検査方式はどれか【午前2 解説】

要点まとめ

• 結論：送信側が生成多項式で割った余りをビット列に付加し受信側で同じ多項式で割り切れるか検査する方式はCRC方式です。
• 根拠：CRCはビット列を多項式で表現して剰余（余り）を付与し，受信側で除算結果が零か否かで誤りを判定します。
• 差がつくポイント：パリティは単純な奇偶検査，ハミングは誤り訂正が目的で，問題文の「生成多項式」「余りを付加」という記述でCRCと判断できます。

正解の理由

よくある誤解

• CRCは誤り訂正ができると思いがち：CRCは誤り検出が目的であり，誤りの位置や訂正はできません（訂正は別の符号が必要）。
• 「パリティ」＝CRCと誤認：パリティ方式は各ブロックのビットの奇偶を記録する単純検査で，多項式除算や余りの概念は使いません。
• 生成多項式の意味を見落とす：問題文の「生成多項式で割る」という表現を見逃すとハミング符号など他方式と混同しやすいです。

解法ステップ

1. 問題文のキーワード抽出：「生成多項式」「割った余りを付加」「同じ生成多項式で割り切れるか」を確認する。
2. キーワード照合：生成多項式と余りを付加する手順はCRCの定義そのものと一致するためCRCを選ぶ。
3. 他選択肢との対比で確定：パリティやハミングは「余りを付加して同じ多項式で除算する」手順を持たない点を確認する。

• 送信側：メッセージ $M(x)$ に $r$ 個の 0 を付けて $M(x)x^r$ とし，$G(x)$ で除算して余り $R(x)$ を得る。送信符号語は $$T(x)=M(x)x^r+R(x)$$
• 受信側：$T(x)$ を $G(x)$ で除算し余りが $0$ なら誤りなし。

• $G(x)$ を多項式で表すと係数列は 1011（上位から）。手計算で除算して余りを求め，それを付加して送ります。

選択肢別の誤答解説

• ア: CRC方式 — 正解。生成多項式による除算で余りを付加／検査する方式であるため本文の記述と一致します。
• イ: 垂直パリティチェック方式 — 誤り。垂直パリティは列ごとの奇偶ビットをチェックする方式で，多項式除算や余りの付加は行いません。
• ウ: 水平パリティチェック方式 — 誤り。水平（各フレームやバイトごと）のパリティビットを付ける単純な誤り検査で，生成多項式や剰余の概念は使いません。
• エ: ハミング符号方式 — 誤り。ハミング符号は位置に応じた冗長ビットを用いて単一ビット誤りを検出・訂正する誤り訂正符号で，生成多項式で割った余りを付加する方式ではありません。

補足コラム

• CRCの強みは「短い冗長ビットで多くの誤りパターン（特にバースト誤り）を高確率で検出できる」点にあります。生成多項式の次数 $r$ は付加されるCRCビット数を決め，典型的には CRC-16, CRC-32 などの定められた多項式が使われます。
• 検出能力の例：次数 $r$ の生成多項式は長さ $\le r$ のバースト誤りを必ず検出しますが，任意の多ビット誤りを完全に検出するわけではありません。用途に応じた多項式選定が重要です。

FAQ