誤り検出の原理と実装 — CRC、チェックサム、パリティから現実的導入まで
エバープレイ編集部序章：誤り検出が重要な理由
データ通信や記憶装置で扱うビット列は、物理層や媒体のノイズ、ハードウェアの不具合、ソフトウェアのバグなどにより書き換えや破損が生じる可能性があります。誤り検出（error detection）は、受信側や後続処理がデータの正当性を評価し、破損したデータを検出して再送や復旧処理に繋げるための機構です。本稿では、基本原理から主要手法、実装上の注意点、応用例、セキュリティ上の留意点までを詳しく解説します。
誤り検出の基礎概念
誤り検出技術を理解するための基本的な用語と考え方を整理します。
- ビットエラー：送受信の過程で0↔1が反転する現象。
- 誤り検出率（検出能力）：与えられた誤りモデルに対して誤りを検出できる確率。典型的には「未検出誤り」の確率を小さくすることが目標です。
- オーバーヘッド：誤り検出情報（パリティビット、チェックサム、CRCなど）が占める追加ビット数。トレードオフは検出能力とオーバーヘッド。
- 誤りモデル：ビット誤りが独立に発生するランダム誤り、連続したビットが破壊されるバースト誤りなど。手法によって検出に強い誤りタイプが異なります。
主な誤り検出手法
ここでは実務で多用される代表的な技術を取り上げ、仕組みと特徴を説明します。
1) パリティビット
最も単純な手法で、データブロックのビットの1の数の偶奇を1ビットで表します。単一ビット誤りは検出できますが、2ビット誤りなど偶数個の誤りは検出できません。オーバーヘッドが極小である一方、検出能力は限定的です。
2) 単純チェックサム（加算型）
データをワード単位で加算して生じる下位ビットを付加する方式です（例：IP/TCPのチェックサムは16ビットワードの1の補数和）。ランダムな誤りに対してある程度の検出能力がありますが、順序の入れ替えや特定の誤りパターンでは未検出となることがあります。
3) Fletcher や Adler
Fletcher チェックサムや Adler-32 は単純加算の改良版で、累積和を2つの値で取るなどして検出性を向上させます。高速かつ実装が容易なのでアプリケーションレベルや圧縮フォーマットで用いられますが、暗号的強度はありません。
4) CRC（巡回冗長検査）
CRC は誤り検出で最も広く使われる手法の一つで、ビット列を多項式とみなして生成多項式で割った余り（剰余）を付加します。CRC の主な利点は以下の通りです。
- 生成多項式の次数 r により r ビットの CRC が得られ、全ての長さ ≤ r のバースト誤りを必ず検出します。
- 設計した多項式により特定の誤りパターンに対して高い検出確率を実現できます。
- ハードウェア実装が容易で、シリアル処理でも高速に動作します（1-bit-at-a-time シフトレジスタなど）。
代表的な例として Ethernet の FCS は CRC32、HDLC/PPP などで 16 ビット CRC、組み込み用途では CRC8 が使われます。CRC の数学的基盤は多項式演算（GF(2) の多項式割り算）で、生成多項式の選択が検出性に直結します。
5) 暗号学的ハッシュ（MD5, SHA-系）
MD5 や SHA-1/256 といったハッシュは整合性検査に使えますが、誤り「検出」自体を目的にするとオーバースペックです。計算コストが高く、主に改竄（攻撃）耐性を必要とする場面で用います。一般的な通信のビット誤り検出では CRC 等がよく選ばれます。
6) エラー訂正符号（ECC）との関係
誤り検出と誤り訂正は目的が異なります。Hamming 符号や Reed–Solomon、BCH は誤り検出に加え訂正能力を持ち、ストレージやディスク、無線通信で広く使われます。訂正付き符号は検出だけでなくその場での修復を可能にするため、ストレージや深宇宙通信など再送が困難な環境で重要です。
CRC の数学的性質（詳細）
CRC を理解する上での重要点を少し深掘りします。
- データビット列を多項式 D(x) と表現し、生成多項式 G(x)（次数 r）で割った余り R(x) を付加します。送信時には T(x)=x^r D(x)+R(x) を送ります。受信側は T'(x) を G(x) で割り、余りが 0 ならば整合と判断します。
- 性質：もし伝播した誤りを E(x) と表すと、受信値は T(x)+E(x)。割り算の余りが 0 となるのは G(x) が E(x) を割り切る場合のみ。よって G(x) の選定次第で特定の誤りを全て検出できます。
- 一般的な結果：CRC の次数 r はすべてのバースト誤り長 ≤ r を確実に検出。さらに、特定の多項式は任意の奇数個のビット誤りを検出する性質を持つ（x+1 を因子に持つかどうかで異なる）。
実装上の注意点
誤り検出方式を実装する際に注意すべき点を列挙します。
- バイトオーダ（エンディアン）：チェックサムや CRC の計算順序はプロトコルで定義されるため、送受信で一致させること。
- パディングと初期値／反転（refin/refout、xorout）：多くの CRC 実装は初期レジスタ値や入出力ビット反転を行うため、仕様に合わせる必要があります。
- 性能：ソフトウェアでの高速化（テーブル駆動法、Slicing-by-8 など）や、CPU の専用命令（x86 の CRC32C 命令）を利用すると大きく高速化可能です。
- ハードウェア耐性：ハードウェア実装は高スループットかつ低レイテンシですが、生成多項式の変更が難しい点に注意。
ネットワークとストレージにおける実例
誤り検出が実際にどのように使われているか、代表的な適用例を示します。
- Ethernet：フレーム末尾の FCS（CRC32）により物理層でのバースト誤り検出を行い、破損フレームは破棄される。
- IP/TCP/UDP：IP/TCP は 16 ビットの1の補数チェックサムを利用。簡易で高速だが検出性は CRC より低い。
- ストレージ（ZFS, Btrfs等）：ZFS はブロックの整合性チェックに強力なチェックサム（Fletcher, SHA-256 など）を使い、壊れたデータの検出とリダンダントコピーによる修復を行う。
- 圧縮フォーマット（gzip）：Adler-32 や CRC32 を利用して解凍時のデータ整合性を検証。
誤り検出とセキュリティ
誤り検出はデータ破損を検出するための手段であり、攻撃耐性（改竄検出）とは異なる概念です。CRC やチェックサムは改竄に対して脆弱で、悪意ある相手がデータを変更してチェック値を同時に計算し直せば検出されません。改竄や改竄による不正検知が必要なら暗号的ハッシュ（SHA-256 など）とデジタル署名を使うべきです。
未検出誤り確率の概算
ランダム誤りモデルにおける未検出確率は、一般にチェックビット数 k に対して約 1/2^k と概算できます（ただしアルゴリズムの性質や誤りモデルによって上下）。例えば 32 ビット CRC の場合、単純なランダムエラーに対する未検出確率は非常に低くなりますが、特定の構造化された誤りや攻撃には脆弱です。
ベストプラクティス（実務向けガイド）
- 用途に応じて手法を選ぶ：ネットワークのフレーム誤り検出は CRC、アプリケーションレベルの整合性は高速チェックサムまたは暗号ハッシュ、ストレージは強力なチェックサム＋冗長化を組み合わせる。
- 仕様に忠実な実装：既存プロトコルの CRC 設定（多項式、初期値、入出力反転、XOR 出力）に合わせる。
- 性能と安全性のバランス：高スループットを要する場合はハードウェアアクセラレーションやテーブル方式を検討するが、セキュリティ要件が高ければ暗号学的手法を併用する。
- 監視とログ：未検出誤りは発見が遅れる危険があるため、チェック失敗率の監視やデータ整合性の定期検査を行う。
まとめ
誤り検出は通信やストレージの信頼性を担保する基礎技術です。単純なパリティから高度な CRC、多項式の選定、さらに暗号的ハッシュとの使い分けまで、用途と脅威モデルに応じて適切な手法を選ぶことが重要です。実装では仕様の厳密な踏襲、エンディアンやパディングの取り扱い、性能最適化手法の適用を怠らないようにしてください。
参考文献
- RFC 1071 - Computing the Internet Checksum
- Ross Williams - A Painless Guide to CRC
- Wikipedia - Cyclic redundancy check
- Wikipedia - Fletcher's checksum
- Wikipedia - Adler-32
- Wikipedia - Hamming code
- Wikipedia - Reed–Solomon error correction
- Wikipedia - Ethernet frame (FCS/CRC32)
- OpenZFS - FAQ (checksums and end-to-end verification)
投稿者プロフィール
