CRC

CRC（Cyclic Redundancy Check）を具体的な数値例で「手計算の流れが追える形」で説明します。

ここでは一番シンプルな CRC-4（小さな例） を使います。

⸻

1. 前提（今回の条件）

データ（送信したいビット列）

1101

生成多項式（Generator Polynomial）

G(x) = 1011

これはビット列としては：

• 1x³ + 0x² + 1x + 1

⸻

2. CRCの基本手順

CRCはこの3ステップです：

① 0を追加（冗長ビット分） ② mod 2 の割り算 ③ 余りをCRCとして付加

⸻

3. ステップ①：0を追加

生成多項式の長さは 4ビットなので

1101 → 1101000

（末尾に3つの0を追加）

⸻

4. ステップ②：mod 2 除算（XOR割り算）

CRCは普通の割り算ではなく：

引き算 = XOR（排他的論理和）

です。

⸻

計算過程

初期状態

1101000 ÷ 1011

⸻

1回目

左4ビット：

1101 ⊕1011

0110

次のビットを下ろす：

01100

⸻

2回目（先頭0なのでスキップ）

1100

⸻

XOR

1100 ⊕1011

0111

次のビットを下ろす：

1110

⸻

3回目

1110 ⊕1011

0101

次のビットを下ろす：

1010

⸻

4回目

1010 ⊕1011

0001

次のビットなし

⸻

5回目（最後）

0001 → 余り

⸻

5. ステップ③：CRC完成

余りは：

0001

⸻

送信データ

1101 + 0001 = 11010001

⸻

6. 受信側の検証

受信側はこれを同じように割ります：

11010001 ÷ 1011

⸻

結果

• 余りが 0 → OK
• 余りが 0以外 → エラー

⸻

7. なぜこれで検出できるのか

CRCはこういう性質を使っています：

正しいデータは「特定の生成多項式で割り切れる」

つまり：

正常データ → remainder = 0 破損データ → remainder ≠ 0

⸻

8. 直感的な理解

CRCは実はこういうものです：

イメージ

データを「数学的な整形ルール」に従って加工しておき そのルールに合わなければ壊れていると判断する

⸻

9. ポイント

CRCの本質

• データを多項式として扱う
• XORで割り算する
• 余りを付加する
• 受信時に割り切れるか確認する

⸻

性質

項目 内容 目的 誤り検出 修復 できない 計算 XORのみ（軽い） 強さ バースト誤りに強い

⸻

10. まとめ

CRCとは「データを多項式として扱い、特定のルール（生成多項式）で割り切れるかどうかで破損を検出する仕組み」です。

⸻