2008年7月4日星期五

Why USB CRC16 does not use a primitive polynomial?


I was wondering, why USB CRC16 does not use a primitive polynomial?

The USB CRC16 G(x) = x^16 + x^15 + x^2 + 1.
To check whether it is a primitive polynomial, I write a haskell program below:

------------ Crc.hs ----------------
module Crc where
import Data.Bits
ini :: Int ini = 1
crc_size :: Int
crc_size = 16
crc_poly :: Int
crc_poly = 1 + 2^2 +2^15

crc :: Int->Int->Int
crc x 0 = x
crc x n = crc (crc_cycle' x) (n-1)

mask = shiftL 1 crc_size - 1
crc_cycle' :: Int -> Int
crc_cycle' x | (testBit x (crc_size - 1 )) = (xor (shiftL x 1) crc_poly) .&. mask
|otherwise = (shiftL x 1) .&. mask

------------------------------------------------------------------

1) run ghci
2) :l Crc
3) crc ini (2^16-1)
after step (3), the answer is 2, indicate that G(x) is not a primitive one.

Change G'(x) = 1 + x + x^3 + x^12 + x^16
re-do step (1), (2), (3), the answer is 1, prove that G'(x) is a primitive one.

In my memory, the primitive polynomial is best for CRC check. why don't use it in USB specification?

I want to find the answer.

没有评论: