理論的なエラー検出コード - CRC

より理論的なエラー検出コードとして、Cyclic Redundancy Check(CRC)というコードがある。

少し形式張るが、nビットのデータa_n-1、a_n-2、…、a₀を0か1の値をとる係数とする

a_n-1X^n-1+a_n-2X^n-2+…+a₂X²+a₁X¹+a₀

という多項式と考え、これをある多項式で割り、その余りをチェックビットとする。この割り算をする多項式は整数でいうと素数のような因数分解できない多項式で、16ビットのチェックビットの場合は、

X¹⁶+X¹²+X⁵+1

がX.25やBluetoothなどで伝送エラーを検出するために用いられている。また、IEEE802.3では

X³²+X²⁵+X²³+X²²+X¹⁶+X¹²+X¹¹+X¹⁰+X⁸+X⁷+X⁵+X⁴+X²+X+1

という多項式を使い、32ビットのチェックビットを作っている。

このように作られたCRCでは1ビットエラーが検出できるだけでなく、n-1ビット以下の長さの範囲内であれば、その中に複数のエラービットがあっても検出できることが保証されている。通信の場合は雑音で連続した複数のビットが誤るという場合が多く、このように連続した複数ビットのエラーが検出できるというのは大きなメリットである。

多項式での割り算は、図2.11に示すようにチェックビットの長さのシフトレジスタを使い、係数が1の項(前述の16ビットの例では12と5)の所にXORを入れて引き算(係数が2進数の場合は足し算と同じ)を行うことで実現できる。図2.11の右側から順にデータビットを入れ、すべてのデータビットがシフトインされた時点でのシフトレジスタの内容がチェックビットとなっているので、これをシフトアウトしてデータに付加してやれば良い。

CRCは、このようにシフトレジスタを用いると比較的簡単な回路で実現できる。そして、入力データビットを順次シフトインしていくので、通信のように順次データを送るという場合は良いのであるが、コンピュータのバスのように並列にデータを伝送する場合にはチェックビットの生成に時間が掛ってしまうという問題がある。このため、CRCはブロックでデータを順次伝送するEthernetなどの通信や、ディスクとのデータのブロック伝送などには広く使われているが、並列伝送を行うプロセサ内部のデータバスなどでは、CRCは用いられない。