CRC（巡回冗長検査）
送信データを生成多項式で多項式の割り算（XOR）し、その余りを CRC として付ける。割り算を 1 段ずつ動かして、なぜ誤りが検出でき、なぜ一部のパターンはすり抜けるのかを体感します。
送信データ
生成多項式 G
データ M（ビット数 k）
—
CRC ビット数 r
—
CRC（＝余り）
—
多項式の割り算（mod-2 ＝ 桁上がりなしの XOR 引き算）— G の最上位が立つ桁で XOR、1 段ずつ右へ
—
受信側：ビットを反転させて誤りを起こす
送信される符号語（データ＋CRC）。クリックで通信路ノイズを再現＝そのビットを反転
—
CRC はデータビット列を 1 つの多項式とみなします（各ビットが
こうして作った符号語は必ず G で割り切れます。受信側はもう一度 G で割り、余りが 0 なら誤りなし、 0 でなければ誤りありと判定します。
ただし、化けたビットの「誤りパターン」がたまたま G の倍数になると、余りが 0 のまま＝すり抜け（検出漏れ）が起きます。
x の係数）。
データの後ろに r 個の 0 を付けてから、あらかじめ決めた生成多項式 Gで
mod-2 の割り算（引き算が XOR になる割り算）を行い、その余りを CRC として末尾に書き込みます。こうして作った符号語は必ず G で割り切れます。受信側はもう一度 G で割り、余りが 0 なら誤りなし、 0 でなければ誤りありと判定します。
ただし、化けたビットの「誤りパターン」がたまたま G の倍数になると、余りが 0 のまま＝すり抜け（検出漏れ）が起きます。
いま何が起きている？
ここが CRC の核心
- CRC は余り＝データを生成多項式で割った剰余。引き算はすべて XOR（桁上がりなし）。
- 受信側で再度割り、余り 0 なら OK・非0 なら誤り。訂正はせず検出だけ（ハミング符号との違い）。
- 誤りパターン E が G の倍数のときだけ検出漏れ。良い G を選べば連続ビット誤り（バースト）に強い。
- Ethernet・ZIP・USB など、ばらまかれた短い検査ビットで巨大なデータの破損を高速に弾く実用技術。