通信で受け取ったビット列は、見た目だけでは途中で変わったか分かりません。そこで送信側は、データから計算した短い検査値を添えます。受信側が同じ規則で計算し直して食い違えば、届いた列に問題があると気づけます。
CRC（巡回冗長検査）は、この検査値をビット列を表す多項式の割り算の余りから作る方式です。短い範囲にまとまった誤りを確実に見つけられる一方、余りが同じになる別の列も存在します。小さな計算例から、その二つが両立する理由をたどります。
簡単にまとめると？
- CRCの割り算では、桁上がりのある引き算の代わりにXORを使います。送信側と受信側で、生成多項式やビットの扱いをそろえる必要があります。
- 次数r、定数項1の生成多項式なら、最初と最後の誤りの間がrビット以内に収まる非ゼロの誤りを検出できます。
- 検査を通ったことは無誤りの証明ではありません。CRCだけで誤った場所を直したり、送り手の真正性を保証したりはできません。
0と1の列を、XORで割る
まず、実際の通信規格より小さい説明用の例を使います。データは4ビットの1101、割る側は1011とします。ビット列を左から高い次数の係数として読むと、1101はx³ + x² + 1、1011はx³ + x + 1です。割る側の式を生成多項式と呼びます。
係数は0と1だけで、足し算も引き算も2を法として行います。同じ桁の1と1は0になり、隣の桁への繰り上がりや繰り下がりはありません。これは、二つのビットが違うときだけ1になるXOR（排他的論理和）と同じ操作です。
生成多項式の最高次数は3なので、検査値の場所としてデータの末尾に0を3個足します。1101000の左端の1へ1011を合わせ、XORして消し、次の左端の1へ合わせ直します。筆算をビット列で書くと、次のようになります。
1101000
XOR 1011000
--------
0110000
XOR 0101100
--------
0011100
XOR 0010110
--------
0001010
XOR 0001011
--------
0000001残った3ビットの余りは001です。最初に空けた場所へ入れると、送る列は1101 001になります。この列を1011で割ると余りは000。最後に同じ余りをXORしたことで、割り切れる列ができたためです。
ここでは、初期値0、末尾反転なし、左を高い次数とする素朴な多項式モデルに限定しています。この7ビットの列を、そのまま実用のCRC-16やCRC-32の検査値と比較することはできません。
受信側には、変わった場所の余りが残る
受信側は、検査値を含む7ビット全体を同じ1011で割ります。何も変わらなければ余りは000ですが、最後の1ビットが反転して1101000になれば、余りは001です。データ部分だけでなく、添えた検査値の誤りも検査対象になります。
この仕組みは、受信した列を「送った列」と「反転した場所だけを1にした誤りパターン」のXORとして考えると見通せます。多項式の余りはXORに対して線形です。送った列の余りが0なので、受信側に残るのは誤りパターンを割った余りです。
図の3段目にある誤り0001011は、生成多項式1011そのものです。これは割り切れるため、受信列の余りも000になります。元のデータ1101が1100へ変わったことを、この検査だけでは見抜けません。RFC 3385も、誤りが別の正しい符号語へ移る場合に見逃しが起きると説明しています。
「3ビット以内」は、反転した個数ではなく広がり
CRCが得意なバースト誤りとは、ある範囲にまとまって起きる誤りです。その長さは、最初に反転した位置から最後に反転した位置までを、両端を含めて数えます。間のビットは変わっていなくても構いません。たとえば101は反転数が2個、バースト長は3です。
次数rで定数項が1の生成多項式は、長さr以下の非ゼロのバースト誤りを必ず検出します。位置のずれを表すxの累乗を取り除くと、その誤りの多項式は次数r未満です。より高い次数の生成多項式では割り切れず、しかも定数項1なので位置をずらしてもこの性質は変わりません。
今回のr＝3の例なら、長さ1〜3の誤りはどこにあっても検出できます。7ビットの枠に置けるそのようなパターン23種類を全て計算し、余りが0にならないことを確かめました。一方、先ほど見逃した1011は長さ4です。これは実機の通信試験ではなく、決めた多項式に対する全列挙計算です。
長さがrを超えると全てを見逃すわけでもありません。検出されるかどうかは、その誤りパターンが生成多項式で割り切れるかで決まります。「何ビットのCRCか」に加えて、多項式、保護するデータの長さ、想定する誤りの分布が重要になる理由です。
実際の規格では、初期値と並べ方まで合わせる
実装でCRCの値が一致しないときは、多項式だけを確認しても足りません。計算を始める値、入力ビットを処理する向き、最後の反転、検査値を送るバイト順、どのフィールドまで計算に含めるかを照合します。どれかが違えば、同じデータでも別の値になります。
具体例として、PPPのフレーム形式を定めるRFC 1662の付録C.2では、16ビットFCSの初期値は0xffffです。送信時には計算値を全ビット反転し、下位バイトから付けます。受信時はFCSを含めて計算し、0xf0b8との一致を調べます。説明用モデルの「余り0」を実装へ直接持ち込むと、正しいフレームまで失敗と判定してしまいます。
CRCに食い違いがあれば、誤りの検出まではできても、それだけで元の値は一意に決まりません。受信側が捨てて再送を待つのか、別の誤り訂正を使うのかは、その上の通信設計の仕事です。また、生成規則を知る相手は変更後のデータに合わせて検査値も作り直せます。意図的な改ざんやなりすましを防ぐ用途には、認証付きの仕組みを別に用意する必要があります。
CRCを評価するときは、まず対象規格の計算条件をそろえ、既知の検査値で動作を確認します。そのうえで、検出できる誤りの範囲と、残る見逃しを分けて読むと、検査を通ったという結果を過大に解釈せずに済みます。
出典
- RFC 3385 — iSCSI CRC/Checksum Considerations（2002年9月、Informational）。第1・3節の誤りモデル、線形性、見逃しの条件を参照。現行の実装値を一律に定める規格ではありません。
- RFC 1662 — PPP in HDLC-like Framing（1994年7月、STD 51）。第3.1節のFCSと付録C.1〜C.2の16ビットFCS処理を参照。本文の3ビット例と図はQuantum Seaによる説明用の独自計算です。