usb中的crc算法证明

    crc广泛应用于通信中的数据校验，usb也不例外。usb中的crc算法规定如下：
   “ For CRC generation and checking, the shift registers in the generator and checker are seeded with an all-
ones pattern.  For each data bit sent or received, the high order bit of the current remainder is XORed with
the data bit and then the remainder is shifted left one bit and the low-order bit set to zero.  If the result of
that XOR is one, then the remainder is XORed with the generator polynomial.
When the last bit of the checked field is sent, the CRC in the generator is inverted and sent to the checker
MSb first.  When the last bit of the CRC is received by the checker and no errors have occurred, the
remainder will be equal to the polynomial residual. “
    按此crc生成算法，实际上余数是输入数据后面加上n位1之后的数据除以生成多项式的结果。
    以token校验用的crc5为例，“A five-bit CRC field is provided for tokens and covers the ADDR and ENDP fields of IN, SETUP, and OUT tokens or the time stamp field of an SOF token.  The generator polynomial is:
G(X) = X^5+X^2+1
    The binary bit pattern that represents this polynomial is 00101B.  If all token bits are received without
error, the five-bit residual at the receiver will be 01100B.
    那么结果为什么是01100B而不是其它呢？下面尝试证明之。以前证明过，不过后来忘记了，最近又费了半天
劲重新证明了一下，这回记录下来。
    设数据为M，源端生成的crc结果为C，则有
    1式       M*2^n + A = k*G +C    其中*2^n表式把M左移n位，A表示n位的1，也就是把输入数据左移n位，右面补1。
   根据usb规定，接收端收到的数据为：M*2^n + C_  (C_表示C按位取反)。则接收端有
    2式                 (M*2^n+C_) * 2^n + A = m*G + D
  我们需要证明的就是对于crc5，D为01100。
   首先需要说明的是，crc中采用的按位模2的算法，对于此算法，对于任意数据y，有y+y=0，a-b=a+b。
   2式展开得3式     M*2^n*2^n+C_*2^n + A = m*G +D
   1式两边乘2^n得4式   M*2^n*2^n + A*2^n = k*G*2^n + C*2^n
    4式加3式，并例用a+a=0，有   C_*2^n + A + A&2^n = (m + K*2^n )*G + D +C*2^n
    两边加上C*2^n    C_*2^n + A + A*2^n  + C*2^n =  (m + K*2^n )*G + D
    因为C_ +  C = A， 有 A = (m + K*2^n )*G + D
    所以D为A除以G后的余数，也就是说按照usb中crc的校验方法，对于任意的输入M，crc5校验结果为01100B。
   证毕。

   不对的地方欢迎大家指证。