CRC｜巡回冗長検査で通信誤り検出

2025.09.27

CRC

CRC（Cyclic Redundancy Check）は、送受信データや保存データに付与する冗長ビット列であり、符号多項式による剰余演算を用いて効率よく誤り検出を行う方式である。単純なパリティや加算チェックサムに比べ、連続したビット反転（バースト誤り）への検出能力が高く、通信プロトコル、ストレージ、ファイル形式など広範に用いられている。検出器としての本質は、生成多項式で割った剰余がゼロになる符号語のみを正当とみなす点にある。符号化・検査はシフトレジスタやXOR回路で実装でき、ソフトウェアでもルックアップテーブルやビット演算で高速化が可能である。

Table Of Contents

基本原理と数学的背景

CRCは2進数列を多項式として解釈し、あらかじめ定めた生成多項式G(x)で割った剰余R(x)を冗長情報として付加する。受信側は同じG(x)で割り、剰余が0であればエラーなしと判断する。演算はGF(2)上の加算（XOR）とシフトで構成され、乗算や除算もXORとシフトで表現できるため、ハードウェア・ソフトウェアの双方で軽量に実装できる。

生成多項式とパラメータ

代表的なCRCは生成多項式（degree、タップ位置）だけでなく、初期値（Init）、入力・出力のビット反転（RefIn/RefOut）、最終XOR（XorOut）、入力・出力のビット順序（LSB/MSB）など複数のパラメータで規定される。実務では「同じ名称でもパラメータが異なる実装」が存在するため、版管理文書や規格票で厳密に整合させることが重要である。

符号化の手順（送信側）

  1. データ多項式M(x)を用意する（必要ならば初期値や反転を適用）。
  2. M(x)に生成多項式の次数kだけ0を付加し、G(x)で割る。
  3. 得られた剰余R(x)をフレーム末尾に付与し、符号語C(x)=M(x)·x^k+R(x)として送信する。

検査の手順（受信側）

  1. 受信符号語C′(x)に対し、送信側と同一の手順（反転、順序、初期値）で前処理する。
  2. G(x)で割り、剰余が0（または規格で定める検査値）であれば合格とする。

代表的な規格と用途

  • CRC-8/CRC-16：組込み機器やシリアル通信で広く採用。CAN（Classical/FD）など。
  • CRC-CCITT（X.25）：通信系の歴史的実装で知られる。
  • CRC-32（IEEE 802.3）：イーサネット、ZIP、PNGなどファイル/リンク層で標準的。
  • CRC-64（ECMAなど）：大規模データの誤り検出や重複排除で利用。

用途は物理・データリンク層のフレーム保全、ストレージのブロック整合性、アーカイブの整合性確認など多岐にわたる。アンテナや伝送路の雑音に起因する反転誤りに対し、高い検出性能を示す。

エラー検出能力と限界

CRCは選んだ生成多項式に応じて、検出できる誤りパターンの保証が与えられる。一般に、単一ビット誤り、二重ビット誤り、奇数重み誤り、特定長以下のバースト誤りの完全検出などが達成できる。Hamming距離は符号語集合の最小距離であり、最小距離dであれば（d−1）個までの誤り検出が理論上保証される。一方でCRCは誤り訂正符号ではないため、自動修復は行わない。誤り訂正が必要なら誤り訂正（FEC）やハイブリッドARQの導入を検討する。

パリティ・チェックサムとの比較

単純パリティは奇数個の反転検出に限定され、チェックサム（加算和）は桁落ちや交換に弱い。これに対しCRCは多項式除算に基づき、特定長以下のバースト誤りを理論的に保証して検出できる。計算コストはやや高いが、ハードウェア実装（LFSR）やテーブル化により実運用では十分低廉である。

実装の勘所（ソフトウェア）

  • テーブル駆動：256エントリ×NバイトのLUTで1バイト単位更新を高速化する。
  • ビット反転・順序：RefIn/RefOutやビットエンディアンの取り扱いを規格と一致させる。
  • 初期値・最終XOR：InitとXorOutを誤ると相互運用に失敗する。テストベクトルで検証する。
  • 並列化：64bit幅ロードやPCLMULQDQ（キャリーなし乗算）による高速CRC-32など。

実装の勘所（ハードウェア）

LFSR（Linear Feedback Shift Register）で実装する。Galois型やFibonacci型の配線差に留意し、スループット要件に応じてアンロールやパイプライン化を行う。FPGA/ASICではXORツリーの遅延、配線長、リソース使用量のバランスが設計ポイントとなる。

多項式選定の指針

用途の誤りモデル（ランダム誤りか、突発性の高いバースト誤りか）とフレーム長から候補を絞る。例えばCRC-32（0x04C11DB7）は広い用途で実績があり、CRC-16-IBMやCRC-16-CCITTは短フレームで使いやすい。近年は最小距離の下限やバースト検出長を最適化した候補も提案されている。

通信システムとの関係

物理層・リンク層では変調や拡散と組み合わせて信頼性を高める。例えばAMやFM、多値のQAM、直交多重のOFDMといった変調方式の上で、フレーミングの末尾にCRCを付与する。拡散符号を用いるスプレッドスペクトラムや周波数ホッピングでも、上位層のFCSとしてCRCが機能する。

よくある実装不整合と検証

  • 送受で反転規則が一致しない（RefIn/RefOutの取り違え）。
  • 初期値・終端XORの未統一、ゼロパディング長の相違。
  • ビット順序（LSBファースト/MSBファースト）の誤解。
  • テーブル生成多項式の表記ミス（0x04C11DB7と0xEDB88320の相互表現）。

対策として、規格が配布する既知のテストベクトル（入力と期待CRC値）で往復検証を行い、異機種間や異言語実装の整合を確保する。

データ保全設計への組み込み

ログ構造ファイルやジャーナリング、パケット再送制御と組み合わせ、検知→再送/再読→復旧というレイヤ化を設計する。ストレージではブロックごとにCRCを保持し、メタデータ領域とは分離して耐損傷性を高める。通信ではMTUやフレーミングの境界に合わせ、バースト誤り長の保証と再送コストを最適化する。

用語メモ

FCS（Frame Check Sequence）：フレーム末尾に付く検査列。LFSR：線形帰還シフトレジスタ。Hamming距離：符号語間の最小ハミング距離。バースト誤り：連続ビット反転。RefIn/RefOut：入出力のビット反転。XorOut：最終XORの定数。

コメント（β版）