日本語
メニュー

CRC(巡回冗長検査)とは

しーあーるしー

データのビット列を多項式とみなして生成多項式で割った余りを検査用の値として付け、受け取った側で同じ計算をしてデータの誤りを検出する方法。イーサネットやPCI Express、USB、ファイル形式などで広く使われる。

「CRC(巡回冗長検査)」は、2分野の4問の練習問題に出てきます(論理回路, インターフェース・バス規格など)。

この用語の分野: インターフェース・バス規格

しくみ

CRCは、データのビット列を2を法とする多項式の係数とみなし、生成多項式で割った余りを求めます。2を法とする計算では足し算も引き算もXORなので、割り算は「先頭が1なら生成多項式をXORして1桁ずらす」の繰り返しになります。幅wビットのCRCでは、データの後ろにw個の0を付けて割った余りのwビットを付けて送り、受け取った側で同じ計算をして一致するかを確かめます。実際の規格では、初期値、各バイトのビット反転、最後のXORなどの約束を加えて定義されます。

検出できる誤りと使われる場所

幅wビットのCRCは、長さw以下の連続した誤り(バースト誤り)をすべて検出でき、それ以外のでたらめな誤りを見逃す確率もおおよそ2⁻ʷと小さくなります。ただし誤りを見つけるだけで訂正はできないので、見つけたら再送などで回復します。イーサネットのFCS(CRC-32)、PCI Expressのパケット、USB、CAN、ストレージのコマンドやZIP・PNGなどのファイル形式で使われ、ハードウェアではフリップフロップとXORゲートの線形帰還シフトレジスタで計算できます。

CRC(巡回冗長検査)の練習問題に挑戦

2入力XOR(排他的論理和)ゲートの出力が1になるのはどのときか。

  1. A2つの入力がともに1のとき
  2. B2つの入力が異なるとき
  3. C2つの入力がともに0のとき
答えと解説を見る

正解：B. 2つの入力が異なるとき

XORは2つの入力が異なるとき1、同じとき0を出力します。式では A⊕B = A・¬B + ¬A・B です。「一方の入力が1なら他方を反転、0ならそのまま通す」と見ることもでき、制御付きインバータとして使えます。半加算器の和、比較回路(一致検出はXNOR)、パリティの計算、暗号のストリーム暗号やCRCの計算など、用途が広いゲートです。

シフトレジスタの一部の出力のXORを入力に戻す線形帰還シフトレジスタ(LFSR)の代表的な用途はどれか。

  1. A疑似乱数パターンの生成や、テストでのパターン生成・CRC計算
  2. B正確な時刻を計る
  3. Cアナログ信号を増幅する
答えと解説を見る

正解：A. 疑似乱数パターンの生成や、テストでのパターン生成・CRC計算

LFSRは適切なタップを選ぶと、nビットで全0を除く 2ⁿ − 1 通りの状態を巡回する、一見ランダムな系列(M系列)を生成します。XORとフリップフロップだけで作れるため、内蔵テスト(BIST)のパターン生成と結果の圧縮、イーサネットなどのCRC計算、信号を平均化して電磁ノイズを減らすスクランブラに使われます。系列は予測可能なので、暗号用の乱数には使えません。

よくある質問

CRCとチェックサムの違いは?

チェックサムはバイトを足し合わせるなどの単純な計算で、順番の入れ替えや打ち消し合う誤りを見逃しやすいのに対し、CRCは多項式の割り算に基づくのでビットの位置まで区別し、バースト誤りなどを確実に見つけられます。

CRCで誤りを訂正できますか?

一般にはできません。CRCは誤りの有無を調べる符号で、どのビットが誤ったかは分からないため、訂正が必要なメモリなどではハミング符号などのECCを使います。

解説の中の「CRC(巡回冗長検査)」

「CRC(巡回冗長検査)」が出てくる問題(4問)

  1. 2入力XOR(排他的論理和)ゲートの出力が1になるのはどのときか。
  2. シフトレジスタの一部の出力のXORを入力に戻す線形帰還シフトレジスタ(LFSR)の代表的な用途はどれか。
  3. PCI Expressのデータリンク層が、伝送中のビットの誤りに対して行うこととして正しいものはどれか。
  4. PCI Expressで、64バイトの小さなデータを書き込むパケットを多数送ると、実効的な帯域が理論値よりかなり小さくなる。その主な理由はどれか。

インターフェース・バス規格の参考書を探す PR

Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。

半導体・電子回路・情報の計算ツール

CRC計算ツールCRC-8・CRC-16・CRC-32などを、文字列か16進数のバイト列から計算。多項式の割り算の途中も表示ハミング符号の計算ツールデータをハミング符号に符号化し、ビットを押して誤りを入れると、シンドロームで位置を求めて訂正する様子を確かめられます

関連する用語

PCI Express シフトレジスタ フリップフロップ BIST(組み込み自己テスト) アイソクロナス転送 アイパターン イコライザ 128b/130b符号化 AXI NRZ

用語集の一覧へ