Cyclic Redundancy Check
- 送信するデータを高次の多項式とみなす。
- 例: 'A' = 01000001 -> x6 + 1
- 生成多項式 (Checking Polynomial) P(x) で割りその余り(BCC: Block Check Character)を CRC とする。
- CRC 生成多項式の例
CRC-12 ... P(x) = x12 + x11 + x3 + x2 + x + 1
CRC-16 ... P(x) = x16 + x15 + x2 + 1
CRC-CCITT ... P(x) = x16 + x12 + x5 + 1
送信側の計算
- 入力データをメッセージ多項式 M(x) と変形する。
- 生成多項式 P(x) の最高次項 xk と M(x) をかけて xkM(x)とする。
- xkM(x) を P(x) で割る。
- この余りが CRC 符号となる。但し、以上での演算には modulo 2 という演算を使う。
0 + 0 = 0, 1 + 0 = 1, 0 - 1 = 1
0 + 1 = 1, 1 + 1 = 0, 1 - 0 = 1
受信側の計算
- 受信データは CRC 符号付きデータである。これを生成多項式 P(x) で割り、その
余りが 0 であれば正常。余りが出ればエラー。
計算プログラム例