CRC（巡回冗長検査）

📌

CRCとは

CRC（Cyclic Redundancy Check、巡回冗長検査）とは、送信するデータをあらかじめ決めた「生成多項式」で割り算し、その余りを検査用のビット（CRC）としてデータに付ける誤り検出方式です。

受信側は、受け取ったフレーム（データ + CRC）を同じ生成多項式で割り、余りが 0 なら誤りなし、0 でなければ誤りありと判断します。割り算といっても、繰り上がりのないXOR（モジュロ2演算）を使うのが特徴。上のツールで誤りを注入すると、余りが 0 でなくなり検出される様子が見られます。

🔢

生成多項式の使い方

生成多項式とは、割る数（除数）を多項式の形で表したものです。例えば x³ + x + 1 はビット列 1011 に対応します（各次数の係数が 0/1）。
・① 0 の付加：データの後ろに「生成多項式の次数」個の 0 を付ける（3次なら 0 を 3 個）
・② モジュロ2除算：先頭から見て 1 が立っていれば生成多項式を XOR、0 なら何もしない、を繰り返す
・③ 余りが CRC：最後に残った下位ビットが CRC。これをデータに付けて送る

送信フレームは生成多項式で割り切れるように作られているので、受信側で割って余りが出れば「途中で誤った」と分かる仕組みです。

⚖️

パリティとの違い

同じ誤り検出でも、パリティチェックと CRC では精度が大きく違います。
・パリティ：1ビット追加するだけで簡単だが、2ビット同時の誤りは検出できない（偶数個の誤りを見逃す）
・CRC：複数ビットの誤りやバースト誤り（連続した誤り）を高い確率で検出できる。計算はやや複雑だが回路で高速に実行できる

このため CRC はイーサネット・USB・ZIP・QRコードなど、信頼性が必要なほぼあらゆる場面で使われています。なお CRC は誤り検出のみで訂正はできない点に注意してください（訂正にはハミング符号などが必要）。

⊕

XOR（排他的論理和）とは何か

XOR（＝排他的論理和）とは、2つのビットが「違う」なら1、「同じ」なら0を返す計算です。CRCの割り算はこのXORを使った「繰り上がりのない特殊な引き算」として行われます。

なぜXORを使うのか。普通の割り算は繰り上がり・繰り下がりが発生して複雑になりますが、XORを使ったモジュロ2演算（＝2を法とした演算）は繰り上がりがないため、回路やプログラムで極めて高速に実装できます。これがCRCを実用的にしている核心です。

身近な例えは「鍵のかけ外し」です。XORを2回かけると元に戻ります（A ⊕ B ⊕ B = A）。これは「間違った鍵を2回かけると開く」のと同じで、CRCの誤り検出はこの「元に戻る」性質を利用しています。送信フレームを生成多項式でXOR除算したときに余りが0になるよう作っておけば、受信側は同じ除算で余りが0かどうか確認するだけでよいのです。

⚡

バースト誤りに強い理由

バースト誤り（＝連続して起こるビットの誤り）とは、ノイズや傷など現実の障害で起きやすい「まとまった誤り」のことです。例えばCDの傷で5ビット連続して読み取れないといったケースです。

なぜCRCはバースト誤りに強いのか。パリティチェックは「1の個数の偶奇」しか見ないため、連続した複数ビットの誤りが「偶数個」だと素通りしてしまいます。一方CRCはデータ全体を多項式として扱い、複数ビットにわたる誤りのパターン全体を生成多項式で割り算します。そのため、誤りが連続していても余りに影響が出やすく、検出率が高くなります。

具体的には、生成多項式が n 次（ビット長が n+1 のもの）であれば、n ビット以内のバースト誤りはすべて検出できるという保証があります。例えばイーサネット（＝有線LAN）で使われる CRC-32（32ビットのCRC）は、32ビット以内の連続した誤りを100%検出できます。現実の通信障害のほとんどはバースト誤りなので、CRCは非常に実用的な選択です。