Cyclic Redundancy check (CRC) Polynomials:
CRC-8: c(x) = x8
+ x2 + x + 1
CRC-10: c(x) = x10 + x9 + x5 + x4
+ x + 1
CRC-12: c(x) = x12 + x11 + x3 + x2
+ 1
CRC-16: c(x) = x16 + x15 + x2 + 1
CRC-CCITT:c(x) = x16 + x12 + x5 + 1
CRC-32: c(x) = x32 + x26 + x23 + x22
+ x16 + x12 + x11 + x10 + x8
+ x7 + x5 + x4 + x2 + x + 1
CRC can detect all single-bit errors, all
double-bit errors, any odd number of errors, any burst error where the length of
burst is less than k bits (k = degree of c(x)), and most burst error of larger
than k bits.
CRC Example:
1: M(x) = 1001,1010 //Message to be send
2: C(x) = 1,0000,0111 //Polynomial, degree =
8 (k = 8)
3: Shift left M(x) by 8 (the degree of c(x)) and add E(x) to produce message。其中E(x)
= "0000,0000"或M(x)的下一个字节。
4: Polynomial long division by c(x) to yield remainder. R(x) = 1100,1111.
5: So, the message minus R(x) would be exactly divisible by C(x).
Note: Addition, subtraction and division here means Exclusive-OR (XOR).
|
1 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
M(x)*x8/C(x)的商,在此没有用处。 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
M(x)*x8 + E(x);
分界线左边是M(x),右边是E(x) |
| xor |
1 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
|
1 |
|
|
|
|
|
|
|
|
分界线右边C1(x)
= 1000，0000 |
|
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
|
| xor |
|
|
|
1 |
|
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
|
|
|
|
|
分界线右边C2(x)
= 0111，0000 |
|
|
|
|
0 |
|
1 |
0 |
0 |
1 |
|
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
0 |
|
| xor |
|
|
|
|
|
1 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
|
1 |
|
|
|
分界线右边C3(x)
= 0011，1000 |
|
|
|
|
|
|
0 |
0 |
0 |
1 |
|
1 |
1 |
0 |
0 |
|
1 |
0 |
0 |
0 |
|
| xor |
|
|
|
|
|
|
|
|
1 |
|
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
分界线右边C4(x)
= 0000，0111 |
|
|
|
|
|
|
|
|
|
0 |
|
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
1 |
(M(x)*xk + E(x))/C(x)的余数R(x)。
运算到最后，分界线左边一定是'0'，所以，R(x)一定是8位。 |
最后，P(x)
= M(x)*xk + R(x) = 1001,1010,0000,0000 + 1100,1111 =
1001,1010,1100,1111
其实R(x) = E(x) xor C1(x) xor C2(x) xor
C3(x) xor C4(x).....xor Cn(x).
其中，"C1(x) xor C2(x) xor C3(x) xor C4(x).....xor Cn(x)"是由M(x)的值决定的。
所以，在单片机中，只要做一个256字节的表格，根据M(x)查出"C1(x)
xor C2(x) xor C3(x) xor C4(x).....Cn(x)"的值，再与E(x)异或就可以得到R(x)了。
当然，也可以做两个16字节的表格，分别查出"C1(x) xor
C2(x)" 和 "C3(x) xor C4(x)"的值，再将他们异或，然后将结果与E(x)异或，得到R(x)。
然后，再把R(x)作为下一轮的M(x),继续查表，与下一字节异或，产生新的Rx(x)。如此循环，直到最后一个字节,然后，将结果作为M(x)再查一次表（是为最后添加的那个0x00查的）。
CRC-8的51单片机实现：
51的表格（汇编）：
db 000h,007h,00eh,009h,01ch,01bh,012h,015h,038h,03fh,036h,031h,024h,023h,02ah,02dh;
db 070h,077h,07eh,079h,06ch,06bh,062h,065h,048h,04fh,046h,041h,054h,053h,05ah,05dh;
db 0e0h,0e7h,0eeh,0e9h,0fch,0fbh,0f2h,0f5h,0d8h,0dfh,0d6h,0d1h,0c4h,0c3h,0cah,0cdh;
db 090h,097h,09eh,099h,08ch,08bh,082h,085h,0a8h,0afh,0a6h,0a1h,0b4h,0b3h,0bah,0bdh;
db 0c7h,0c0h,0c9h,0ceh,0dbh,0dch,0d5h,0d2h,0ffh,0f8h,0f1h,0f6h,0e3h,0e4h,0edh,0eah;
db 0b7h,0b0h,0b9h,0beh,0abh,0ach,0a5h,0a2h,08fh,088h,081h,086h,093h,094h,09dh,09ah;
db 027h,020h,029h,02eh,03bh,03ch,035h,032h,01fh,018h,011h,016h,003h,004h,00dh,00ah;
db 057h,050h,059h,05eh,04bh,04ch,045h,042h,06fh,068h,061h,066h,073h,074h,07dh,07ah;
db 089h,08eh,087h,080h,095h,092h,09bh,09ch,0b1h,0b6h,0bfh,0b8h,0adh,0aah,0a3h,0a4h;
db 0f9h,0feh,0f7h,0f0h,0e5h,0e2h,0ebh,0ech,0c1h,0c6h,0cfh,0c8h,0ddh,0dah,0d3h,0d4h;
db 069h,06eh,067h,060h,075h,072h,07bh,07ch,051h,056h,05fh,058h,04dh,04ah,043h,044h;
db 019h,01eh,017h,010h,005h,002h,00bh,00ch,021h,026h,02fh,028h,03dh,03ah,033h,034h;
db 04eh,049h,040h,047h,052h,055h,05ch,05bh,076h,071h,078h,07fh,06ah,06dh,064h,063h;
db 03eh,039h,030h,037h,022h,025h,02ch,02bh,006h,001h,008h,00fh,01ah,01dh,014h,013h;
db 0aeh,0a9h,0a0h,0a7h,0b2h,0b5h,0bch,0bbh,096h,091h,098h,09fh,08ah,08dh,084h,083h;
db 0deh,0d9h,0d0h,0d7h,0c2h,0c5h,0cch,0cbh,0e6h,0e1h,0e8h,0efh,0fah,0fdh,0f4h,0f3h;
51的表格（C语言）：
const unsigned char code CRC8[256] = {
0x00,0x07,0x0e,0x09,0x1c,0x1b,0x12,0x15,0x38,0x3f,0x36,0x31,0x24,0x23,0x2a,0x2d,
0x70,0x77,0x7e,0x79,0x6c,0x6b,0x62,0x65,0x48,0x4f,0x46,0x41,0x54,0x53,0x5a,0x5d,
0xe0,0xe7,0xee,0xe9,0xfc,0xfb,0xf2,0xf5,0xd8,0xdf,0xd6,0xd1,0xc4,0xc3,0xca,0xcd,
0x90,0x97,0x9e,0x99,0x8c,0x8b,0x82,0x85,0xa8,0xaf,0xa6,0xa1,0xb4,0xb3,0xba,0xbd,
0xc7,0xc0,0xc9,0xce,0xdb,0xdc,0xd5,0xd2,0xff,0xf8,0xf1,0xf6,0xe3,0xe4,0xed,0xea,
0xb7,0xb0,0xb9,0xbe,0xab,0xac,0xa5,0xa2,0x8f,0x88,0x81,0x86,0x93,0x94,0x9d,0x9a,
0x27,0x20,0x29,0x2e,0x3b,0x3c,0x35,0x32,0x1f,0x18,0x11,0x16,0x03,0x04,0x0d,0x0a,
0x57,0x50,0x59,0x5e,0x4b,0x4c,0x45,0x42,0x6f,0x68,0x61,0x66,0x73,0x74,0x7d,0x7a,
0x89,0x8e,0x87,0x80,0x95,0x92,0x9b,0x9c,0xb1,0xb6,0xbf,0xb8,0xad,0xaa,0xa3,0xa4,
0xf9,0xfe,0xf7,0xf0,0xe5,0xe2,0xeb,0xec,0xc1,0xc6,0xcf,0xc8,0xdd,0xda,0xd3,0xd4,
0x69,0x6e,0x67,0x60,0x75,0x72,0x7b,0x7c,0x51,0x56,0x5f,0x58,0x4d,0x4a,0x43,0x44,
0x19,0x1e,0x17,0x10,0x05,0x02,0x0b,0x0c,0x21,0x26,0x2f,0x28,0x3d,0x3a,0x33,0x34,
0x4e,0x49,0x40,0x47,0x52,0x55,0x5c,0x5b,0x76,0x71,0x78,0x7f,0x6a,0x6d,0x64,0x63,
0x3e,0x39,0x30,0x37,0x22,0x25,0x2c,0x2b,0x06,0x01,0x08,0x0f,0x1a,0x1d,0x14,0x13,
0xae,0xa9,0xa0,0xa7,0xb2,0xb5,0xbc,0xbb,0x96,0x91,0x98,0x9f,0x8a,0x8d,0x84,0x83,
0xde,0xd9,0xd0,0xd7,0xc2,0xc5,0xcc,0xcb,0xe6,0xe1,0xe8,0xef,0xfa,0xfd,0xf4,0xf3,
};
i = 1 , m = UARTIn[0] ;
while(i <= UARTPtr){
m = CRC8[m] ^ UARTIn[i];
i++;
}
m = CRC8[m];
CRC-8的PIC单片机实现：两个表格CRC8L和CRCH分别为51表格的第一行和第一列。其实，51表格中的每一个数字都是其对应的行、列坐标处的数字异或的结果。
CRC8L:
addwf PCL
retlw 0x00
retlw 0x07
retlw 0x0e
retlw 0x09
retlw 0x1c
retlw 0x1b
retlw 0x12
retlw 0x15
retlw 0x38
retlw 0x3f
retlw 0x36
retlw 0x31
retlw 0x24
retlw 0x23
retlw 0x2a
retlw 0x2d
CRC8H:
addwf PCL
retlw 0x00
retlw 0x70
retlw 0xe0
retlw 0x90
retlw 0xc7
retlw 0xb7
retlw 0x27
retlw 0x57
retlw 0x89
retlw 0xf9
retlw 0x69
retlw 0x19
retlw 0x4e
retlw 0x3e
retlw 0xae
retlw 0xde
;Input: FSR, CRCCounter
;Output: FSR+CRCCounter,FSR+CRCCounter+1;
;Output: STATUS.C=1 if CRC+CRCCounter and CRC+CRCCounter+1 matchs with their old value, otherwise STATUS.C=0
CRC8:
banksel bank0
clrf Temp
CRC8_10:
swapf Temp,w
andlw 0x0f
call CRC8H
xorwf Temp,w
xorwf Temp
xorwf Temp,w
andlw 0x0f
call CRC8L
xorwf INDF,w
xorwf Temp
incf FSR
decfsz CRCCounter
goto CRC8_10
swapf Temp,w
andlw 0x0f
call CRC8H
xorwf Temp,w
xorwf Temp
xorwf Temp,w
andlw 0x0f
call CRC8L
xorwf Temp
swapf Temp,w
andlw 0x0f
call Hex2Asc
xorwf INDF,w
xorwf INDF
incf FSR
xorwf Temp,w
xorwf Temp
xorwf Temp,w
andlw 0x0f
call Hex2Asc
xorwf INDF,w
xorwf INDF
xorwf Temp
btfss STATUS,Z
bcf STATUS,C
btfsc STATUS,Z
bsf STATUS,C
incf FSR
return
CRC的PC机实现：
由于k阶多项式的第2k项一定为"1"，所以：
1: 将M(x)左移k位（在M(x)后面加k个"0"），放到寄存器中。
2: 将寄存器左移一位，若移出位为"1"，则将寄存器与多项式C(x)的0~(k-1)项异或，否则不变，如此循环k次。
以CRC-8为例：
UCHR _cded CRC8( UCHR* strBuf, DWORD& dwLength)
{
UCHR bCRC;
if(dwLength ==0) return 0;
__asm
{
pushf;
mov edx, strBuf;
mov ebx, dwLength; //dwLength为引用传递，地址
-> ebx。
mov
ebx,[ebx]; //取得dwLength的值
-> ebx。
mov ah,[edx];
//将M(x)放入寄存器高8位。
dec ebx;
jz crc4;
//如果dwLength == 1
则在寄存器低8位添加"0000,0000"。
crc1: inc edx;
//否则就将M(x)的下一个字节放入寄存器低8位。
mov al,[edx];
mov ecx,8;
//循环8次，一定用ecx,不可用cx，否则Debug编译时正确，Release编译时执行错误。
crc2: shl ax,1;
//左移。
jnc crc3;
//如果移出位为"1"就异或，否则继续移位。
xor ah,7;
//C(x) = x8 + x2 + x + 1 = x8
+ 7。由于x8已经移出，故只异或0~(k-1)项x2 + x
+ 1即可。
crc3: loop crc2;
dec ebx;
jnz crc1;
crc4: mov al,0;
//在寄存器低8位添加"0000,0000"。
mov ecx,8;
crc5: shl ax,1;
jnc crc6;
xor ah,7;
crc6: loop crc5;
mov bCRC,ah;
popf;
}
return bCRC;
}
对于CRC-16或CRC-CCITT，初始化时要将M(x)放到eax的高16位，M(x)的下一个word或添加的"0000,0000,0000,0000"要放到ax。做运算时，eax与多项式的0~15位及其后面扩展的16个"0"异或（第16位已经移出），即与"1000，0000，0000，0101；0000，0000，0000，0000"或"0001，0000，0010，0001；0000，0000，0000，0000"异或。
点击此处查看原文 >>
系统分类:
嵌入式 | 用户分类:
| 来源:
原创