CRC、データの誤りを検査するために生成される符号である。
身近なところだとZIP形式のアーカイブのインデックス部分にはファイル名とともに32ビットのCRCが含まれていて、
アーカイブを解凍して得られたデータのCRCとインデックスのCRCを比較して、一致しなければアーカイブが壊れていると教えてくれると。
CRCは誤り検出の符号としては検出率が高いと思われている。
誤り検出の方法としてパリティビットを付加するという方法があるが、
1ビットのパリティビットでは1ビットの誤りは検知できるが、2ビット以上の誤りは見のがす可能性がある。
チェックサムということで一連のデータの各ワードの総和を使う方法があるが、
データの順番が変わっても同じ値になるとか、偶然同じ値になるような誤りが発生する可能性は低くない。
それに比べればCRCは誤り検出率が高く、計算アルゴリズムもそんなに大変ではない。(単純なパリティやチェックサムよりは複雑だが)
ただし、MD5とかSHA1のようなハッシュ関数のように改ざん検出だとかに使えるほど衝突しにくいわけではない。
あくまでも偶然、データに誤りが発生したのを検出するためのものである。
CRCというのは一連のデータに対するわり算の答えを表している。
よく使われるCRC32では2進数で 100000100110000010001110110110111 でデータを割ったときの余りとなっているとのこと。
ソフトウェアで実装するときにはこういう方法が使われることが多いそうで。
テーブルに0x00～0xFFに対するCRC32の計算値を格納しておいて、それをうまく使うと簡単に計算できるそう。
確かにこれなら使いやすそうですね。
CRC32はこのように優秀な誤り検査符号なのだが、貧弱な誤り検出符号にまつわるこんなエピソードがある。
システムのある部分では8ビットチェックサムで検査を行うようになっていたよう。
8ビット単位でデータを足し算し続けるだけという簡単な仕組みだから採用されていたんだろうな。
ここにあるデータと8ビットチェックサムが偶然一致してしまうデータを送り込むとバグが発生した。
当初、原因が分からず、調査にはだいぶ時間がかかったようだが、これを発見した人は「君は1/256の確率を引いてしまったのだ」と教えてくれた。
どうも横着してチェックサムに差があること=データが変化したことと解釈する仕組みになっていたらしく、
それがゆえにチェックサムが偶然一致するデータを送ると想定外の動きをしてしまったそうで。
上の例は誤り検出符号の使い方としてそもそも間違えていて、2つのデータが違うことを検出するのに使うのは正しい使い方とは言えない。
よりによってそれが8ビットしかなかったので、1/256の確率でこの問題が顕在化してしまったわけだ。簡単には発生しないが、起こせなくもなかったと。
その後、全データなめて変化したことを検出する仕組みに変えたとのこと。それが正しい。
CRC32は各所で多用されていて、ここもCRC32なのかと驚くこともしばしば。
職場でもよく使ってるのよ。ここはCRC32付けてるから、データが狂ったのは発見できると考えてOKとか、そういう話も多い。
ほどよい誤り検査符号なんでしょうね。そんなに難しくもなく、長くもなく、それで検出能力は十分高い。ありがたいものだ。