パリティチェックとCRCとは ― 誤り検出の仕組み

パリティチェックとCRCは、データの誤りを検出する仕組みです。送信側は検査用の値を計算して、データに付けます。受信側は同じ計算をやり直して、届いた値と比べます。パリティチェックは、1の個数の偶奇を使う単純な計算です。CRCは、生成多項式で割った余りを使う、より強力な計算です。

EthernetのフレームではCRCの値を末尾のFCSに入れ、誤りのあるフレームは捨てます。捨てたデータを再送するのは、上の層のTCPです。

通信では、データを電気信号・光・電波として送ります。信号は、本来の値と違う形で届くことがあります。原因は、ケーブル近くの電気ノイズや無線LANの電波干渉、光ファイバの劣化などです。

届いた信号は、0か1かに判定し直されます。このとき、本来1だったビットが0に化けてしまうことがあります。これをビット誤りと呼びます。

通信技術が発達しても、ビット誤りが起きる可能性をゼロにはできません。そこで通信では、誤りを起こさない工夫に加えて、誤りが起きたことに気づける仕組みを用意します。これが誤り検出です。

1. 1

   誤り検出

   届いたデータに誤りがあるかないかだけを判定します。どのビットが間違っているかは分かりません。誤りが見つかったデータは、捨てるか、再送を頼みます。

2. 2

   誤り訂正

   誤りがあるかないかに加えて、どのビットが間違っているかまで特定します。特定したビットは、その場で元に戻します。再送を待たずに済みますが、検出だけの方式より多くの検査ビットが必要です。

パリティチェック・チェックサム・CRCは、基本的に誤り検出の方式です。ハミング符号は、誤り訂正もできる代表的な方式です。メモリのECCなどに使われます。

パリティチェックは、データ中の1の個数が偶数か奇数かを利用する、最も単純な誤り検出の方式です。送信側は、データの末尾にパリティビットを1ビット付け足します。あらかじめ決めたルールに合わせて、その値を選びます。

受信側は、届いたデータ部分だけを使って同じ計算をやり直します。計算し直した値と届いたパリティビットが一致すれば誤りなし、一致しなければ誤りありと判定します。

1ビットが反転すると、1の個数は必ず1個増減します。そのため偶奇が必ず変わり、1ビットの誤りは必ず検出できます。一方、偶数個のビットが反転すると、1の個数が偶数個ぶん増減するので、偶奇は変わりません。偶数個の誤りは必ず見逃されます。次の2つの図で、この動きを確かめられます。

7ビットのデータの各ビットを押すと0と1が切り替わり、右端のパリティビットが自動で計算されます。偶数パリティと奇数パリティの切り替えで、値がどう変わるか確かめられます。

データにパリティビットを付けたものを、符号語と呼びます。下の図では、送信した符号語に通信中に起きることを、誤りなし・1ビット反転・2ビット反転の3つから選べます。選んだ内容によって、受信側の判定がどう変わるかを確かめられます。

ここまでのパリティチェックは、垂直パリティとも呼ばれます。垂直パリティだけでは、誤り検出しかできません。データをブロックごとに並べて、各行のパリティと各列のパリティの両方を付ける方法もあります。こうすると、1ビットの誤りを訂正できるようになります。

次の例は、3×3のデータに、行ごとの偶数パリティと列ごとの偶数パリティを付けたものです。

行2・列3のビットが通信中に1から0へ化けたとします。受信側が行ごと・列ごとにパリティを計算し直すと、行2と列3のパリティが合わなくなります。誤りは、パリティが合わない行と列が交わるマスだと特定できます。そのビットを反転すれば、訂正できます。

行と列という2方向からそれぞれ独立にチェックすることで、誤りの位置まで絞り込めます。次のハミング符号も、検査ビットの組み合わせから位置を特定する、同じ発想を使います。

チェックサムは、データを一定のビット数ごとに区切って足し合わせる方式です。その合計を、検査用の値にします。パリティチェックが使うのは、1の個数の偶奇だけです。チェックサムは合計値そのものを使うため、より多くの誤りを検出できます。

IPヘッダ・TCPヘッダ・UDPヘッダには、それぞれチェックサムの欄があります。ルーティングの記事で説明したとおり、ルータを1台通過するたびに、IPヘッダのTTLは1減ります。IPヘッダのチェックサムは、このとき同時に再計算されます。TCP・UDPのヘッダにも同じ欄があり、データ部分も含めた誤りを検出します。

CRCは、データを2進数の値とみなして割り算をする方式です。割る数には、あらかじめ決めた定数を使います。この定数を生成多項式と呼びます。割ったときの余りが、検査用の値になります。

計算は複雑ですが、見逃す確率が低い方式です。特に、連続した複数ビットの誤りに強い特徴があります。このような誤りを、バースト誤りと呼びます。

CRCの割り算では、ふつうの引き算の代わりにXOR演算を使います。XOR演算は、桁ごとに同じなら0、違えば1になる演算です。生成多項式の次数がnのとき、検査用の値はnビットになります。

カプセル化の記事で説明した、Ethernetフレーム末尾のFCSは、32ビットのCRCであるCRC-32です。ネットワークで最も広く使われているCRCの実例です。CRC-32のほかにも、生成多項式の長さが違うCRC-8やCRC-16など、用途に応じたビット数のCRCがあります。

CRCは、通信中の偶発的な誤りを見つける仕組みです。意図的な改ざんの検知には使えません。攻撃者はデータを書き換えたうえで、合うCRCを計算し直して付け直せるからです。改ざんの検知には、秘密の鍵を使う別の仕組みが必要です。

短い例で、実際にCRCを手計算します。データを1101、生成多項式を1011とします。1011は、x³+x+1を2進数で表したものです。生成多項式が4ビットなので、データの末尾に0を3個足してから割り算を始めます。

4段のXOR演算を終えると、末尾3ビットに余り001が残ります。これがCRCです。送信するデータは、元のデータの末尾にこのCRCを付けた1101001になります。

受信側は、届いた1101001を同じ生成多項式で割り直します。誤りがなければ、余りは000になります。送信した7ビットのうちどこか1ビットだけを反転させて割り直すと、7通りのどの位置でも余りは000になりません。このCRCでは、すべての1ビット誤りが検出できます。

ハミング符号は、誤りが起きたビットの位置を特定できる方式です。そのために、複数の検査ビットを、それぞれ異なるビットの組み合わせから計算しておきます。位置が分かれば、そのビットを反転させるだけで元に戻せます。

よく使われる(7,4)ハミング符号は、4ビットのデータに3ビットの検査ビットを加えて、7ビットの符号にします。(7,4)ハミング符号は、1ビットの誤りを訂正できます。

たとえば、データ1011を符号化すると、符号0110011ができます。このうち5ビット目を反転させて受信したとします。検査ビットの照合結果から、5ビット目が誤りだと特定できます。そのビットを反転させれば、元のデータに戻せます。

(7,4)ハミング符号だけでは、1ビットの誤りの訂正と2ビットの誤りの検出を同時には行えません。2ビットの誤りが起きても、検査ビットの照合結果は1ビットの誤りと同じように見えます。そのため、元の2ビットとは別のビットを必ず直してしまいます。

1ビットの訂正と2ビットの検出を同時に行うには、符号全体に1ビットの全体パリティを付け加えます。この形を、拡張ハミング符号（8,4）と呼びます。メモリのECCなどで1ビット訂正・2ビット検出と説明される方式は、この拡張ハミング符号の形です。

検査ビットの照合結果と全体パリティの両方が一致しなければ、1ビットの誤りとして位置を特定し、訂正できます。全体パリティのビットだけが反転した場合も1ビットの誤りとして検出でき、そのビットを戻せば訂正できます。照合結果だけが一致せず、全体パリティは一致するときは、2ビットの誤りが起きていると分かります。ただし、位置は特定できません。

誤りを検出したあとの対応は、層によって違います。

1. 1

   データリンク層：捨てるだけ

   OSI参照モデルの記事で説明したとおり、Ethernetは受信したフレームのFCSで誤りを検出すると、そのフレームを捨てるだけです。再送を頼む手続きは、Ethernet自身には含まれていません。

2. 2

   トランスポート層：再送を頼む

   TCPハンドシェイクの記事で説明したとおり、TCPは一定時間内にACKが返らなければ、同じデータを再送します。確認応答と再送を組み合わせて信頼性を確保する方式をARQと呼びます。UDPにはこの仕組みがありません。

Ethernetが誤りのあるフレームを捨てても、上位でTCPを使っていれば再送されます。送信側が、ACKが返ってこないことをきっかけに再送するからです。下位層が誤りを検出し、上位層が再送します。この組み合わせで、データが届いたかどうかが確かめられます。

一方、HDLCやベーシック手順は、データリンク層の中で再送まで行う手順です。その手順は、伝送制御の記事で説明しています。