CRCとは? 0と1の割り算で通信の誤りを見つけるしくみ

身近なところでは

ダウンロードしたZIPファイルを開こうとして、「ファイルが壊れています」と表示されたことはないでしょうか。ZIPファイルには、中のファイルごとに、中身から計算した検査用の値が書かれています。開くソフトは同じ値を計算し直し、合わなければ「壊れている」と判断します。この値がCRCです。

データは0と1の並びで運ばれ、保存されます。その途中で、0が1に、1が0にひっくり返ることがあります。ケーブルに入る電気の雑音、弱い電波、メモリに当たる宇宙からの粒子(ソフトエラー)などが原因です。

どれもめったに起きませんが、ゼロにはできません。例えば誤る割合が1兆ビットに1個でも、1秒に10億ビット送れば、約17分に1個は誤ります。そこで、受け取った側で確かめるしくみが必要になります。

検査用の値を付ける、という考え方

お店の商品のバーコード(JANコード)は、ふつう13桁の数字です。最後の1桁は、ほかの12桁から決まった計算で作った検査用の数字です。レジは同じ計算をして最後の1桁と合うかを確かめ、合わなければ読み直します。

「データから計算した短い値を一緒に送り、受け取った側で計算し直して比べる」。これが誤りを見つける基本の考え方です。CRCも同じ考え方で、計算のしかたが違うだけです。

いちばん簡単な検査: パリティ

0と1の並びで最も簡単なのは、1の個数を数える方法です。データの1の個数が偶数になるように、最後に0か1を1つ付け足します。この1ビットをパリティビットと呼びます。

例えば1011001は1が4個(偶数)なので、0を付けて10110010として送ります。途中で1ビットだけひっくり返ると、1の個数が奇数になるので、誤りに気づけます。

ところが、2ビットが同時にひっくり返ると、1の個数は偶数のままで、誤りを見逃します。雑音はある時間続けて入ることが多く、となり合う何ビットかがまとめて化けやすいのです。このひとかたまりの誤りをバースト誤りと呼びます。化けたビットが偶数個なら、パリティは見逃します。

足し算の検査: チェックサム

データを16ビットなどの塊に区切って全部足し、合計を付ける方法もあります。これをチェックサムと呼び、インターネットのIPやTCPで使われています(RFC 1071)。

ただし足し算は、順番を入れ替えても答えが同じです。そのため、塊どうしが入れ替わる誤りや、ある塊が1増えて別の塊が1減る誤りを見逃します。CRCは、ビットの位置まで区別できるように計算を工夫した方法です。

CRCが使われている所

CRCは、身の回りの通信やファイルで広く使われています。名前の後の数字は、検査用の値のビット数です。

イーサネットでは、データを「フレーム」というまとまりに分けて送り、最後に4バイト(32ビット)のCRCを付けます。この部分をFCS(フレームの検査用の並び)と呼びます。

受け取った機器は、FCSが合わないフレームを捨てます。イーサネット自身は送り直さず、欠けたデータは、TCPというしくみが送り直します。Wi-Fiでは、正しく届くと受け取った側が返事を返し、返事がなければ送り直します(「Wi-Fiのしくみとは?」)。

しくみ1: 繰り上がりのない、0と1だけの計算

CRCの計算は、ふつうの算数とは少し違う「0と1だけの世界」で行います。この世界の足し算の規則は、次の3つです。

• 0+0=0
• 0+1=1、1+0=1
• 1+1=0(繰り上がりはない)

ふつうの2進数なら1+1=10と繰り上がりますが、ここでは繰り上がりを捨てます。すると「2つが違えば1、同じなら0」となり、XORと同じ規則になります。足し算の回路(半加算器)から、繰り上がりの出力を外したものです。

引き算も同じ規則になります。0−1は「1を足すと0になる数」なので、1+1=0から1です。つまりこの世界では、引き算も足し算も、どちらもXORです。各桁を隣と無関係に計算できるので、回路がとても簡単になります。

数学では、この0と1だけの世界をGF(2)と呼びます。GFはガロア体(Galois field)の略で、19世紀の数学者ガロアの名前です。この記事では「繰り上がりのない2進数の計算」と覚えれば十分です。

しくみ2: 0と1の並びを多項式として見る

次に、0と1の並びを、多項式という形で書き直します。多項式は、x²+3x+1のような、xの何乗かを足し合わせた式です。CRCでは並びの各桁を「xの何乗」という名札で呼び、その桁が1なら書き、0なら書きません。

例えば1011は、左から順にx³・x²・x¹・x⁰の桁なので、x³+x+1になります(x⁰は1と書きます)。xに数を入れて計算するのではなく、xの何乗かは桁の位置を表す印です。

多項式で書くと、数学で調べられてきた多項式の性質を使えます。そのおかげで、「どんな誤りなら必ず見つかるか」を証明できます。

CRCで割る数に使う多項式を、生成多項式と呼びます。イーサネットのCRC-32では、x³²+x²⁶+x²³+…+x+1という32次の式です。仕様書では最上位のx³²を省き、残りの32桁を16進数(2進数の4桁を1文字で書く方法)で04C11DB7と書きます。

しくみ3: 手で計算してみる

小さな例で、CRCを手で求めます。送るデータは4ビットの1101、生成多項式はx³+x+1、つまり1011とします。割る数が4桁なので余りは3桁になり、3ビットのCRCができます。

1. データの後ろにCRCの桁数と同じ3個の0を付け、1101000にする(CRCを入れる席を空ける)
2. 左端の1の下に、割る数1011の左端をそろえて書き、XORする
3. 結果の左端に残った1に、また1011をそろえてXORする。0の桁は飛ばす
4. 割る数が右にはみ出すまで続ける。最後に残った右の3桁が余りで、これがCRC

この例では、4回のXORで余り001が出ました。送る側は、データの後ろにこの余りを付けて1101001を送ります。

ふつうの筆算と違い、「割る数より大きいか」を比べる必要はありません。左端が1ならXORし、0なら次の桁に進むだけです。この単純さが、CRCが速い理由です。

受け取った側は、届いた7ビットをそのまま同じ1011で割ります。誤りがなければ、余りは000になります。余りを付けたことで、全体がちょうど割り切れる並びになっているからです。例えば左から3番目のビットが化けて1111001が届くと、余りは110になり、誤りに気づけます。

実際の規格では約束が少し加わります。例えばイーサネットのCRC-32は、計算の初めの値を全部1にし、最後に全ビットを反転します。初めの値を1にするのは、先頭に0が増えたり減ったりする誤りも見つけるためです。

CRC計算ツールでも、この割り算を1段ずつ見られます。種類をCRC-8、幅を3、生成多項式を3、データの形式を16進数にして、0Dを入れます(0Dは2進数で00001101。先頭の0は余りを変えません)。

しくみ4: 回路で計算する

機器の中では、CRCを専用の小さな回路で、データが流れてくるそばから計算します。使うのは、1ビットを覚える回路を数珠つなぎにして、合図(クロック)のたびに中身を1つ隣へ送る回路です。これをシフトレジスタと呼びます。

3ビットのCRCなら、1ビットを覚える箱をA・B・Cの3つ並べ、2か所にXORを入れます。データは右から1ビットずつ入り、合図ごとに左へ1つずつ進みます。左端のCからあふれたビットは線で右へ戻され、2か所のXORに入ります。

あふれたビットが1のときだけ、2か所でビットが反転します。これは、筆算で「左端が1なら1011をXORする」のと同じ操作です。出力を入力の側へ戻すこのつなぎ方を、線形帰還シフトレジスタ(LFSR)と呼びます。1101と3個の0を入れていくと、箱の中身は次のように変わります。

最後に箱に残るのは001で、筆算の余りと同じです。CRC-32なら箱が32個になり、XORの場所が生成多項式の項に合わせて増えるだけです。

CRCが必ず見つける誤り

CRCの強みは、「この種類の誤りなら必ず見つかる」と言える点です。生成多項式に最上位の項とx⁰の項(+1)の両方があれば、次のことが成り立ちます。PetersonとBrownが1961年の論文で示した性質です。

• 1ビットだけの誤りは、どこで起きても必ず見つかる
• CRCのビット数以下の範囲に収まるバースト誤りは、中で何ビット化けても必ず見つかる(CRC-32なら32ビット以内)
• それより長い誤りも、ほとんど見つかる。どんな誤りの形も同じくらい起こると考えると、32ビットのCRCが見逃すのは約43億回に1回(2の32乗分の1)

データの長さごとに、何ビットまでの誤りをすべて見つけられるかは、生成多項式の選び方で変わります。カーネギーメロン大学のKoopmanは2002年、32ビットの生成多項式を全部調べました。イーサネットのCRC-32は、最大の長さのフレームで3ビットまでの誤りをすべて見つけます。ただし、もっと強い多項式もあるとわかりました。

逆に見逃すのは、誤りの形(どのビットが化けたか)が生成多項式で割り切れるときです。さきほどの1101001で、左から1・3・4番目がそろって化けると、誤りの形は1011000です。これは1011で割り切れるので、余りは000のままで気づけません。4ビットにまたがる誤りなので、3ビットのCRCの保証の外です。実際には16ビットや32ビットのCRCを使います。

CRCにできないこと

誤りを直すことはできない

CRCは、誤りが「ある」ことはわかっても、ふつうは「どこに」あるかまでは教えてくれません。見つけた後は、データを捨てて送り直してもらうか、壊れていると知らせるしかありません。

誤りを直すには、検査用のビットを増やし、どのビットが化けたかまでわかるように工夫します。これを誤り訂正符号(ECC)と呼びます。1950年にハミングが発表したハミング符号は、4ビットのデータに3ビットを足し、1ビットの誤りを直せます。サーバー用のECCメモリは、64ビットごとに8ビットを足し、1ビットの誤りを直し、2ビットの誤りを見つけます。

もっと多くの誤りを直せる符号に、1960年にリードとソロモンが発表したリード・ソロモン符号があります。CDやQRコードで使われ、QRコードが一部汚れていても読めるのはこのためです。CRCと同じく多項式の計算を使います。

直す符号は検査用のビットが多く、計算も重くなります。送り直しができる通信では、軽いCRCで見つけて送り直すほうが効率的なことが多いのです。送り直せない放送や宇宙との通信などでは、直す符号を使います。これを前方誤り訂正(FEC)と呼びます。

わざとの書き換えは見破れない

CRCの計算方法は規格で公開されていて、秘密の鍵を使いません。書き換えた人は、新しいデータでCRCを計算し直して付け直せば済みます。CRCが見つけるのは偶然の誤りで、悪意のある書き換えではありません。

実際に、初期の無線LANの暗号方式WEPは、中身の確認にCRC-32を使っていました。2001年にBorisovらは、暗号を解かずに中身を書き換え、CRCのつじつまも合わせられることを示しました。WEPの暗号もCRCもXORだけで計算するため、どこを反転すればCRCのどこが変わるかを計算で求められたのです。

書き換えを見つけるには、秘密の鍵を使うメッセージ認証コードやデジタル署名を使います(「暗号とは?」)。暗号で使うハッシュ関数も、同じ値になる別のデータを事実上作れないように設計されています。CRCでは、そうしたデータを簡単に作れます。

パリティ・チェックサム・CRC・ECCの違い

よくある誤解

数字で見る

もっと詳しく学ぶ

• 用語の詳しい解説: CRC(巡回冗長検査) / パリティビット / ハミング符号 / ビット誤り率
• 数字で試す: CRC計算ツール / ハミング符号の計算ツール / ビット演算の計算ツール(XORを試す)
• 関連する解説: 「インターネットはどうやってデータを届けるの?」 / 「パスワードはなぜ破られる?」