誤り検出・訂正をやさしく図解 — パリティ・CRC・ハミング符号

通信や記録では、ノイズでビットが化けることがあります。「化けたと気づく」のが誤り検出、「化けた場所を直す」のが誤り訂正。この記事では、パリティチェックから、CRC、そして訂正までできるハミング符号までを、XORの考え方とともに図解します。XORの基礎は 論理演算と真理値表 もどうぞ。

なぜ誤り検出が必要か

データは、通信ケーブルや電波、ディスクなどを通るとき、ノイズや劣化で0が1に、1が0に化けることがあります。届いたデータが正しいかを確かめる仕組みがないと、化けたデータをそのまま信じてしまいます。そこで、元のデータに検査用の情報（冗長ビット）を付け加えて送り、受信側でつじつまを確認します。これが誤り検出・訂正の基本発想です。

パリティチェック — 1の個数の偶奇でチェック

もっとも基本的な方法です。データにパリティビットを1つ足して、1の個数を偶数（偶数パリティ）または奇数（奇数パリティ）にそろえます。受信側で1の個数を数え、決めた偶奇と違えば「どこかで誤りが起きた」と分かります。

パリティチェックは1ビットの誤りを検出できますが、どこが誤ったかは分からず（訂正できない）、2ビットが同時に化けると見逃します（偶数のままになるため）。手軽ですが検出力は限定的です。なお「1の個数の偶奇」は、全ビットのXORを取ることと同じです。

水平垂直パリティ — 位置まで絞る

データを縦横の表に並べ、各行と各列の両方にパリティを付けると、誤ったビットの「行」と「列」が交差点として分かり、1ビットなら位置を特定して訂正できるようになります。パリティを二次元に拡張した考え方で、訂正への第一歩です。

チェックディジット — 入力ミスを防ぐ検査数字

バーコードや会員番号などの末尾に付く検査用の1桁がチェックディジットです。番号の各桁から決まった計算をして末尾の桁を決めておき、入力後に同じ計算をして合わなければ「打ち間違い」を検出します。人間の入力ミス（数字の打ち間違い・順序の入れ替え）対策として身近に使われています。

CRC — バースト誤りに強い検出

CRC（巡回冗長検査）は、データを特定の値（生成多項式）で割った余りを検査符号として付ける方法です。受信側で同じ計算をして余りが合わなければ誤りと判定します。連続した複数ビットの誤り（バースト誤り）に強いのが特長で、通信（イーサネット等）やストレージで広く使われています。検出専用で訂正はできませんが、検出力はパリティよりずっと高いです。

ハミング符号 — 誤りを「訂正」できる

ここまでは主に「検出」でしたが、ハミング符号は1ビットの誤りなら位置を特定して訂正できます。仕組みは、複数のパリティビットを重ねて配置し、それぞれが監視する範囲を工夫すること。受信側で各パリティを検査した結果（シンドローム）が、そのまま誤ったビットの位置を示す番号になるよう設計されています。位置が分かれば、そのビットを反転するだけで訂正完了です。

ただし、訂正には検出だけより多くの冗長ビットが必要です。「どこまで検出・訂正したいか」と「付けるビット数（コスト）」はトレードオフになります。

基本情報技術者試験ではこう出る

「パリティチェックで検出できる誤り（1ビット）・できない誤り（2ビット）」「偶数パリティのパリティビットを求める」「誤り検出と訂正の違い」「ハミング符号は訂正できる／CRCは検出のみ」「チェックディジットの目的」が定番です。押さえるべきは、パリティ＝1ビット検出のみ、CRC＝検出力が高い、ハミング符号＝1ビット訂正できるという役割の違い。パリティ＝XOR、という視点も持っておくと理解が速いです。

よくある質問

Q. 偶数パリティと奇数パリティ、どちらが優れている？
A. 検出力は同じです。違うのは「1の個数を偶数にそろえるか奇数にそろえるか」という取り決めだけ。送信側と受信側で同じ方式を使っていれば、どちらでも1ビット誤りを検出できます。

Q. チェックサムとCRCの違いは？
A. チェックサムはデータの値を単純に足し合わせた合計（の一部）を検査に使う手軽な方法で、検出力は高くありません。CRCは割り算の余りを使うより高度な方法で、バースト誤りに強く検出力が高いです。用途に応じて使い分けます。

Q. 再送との関係は？
A. 通信では、誤りを検出したら送り直してもらう（再送）方式がよく使われます（TCPなど）。一方、再送が難しい場面（放送・記録メディア）では、受信側だけで直せる訂正符号が重宝します。TCPの確認応答と再送は TCPコネクションの可視化 で見られます。

まとめ

誤り対策は、検出（気づく）と訂正（直す）の2段階。パリティ＝1ビット検出（2ビットは見逃す・パリティはXOR）、CRC＝検出力が高い、ハミング符号＝1ビット訂正できる。訂正には多くの冗長ビットが要る、というトレードオフも押さえておきましょう。パリティの正体はXORなので、論理演算とセットで理解すると腹落ちします。

関連ページ: 論理演算と真理値表 ／ 2進数と基数変換 ／ 論理回路シミュレータ ／ 記事一覧