CRCはどんなビット誤りを検出できるのか

[←]　[↑]　[→]

Cyclic Redundancy Check (CRC) は誤り検出符号の一種で、作り方は任意長のメッセージmsg[m-1:0]をnビット左シフトして、ある生成多項式g[n:0]で割った余りをとる。

多項式表記　crc(x) = msg(x) xn  mod g(x)

ベクタ表記　crc[n-1:0] = (msg[m-1:0] << n) mod g[n:0]

メッセージにCRCを付加したコードはg[n:0]で割り切れる

 

　多項式表記　(msg(x) xn + crc(x)) mod g(x) = crc(x) + crc(x) = 0

　ベクタ表記　{msg[m-1:0],crc[n-1:0]} mod g[n:0] = crc[n-1:0] + crc[n-1:0] = 0

このコードのどこかにビット誤りが起きるということは、誤りビット位置に1を立てたerr[m+n-1:0]が加算(XOR)されることだから、もし誤りビットerr[m+n-1:0]がg[n:0]で割り切れなければビット誤りが検出できるというわけである。逆に、偶然g[n:0]で割り切れてしまうビット誤りは検出できない。

◇

コード中のどんなビット誤りが検出できるかはg[n:0]の選び方で決まる。

(1)     任意長の中の1ビット誤りを検出するには、g[n:0]に値1のビットが2個以上あればよい

(2)     任意長の中の奇数個のビット誤り(パリティエラー)を検出するには、g[n:0]に値1のビットが偶数個あればよい

(3)     任意長の中の1個のnビットバースト誤りを検出するには、g[n:0]の両端が値1であればよい。ここでバースト誤りとは連続するnビット内の任意の誤りであり、誤りビットが連続しているという意味ではない。

(4)     (2n-1)ビット長の中の2ビット誤りを検出するには、g[n:0]がn次の原始多項式であればよい

g[n:0]として原始多項式を選ぶと(1)(3)(4)は満たすが(2)は満たさないことになる。そこで原始多項式に(x+1)をかけて(2)を満たすようにすることがある。(1)(4)で1,2ビット誤りが検出できているので(2)を加えれば3ビット誤りが検出できる。ただ4ビット誤りが検出できないので、5,7,...ビット誤りが検出できてもありがたみはない。

◇◇

(1)     任意長の中の1ビット誤りを検出するには、g[n:0]に値1のビットが2個以上あればよい

∵値1のビットが1個(g[n:0]=0…01)のときは左シフトすなわち(10...0)を乗算してerr[m+n-1:0]=0…010…0を作れるが、値1のビットが2個以上すなわちg[n:0]=0…01?…?1 (?は0か1) のとき、これを左シフトしたものを加算(XOR)しても両端の値1を値0にできないので、結局、g[n:0]に何を乗算してもerr[m+n-1:0]=0…010…0にはできない。

◇◇◇

(2)     任意長の中の奇数個のビット誤り(パリティエラー)を検出するには、g[n:0]に値1のビットが偶数個あればよい

∵g[n:0]が偶パリティ(値1のビット数が偶数)ならばg[n:0]を左シフトしても偶パリティであり、さらにこれらを加算(XOR)しても偶パリティのまま。つまりg[n:0]に何を乗算しても奇パリティのerr[m+n-1:0]にはできない。

◇◇◇

(3)     任意長の中の1個のnビットバースト誤りを検出するには、g[n:0]の両端が1であればよい。ここでバースト誤りとは連続するnビット内の任意の誤りであり、誤りビットが連続しているという意味ではない。

∵(n+1)ビットのg[n:0]=1…1に何を乗算してもerr[m+n-1:0]=0…0?…?0…0(?は0か1)の?…?をnビット以下にはできない。

◇◇◇◇

(4)     (2n-1)ビット長の中の2ビット誤りを検出するには、g[n:0]がn次の原始多項式であればよい

∵g[n:0]が原始多項式のとき、xのべき乗{ 1 x x**2 ... x**(2n-2) } の余りnビットはゼロを除くすべての値をつくすから

_________<2n-1-n ><_n_>___余り

1________00……000…01 = 0…01

x________00……000…10 = 0…10

:                 

x**(n-1)__00……001…00 = 1…00

x**n_____00……010…00 = 値1のビットが2個以上

:

x**(2n-2)_10……000…00 = 値1のビットが2個以上

と、値1のビットが1個しかないメッセージ{ x**n ... x**(2n-2) }のCRCは値1のビットが2個以上ある。

次に、値1のビットが2個以上あるメッセージは{ x**n ... x**(2n-2) }を加算(XOR)することにより作れて、そのCRCはゼロを除くnビット値のいずれかだから、値1のビットが1個以上ある。

結局、任意の(2n-1-n)ビット長メッセージとnビットCRCを合わせた(2n-1)ビット長コードには値1のビットが3個以上ある。

ここで、2つのコードを加算(XOR)したものは第三のコードに他ならないから値1のビットは3個以上である。逆にいうと、コードに2ビット以下の誤りを加算(XOR)しても別のコードにはならない(g[n:0]で割り切れない)。

以上の議論ではオールゼロのコード(メッセージもCRCも0･･･0)が抜けているが、これを含めてもコードに2ビット以下の誤りを加算(XOR)しても別のコードにはならないことには変わりない。

◇◇◇◇◇

実際に使われているCRCの生成多項式は必ずしも原始多項式を使っておらず、使用する最大メッセージ長以内でハミング距離が広くとれるものを選んでいるようである。

(例1) CRC-16-CCITT (HDLC)

　g(x) = x16+x12+x5+1 = (x+1)(x15+x14+x13+x12+x4+x3+x2+x+1)

　g[16:0] = (1_0001_0000_0010_0001) = (11) * (1111_0000_0001_1111)

　既約ではなく、原始多項式とパリティエラーを検出するための(x+1)を乗算したもの。

(例2) CRC-16-IBM

　g(x) = x16+x15+x2+1 = (x+1)(x15+x14+1)

　g[16:0] = (1_1000_0000_0000_0101) = (11) * (1100_0000_0000_0001)

　既約ではなく、原始多項式とパリティエラーを検出するための(x+1)を乗算したもの。

(例3) CRC-32 (IEEE802.3 Ethernet)

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

  g[32:0] = (1_0000_0100_1100_0001_0001_1101_1011_0111)

　既約だが原始多項式ではない。1500byte長メッセージに対して3ビット誤りまで検出できる(ハミング距離4)。

[←]　[↑]　[→]