Cyclic Redundancy Check

巡回冗長検査

Cyclic 巡回 Redundancy 冗長 Check 検査

リダンダンシーが冗長性というのは覚えておいてよさそう

略称CRC

主にシリアル通信で、送信データと受信データが同じかどうか確認する手法

TCP/IPでも組み込まれてる理由というか、目的がこれだな

CRCを計算する際には、処理速度を上げるために変換テーブルを用いるのが一般的

ただしCRC-32ではテーブルだけで1KBもRAMを消費するので、変換テーブルをROMに格納する方法がある

通常一つのマイコンでCRCは1,2個なので、定数としてベタ書きできる

メカニズム

生成多項式で（生成多項式で得られた値で）送信データを除算する

生成多項式で得られた値は「マスク」とか呼ぶ

その時の剰余を送信データに付加する

受信側は受信データから剰余を取り除いて真の送信データを得る

真の送信データを生成多項式（送信側と同一にしておく）で除算する

得られた剰余と受信したを比較する

一致していればデータを正常に受信できたものとする

なお、剰余を検証する計算方法は特に決まっていない

受信データから受信した剰余を減算してから生成多項式で除算して、剰余の出ないことを確認しても検証できる

いくつか設定が必要

検査対象の最大データ長によってビット数を決定する

256バイト以下：CRC-8

512バイト以下：CRC-16

1024バイト以下：CRC-32

2048バイト以下：CRC-64

生成多項式を決める

ビット数ごとに代表的な多項式がある

https://ja.wikipedia.org/wiki/巡回冗長検査#主な標準CRC

1993年から2004年にかけて、Koopman と Castagnoli らは16ビットまでと、24ビットおよび32ビットの多項式の総当り的調査を行った。そして、それまで利用されていたものよりも（そのメッセージ長でのハミング距離の観点で）性能のよい多項式を発見し、今後の標準化に役立てられるよう発表した。iSCSIはその研究成果を取り入れている。

Koopman 先生と Castagnoli先生えらい

よく使われるCRC-32多項式は、IEEE勧告のものも V.42、イーサネット、FDDI、ZIP、PNG などで使われているものも、ハミング符号の生成多項式を使っている。これは、誤り検出性能がよいためである。

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

RFC 1952 (gzip) や RFC 2083 (PNG) の末尾にも実装例が載っている

代表例から選択すると基本的に考えるまでもなく決まるが、下記の設定が必要

初期値

シフト方向

出力XOR

入力反転有無

出力反転有無

数学的に理解した方が正確だと思うが、まあこれで検証できるというのはわかった

javascript製のCRC計算機あった