Chapter 09

巡回符号と CRC — 多項式の割り算による誤り検出

本シリーズで最も実務に近い章. CRC (Cyclic Redundancy Check) は、あなたが今この文章を読むまでに何万回も実行されている。 Ethernet フレーム、Wi-Fi パケット、USB 転送、ZIP ファイル、PNG 画像、SATA、CAN バス—— データが動くところには必ずと言っていいほど CRC がいる。
そして中身は驚くほど単純である。データを多項式と見なして、決められた多項式で割った余りを付ける。それだけ。04 章で用意した多項式の除算が、そのまま産業標準になっている。
この章では ①なぜ「巡回」という構造が良いのか ②CRC の具体的手順 ③何が検出できて何ができないのか ④高速実装、まで通す。特に③は実務で誤解が多い部分なので、証明付きで押さえる。

1. 巡回符号 — 「ずらしても符号語」という構造

定義

線形符号\(C\)が、任意の符号語の巡回シフトもまた符号語であるとき、巡回符号という:

\[ (c_0, c_1, \dots, c_{n-1}) \in C \Longrightarrow (c_{n-1}, c_0, \dots, c_{n-2}) \in C \]

多項式表現

符号語\((c_0,\dots,c_{n-1})\)を多項式\(c(x) = c_0 + c_1x + \cdots + c_{n-1}x^{n-1}\)と同一視する。

すると巡回シフトは「\(x\)を掛けて\(x^n-1\)で割った余り」になる。

導出: \(x \cdot c(x) = c_0x + c_1x^2 + \cdots + c_{n-1}x^{n}\)。ここで\(x^n \equiv 1 \pmod{x^n-1}\)（\(\mathrm{GF}(2)\)では\(x^n+1\)）なので、最高次の項が定数項に回り込む:

\[ x c(x) \bmod (x^n-1) = c_{n-1} + c_0 x + c_1 x^2 + \cdots + c_{n-2}x^{n-1} \]

これは確かに 1 つ巡回シフトした符号語 ✓ ∎

この対応が本章のすべてを支える. 「ビット列の巡回シフト」という操作が、「\(x\)を掛ける」という代数になった。一度代数の言葉に翻訳できれば、多項式の理論（因数分解、既約性、根）が丸ごと使えるようになる。

生成多項式

定理: 長さ\(n\)の巡回符号は、\(x^n - 1\)の約数である多項式\(g(x)\)によって

\[ C = \{ m(x)g(x) : \deg m < n - \deg g \} \]

と表せる。この\(g(x)\)を生成多項式という。\(\deg g = n-k\)（検査ビット数）。

導出（あらすじ）: 符号語の中で最低次の非零多項式を\(g(x)\)とする。任意の符号語\(c(x)\)を\(g(x)\)で割って\(c = qg + r\)と書くと、線形性と巡回性から\(r\)も符号語でなければならないが、\(\deg r < \deg g\)は\(g\)の最小性に反する。よって\(r=0\)、つまり全符号語は\(g\)の倍数 ✓ また\(x^n-1\)を\(g\)で割った余りも同様の議論で 0 になるので\(g \mid x^n-1\) ∎

なぜ巡回符号が実装に有利なのか. 生成行列\(G\)（\(k\times n\)の行列、数百〜数千要素）を持つ代わりに、 生成多項式\(g(x)\)という短いビット列 1 本だけ持てばよい。しかも符号化は「多項式の掛け算・割り算」= シフトレジスタと XOR で実装でき、ハードウェアなら数十ゲートで済む。 CRC-32 の実装が数行で書けるのは、この構造のおかげである。

2. CRC の手順

符号化（送信側）

送りたいデータを\(k\)ビット、生成多項式\(g(x)\)の次数を\(r = n-k\)とする。

手順:

データを多項式\(m(x)\)と見なす
\(x^r\)を掛ける（= データを\(r\)ビット左シフト、後ろに 0 を\(r\)個並べる）
\(x^r m(x)\)を\(g(x)\)で割った余り\(R(x)\)を求める
送信する符号語を \(T(x) = x^r m(x) + R(x)\) とする（= データの後ろに余りを付ける）

\[ \boxed{T(x) = x^r m(x) + R(x), \qquad R(x) = x^r m(x) \bmod g(x)} \]

なぜこれで割り切れるのか

\(x^r m(x) = q(x)g(x) + R(x)\)なので

\[ T(x) = x^rm(x) + R(x) = q(x)g(x) + R(x) + R(x) = q(x)g(x) \]

（\(\mathrm{GF}(2)\)では\(R+R=0\) ✓）

つまり\(T(x)\)は必ず\(g(x)\)で割り切れる ∎

標数 2 のご利益がここに出ている. 普通の整数なら「余りを引く」必要があるが、\(\mathrm{GF}(2)\)では引き算 = 足し算なので 余りをそのまま後ろにくっつけるだけで割り切れる形になる。実装が 1 手減る。

検査（受信側）

受信語\(T'(x)\)を\(g(x)\)で割る:

余り = 0 → 誤り無しと判定
余り ≠ 0 → 誤りを検出

さらに、誤りを\(E(x)\)として\(T'(x) = T(x) + E(x)\)と書くと

\[ T'(x) \bmod g(x) = \underbrace{T(x)\bmod g}_{=0} + E(x)\bmod g = E(x) \bmod g(x) \]

07 章のシンドロームと同じ構造である. 余りは送ったデータに依らず、誤りパターンだけで決まる。そして決定的に重要な帰結:
CRC が誤りを見逃す \(\iff\) 誤りパターン\(E(x)\)がちょうど\(g(x)\)の倍数
したがって「どんな誤りを検出できるか」は、「どんな\(E(x)\)が\(g(x)\)で割り切れてしまうか」を調べる問題に完全に帰着する。§4 でこれを行う。

3. 手計算の実例

データ: 1101（\(m(x) = x^3+x^2+1\)） 生成多項式: \(g(x) = x^3 + x + 1\) = 1011（\(r = 3\)）

ステップ 1: データを 3 ビット左シフト → 1101000（\(x^3m(x) = x^6+x^5+x^3\)）

ステップ 2: 1101000 を 1011 で割る（XOR の筆算）:

\[ \begin{aligned} &\underline{1101000}\\ &\underline{1011}\phantom{000} \quad \leftarrow \text{最上位を消す}\\ &\phantom{1}1100\phantom{00}\\ &\phantom{1}\underline{1011}\phantom{00}\\ &\phantom{11}1110\phantom{0}\\ &\phantom{11}\underline{1011}\phantom{0}\\ &\phantom{111}1010\\ &\phantom{111}\underline{1011}\\ &\phantom{1111}001 \end{aligned} \]

各段階を式で追うと:

\(1101000 \oplus 1011000 = 0110000\)
\(0110000 \oplus 0101100 = 0011100\)
\(0011100 \oplus 0010110 = 0001010\)
\(0001010 \oplus 0001011 = 0000001\)

余り\(R\) = 001

ステップ 3: 送信符号語 = 1101 + 001 = 1101001

検算: 1101001 を 1011 で割ると余りが 0 になるはず。

\(1101001 \oplus 1011000 = 0110001\)
\(0110001 \oplus 0101100 = 0011101\)
\(0011101 \oplus 0010110 = 0001011\)
\(0001011 \oplus 0001011 = 0000000\) ✓ 割り切れた

誤りを入れてみる: 3 ビット目が反転して 1111001 を受信したとする。

\(1111001 \oplus 1011000 = 0100001\)
\(0100001 \oplus 0101100 = 0001101\)
次数が足りないのでここで終了 → 余り 101 ≠ 0 → 誤り検出 ✓

4. CRC の検出能力（実務で最も重要な節）

\(g(x)\)の次数を\(r\)とする。以下、すべて「\(E(x)\)が\(g(x)\)の倍数にならない」ことを示す形で証明する。

(a) すべての 1 ビット誤り

1 ビット誤りは\(E(x) = x^i\)。 \(g(x)\)が2 項以上を持つ（定数項と最高次項が両方 1 など、少なくとも 2 つの項がある）なら、 \(x^i\)は\(g\)で割り切れない（\(g\)は\(x\)のべき単項式ではないため）。

→ 必ず検出 ✓

(b) すべての 2 ビット誤り

\(E(x) = x^i + x^j\)（\(i<j\)）\(= x^i(1 + x^{j-i})\)。

\(g(x)\)の定数項が 1 なら\(g\)は\(x\)を因数に持たないので、\(g \mid E\) となるには\(g \mid (1+x^{j-i})\)が必要。

ここで\(g(x)\)が\(1+x^L\)を割り切る最小の\(L\)（\(g\)の周期）を考える。 \(g\)が原始多項式なら\(L = 2^r - 1\)になる。

→ データ長が\(2^r-1\)ビット未満なら、すべての 2 ビット誤りを検出 ✓

（CRC-32 なら\(2^{32}-1 \approx 4\times10^9\)ビット = 512 MB。通常のパケットでは問題にならない。）

(c) すべての奇数個の誤り

定理: \(g(x)\)が\((x+1)\)を因数に持つなら、奇数個のビット誤りを必ず検出する。

導出: \(E(x)\)の項の個数が奇数だとする。\(x = 1\)を代入すると、 \(\mathrm{GF}(2)\)では各項が 1 になるので

\[ E(1) = \underbrace{1 + 1 + \cdots + 1}_{\text{奇数個}} = 1 \]

一方\(g(x) = (x+1)h(x)\)なら\(g(1) = (1+1)h(1) = 0\)。もし\(E\)が\(g\)の倍数\(E = gq\)なら\(E(1) = g(1)q(1) = 0\)となり、\(E(1)=1\)と矛盾 ∎

→ \(g\)に\((x+1)\)の因数を入れておけば、奇数個の誤りは全部検出 ✓

実用の生成多項式はこの性質を必ず持たせてある. CRC-32 の\(g\)は\((x+1)\)を因数に持つ。だから「奇数個のビット反転」は 100% 検出される。

(d) 長さ\(r\)以下のバースト誤り

バースト誤りとは、連続する区間の中で誤りが起きること（区間の両端は必ず誤り）。長さ\(b\)のバーストは

\[ E(x) = x^i \cdot B(x), \qquad \deg B = b-1,\ B\ \text{の定数項} = 1 \]

と書ける（\(x^i\)がバーストの開始位置、\(B\)がバーストの中身）。

\(b \leq r\)のとき: \(\deg B = b-1 < r = \deg g\)なので、\(B\)は\(g\)で割り切れない（次数が足りない）。 \(g\)の定数項が 1 なら\(x^i\)の部分も効かない。よって\(E\)は\(g\)の倍数にならない ∎

→ 長さ\(r\)以下のバースト誤りは 100% 検出 ✓

これが CRC の最大の強みである. 現実の通信誤りは「ランダムに 1 ビット」より「一瞬のノイズで連続数ビットがまとめて壊れる」ことが多い。電気的スパイク、ディスクの傷、無線のフェージング——どれもバースト誤りを起こす。 CRC-32 なら32 ビット連続の破壊まで確実に捕まえる。

(e) 長さ\(r+1\)のバースト、それ以上

長さ\(r+1\)のバースト: 見逃す確率\(2^{-(r-1)}\)
長さ\(r+1\)超のバースト: 見逃す確率\(2^{-r}\)

CRC-32 なら見逃し確率は約\(2^{-32} \approx 2.3\times10^{-10}\)。

まとめ表

誤りの種類	検出能力	条件
1 ビット	100%	\(g\)が 2 項以上
2 ビット	100%	データ長 < \(g\)の周期
奇数個	100%	\(g\)が\((x+1)\)を含む
長さ\(\le r\)のバースト	100%	\(g\)の定数項が 1
長さ\(r+1\)のバースト	\(1-2^{-(r-1)}\)
ランダムな誤り	\(1-2^{-r}\)

5. 標準的な CRC の仕様

名前	\(r\)	生成多項式（16 進）	主な用途
CRC-8	8	0x07	SMBus、センサ
CRC-16-IBM	16	0x8005	Modbus、USB
CRC-16-CCITT	16	0x1021	X.25、Bluetooth、SD カード
CRC-32	32	0x04C11DB7	Ethernet、ZIP、PNG、gzip
CRC-32C	32	0x1EDC6F41	iSCSI、ext4、Btrfs（CPU 命令あり）
CRC-64	64	0x42F0E1EBA9EA3693	XZ、ストレージ

実装パラメータ（ここが実務のハマりどころ）

同じ「CRC-32」でも、以下の 5 つが違うと値が一致しない:

パラメータ	意味	CRC-32 (Ethernet) の値
poly	生成多項式	0x04C11DB7
init	レジスタ初期値	0xFFFFFFFF
refin	入力バイトのビット順を反転するか	true
refout	出力のビット順を反転するか	true
xorout	最後に XOR する値	0xFFFFFFFF

なぜ init と xorout が必要なのか. 素朴な CRC（init=0）には弱点がある——データの先頭に 0 が何個付いても余りが変わらない。 \(0\cdot x^i\)は何を足しても 0 だからである。つまり 0x1234 と 0x00001234 が同じ CRC になり、先頭の 0 の増減を検出できない。
init を全 1 にすると、先頭の 0 でもレジスタが動くのでこの弱点が消える。 xorout は末尾に 0 が付く場合の同様の問題に対処する。 教科書の理論だけで実装すると、必ず既存システムと値が合わない。 上の 5 パラメータを必ず確認すること。

6. 実装

ビットごと（教科書的、遅いが分かりやすい）

uint32_t crc32_bitwise(const uint8_t *data, size_t len) {
    uint32_t crc = 0xFFFFFFFF;              // init
    for (size_t i = 0; i < len; i++) {
        crc ^= (uint32_t)data[i] << 24;     // 上位バイトに入力
        for (int b = 0; b < 8; b++) {
            crc = (crc & 0x80000000)
                ? (crc << 1) ^ 0x04C11DB7   // 最上位が 1 なら poly を XOR
                : (crc << 1);
        }
    }
    return crc ^ 0xFFFFFFFF;                // xorout
}

これは §3 の筆算そのものである。最上位ビットが 1 なら生成多項式を XOR して次数を下げる、という操作を 1 ビットずつ実行している。

テーブル駆動（実用の定番、8 倍速）

1 バイト分（8 回のシフト）の結果を 256 通り事前計算しておく:

uint32_t table[256];
void make_table(void) {
    for (int i = 0; i < 256; i++) {
        uint32_t c = (uint32_t)i << 24;
        for (int b = 0; b < 8; b++)
            c = (c & 0x80000000) ? (c << 1) ^ 0x04C11DB7 : (c << 1);
        table[i] = c;
    }
}

uint32_t crc32_table(const uint8_t *data, size_t len) {
    uint32_t crc = 0xFFFFFFFF;
    for (size_t i = 0; i < len; i++)
        crc = (crc << 8) ^ table[((crc >> 24) ^ data[i]) & 0xFF];
    return crc ^ 0xFFFFFFFF;
}

なぜテーブル化できるのか: CRC は線形である（\(\mathrm{CRC}(a \oplus b) = \mathrm{CRC}(a)\oplus\mathrm{CRC}(b)\)）。線形写像なので、「1 バイト入力したときの効果」を全 256 通り表に持てば、任意の入力に対して表引き 1 回で済む。

ハードウェア命令

CRC-32C: Intel/AMD の CRC32 命令、ARM の CRC32CX 命令で 1 命令
任意の poly: PCLMULQDQ（キャリーレス乗算）で GB/s 級

7. CRC の限界 — 「改ざん検知」には使えない

これは実務で最も重要な注意である.
CRC は偶発的な誤りの検出用であり、悪意ある改ざんには無力である。理由は 2 つ:
① 線形性: \(\mathrm{CRC}(m \oplus \Delta) = \mathrm{CRC}(m) \oplus \mathrm{CRC}(\Delta)\)。つまり攻撃者はデータを\(\Delta\)だけ書き換えたとき、CRC がどう変わるかを正確に計算できる。書き換えた上で CRC も辻褄が合うように直すのは、算数レベルの作業である。
② 鍵が無い: 生成多項式は公開仕様なので、誰でも正しい CRC を計算できる。
改ざん検知が必要なら 18 章の暗号学的ハッシュ（SHA-256）や MAC（HMAC）を使うこと。 「チェックサムが合っているから安全」は、セキュリティの文脈では完全な誤りである。
（歴史的な事故: WEP は RC4 の暗号化に CRC-32 を組み合わせていたが、 CRC の線形性と RC4 の線形性が噛み合って、暗号文のまま任意のビットを改ざんできた。これが WEP が破られた原因の 1 つである。）

8. まとめ

項目	内容
原理	\(T(x) = x^rm(x) + [x^rm(x)\bmod g(x)]\) は必ず\(g\)で割り切れる
検査	受信語を\(g\)で割り、余り 0 なら OK
見逃す条件	誤りパターン\(E(x)\)が\(g(x)\)の倍数のときのみ
強み	長さ\(r\)以下のバースト誤りを 100% 検出
実装	シフトレジスタ + XOR、テーブル駆動、CPU 命令
注意	5 つのパラメータ（poly/init/refin/refout/xorout）を合わせないと値が合わない
限界	線形なので改ざん検知には使えない

次章の予告: CRC は「検出」に特化していた。同じ巡回符号の枠組みで、訂正まで行えるように設計したのが BCH 符号である。鍵になるのは「生成多項式の根を、有限体\(\mathrm{GF}(2^m)\)の中で指定する」という発想—— つまり第 I 部で作った拡大体がついに本領を発揮する。