|
巡回冗長検査（じゅんかいじょうちょうけんさ、）は、誤り検出符号の一種で、主にデータ転送などに伴う偶発的な誤りの検出によく使われている。送信側は、入力されたデータ列をもとに一種の割り算に似た計算を行い、その余りをチェック用の値として追加した上で送信する。受信側では、受け取ったデータを元に同じ計算を行い、その結果をチェック用の値と比較してデータ破損の有無を判断する。 CRCは、デジタル回路で簡単に実装でき、数学的にも分析が容易で、伝送路ノイズによる誤りの検出によく使われている。パリティや単純な加算によるチェックサムに比べ検出精度が高く、その点では高級なチェックサムと言える。単純なチェックサムと同じく、データの改竄に対する耐性はない。 CRCは W. Wesley Peterson が発明し、1961年に論文として発表した。CRC-32と一般に呼ばれているIEEE 802.3のCRCは1975年に登場し、イーサネットなどの各種通信やZIPやPNGなど各所に使われている。 == 概要 == CRC は、巡回符号の理論に基づいた誤り検出符号の一種である。その計算は筆算による多項式の除算に似ており、送受信するデータを二進数とみなして、あらかじめ決めておいた特定の数で割り、その余りをチェック用の値として使う。除算に使う特定の数を生成多項式といい、送信側と受信側で揃えておく必要がある。また、有限体の繰り下がり（繰り上がり）のない算術を使っている点が通常の除算とは異なる。余りの長さは常に除数の長さ以下であり、除数の長さによって結果の長さを決定できる。 CRC には多数のバリエーションがあり、主に出力結果のビット幅や生成多項式に違いがある。チェック用の値が n ビットになる CRC は CRC-n と表記される。規格によって生成多項式が異なることが多く、CRC-n XXX というように表記される（主な標準CRC）。 CRCは任意の有限体を使って構築できるが、一般に使われているCRCは有限体 GF(2) を使用している。すなわち、2つの元の体であり、それを通常1と0で表す。 CRCがよく使われている重要な理由として、効率が保証されている点が挙げられる。nビットCRCは通常、nビット未満の連続する誤り（バースト誤り）を検出できる。言い換えれば、nビットの範囲内に1ビットの誤りが複数存在する場合を検出できる。また、それより長いバースト誤りも 1-2-n の確率で検出する。データ通信での誤りも記憶装置での誤りも、誤りは無作為に出現するわけではなくバースト性がある。そのため、CRCの性質はそれらによく合っており、単にパリティチェックを複数行うよりも便利である。 最も単純な誤り検出であるパリティビットは、最も単純なCRCと見ることもできる（除数は2ビットの 11 である）。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「巡回冗長検査」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Cyclic redundancy check 」があります。 スポンサード リンク
|