wdefu 2007-4-12 13:55
高速以太网CRC校验的实现
[align=left][align=center][b][font=宋体]一、[/font][font=Times New Roman][/font][/b][b][font=宋体]引言[/font][/b][/align][/align][font=Times New Roman] [/font][font=宋体]为了确保数据在计算机系统中传输和存储中正确可靠，引入了信道编码。对于信道编码有两个方面，一是要求编码后的码流频谱适应信道频率特性，二是检测并纠正产生的误码。前者属于谱成形技术，后者为差错控制技术。[/font][font=Times New Roman]CRC[/font][font=宋体]码属于后者。它是通过增加冗余信息，达到发现误码的目的。常见的冗余校验有奇偶校验，海明校验，循环冗余校验。[/font]
[font=Times New Roman] [/font][font=宋体]本文讨论循环冗余校验（[/font][font=Times New Roman]CRC[/font][font=宋体]）的实现，及其在以太网中的应用。[/font]
[font=Times New Roman] [/font]
[align=center][align=center][b][font=宋体]二、[/font][font=Times New Roman][/font][/b][b][font=宋体]循环冗余码介绍[/font][/b][/align][/align][font=Times New Roman] 1[/font][font=宋体]循环冗余码是建立在近世代数基础上的。编解码电路简单，检错能力强。在计算机系统的数据存储及传输中得到广泛应用。[/font]
[font=Times New Roman] 2[/font][font=宋体]编码原理[/font]
[font=Times New Roman] [/font][font=宋体]设待发送比特数据为[/font][font=Times New Roman]D[/font][font=宋体]（[/font][font=Times New Roman]x[/font][font=宋体]）[/font][font=Times New Roman],[/font][font=宋体]生成多项式为[/font][font=Times New Roman]G[/font][font=宋体]（[/font][font=Times New Roman]x[/font][font=宋体]）。信息码长[/font][font=Times New Roman]k[/font][font=宋体]位，校验码长[/font][font=Times New Roman]n-k[/font][font=宋体]位，则编码后的码长为[/font][font=Times New Roman]n[/font][font=宋体]位。如图[/font][font=Times New Roman]1[/font][font=宋体]：[/font]
[align=center][font=宋体][img]http://www.icembed.com/UploadFiles/200632720191734.gif[/img][/font][/align][align=center] [/align][align=left][font=宋体][font=宋体] [/align][align=left][align=left][font=宋体]编码步骤：信息数据[/font][font=Times New Roman]D[/font][font=宋体]（[/font][font=Times New Roman]x[/font][font=宋体]）乘以[/font][font=Times New Roman][/font][font=宋体]，得到的多项式除以生成多项式[/font][font=Times New Roman]G[/font][font=宋体]（[/font][font=Times New Roman]x[/font][font=宋体]），最终得到的余式[/font][font=Times New Roman]R[/font][font=宋体]（[/font][font=Times New Roman]x[/font][font=宋体]）即为[/font][font=Times New Roman]CRC[/font][font=宋体]校验码。它跟在信息码后一并发往信道。[/font][/align][/align][align=left][align=left][font=Times New Roman] [/font][font=宋体]并不是所有的多项式都可以做位生成多项式[/font][font=Times New Roman]G(x)[/font][font=宋体]，常见的生成多项式有：[/font][/align][/align][align=left][align=left][font=Times New Roman]CRC8=X8+X5+X4+1[/font][/align][/align][align=left][align=left][font=Times New Roman]CRC-CCITT=X16+X12+X5+1[/font][/align][/align][align=left][align=left][font=Times New Roman]CRC12=X12+X11+X3+X2+1[/font][/align][/align][align=left][align=left][font=Times New Roman]CRC16=X16+X15+X5+1[/font][/align][/align][align=left][align=left][font=Times New Roman]CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1[/font][/align][/align][font=Times New Roman]3 CRC32[/font][font=宋体]的实现[/font]
[font=宋体]以太网信道编码采用的是[/font][font=Times New Roman]CRC32[/font][font=宋体]，所以在这里给出[/font][font=Times New Roman]CRC32[/font][font=宋体]的实现，它在一般[/font][font=Times New Roman]CRC[/font][font=宋体]基础上增加了些细节。[/font]
[font=宋体]介绍以太网[/font][font=Times New Roman]MAC[/font][font=宋体]帧结构[/font]
[align=center][font=宋体][img]http://www.icembed.com/UploadFiles/200632720191580.gif[/img][/font][/align]
[font=宋体][font=宋体]从数学上讲，相应给定帧的[/font][font=Times New Roman]CRC[/font][font=宋体]值由下述过程定义：[/font]
[font=宋体]（1） [/font][font=宋体]对该帧的前[/font][font=Times New Roman]32[/font][font=宋体]位作求补运算。[/font]
[font=宋体]（2） [/font][font=宋体]然后，将该帧的[/font][font=Times New Roman]n[/font][font=宋体]位看作为[/font][font=Times New Roman](n-1)[/font][font=宋体]阶多项式[/font][font=Times New Roman]M[/font][font=宋体]（[/font][font=Times New Roman]x[/font][font=宋体]）的系数。[/font]
[font=宋体]（3） [/font][font=Times New Roman]M[/font][font=宋体]（[/font][font=Times New Roman]x[/font][font=宋体]）乘以[/font][font=Times New Roman][/font][font=宋体]，然后除以[/font][font=Times New Roman]G[/font][font=宋体]（[/font][font=Times New Roman]x[/font][font=宋体]），得到余式[/font][font=Times New Roman]R[/font][font=宋体]（[/font][font=Times New Roman]x[/font][font=宋体]）。[/font]
[font=宋体]（4） [/font][font=宋体]对该比特位逐位求补，结果作为[/font][font=Times New Roman]CRC[/font][font=宋体]。[/font]
[font=Times New Roman] [/font]
[font=宋体]主要实现方式有串行和并行两种：[/font]
[font=宋体]（[/font][font=Times New Roman]a[/font][font=宋体]）通过线性反馈移位寄存器串行实现（以[/font][font=Times New Roman]CRC-CCITT[/font][font=宋体]为例），见图[/font][font=Times New Roman]2[/font]
[font=Times New Roman][/font]
[img]http://www.icembed.com/UploadFiles/200632720194621.gif[/img]
[font=宋体]信息流由低位送入寄存器，当所有信息比特送入寄存器完毕后，寄存器中则为校验码。[/font]
[font=Times New Roman] [/font][font=宋体]（[/font][font=Times New Roman]b[/font][font=宋体]）[/font][font=Times New Roman]CRC32[/font][font=宋体]的并行实现[/font]
[font=Times New Roman] [/font][font=宋体]串行处理对于高速以太网如[/font][font=Times New Roman]100M[/font][font=宋体]，[/font][font=Times New Roman]10G[/font][font=宋体]等，显然是不合适的，在此我门给出[/font][font=Times New Roman]CRC[/font][font=宋体]的并行实现方法，以一个字节位处理单位。下面给出[/font][font=Times New Roman]C[/font][font=宋体]语言实现的[/font][font=Times New Roman]CRC32[/font][font=宋体]源程序：[/font]
[font=宋体][img]http://www.icembed.com/UploadFiles/200632720194360.gif[/img][img]http://www.icembed.com/UploadFiles/200632720195371.gif[/img][img]http://www.icembed.com/UploadFiles/200632720195797.gif[/img][/font]
[font=宋体][font=宋体]
[font=宋体]由于以太网[/font][font=Times New Roman]CRC32[/font][font=宋体]要求对帧的前[/font][font=Times New Roman]32bit[/font][font=宋体]取反，我门可以初始化寄存器为全[/font][font=Times New Roman]1[/font][font=宋体]来达到此目的。[/font]
[font=Times New Roman]Crcbuff[/font][font=宋体]中存放需要编码的信息比特，最后计算出[/font][font=Times New Roman]CRC[/font][font=宋体]校验码，跟随信息码一同发送出去。[/font]
[align=center][align=center][b][font=Times New Roman]4[/font][/b][b][font=宋体]总结[/font][/b][/align][/align][font=Times New Roman] [/font][font=宋体]本文是针对项目中嵌入式设备的联网问题，设计的[/font][font=Times New Roman]CRC32[/font][font=宋体]校验算法，已经在[/font][font=Times New Roman]FPGA[/font][font=宋体]中成功实现，由于用[/font][font=Times New Roman]FPGA[/font][font=宋体]实现编码相对简单，这里就不再累述。[/font]
[/font]
[/font][/font][/font][/font]