インターネットでファイルをダウンロードしているとき、1ビットでも化けていたらどうなるでしょうか。実行ファイルなら起動不能、圧縮ファイルなら展開エラー、制御信号なら機器の誤動作——データの正しさが保証されなければ、ディジタル通信は成り立ちません。
しかし、現実の通信路にはノイズが付き物です。銅線を流れる電気信号は外部磁場に乱され、無線信号はフェージングに揺さぶられ、光ファイバーですら微小な歪みを受けます。そこで必要になるのが誤り検出（error detection）の技術です。送信側がデータに少しの冗長情報を付加し、受信側がそれを検算することで「受け取ったデータは正しいか？」を判定します。
誤り検出は通信だけでなく、以下のような幅広い場面で活躍します。
- Ethernet / Wi-Fi: フレーム末尾のFCS（Frame Check Sequence）にCRC-32が使われ、破損フレームを即座に破棄します
- ZIP / PNG / PDF: ファイルフォーマット内部にCRCを埋め込み、データ破損を検出します
- ハードディスク / SSD: セクタ単位でCRCを付加し、読み出しデータの健全性を保証します
- 宇宙通信: 深宇宙探査機からの微弱な信号でも、CRCによる誤り検出と再送制御（ARQ）で信頼性を確保します
本記事の内容
- パリティチェックとチェックサムの原理と限界
- CRC（巡回冗長検査）の概念と数学的基盤
- GF(2)上の多項式演算（mod 2 の世界）
- CRCの符号化と検査の手順
- バースト誤り検出能力の保証
- 標準生成多項式（CRC-8, CRC-16, CRC-32）
- シフトレジスタによるハードウェア実装
- Pythonでのスクラッチ実装と誤り検出シミュレーション
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
誤り検出の基本的な考え方
なぜ誤り検出が必要なのか
ディジタル通信では、送信側がビット列 $\bm{d} = (d_1, d_2, \dots, d_k)$ を送り、受信側がビット列 $\bm{r} = (r_1, r_2, \dots, r_n)$ を受け取ります。通信路にノイズがなければ $\bm{r} = \bm{d}$ ですが、現実にはビット反転が起こり得ます。このとき、受信側が何の手がかりもなければ、誤りの存在にすら気づけません。
誤り検出の基本戦略はシンプルです。送信データにある種の「検算用の情報」（冗長ビット）を付け加えて送信し、受信側がその検算を実行します。検算が合わなければ「どこかが壊れている」と分かるので、再送を要求したりデータを破棄したりできます。
この冗長ビットを付加する方法はさまざまですが、誤り検出能力と計算コストのトレードオフがあります。最も単純な方法から順に見ていきましょう。
パリティチェック — 最も単純な誤り検出
直感的な理解
パリティチェックは「ビットの数を数える」という、これ以上ないほど単純な発想に基づいています。
偶数パリティの考え方は次の通りです。データ中の 1 の個数が偶数になるように、末尾に1ビットだけ追加します。受信側は全ビットの 1 の個数を数え、偶数なら OK、奇数なら誤りあり——これだけです。
数学的な表現
$k$ ビットのデータ $\bm{d} = (d_1, d_2, \dots, d_k)$ に対して、偶数パリティビット $p$ を次のように定義します。
$$ p = d_1 \oplus d_2 \oplus \cdots \oplus d_k = \bigoplus_{i=1}^{k} d_i $$
ここで $\oplus$ は排他的論理和（XOR）です。送信データは $\bm{c} = (d_1, d_2, \dots, d_k, p)$ の $k+1$ ビットとなります。
受信側では、受信ビット列 $\bm{r} = (r_1, r_2, \dots, r_k, r_{k+1})$ の全ビットの XOR を計算します。
$$ s = \bigoplus_{i=1}^{k+1} r_i $$
$s = 0$ なら誤りなし（または偶数個の誤り）、$s = 1$ なら奇数個の誤りが検出されます。
パリティチェックの限界
パリティチェックは1ビット誤りを確実に検出できますが、致命的な弱点があります。
- 偶数個の誤りを見逃す: 2ビットが同時に反転すると、1 の総数の偶奇は変わらないため、誤りを検出できません
- 誤りの位置が分からない: 誤りの存在は分かっても、どのビットが反転したかは不明です
- バースト誤りに弱い: 連続した複数ビットの誤り（バースト誤り）を検出する保証がありません
つまり、パリティチェックは「1ビット誤り検出」しかできない最も弱い方式です。しかし、計算コストは極めて低く、UARTなどのシリアル通信では今でも使われています。
パリティチェックよりもう少し強力な方法はないでしょうか。次に見るチェックサムは、データを「数値の列」として扱うことで検出能力を向上させます。
チェックサム — 数値の合計による検出
基本的な仕組み
チェックサムは、データをバイト列や整数列とみなし、それらの合計値（または合計の一部）を検算用に付加する方式です。パリティがビット単位の XOR だったのに対し、チェックサムはバイトやワード単位の算術演算を使います。
たとえば、IP（Internet Protocol）ヘッダのチェックサムは以下のように計算されます。
- ヘッダを16ビットワードに分割する
- 全ワードを1の補数で加算する
- 結果の1の補数をチェックサムとする
受信側で同じ計算を行い、結果がすべて 1（16ビットなら 0xFFFF）であれば誤りなし、そうでなければ誤りあり、と判定します。
1の補数チェックサムの計算例
4つの16ビットワード $w_1 = \mathtt{0x4500}$, $w_2 = \mathtt{0x003C}$, $w_3 = \mathtt{0x1C46}$, $w_4 = \mathtt{0x4000}$ のチェックサムを計算してみましょう。
まず通常の加算を行います。
$$ w_1 + w_2 + w_3 + w_4 = \mathtt{0x4500} + \mathtt{0x003C} + \mathtt{0x1C46} + \mathtt{0x4000} = \mathtt{0xA182} $$
桁上がり（キャリー）がなければ、1の補数は単にビット反転です。
$$ \text{checksum} = \overline{\mathtt{0xA182}} = \mathtt{0x5E7D} $$
チェックサムの限界
チェックサムはパリティよりも多くの誤りパターンを検出できますが、以下の弱点があります。
- バイト順の入れ替えを検出できない: 2つのワードの位置が入れ替わっても合計は同じなので、検出できません
- 補い合う誤りを見逃す: あるワードが $+\delta$ 、別のワードが $-\delta$ だけ変化すると、合計は不変です
- 検出能力の理論的保証が弱い: どのような誤りパターンを必ず検出できるか、という厳密な保証が難しいです
特に3番目の点が重要です。信頼性の高い通信を設計するには「この誤り検出方式は、○○なパターンの誤りを確実に検出できる」という数学的保証が欲しいのです。
ここで登場するのが CRC（巡回冗長検査）です。CRC は多項式の除算という代数的操作に基づいており、検出能力に関する明確な理論的保証があります。
CRC（巡回冗長検査）の概念
CRCとは何か
CRC（Cyclic Redundancy Check、巡回冗長検査）は、ビット列を GF(2) 上の多項式 として扱い、あらかじめ決めた生成多項式（generator polynomial）で割った剰余を冗長ビットとして付加する方式です。
身近なアナロジーで考えてみましょう。小学校で習った「9 で割った余りによる検算」を思い出してください。たとえば $123 \times 456 = 56088$ を検算するとき、$123$ を $9$ で割った余りは $6$、$456$ を $9$ で割った余りは $6$、$6 \times 6 = 36$ を $9$ で割った余りは $0$。答え $56088$ を $9$ で割った余りも $0$ なので、計算は（おそらく）正しいと判定できます。
CRC もこれと同じ発想です。ただし、10進数の代わりに 2進多項式 を使い、除数として 生成多項式 を使います。割った余り（剰余）が CRC 値であり、これをデータに付加して送信します。受信側は全体を同じ生成多項式で割り、余りが $0$ なら誤りなし、$0$ でなければ誤りあり、と判定します。
CRC の名前の由来
「巡回」（cyclic）という言葉は、CRC が巡回符号（cyclic code）の一種であることに由来します。巡回符号とは、符号語を巡回シフト（ビット列を左に1つずらして、はみ出したビットを右端に戻す操作）しても、やはり符号語であるという性質を持つ線形符号です。
この巡回性は、生成多項式による剰余計算という代数的構造から自然に導かれます。そして、この構造こそが CRC の強力な誤り検出能力の源泉です。
CRC の仕組みを理解するには、まず GF(2) 上の多項式演算を知る必要があります。
GF(2) 上の多項式演算
GF(2) とは
GF(2)（Galois Field of order 2）は、要素が $\{0, 1\}$ の2つだけからなる有限体（ガロア体）です。加算と乗算は次のように定義されます。
$$ \begin{array}{c|cc} + & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & 1 & 0 \end{array} \qquad \begin{array}{c|cc} \times & 0 & 1 \\ \hline 0 & 0 & 0 \\ 1 & 0 & 1 \end{array} $$
加算は XOR（排他的論理和）と同じです。特に重要な性質として、GF(2) では加算と減算が同じ操作になります。$1 + 1 = 0$ なので、$a – b = a + b$ です。この性質は CRC の計算で頻繁に使います。
GF(2) 上の多項式
GF(2) 上の多項式とは、係数が $0$ または $1$ のみの多項式です。ビット列 $(b_n, b_{n-1}, \dots, b_1, b_0)$ は、多項式 $B(x) = b_n x^n + b_{n-1} x^{n-1} + \cdots + b_1 x + b_0$ と1対1に対応します。
たとえば、ビット列 $10110$ は次の多項式に対応します。
$$ 1 \cdot x^4 + 0 \cdot x^3 + 1 \cdot x^2 + 1 \cdot x + 0 = x^4 + x^2 + x $$
GF(2) 上の多項式の加算
GF(2) 上の多項式の加算は、同じ次数の係数同士を XOR するだけです。繰り上がりは発生しません。
$$ (x^4 + x^2 + x) + (x^3 + x^2 + 1) = x^4 + x^3 + x + 1 $$
$x^2$ の項は $1 \oplus 1 = 0$ で消えます。ビット列で書けば $10110 \oplus 01101 = 11011$ です。
GF(2) 上の多項式の乗算
乗算は通常の多項式の積と同じ手順ですが、係数の計算で XOR を使います。
$$ (x^2 + 1)(x + 1) = x^3 + x^2 + x + 1 $$
展開すると $x^3 + x^2 + x + 1$ です。通常の多項式なら $x^3 + x^2 + x + 1$ で同じですが、係数に $2$ 以上が現れた場合は mod 2 で $0$ になることに注意してください。
GF(2) 上の多項式の除算
CRC の核心は多項式の除算です。通常の長除法と同じ手順ですが、引き算の代わりに XOR を使います。
$x^6 + x^4 + x^2 + x + 1$（ビット列 $1010111$）を $x^3 + x + 1$（ビット列 $1011$）で割る例を見てみましょう。
1 1 0 1 ← 商
─────────
1011 ) 1 0 1 0 1 1 1
1 0 1 1
─────────
0 0 1 1 1 1
0 0 0 0
─────────
0 1 1 1 1
0 0 0 0
───────
1 1 1 1
1 0 1 1
───────
1 0 0 ← 剰余
結果は、商が $x^3 + x^2 + 1$（ビット列 $1101$）、剰余が $x^2$（ビット列 $100$） です。
この「剰余」が CRC 値にあたります。GF(2) の除算では引き算が XOR なので、通常の除算における「被除数の先頭ビットが除数の先頭ビットより小さいかどうか」の判定が不要になり、先頭ビットが $1$ なら商に $1$ を立てて XOR、$0$ ならスキップ という非常に単純な手順になります。
この多項式演算の基盤を使って、実際に CRC の符号化と検査がどのように行われるかを見ていきましょう。
CRC の符号化 — 生成多項式による剰余計算
符号化の手順
CRC の符号化では、$k$ ビットのデータ $D(x)$ に対して、次数 $r$ の生成多項式 $G(x)$ を使い、$r$ ビットの CRC 値を計算して付加します。手順は以下の通りです。
ステップ 1: データ多項式 $D(x)$ に $x^r$ を掛けます。これはビット列の末尾に $r$ 個の $0$ を追加する操作に相当します。
$$ D(x) \cdot x^r $$
ステップ 2: $D(x) \cdot x^r$ を生成多項式 $G(x)$ で割り、剰余 $R(x)$ を求めます。
$$ D(x) \cdot x^r = Q(x) \cdot G(x) + R(x) $$
ここで $Q(x)$ は商、$R(x)$ は剰余です。$R(x)$ の次数は $r-1$ 以下です。
ステップ 3: 送信データ $T(x)$ を次のように構成します。
$$ T(x) = D(x) \cdot x^r + R(x) $$
GF(2) では加算と減算が同じなので、$T(x) = D(x) \cdot x^r – R(x) = D(x) \cdot x^r + R(x)$ です。
送信データが生成多項式で割り切れることの証明
$T(x)$ を $G(x)$ で割ってみましょう。
$$ T(x) = D(x) \cdot x^r + R(x) $$
ステップ 2 の式 $D(x) \cdot x^r = Q(x) \cdot G(x) + R(x)$ を変形すると、GF(2) 上では加算と減算が同一なので、
$$ D(x) \cdot x^r + R(x) = Q(x) \cdot G(x) + R(x) + R(x) = Q(x) \cdot G(x) $$
$R(x) + R(x) = 0$（GF(2) では任意の元について $a + a = 0$）であるため、次が成り立ちます。
$$ T(x) = Q(x) \cdot G(x) $$
したがって、$T(x)$ は $G(x)$ で割り切れます。これが CRC の核心的な性質です。
具体例
データ $D = 1101011$（$D(x) = x^6 + x^5 + x^3 + x + 1$）に対して、生成多項式 $G(x) = x^3 + x + 1$（ビット列 $1011$, $r = 3$）で CRC を計算します。
ステップ 1: $D(x) \cdot x^3$ はビット列 $1101011\mathbf{000}$ です。
ステップ 2: $1101011000$ を $1011$ で割ります。
1 1 1 0 0 0 1
─────────────────
1 0 1 1 ) 1 1 0 1 0 1 1 0 0 0
1 0 1 1
─────────
1 1 0 0
1 0 1 1
───────
0 1 1 1
0 0 0 0
───────
0 1 1 1 0
0 0 0 0
─────
1 1 1 0 0
1 0 1 1
───────
1 0 1 0
1 0 1 1
─────
0 0 1 ← 剰余 R = 001
剰余は $R(x) = 1$（ビット列 $001$）です。
ステップ 3: 送信データは $T = 1101011\mathbf{001}$ となります。
受信側がこのビット列 $1101011001$ を $1011$ で割ると、剰余は $0$ になるはずです。これで誤りがないことが確認できます。
符号化の手順が分かったところで、次は受信側での検査がどのように機能するかを見ていきましょう。
CRC の検査 — 受信データの検証
検査の原理
受信側は、受信データ $\bm{r}$ に対応する多項式 $R'(x)$ を生成多項式 $G(x)$ で割り、剰余（シンドローム）$S(x)$ を計算します。
$$ S(x) = R'(x) \mod G(x) $$
$S(x) = 0$ なら「誤りなし」と判定し、$S(x) \neq 0$ なら「誤りあり」と判定します。
誤りがある場合
送信データ $T(x)$ に誤り $E(x)$ が加わり、受信データが $R'(x) = T(x) + E(x)$ であるとします。シンドロームは次のようになります。
$$ S(x) = R'(x) \mod G(x) = (T(x) + E(x)) \mod G(x) $$
$T(x)$ は $G(x)$ で割り切れる（$T(x) \mod G(x) = 0$）ので、
$$ S(x) = E(x) \mod G(x) $$
となります。つまり、シンドロームは誤りパターン $E(x)$ のみに依存し、送信データ $T(x)$ には依存しません。これは非常に重要な性質です。
検出できない誤りの条件
$S(x) = 0$、すなわち誤りが検出できないのは、$E(x)$ が $G(x)$ で割り切れる場合、つまり
$$ E(x) = G(x) \cdot K(x) \quad \text{（ある多項式 $K(x)$ が存在）} $$
のときに限られます。生成多項式 $G(x)$ を適切に選ぶことで、この条件を満たす誤りパターンを極力少なくすることが CRC 設計の要点です。
検査の具体例
先ほど符号化した $T = 1101011001$ を受信し、CRC 検査を行います。
誤りなしの場合: $1101011001$ を $1011$ で割ると、剰余は $000$（$S(x) = 0$）なので、「誤りなし」と判定します。
1ビット誤りの場合: 5ビット目（左から数えて）が反転し、$1101\mathbf{1}11001$ を受信したとします（受信データ $1101111001$）。これを $1011$ で割ると、剰余は $000$ にはなりません。「誤りあり」と判定できます。
CRC は誤りの存在を検出できますが、パリティと同様に誤りの位置は特定できません。誤りの位置を特定して訂正するには、ハミング符号やリードソロモン符号などの誤り訂正符号が必要です。
では、CRC はどのような誤りパターンをどこまで検出できるのでしょうか。次にその理論的保証を見ていきます。
CRC の誤り検出能力
1ビット誤りの検出
1ビット誤りの誤りパターンは $E(x) = x^i$（$i$ はビット位置）です。この誤りが検出できないのは $x^i$ が $G(x)$ で割り切れるときです。
$G(x)$ が $x^0 = 1$ を含む項を持つ（すなわち定数項が $1$、つまり $G(0) = 1$）ならば、$G(x)$ は $x$ の因子を持たないため、$x^i$ は $G(x)$ で割り切れません。
定理: $G(x)$ の定数項が $1$（$x + 1$ を因子に含まないか、または定数項が存在する）ならば、CRC はすべての1ビット誤りを検出できます。
実用上、生成多項式の定数項は常に $1$ です（そうでなければ $G(x) = x \cdot G'(x)$ と書け、実質的な検査能力が下がるため）。
2ビット誤りの検出
2ビット誤りの誤りパターンは $E(x) = x^i + x^j = x^j(x^{i-j} + 1)$（$i > j$）です。$G(x)$ の定数項が $1$ なら $x^j$ の因子は問題になりませんから、$E(x)$ が $G(x)$ で割り切れるのは $x^{i-j} + 1$ が $G(x)$ で割り切れるとき、すなわち $G(x) \mid (x^{i-j} + 1)$ のときです。
$G(x)$ が $x^e + 1$ を割り切らない最小の $e$ を $G(x)$ の位数（order）と呼びます。データ長 $n$ が位数 $e$ 以下であれば、$i – j < e$ となるすべての2ビット誤りパターンが検出可能です。
定理: $G(x)$ の位数が $e$ のとき、データ長 $n \leq e$ ならば、すべての2ビット誤りを検出できます。
奇数個の誤りの検出
$G(x)$ が因子 $(x + 1)$ を含むとき、すべての奇数個の誤りを検出できます。
証明の概略: 奇数個のビットが反転した誤りパターン $E(x)$ は、$x = 1$ を代入すると $E(1) = 1$（GF(2) 上で奇数個の $1$ の和は $1$）です。一方、$G(x) = (x+1) \cdot G'(x)$ なら、$G(x)$ の倍数 $F(x) = G(x) \cdot K(x)$ は $F(1) = G(1) \cdot K(1) = 0 \cdot K(1) = 0$ を満たします。$E(1) = 1 \neq 0$ なので、$E(x)$ は $G(x)$ の倍数ではなく、検出されます。
バースト誤りの検出
CRC が特に威力を発揮するのはバースト誤りの検出です。バースト誤りとは、連続するビット区間内で1つ以上のビットが反転する誤りパターンです。長さ $b$ のバースト誤りとは、最初と最後の誤りビットの間の距離が $b$ であるようなパターンを指します。
長さ $b$ のバースト誤りは次の形で表せます。
$$ E(x) = x^j \cdot (x^{b-1} + \cdots + 1) = x^j \cdot B(x) $$
ここで $B(x)$ は次数 $b-1$ の多項式で、$B(x)$ の最高次の係数と定数項はともに $1$ です（バーストの先頭と末尾は必ず誤りビット）。
$G(x)$ の次数を $r$（つまり CRC は $r$ ビット）とすると、以下が成り立ちます。
定理 1（完全検出）: 長さ $b \leq r$ のすべてのバースト誤りを検出できます。
証明: $G(x)$ の定数項は $1$ なので $x^j$ は因子にならず、$B(x)$ の次数は $b – 1 \leq r – 1 < r = \deg(G(x))$ です。次数が $G(x)$ より低い $B(x)$ は $G(x)$ で割り切れないため（$B(x)$ の最高次係数は $1$ であり $B(x) \neq 0$）、$E(x)$ は $G(x)$ で割り切れず、検出されます。
定理 2（高確率検出）: 長さ $b = r + 1$ のバースト誤りは、$1 – 2^{-(r-1)}$ の確率で検出できます。
定理 3（ランダム誤り）: 長さ $b > r + 1$ のバースト誤りは、$1 – 2^{-r}$ の確率で検出できます。
たとえば CRC-32（$r = 32$）の場合、32ビット以下のバースト誤りはすべて検出でき、33ビットのバースト誤りは $1 – 2^{-31} \approx 99.99999995\%$ の確率で検出できます。これが CRC の実用上の強さです。
検出能力のまとめ
次数 $r$ の生成多項式 $G(x)$ を持つ CRC の検出能力をまとめます。
| 誤りパターン | 検出条件 |
|---|---|
| すべての1ビット誤り | $G(x)$ の定数項が $1$（常に成立） |
| すべての2ビット誤り | データ長 $\leq G(x)$ の位数 |
| すべての奇数個の誤り | $G(x)$ が $(x+1)$ を因子に含む |
| 長さ $\leq r$ のバースト誤り | 常に成立 |
| 長さ $r+1$ のバースト誤り | 確率 $1 – 2^{-(r-1)}$ |
| 長さ $> r+1$ のバースト誤り | 確率 $1 – 2^{-r}$ |
パリティやチェックサムにはこのような体系的な保証がありません。CRC がディジタル通信やストレージで広く使われる理由は、この厳密な誤り検出保証にあります。
では、実際に使われている生成多項式にはどのようなものがあるのでしょうか。次に、業界標準の生成多項式を紹介します。
標準生成多項式 — CRC-8, CRC-16, CRC-32
生成多項式の選び方
生成多項式の選択は CRC の検出能力を決定する重要な設計判断です。良い生成多項式の条件は以下の通りです。
- 定数項が $1$: すべての1ビット誤りを検出するため
- $(x+1)$ を因子に含む: すべての奇数個の誤りを検出するため
- 位数が大きい: 2ビット誤りの検出保証範囲を広げるため
- 次数 $r$ が適切: バースト誤り検出保証長とのバランス
CRC-8
CRC-8 は 8 ビットの CRC であり、短いデータフレーム（数十バイト以下）の保護に使われます。
$$ G(x) = x^8 + x^2 + x + 1 $$
ビット列表記: $\mathtt{0x07}$（$x^8$ の項を除いた下位8ビット）
用途: I2C、1-Wire、ATM ヘッダ (HEC) など
CRC-16-CCITT
CRC-16 は通信プロトコルで広く使われます。CCITT（現 ITU-T）が標準化した生成多項式は次の通りです。
$$ G(x) = x^{16} + x^{12} + x^5 + 1 $$
ビット列表記: $\mathtt{0x1021}$
用途: X.25、HDLC、Bluetooth、SD カードなど
CRC-32
CRC-32 は最も広く使われる CRC です。IEEE 802.3（Ethernet）で採用され、ZIP、PNG、MPEG-2 など無数のプロトコルやファイルフォーマットで使われています。
$$ G(x) = x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1 $$
ビット列表記: $\mathtt{0x04C11DB7}$
この多項式は以下のように因数分解できます。
$$ G(x) = (x + 1) \cdot P(x) $$
$(x+1)$ を因子に含むため、すべての奇数個の誤りを検出できます。また、32ビット以下のすべてのバースト誤りを検出し、位数は $2^{31} – 1 = 2{,}147{,}483{,}647$ であるため、約20億ビット（約256MB）以下のデータであればすべての2ビット誤りも検出できます。
生成多項式の比較
| 方式 | 次数 $r$ | バースト検出保証長 | 主な用途 |
|---|---|---|---|
| CRC-8 | 8 | 8ビット | 短いフレーム、センサ通信 |
| CRC-16-CCITT | 16 | 16ビット | シリアル通信、無線 |
| CRC-32 | 32 | 32ビット | Ethernet、ファイル |
CRC の理論を理解したところで、次はこの計算をハードウェアでどう実現するかを見ていきましょう。CRC の多項式除算は、シフトレジスタ回路によって極めて効率的に実装できます。
ハードウェア実装 — シフトレジスタによる CRC 計算
基本原理
CRC の計算は、$r$ ビットの線形フィードバックシフトレジスタ (LFSR: Linear Feedback Shift Register) で実現できます。生成多項式 $G(x) = x^r + g_{r-1} x^{r-1} + \cdots + g_1 x + 1$ に対して、次のような回路を構成します。
- $r$ 個のフリップフロップ（レジスタ）$R_0, R_1, \dots, R_{r-1}$ を直列に並べます
- 生成多項式の係数 $g_i = 1$ であるビット位置に XOR ゲートを配置します
- 入力データを1ビットずつ MSB（最上位ビット）から入力し、各クロックでシフトします
- すべてのデータビットを入力し終えた後、レジスタに残った値が CRC です
CRC-3 のシフトレジスタ回路の例
生成多項式 $G(x) = x^3 + x + 1$（ビット列 $1011$）のシフトレジスタ回路を考えます。
データ入力 ──→ [XOR] ──→ [R2] ──→ [R1] ──→ [XOR] ──→ [R0]
↑ ↑
└─────────── R0 の出力 ────────┘
回路の動作を追跡します。
- 各クロックで、$R_0$ の出力がフィードバックとして XOR ゲートに入力されます
- フィードバックが接続される位置は、$G(x)$ で係数が $1$ の項（$x^0$ と $x^1$）に対応します
- $x^3$ の項はレジスタ全体のシフト操作に対応するため、明示的な XOR は不要です
動作の追跡
データ $1101011$（$D(x) = x^6 + x^5 + x^3 + x + 1$）に対して、$G(x) = x^3 + x + 1$ の CRC を計算します。レジスタの初期値は $(R_2, R_1, R_0) = (0, 0, 0)$ です。
末尾に $r = 3$ 個のゼロを追加した入力ビット列 $1101011000$ を1ビットずつ処理します。
| ステップ | 入力ビット | フィードバック | $R_2$ | $R_1$ | $R_0$ |
|---|---|---|---|---|---|
| 初期 | — | — | 0 | 0 | 0 |
| 1 | 1 | 0 XOR 1 = 1 | 1 | 0 | 1 |
| 2 | 1 | 1 XOR 1 = 0 | 0 | 1 | 0 |
| 3 | 0 | 0 XOR 0 = 0 | 0 | 0 | 1 |
| 4 | 1 | 1 XOR 1 = 0 | 0 | 1 | 0 |
| 5 | 0 | 0 XOR 0 = 0 | 0 | 0 | 1 |
| 6 | 1 | 1 XOR 1 = 0 | 0 | 1 | 0 |
| 7 | 1 | 0 XOR 1 = 1 | 1 | 0 | 1 |
| 8 | 0 | 1 XOR 0 = 1 | 1 | 1 | 0 |
| 9 | 0 | 0 XOR 0 = 0 | 0 | 1 | 1 |
| 10 | 0 | 1 XOR 0 = 1 | 1 | 1 | 0 |
最終的なレジスタ値は $(R_2, R_1, R_0) = (1, 1, 0)$、すなわち CRC = $110$ です。
ただし、ここでの回路は簡易的なモデルです。実際のステップ追跡では、フィードバックビット（シフト前の $R_2$ XOR 入力ビット）に応じてレジスタ更新が行われ、生成多項式 $1011$ に対応した長除法と同じ結果が得られます。この結果が前述の手計算による長除法と一致することを確認してみてください。
ハードウェア実装の利点
シフトレジスタによる CRC 計算には、以下の利点があります。
- 1クロックで1ビットを処理: データが到着するたびにリアルタイムで計算が進みます
- 回路が極めてシンプル: フリップフロップと XOR ゲートだけで構成できます
- パイプライン化が容易: 高速通信にも対応可能です
Ethernet の物理層チップでは、10 Gbps 以上の速度で CRC-32 をリアルタイム計算するシフトレジスタ回路が動いています。ソフトウェア実装ではルックアップテーブルによる高速化が一般的ですが、ハードウェアではこの単純な回路構造が最適です。
理論とハードウェアの仕組みを理解したところで、いよいよ Python で CRC を実装してみましょう。
Python 実装 — CRC 計算の基本
ビット単位の CRC 計算
まず、GF(2) 上の多項式除算を忠実に再現する「ビット単位」の CRC 計算を実装します。この実装は理論の理解に最適です。
import numpy as np
def crc_encode_bitwise(data_bits, generator):
"""
ビット単位のCRC符号化
Parameters
----------
data_bits : list of int
データビット列（MSBファースト）
generator : list of int
生成多項式のビット表現（MSBファースト, 最高次の1を含む）
Returns
-------
crc : list of int
CRCビット列
codeword : list of int
データ + CRC の符号語
"""
r = len(generator) - 1 # CRCのビット数
# データの末尾にr個の0を追加
padded = list(data_bits) + [0] * r
# GF(2)上の多項式長除法
register = list(padded)
for i in range(len(data_bits)):
if register[i] == 1:
for j in range(len(generator)):
register[i + j] ^= generator[j]
# 剰余がCRC
crc = register[-r:]
# 符号語 = データ + CRC
codeword = list(data_bits) + crc
return crc, codeword
def crc_check_bitwise(received_bits, generator):
"""
ビット単位のCRC検査
Parameters
----------
received_bits : list of int
受信ビット列（データ + CRC）
generator : list of int
生成多項式のビット表現
Returns
-------
syndrome : list of int
シンドローム（全て0なら誤りなし）
is_valid : bool
誤りなしならTrue
"""
r = len(generator) - 1
register = list(received_bits)
for i in range(len(received_bits) - r):
if register[i] == 1:
for j in range(len(generator)):
register[i + j] ^= generator[j]
syndrome = register[-r:]
is_valid = all(s == 0 for s in syndrome)
return syndrome, is_valid
# 具体例: 記事中の手計算と同じ例
data = [1, 1, 0, 1, 0, 1, 1]
gen = [1, 0, 1, 1] # G(x) = x^3 + x + 1
crc, codeword = crc_encode_bitwise(data, gen)
print(f"データ: {data}")
print(f"生成多項式: {gen}")
print(f"CRC: {crc}")
print(f"符号語: {codeword}")
# 検査（誤りなし）
syndrome, is_valid = crc_check_bitwise(codeword, gen)
print(f"\n--- 誤りなしの検査 ---")
print(f"シンドローム: {syndrome}")
print(f"検査結果: {'OK (誤りなし)' if is_valid else 'NG (誤りあり)'}")
# 検査（1ビット誤りあり）
corrupted = list(codeword)
corrupted[3] ^= 1 # 4ビット目を反転
syndrome, is_valid = crc_check_bitwise(corrupted, gen)
print(f"\n--- 1ビット誤りの検査 ---")
print(f"受信データ: {corrupted}")
print(f"シンドローム: {syndrome}")
print(f"検査結果: {'OK (誤りなし)' if is_valid else 'NG (誤りあり)'}")
このコードを実行すると、データ $1101011$ に対する CRC が $001$ と計算され、手計算の結果と一致することが確認できます。また、1ビット反転を加えた場合にはシンドロームが非ゼロとなり、「誤りあり」と正しく判定されます。このように、CRC の符号化・検査の原理がそのままコードになっていることが分かります。
次に、実用的な CRC-32 の実装に進みましょう。
Python 実装 — CRC-32 とルックアップテーブル
バイト単位の CRC-32 実装
実用上の CRC 計算では、ビット単位の処理は遅すぎるため、ルックアップテーブルを使ったバイト単位の高速計算が一般的です。256エントリのテーブルを事前に計算しておき、入力データを1バイトずつ処理します。
import numpy as np
def make_crc32_table(poly=0xEDB88320):
"""
CRC-32のルックアップテーブルを生成
（反転多項式 0xEDB88320 を使用: 0x04C11DB7のビット反転）
Parameters
----------
poly : int
反転生成多項式
Returns
-------
table : list of int
256エントリのルックアップテーブル
"""
table = []
for byte in range(256):
crc = byte
for _ in range(8):
if crc & 1:
crc = (crc >> 1) ^ poly
else:
crc >>= 1
table.append(crc)
return table
def crc32_calc(data_bytes, table):
"""
CRC-32をルックアップテーブルで計算
Parameters
----------
data_bytes : bytes
入力データ
table : list of int
ルックアップテーブル
Returns
-------
crc : int
CRC-32値（32ビット符号なし整数）
"""
crc = 0xFFFFFFFF # 初期値（全ビット1）
for byte in data_bytes:
index = (crc ^ byte) & 0xFF
crc = (crc >> 8) ^ table[index]
return crc ^ 0xFFFFFFFF # 最終XOR
# テーブル生成
crc32_table = make_crc32_table()
# テスト: "123456789" のCRC-32は 0xCBF43926 であることが知られている
test_data = b"123456789"
result = crc32_calc(test_data, crc32_table)
print(f"入力: {test_data}")
print(f"CRC-32: 0x{result:08X}")
print(f"期待値: 0xCBF43926")
print(f"一致: {result == 0xCBF43926}")
# Python標準ライブラリとの比較
import binascii
std_result = binascii.crc32(test_data) & 0xFFFFFFFF
print(f"\n標準ライブラリ: 0x{std_result:08X}")
print(f"自作と一致: {result == std_result}")
このコードでは、2つの実装上のポイントがあります。
1つ目は反転多項式（reflected polynomial）の使用です。標準の CRC-32 多項式 $\mathtt{0x04C11DB7}$ のビット順序を逆にした $\mathtt{0xEDB88320}$ を使うことで、LSB（最下位ビット）ファーストの処理が可能になります。これは Ethernet など多くのプロトコルが LSB ファーストでデータを送信するためです。
2つ目は初期値と最終 XOR です。レジスタの初期値を $\mathtt{0xFFFFFFFF}$ とし、最終結果に $\mathtt{0xFFFFFFFF}$ を XOR します。初期値を全 $1$ にする理由は、データ先頭に $0$ が追加されても CRC が変わるようにするためです。先頭の $0$ に対して CRC が変化しないと、データの前にゼロパディングが付いても検出できない問題が生じます。
テストベクトル "123456789" に対する CRC-32 値 $\mathtt{0xCBF43926}$ は広く知られた検証値であり、自作実装と標準ライブラリの結果が一致することで実装の正しさを確認できます。
Python 実装 — ビット誤り検出のシミュレーション
シミュレーションの設計
CRC の誤り検出能力を実験的に検証するため、ランダムなデータに対してさまざまな誤りパターンを注入し、CRC が正しく検出できるかをモンテカルロシミュレーションで調べます。
import numpy as np
import matplotlib.pyplot as plt
def crc_encode(data_bits, generator):
"""ビット単位のCRC符号化（NumPy配列版）"""
r = len(generator) - 1
padded = np.concatenate([data_bits, np.zeros(r, dtype=int)])
for i in range(len(data_bits)):
if padded[i] == 1:
padded[i:i+len(generator)] ^= generator
crc = padded[-r:]
codeword = np.concatenate([data_bits, crc])
return codeword
def crc_check(received, generator):
"""ビット単位のCRC検査（NumPy配列版）"""
r = len(generator) - 1
buf = received.copy()
for i in range(len(received) - r):
if buf[i] == 1:
buf[i:i+len(generator)] ^= generator
syndrome = buf[-r:]
return np.all(syndrome == 0)
def simulate_error_detection(data_len, generator, error_type, n_trials=10000):
"""
誤り検出シミュレーション
Parameters
----------
data_len : int
データ長（ビット）
generator : np.ndarray
生成多項式
error_type : str
'single', 'double', 'burst_short', 'burst_long', 'random'
n_trials : int
試行回数
Returns
-------
detection_rate : float
誤り検出率
"""
r = len(generator) - 1
n = data_len + r # 符号語長
detected = 0
for _ in range(n_trials):
# ランダムデータ生成
data = np.random.randint(0, 2, data_len)
codeword = crc_encode(data, generator)
# 誤り注入
error = np.zeros(n, dtype=int)
if error_type == 'single':
# 1ビット誤り
pos = np.random.randint(0, n)
error[pos] = 1
elif error_type == 'double':
# 2ビット誤り
positions = np.random.choice(n, 2, replace=False)
error[positions] = 1
elif error_type == 'burst_short':
# 短いバースト誤り（長さ <= r）
burst_len = np.random.randint(2, r + 1)
start = np.random.randint(0, n - burst_len + 1)
burst = np.random.randint(0, 2, burst_len)
burst[0] = 1 # バースト先頭は必ず1
burst[-1] = 1 # バースト末尾は必ず1
error[start:start+burst_len] = burst
elif error_type == 'burst_long':
# 長いバースト誤り（長さ = r + 1 ~ r + 5）
burst_len = np.random.randint(r + 1, r + 6)
burst_len = min(burst_len, n)
start = np.random.randint(0, max(1, n - burst_len + 1))
burst = np.random.randint(0, 2, burst_len)
burst[0] = 1
burst[-1] = 1
error[start:start+burst_len] = burst
elif error_type == 'random':
# ランダムな3ビット誤り
positions = np.random.choice(n, 3, replace=False)
error[positions] = 1
# 誤りが全ゼロなら再生成（誤りなしを除外）
if np.all(error == 0):
continue
# 受信データ
received = codeword ^ error
# 検査
if not crc_check(received, generator):
detected += 1
return detected / n_trials
# 生成多項式の定義
generators = {
'CRC-3 (x^3+x+1)': np.array([1, 0, 1, 1]),
'CRC-4 (x^4+x+1)': np.array([1, 0, 0, 1, 1]),
'CRC-8': np.array([1, 0, 0, 0, 0, 0, 1, 1, 1]), # x^8+x^2+x+1
}
error_types = ['single', 'double', 'burst_short', 'burst_long', 'random']
error_labels = ['1ビット誤り', '2ビット誤り',
'バースト(≤r)', 'バースト(>r)', 'ランダム3ビット']
data_len = 32
n_trials = 5000
# シミュレーション実行
results = {}
for gen_name, gen in generators.items():
rates = []
for etype in error_types:
rate = simulate_error_detection(data_len, gen, etype, n_trials)
rates.append(rate)
results[gen_name] = rates
# 結果表示
print(f"{'誤りタイプ':<18}", end="")
for gen_name in generators:
print(f"{gen_name:>22}", end="")
print()
print("-" * 84)
for i, label in enumerate(error_labels):
print(f"{label:<18}", end="")
for gen_name in generators:
print(f"{results[gen_name][i]:>21.4f}", end="")
print()
このシミュレーションの結果から、以下のことが読み取れます。
- 1ビット誤りの検出率は 1.0（100%） です。すべての生成多項式の定数項が $1$ であるため、理論通りすべての1ビット誤りが検出されます。
- 2ビット誤りの検出率もほぼ 1.0 です。データ長 32 ビットは、いずれの生成多項式の位数よりも十分小さいためです。
- バースト長 $\leq r$ の誤りの検出率は 1.0 です。これも理論の保証通りです。
- バースト長 $> r$ の誤りの検出率は 1.0 未満 ですが、CRC の次数 $r$ が大きいほど 1.0 に近づきます。CRC-8 では $1 – 2^{-7} \approx 0.9922$ が理論値です。
検出率のバースト長依存性の可視化
バースト誤りの長さを変化させたとき、検出率がどう変わるかを可視化します。
import numpy as np
import matplotlib.pyplot as plt
def crc_encode(data_bits, generator):
"""ビット単位のCRC符号化"""
r = len(generator) - 1
padded = np.concatenate([data_bits, np.zeros(r, dtype=int)])
for i in range(len(data_bits)):
if padded[i] == 1:
padded[i:i+len(generator)] ^= generator
return np.concatenate([data_bits, padded[-r:]])
def crc_check(received, generator):
"""ビット単位のCRC検査"""
r = len(generator) - 1
buf = received.copy()
for i in range(len(received) - r):
if buf[i] == 1:
buf[i:i+len(generator)] ^= generator
return np.all(buf[-r:] == 0)
def simulate_burst_detection(data_len, generator, burst_len, n_trials=5000):
"""特定のバースト長に対する検出率"""
r = len(generator) - 1
n = data_len + r
if burst_len > n:
return None
detected = 0
valid_trials = 0
for _ in range(n_trials):
data = np.random.randint(0, 2, data_len)
codeword = crc_encode(data, generator)
# バースト誤り生成
start = np.random.randint(0, max(1, n - burst_len + 1))
burst = np.random.randint(0, 2, burst_len)
burst[0] = 1
burst[-1] = 1
error = np.zeros(n, dtype=int)
error[start:start+burst_len] = burst
if np.all(error == 0):
continue
valid_trials += 1
received = codeword ^ error
if not crc_check(received, generator):
detected += 1
return detected / valid_trials if valid_trials > 0 else 0
# CRC-8で実験
generator_crc8 = np.array([1, 0, 0, 0, 0, 0, 1, 1, 1])
r = 8
data_len = 64
burst_lengths = list(range(2, 20))
detection_rates = []
for bl in burst_lengths:
rate = simulate_burst_detection(data_len, generator_crc8, bl, n_trials=5000)
detection_rates.append(rate)
# 理論値
theory_rates = []
for bl in burst_lengths:
if bl <= r:
theory_rates.append(1.0)
elif bl == r + 1:
theory_rates.append(1.0 - 2**(-(r-1)))
else:
theory_rates.append(1.0 - 2**(-r))
# 可視化
plt.figure(figsize=(10, 6))
plt.plot(burst_lengths, detection_rates, 'o-', color='#00e5ff',
markersize=6, label='シミュレーション', linewidth=2)
plt.plot(burst_lengths, theory_rates, 's--', color='#ff6e40',
markersize=6, label='理論下限', linewidth=2)
plt.axvline(x=r, color='#ffd740', linestyle=':', linewidth=1.5,
label=f'r = {r} (CRC bit数)')
plt.axvline(x=r+1, color='#69f0ae', linestyle=':', linewidth=1.5,
label=f'r + 1 = {r+1}')
plt.xlabel('Burst Length (bits)', fontsize=12)
plt.ylabel('Detection Rate', fontsize=12)
plt.title('CRC-8: Burst Error Detection Rate vs Burst Length', fontsize=14)
plt.legend(fontsize=11)
plt.ylim(0.98, 1.005)
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('crc8_burst_detection.png', dpi=150, bbox_inches='tight')
plt.show()
グラフから、以下の重要な事実が読み取れます。
- バースト長 $\leq 8$（= $r$）のとき、検出率は完全に 1.0 です。青い丸がすべて $1.0$ に張り付いており、理論の「長さ $r$ 以下のバースト誤りは100%検出」が実験でも裏付けられています。
- バースト長が $r$ を超えると検出率がわずかに下がる ものの、CRC-8 でも $0.992$ 以上（理論下限 $1 – 2^{-7} \approx 0.9922$）を維持しています。シミュレーション値は理論下限よりもやや高くなっていますが、これは理論値が「最悪ケース」の下限であるためです。
- バースト長 $= r + 1$ と $> r + 1$ で理論下限が変わる ことがオレンジの破線で確認できます。$r + 1$ では $1 – 2^{-(r-1)}$、それ以上では $1 – 2^{-r}$ です。
CRC-32 のシミュレーション
最後に、実用的な CRC-32 を使って、データ破損の検出を行います。
import numpy as np
import binascii
import matplotlib.pyplot as plt
def inject_burst_error(data, start, length):
"""バイト列にバースト誤りを注入"""
data_array = bytearray(data)
bit_len = len(data_array) * 8
for i in range(length):
bit_pos = start + i
if bit_pos >= bit_len:
break
byte_idx = bit_pos // 8
bit_idx = 7 - (bit_pos % 8)
# ランダムにビットを反転
if np.random.random() > 0.3:
data_array[byte_idx] ^= (1 << bit_idx)
return bytes(data_array)
# CRC-32による誤り検出のデモ
np.random.seed(42)
# テストデータ
original_data = b"The quick brown fox jumps over the lazy dog"
original_crc = binascii.crc32(original_data) & 0xFFFFFFFF
print(f"元データ: {original_data}")
print(f"CRC-32: 0x{original_crc:08X}")
print(f"データ長: {len(original_data)} bytes = {len(original_data)*8} bits")
print()
# さまざまな誤りパターンのテスト
error_scenarios = [
("1ビット反転 (先頭)", 0, 1),
("1ビット反転 (末尾)", len(original_data)*8 - 1, 1),
("8ビットバースト", 50, 8),
("16ビットバースト", 100, 16),
("32ビットバースト", 150, 32),
("64ビットバースト", 50, 64),
]
print(f"{'シナリオ':<26} {'CRC値':>12} {'検出':>6}")
print("-" * 50)
for name, start, length in error_scenarios:
corrupted = inject_burst_error(original_data, start, length)
corrupted_crc = binascii.crc32(corrupted) & 0xFFFFFFFF
detected = corrupted_crc != original_crc
print(f"{name:<26} 0x{corrupted_crc:08X} {'検出' if detected else '見逃し'}")
# 大規模シミュレーション: バースト長ごとの検出率
burst_lengths_test = [1, 2, 4, 8, 16, 24, 32, 33, 40, 48, 64]
n_sim = 10000
detection_results = []
for bl in burst_lengths_test:
detected_count = 0
for _ in range(n_sim):
data = np.random.bytes(64)
start = np.random.randint(0, 64 * 8 - bl)
corrupted = inject_burst_error(data, start, bl)
if corrupted != data:
original_crc_val = binascii.crc32(data) & 0xFFFFFFFF
corrupted_crc_val = binascii.crc32(corrupted) & 0xFFFFFFFF
if original_crc_val != corrupted_crc_val:
detected_count += 1
rate = detected_count / n_sim
detection_results.append(rate)
# 可視化
fig, ax = plt.subplots(figsize=(10, 6))
ax.bar(range(len(burst_lengths_test)), detection_results,
color=['#00e5ff' if bl <= 32 else '#ff6e40' for bl in burst_lengths_test],
alpha=0.8, edgecolor='white', linewidth=0.5)
ax.set_xticks(range(len(burst_lengths_test)))
ax.set_xticklabels([str(bl) for bl in burst_lengths_test])
ax.set_xlabel('Burst Error Length (bits)', fontsize=12)
ax.set_ylabel('Detection Rate', fontsize=12)
ax.set_title('CRC-32: Burst Error Detection Rate (10,000 trials per length)', fontsize=14)
ax.set_ylim(0.99, 1.005)
ax.axvline(x=burst_lengths_test.index(32) + 0.5, color='#ffd740',
linestyle='--', linewidth=2, label='r = 32 boundary')
ax.legend(fontsize=11)
ax.grid(True, alpha=0.3, axis='y')
plt.tight_layout()
plt.savefig('crc32_detection_simulation.png', dpi=150, bbox_inches='tight')
plt.show()
print(f"\n{'バースト長':>10} {'検出率':>10} {'理論保証':<20}")
print("-" * 45)
for bl, rate in zip(burst_lengths_test, detection_results):
if bl <= 32:
theory = "100% (b ≤ r)"
elif bl == 33:
theory = f"≥ {1-2**(-31):.10f}"
else:
theory = f"≥ {1-2**(-32):.10f}"
print(f"{bl:>10d} {rate:>10.6f} {theory:<20}")
この結果から、CRC-32 の実用上の強力さが明確に確認できます。バースト長 32 ビット以下のすべてのケースで検出率が 1.0 であり、33ビット以上でもほぼ $1.0$ に近い値を示しています。64バイトのランダムデータに対する 10,000 回の試行でも見逃しはほとんど発生しません。これが Ethernet や ZIP などの実用プロトコルが CRC-32 を採用する理由です。
パリティ・チェックサム・CRC の比較
ここまでに学んだ3つの誤り検出方式を総合的に比較しておきましょう。
| 特性 | パリティ | チェックサム | CRC |
|---|---|---|---|
| 冗長ビット数 | 1ビット | 8〜32ビット | 8〜32ビット（可変） |
| 計算コスト | 極めて低い | 低い | 中程度 |
| 1ビット誤り検出 | 可能 | 可能 | 可能 |
| 2ビット誤り検出 | 不可 | 確率的 | 保証あり（条件付き） |
| バースト誤り検出 | 保証なし | 限定的 | $r$ ビットまで完全保証 |
| 数学的保証 | 弱い | 弱い | 強い（代数的） |
| 主な用途 | UART | IP, TCP/UDP | Ethernet, ストレージ |
CRC はパリティやチェックサムに比べて計算コストがやや高いものの、その検出能力の差は圧倒的です。特に、バースト誤りに対する完全な検出保証は、他の方式にはない CRC 独自の強みです。
まとめ
本記事では、誤り検出の基礎からCRC（巡回冗長検査）の理論と実装までを解説しました。
- パリティチェックは最も単純な誤り検出方式ですが、偶数個の誤りを見逃す弱点があります
- チェックサムはバイト単位の算術演算で検出能力を向上させますが、数学的保証が弱いです
- CRC はGF(2)上の多項式除算に基づき、バースト誤り検出に関する厳密な理論的保証を持ちます
- 生成多項式 $G(x)$ の次数 $r$ 以下のバースト誤りはすべて検出でき、それ以上でも $1 – 2^{-r}$ 以上の確率で検出できます
- CRC-32 は Ethernet、ZIP、PNG など無数の規格で採用されており、32ビット以下のバースト誤りを完全に検出します
- シフトレジスタ回路やルックアップテーブルにより、ハードウェア・ソフトウェア双方で効率的に実装できます
CRC は「誤りの存在を検出する」技術ですが、誤りの位置を特定して訂正することはできません。CRC で誤りが検出された場合、通常は再送制御（ARQ: Automatic Repeat reQuest）でデータの再送を要求します。一方、再送が困難な状況（リアルタイム通信や深宇宙通信など）では、誤り訂正符号（FEC: Forward Error Correction）を CRC と組み合わせて使います。
次のステップとして、以下の記事も参考にしてください。