とことこロゴス
メニュー

CRC

読み：しーあーるしー　／　英語表記：Cyclic Redundancy Check

送るビット列を多項式とみなし、あらかじめ決めた多項式で割った余りを検査用の値として付け、受信側も同じ計算をして誤りの有無を確かめる誤り検出方式である。連続したビットがまとめて化けるバースト誤りの検出に強く、イーサネットのFCSなどに使われる。誤りの位置を特定して直す誤り訂正の機能は持たない。

イマシルちゃんの解説

通信の途中でノイズが入ると、0と1が入れ替わる誤りが起きることがあるんだ。
CRCは、そんな誤りを見つけるための誤り検出方式だよ。
送る側はデータを決まった値で割り算して、その余りをデータの後ろに付けて送るの。
受け取った側も同じ割り算をして、余りが合わなければ途中で壊れたと分かるんだ。
この割り算は繰り上がりや繰り下がりを使わない特別な計算だから、回路で速く処理できるよ。
LANで送るフレームにも付いていて、壊れたデータをそのまま使わないように守ってくれるんだ。

より深い解説

誤り検出の中での位置付け

伝送路では、雑音や信号の劣化によってビットが反転することがある。受信側が誤りに気付くには、送信側がデータから計算した検査用の値を一緒に送る必要がある。CRC（Cyclic Redundancy Check：巡回冗長検査）は、この検査用の値を多項式の割り算で作る誤り検出方式である。

CRCで付ける検査用のビット列を、CRC値やチェックビットと呼ぶ。イーサネットでは、この値をフレーム末尾のFCS（Frame Check Sequence）フィールドに入れる。FCSはフレームの中の欄の名前であり、CRCはその値を計算する方式である。両者を同じものとして覚えると、「FCSにはどんな方式の値が入るか」という問いに答えられない。

CRCは誤りがあることを検出するだけで、どのビットが誤ったかは分からない。誤りを検出した受信側は、そのデータを捨てる。再送が必要なら、TCPのような上位の仕組みや、再送手順を持つデータリンクの制御に任せる。

ビット列を多項式として扱う

CRCでは、ビット列を各ビットを係数とする多項式とみなす。例えばビット列 1011 は、左から x^3、x^2、x^1、x^0 の係数と考えて x^3 ＋ x ＋ 1 を表す。

係数の計算は2を法として行う。足し算も引き算も繰り上がり・繰り下がりがなく、1 ＋ 1 ＝ 0 となる。つまりビットごとの排他的論理和（XOR）と同じである。このため多項式の割り算は、桁をそろえてXORを繰り返すだけで計算できる。シフトレジスタとXOR回路で実装でき、ハードウェアで高速に処理できる。

送信側と受信側があらかじめ決めておく割る数を生成多項式と呼ぶ。生成多項式の最高次数を r とすると、余りは常に r ビットになる。

送信側と受信側の手順

  1. 送信側は、データのビット列の後ろに r 個の0を付ける。多項式では x^r を掛けることにあたる。
  2. 0を付けたビット列を生成多項式で割り、r ビットの余りを求める。
  3. 付けた0の位置を余りで置き換えて送信する。これで送信するビット列全体は生成多項式で割り切れる。
  4. 受信側は、受け取ったビット列全体を同じ生成多項式で割る。
  5. 余りが0なら誤りなしと判断する。0以外なら誤りありと判断してデータを捨てる。

手順3で余りを足すと割り切れるのは、2を法とする計算では足すことと引くことが同じだからである。0を付けたビット列から余りを引けば、ちょうど割り切れる値になる。

計算例で確かめる

データを 11010011、生成多項式を x^3 ＋ x ＋ 1（ビット列 1011）とする。最高次数は3なので、データの後ろに0を3個付けて 11010011000 を割る。先頭が1の位置に 1011 をそろえてXORし、先頭の1を消していく。

11010011000
1011
-----------
01100011000
 1011
-----------
00111011000
  1011
-----------
00010111000
   1011
-----------
00000001000
       1011
-----------
00000000011   → 下位3ビットが余り

送信するビット列は、データの後ろに余りを付けた 11010011011 である。受信側がこれを 1011 で割ると、余りは 000 になる。

途中で左から5番目のビットが反転したとする。受信側が同じ割り算をすると余りは 101 となり、0ではないので誤りを検出できる。

見逃す誤りと検出できる誤り

送信したビット列を多項式 T(x)、誤りでビットが反転した位置を1で表した多項式を E(x) とする。受信したビット列は T(x) ＋ E(x) である。T(x) は生成多項式 G(x) で割り切れるので、受信側の余りは E(x) を G(x) で割った余りに等しい。

したがって、E(x) が G(x) の倍数になる誤りだけを見逃す。上の例で、送信ビット列の左から4〜7番目に 1011 の形の誤りが重なると、受信したビット列は 11000101011 になる。このときの余りは 000 であり、誤りを検出できない。

この性質から、生成多項式の選び方によって次の誤りを必ず検出できる。

誤りの種類必ず検出できる条件理由
1ビットの誤り生成多項式が2つ以上の項を持つE(x) ＝ x^i は2項以上の多項式で割り切れない
奇数個のビット誤り生成多項式が x ＋ 1 で割り切れる奇数個の項を持つ E(x) は x ＋ 1 で割り切れない
長さ r 以下のバースト誤り生成多項式の定数項が1である誤りの範囲が r ビット以内なら、E(x) は G(x) で割り切れない

ここでバースト誤りの長さは、最初に反転したビットから最後に反転したビットまでの範囲を数える。r ビットの余りを使うCRCは、長さ r ビット以下のバースト誤りをすべて検出できる。これより長いバースト誤りも大部分は検出できるが、すべてではない。

離れた位置の2ビット誤りには注意が必要である。上の例の生成多項式 x^3 ＋ x ＋ 1 は、x^7 ＋ 1 を割り切る。このため、ちょうど7ビット離れた2ビットが同時に反転すると見逃す。例えば送信ビット列の左から2番目と9番目を反転した 10010011111 の余りは000になる。実用のCRCは、データ長の範囲内でこのような見逃しが起きにくい生成多項式を選んでいる。

イーサネットのFCSの計算

イーサネット（IEEE 802.3）のFCSは32ビット（4オクテット）であり、次の生成多項式を使うCRC-32で計算する。

G(x) ＝ x^32 ＋ x^26 ＋ x^23 ＋ x^22 ＋ x^16 ＋ x^12 ＋ x^11 ＋ x^10 ＋ x^8 ＋ x^7 ＋ x^5 ＋ x^4 ＋ x^2 ＋ x ＋ 1

最高次の x^32 を除いた係数を16進数で書くと 0x04C11DB7 になる。計算の範囲は、宛先MACアドレスから、送信元MACアドレス、タイプ／長さ、データ、パディングまでである。同期用のプリアンブルとSFDは含まない。IEEE 802.3は、単純な割り算に加えて、先頭32ビットを反転してから計算するといった手順も定めている。

KoopmanのCRC多項式の評価によると、この多項式のハミング距離は、データ部分が91,607ビット以下なら4である。ハミング距離が4なら、それより1少ないビット数までの誤りは、どの位置で起きても検出できる。最大長1,518オクテットのベーシックフレームでFCSを除いた部分は1,514オクテット、つまり 1,514 × 8 ＝ 12,112ビットである。この範囲は91,607ビットより十分短いので、標準的なフレームでは3ビット以下の誤りを必ず検出できる。

受信したイーサネットフレームのFCSが一致しない場合、そのフレームは破棄される。イーサネット自体は誤りを通知したり再送したりしない。TCPを使う通信では、届かなかったデータをTCPが再送する。

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

誤りを扱う方式は、計算の手間と検出・訂正の能力が異なる。同じ「検査用の値を付ける」方式でも、何をどこまで見つけられるかを比べる。

方式検査用の値の作り方能力主な利用場面
パリティチェック1の個数が偶数か奇数かをそろえる1ビット奇数個の誤りは検出できるが、偶数個の誤りは見逃す単純な伝送やメモリ
インターネットチェックサム16ビット単位の1の補数和計算が軽い。CRCより検出能力は低いIPv4ヘッダー、TCP、UDP
CRC生成多項式で割った余り1ビット誤りとバースト誤りに強い。訂正はできないイーサネット、HDLC、無線LANなどのフレーム
ハミング符号複数の検査ビットの組合せ1ビットの誤りの位置を特定して訂正できるECCメモリなど

パリティチェックは1ビットの追加で済むが、2ビット同時の反転を見逃す。インターネットチェックサムはソフトウェアで計算しやすい足し算である。一方、データの順序が入れ替わるような誤りには弱い。CRCは回路で高速に計算でき、伝送路で起きやすい連続した誤りに強いため、データリンク層のフレームに使われる。

IPv6ではIPヘッダーのチェックサムが廃止された。データリンク層のCRCと、TCP・UDPのチェックサムで誤りを検出できるため、ルータごとの再計算を省いたのである。

意図的な改ざんは防げない

CRCは偶然の誤りを見つけるための方式であり、改ざん対策ではない。計算方法が公開されているため、データを書き換えた攻撃者は新しいCRC値を計算し直して付け替えられる。CRCは線形な計算なので、どのビットを反転すればCRC値がどう変わるかも予測できる。

無線LANの古い暗号化方式であるWEPは、改ざんの検査にCRC-32を使っていた。この線形性が、暗号文のビットを書き換えても検査を通してしまう弱点の一因になった。改ざんの検出には、鍵を使って計算するHMACなどのメッセージ認証コードを使う。

運用で見るFCSエラー

スイッチやルータのインタフェースでは、FCSが一致しなかったフレームの数をCRCエラーやFCSエラーとして数えている。この値の増加は、そのリンクの物理的な品質に問題があることを示す手掛かりになる。

観測した状態確認すること
特定のポートだけCRCエラーが増えるケーブルやコネクタの損傷、配線の長さ、光モジュールの受光レベル
片側だけで多くのエラーが出る両端の速度やデュプレックスの設定が一致しているか
隣接装置へエラーが広がるカットスルー方式のスイッチが、誤りのあるフレームを転送していないか
エラーは少ないが通信が遅い破棄されたフレームによるTCPの再送が起きていないか

フレーム全体を受信してFCSを確かめてから転送するストアアンドフォワード方式のスイッチは、誤りのあるフレームを転送しない。宛先MACアドレスを読んだ時点で転送を始めるカットスルー方式は、転送を始めた後でFCSの誤りに気付く。このため、誤りのあるフレームが次の区間へ伝わることがある。

午後での問われ方

午後問題では、CRCの計算そのものより、誤り検出の位置付けや障害の読み取りが問われやすい。

問われる場面押さえるポイント
フレームの構造FCSがフレームの末尾にあり、プリアンブルを除いた範囲から計算されることを読み取る
誤りを検出した後の動作受信側はフレームを捨てるだけで、再送はTCPなどの上位層が行うと説明する
インタフェースの統計CRCエラーの増加から、ケーブルや設定の不一致などの物理的な原因を推定する
スイッチの転送方式ストアアンドフォワードとカットスルーで、誤りのあるフレームの扱いが異なる理由を述べる
改ざん対策との区別CRCでは意図的な改ざんを検出できず、鍵を使うメッセージ認証が必要な理由を述べる

参考資料

この用語が出てくる記事

↑