誤り検出・訂正をやさしく図解 — パリティチェック・CRC・バースト誤り・ハミング符号

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

なぜ誤り検出が必要か

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

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

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

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

見逃すのは2ビットだけではありません。1ビット化けるたびに1の個数の偶奇が入れ替わるので、誤ったビットが奇数個なら検出、偶数個なら見逃す、というのがパリティチェックの正確な性質です。

ノイズで数ビットがまとめて化けると、誤りの個数が偶数になる可能性は十分にあります。この「まとめて化ける」誤りが、このあと説明するバースト誤りです。

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

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

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

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

バースト誤りとは — 近くのビットがまとめて化ける誤り

バースト誤りとは、近くにある複数のビットがまとめて誤る誤りのことです。雷やモーターなどの電気ノイズ、無線の電波の乱れ、記録面の傷は、一瞬で数ビット〜数十ビットに影響します。そのため実際の通信や記録では、誤りがばらばらに散らばるより、1か所に固まって起きることが多くあります。

最初に誤ったビットから最後に誤ったビットまでの長さをバースト長と呼びます。間のビットがすべて誤っている必要はなく、たとえば「1ビット目と4ビット目が誤り、2・3ビット目は無事」でもバースト長は4です。

このように、パリティチェックはバースト誤りに弱い方式です。そこで、バースト誤りまでしっかり検出するために使われるのが、次のCRCです。

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

CRC（巡回冗長検査、Cyclic Redundancy Check）は、データを生成多項式と呼ばれる決まったビット列で割り、その余りを検査用のビットとして付ける方法です。受信側で同じ割り算をして、余りが合わなければ誤りと判定します。検出専用で訂正はできませんが、検出力はパリティよりずっと高いです。

CRCの計算方法（手順）

1. 送信側：データの後ろに、生成多項式の次数と同じ個数の0を付ける（次数3なら0を3個）
2. それを生成多項式のビット列で割り、余りを求める
3. 付けた0の部分を余りに置き換えて送る
4. 受信側：受け取ったビット列全体を同じ生成多項式で割る。余りが0なら誤りなし、0以外なら誤りあり

ここでの割り算は、ふつうの割り算とは少し違う「2を法とする割り算」です。繰り上がり・繰り下がりがなく、引き算の代わりにXORを使います。XORは「同じなら0、違えば1」なので、筆算の各段は「先頭が1なら生成多項式をXORする」だけのくり返しになります。

CRCの計算例 — データ1101、生成多項式 x³＋x＋1

生成多項式 x³＋x＋1 は、x³・x²・x¹・x⁰ の係数を並べてビット列 1011 と表します（x²の項がないので2桁目が0）。次数は3なので、検査ビットは3ビットです。データ 1101 の後ろに0を3個付けた 1101000 を、1011 で割っていきます。

  1101000   ← データ1101の後ろに0を3個付ける
  1011      ← 先頭が1なので、1011をXOR
  -------
  0110000
   1011     ← 次の1の位置にそろえてXOR
  -------
  0011100
    1011
  -------
  0001010
     1011
  -------
  0000001   ← 残った下3桁「001」が余り

余りは 001。送信するのは、データの後ろに余りを付けた 1101001 です。

表の最後の行は、2ビットがまとめて化けたケースです。1の個数は4個のままでパリティなら見逃しますが、CRCでは余りが0にならず、ちゃんと誤りに気づけます。

CRCがバースト誤りに強い理由

CRCには、検査ビットがrビット（生成多項式の次数がr）なら、長さr以下のバースト誤りは必ず検出できるという性質があります（x⁰の項が1の生成多項式の場合。実際に使われる生成多項式はこの条件を満たしています）。上の例は検査ビット3ビットなので、長さ3以下のバースト誤りはどこで起きても見逃しません。

実用ではCRC-32（検査ビット32ビット）がよく使われ、32ビット以下のバースト誤りはすべて検出できます。それより長い誤りでも、偶然に余りが一致して見逃すのは、およそ数十億回に1回程度です。

CRCはどこで使われている？

イーサネットのFCSは、フレームの末尾に付く4バイトの検査値です。受信したNICやスイッチはCRCを計算し直し、合わないフレームは捨てます。フレームやMACアドレスの話は IPアドレスとMACアドレスの違い も役に立ちます。

なお、CRCが防ぐのはノイズなどによる偶然の誤りです。計算方法が公開されているため、悪意のある改ざんなら余りまで合わせて書き換えられてしまいます。改ざん対策には、暗号学的ハッシュ関数や、それを使ったディジタル署名を使います（ディジタル証明書とは？）。

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

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

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

誤り検出・訂正の方式を比較

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

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

CRCでは「生成多項式で割った余りを検査に使う」「バースト誤りの検出に適している」の2点がよく問われます。選択肢に「誤りを訂正できる」とあればCRCでは誤り、と判断できるようにしておきましょう。

よくある質問

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

Q. バースト誤りとは？
A. 近くにある複数のビットがまとめて誤る誤りです。ノイズや傷は一瞬で数ビット〜数十ビットに影響するため、誤りが1か所に固まって起きます。パリティチェックは誤ったビットが偶数個だと見逃しますが、CRCは検査ビット数以下の長さのバースト誤りをすべて検出できます（くわしくは上の解説）。

Q. CRCの計算方法は？
A. データの後ろに生成多項式の次数ぶんの0を付け、生成多項式で割った余りを求めます。割り算はXORを使う「2を法とする割り算」です。余りをデータの後ろに付けて送り、受信側で全体を割って余りが0なら誤りなしと判定します。手計算の例は本文の「CRCの計算例」を見てください。

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

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

まとめ

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

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