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

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

要点まとめ

• 結論→CRC方式が正解。送信側で生成多項式で割った余りを付加し、受信側で同多項式で割り切れるかで誤りを判定します。
• 根拠→CRCはデータを多項式とみなし，生成多項式で除算して得た余りを付加する巡回冗長検査（Polynomial CRC）です。
• 差がつくポイント→問題文の「生成多項式」「余り」「割り切れる」のキーワードを見落とさず即座にCRCを選べるかが得点差に直結します。

正解の理由

よくある誤解

• 「パリティチェック方式でも生成多項式を使う」と混同する誤り：垂直／水平パリティは単純なビット和（XOR）による誤り検出で、生成多項式による除算という概念は含みません。
• 「CRCは誤り訂正も行える」と考える誤り：CRCは主に検出用であり，単独での訂正能力はありません（外部処理や冗長手法が必要）。
• 「ハミング符号と同じ仕組み」と思う誤り：ハミング符号は誤り訂正（単一ビット訂正など）を目的とした符号で方式が異なります。

解法ステップ

1. 問題文のキーワードを抽出：「生成多項式」「余り」「割り切れる」などの語句を確認。
2. 各選択肢の特徴と照合：CRCは生成多項式＋余り、パリティは行・列の単純な奇遇チェック、ハミングは訂正符号。
3. 最短で回答：キーワードに一致するCRC（ア）を選ぶ。

選択肢別の誤答解説

• ア: CRC方式 — 正解。生成多項式で除算し余りを付加、受信で割り切れるかを判定する巡回冗長検査法です。
• イ: 垂直パリティチェック方式 — 各ビット位置（列）ごとにパリティビットを付けて誤り検出を行う方式で、生成多項式や余り除算は使いません。二次元パリティの縦方向に相当する考え方です。
• ウ: 水平パリティチェック方式 — 各データ単位（行）ごとにパリティを付加する方式で、単純な偶奇検査により一部の誤りを検出しますが、生成多項式で割る方式ではありません。
• エ: ハミング符号方式 — パリティビットを配置して誤り位置を特定し単一ビット訂正が可能な符号方式で、CRCのような多項式除算による余り判定ではありません。

補足コラム

• CRCの仕組み（数学的表現）
  データ多項式を $D(x)$、生成多項式を $G(x)$（次数$r$）とすると、送信する多項式は $$T(x)=D(x)\cdot x^r+R(x)$$ であり、$R(x)$ は $D(x)\cdot x^r$ を $G(x)$ で割ったときの余り（次数 $<r$）です。受信側で $T(x)$ を $G(x)$ で割って余りが0なら整合と判定します。
• 検出能力の目安：適切な $G(x)$ を選べば単一ビット誤りや一定長以下のバースト誤りを高確率で検出できます（CRC-16, CRC-32 等の実用的生成多項式が存在）。
• 実装面：ハードウェアではLFSR（線形帰還シフトレジスタ）により高速に計算できます。簡易的なソフト実装例は以下のようになります。

# 簡易的なビット演算によるCRC（例、8ビットポリで概念示す）
def crc_compute(data_bytes, poly, r):
    reg = 0
    for b in data_bytes:
        reg ^= b << (r - 8)  # 簡易表現：データを上位寄せで混ぜる
        for _ in range(8):
            if reg & (1 << (r + 7)):  # 最上位ビットのチェック
                reg = (reg << 1) ^ poly
            else:
                reg <<= 1
            reg &= (1 << (r + 8)) - 1
    return reg >> 8  # 余りを返す（概念例）

FAQ