在网络用户和流量爆炸性增长的今天，通信设备需要兼顾传输性能和效率。目前通信设备的处理带宽已经突破了千兆，10G接口设备已经越来越普遍。高带宽带来的挑战就是数字信号越来越容易受到噪声的影响，事实上，传输错误的发生是非常普遍。任何经由电子方式传输的信息都容易收到干扰，都会对传输产生令人惊讶而不可预测的影响。在某些情况下，当接收方检测到错误时，该信息帧将会被接收方丢弃，同时通知发送者重发该信息帧；在另外一些情况下，接收到的有限错误将会被接收方检测到并且被纠正而无需发送方重新发送，这就需要接收方具有某种程度上的检错纠错能力。重传的方式虽然不要求接收方具有纠错能力，但是需要网络规划时提供一条反向通道传输握手信息，而且降低了传输性能；后者无需反向通道，也不会降低传输效率。目前很多传输标准都定义了检错纠错特性。

循环冗余校验(CRC)是一种重要的线性分组码，不但具有极强的检测能力，而且编解码器采用硬件实现比较简单，特别适合于检测错误，同时还能纠正单比特错误。利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位校验码，附在原始信息后边，构成一个共k+r位的新的二进制码序列数，然后发送出去；在接收端，根据信息码和校验码之间所遵循的规则进行检验，以确定传送中是否出错。在差错控制理论中，这个规则被称为生成多项式。根据r的阶数，可以构造CRC4，CRC16，以及CRC32等不同的生成多项式。通过CRC校验码对整个帧结构进行保护是对随机和突发错误进行检测的最好方法。

目前在传输系统中使用最广泛的数据报文封装结构为通用帧结构(GFP)。GFP在接收定帧时不采用特殊字节进行帧对齐，而是通过对GFP核心帧头的长度域PLI进行CRC16计算，从而判断下一GFP帧的开始来达到定帧的目的。在发送的时候，这个长度域加上其CRC16校验和构成了GFP的核心帧头。除了核心帧头以外，GFP的静荷类型帧头同样也是收到CRC16的保护。在GFP中，无论是核心帧头中的长度域还是静荷类型帧头中的类型域对于GFP来说都是非常重要的信息，因此在标准中都对其定义了单比特误码的纠错要求。具有同样检错和纠错要求的标准还有RFC2823。

对于能够自动纠错的CRC编码，纠错能力与编解码器件复杂度是一个矛盾体。纠错能力越强，编解码器件的实现越复杂，同时需要附加的冗余比特越多。因为CRC种类众多，所以CRC16将是本文讨论的重点。

本文目的不在于对CRC进行完备、详尽的推导和论证，而是以CRC16为例说明高速并行CRC算法的硬件实现，同时给出CRC16单比特误码纠错的FPGA实现。可以将这个例子推广到所有的CRC生成多项式。这里首先给出一个对单比特纠错基础性的结论，即接收端校验码计算值仅仅与传输错误以及生成多项式相关。

令T(x)=a_n-1x^n-1+a_n-2x^n-2+…a₂x²+a₁x¹+a₀为发送的信息序列，这里采用数组T=[a_n-1,a_n-1,…a₂,a₁,a₀]来表示，其中a_i=0 or 1,0≤i≤n-1。

同时令接收信息序列表示为T'(x)=b_n-1x^n-1+b_n-2x^n-2+…+b₁x¹+b₀，这里仍然采用数组来表示，其中b_i=0 or 1,0≤i≤n-1。

这样定义误差序列E=T'-T=[e_n,e_n-1,…e₁,e₀]。误差序列第i位取值为

当e_i=0时，表示i位无错；当e_i=1时，表示i位出错。接收端校验码计算值可以通过下式得到：

其中，H为生成多项式构成的生成矩阵。从高等代数基本理论可以知道，生成矩阵一定是线性无关的，因此T*H^T=0，接收端校验码计算值只与误差序列和生成多项式有关，与被保护的信息序列本身无关。换句话说，生成多项式和误码决定了接收端的校验值计算结果。

CRC16并行FPGA实现

目前常用的CRC16多项式包括x¹⁶+x¹²+x⁵+1以及x¹⁶+x¹⁵+x²+1。前者主要使用于X.25、GFP以及ATM封装定帧，根据其系数将其记为1021(最高位不记)；后者为CCITT定义的CRC16生成多项式，记为8005。本文主要针对前者进行高速实现并给出单比特误码纠错实现建议，所以下文所指的CRC16多项式为1021。

针对CRC16实现，目前存在以下三种主要实现方法：逐比特计算法、查表法和并行计算法。逐比特计算法就是根据CRC16的多项式定义，采用除法硬件电路实现CRC16计算，按照一组线性反馈移位寄存器和模2加单元完成硬件上的除法功能。这种方法实现简单、容易理解，但是不能在高速前提下应用。查表法是一种采用较多的软件实现方式，其代码量少，对于硬件实现来说最大的瓶颈就是需要一个极大的CRC16查找表(LUT，Look-Up Table)。该LUT的大小随输入数据宽度不同而不同。对于8比特数据输入，其LUT需要为个索引值；对于16比特数据输入，其LUT需要为2¹⁶=65536个索引值。因此LUT的大小对FPGA结构本身就是一个挑战。而并行算法则是根据CRC16多项式反馈特性，将串行的比特反馈等效成并行计算等式。以16比特输入为例，其优化后的并行计算等式见图1。

图1：CRC16并行计算等式。

在图1中，R[i]=D[i]⊕C^pre(i)，运算‘⊕’表示二进制异或运算，D[i]表示输入输入数据的第i位，C^pre(i)表示上一个CRC16值的第i位。

CRC16单比特误码纠错原理

前面描述了16比特数据输入的CRC16并行实现，下面将描述怎样在FPGA中实现单比特误码纠错。同样，假设T_tr=[a_n-1,a_n-2,…,a₂,a₁,a₀]为需要传递的信息序列，CRC_tr为该信息序列的CRC16校验码，那么发送序列为(T_tr<<16)&(CRC_tr)；同理，接收端的接收序列为(T_rx<<16)&(CRC_rx)，其中T_rx=[a'_n-1,a'_n-2,…a'₂,a'₁,a'₀]为接收的信息序列，CRC_rx为接收的CRC16校验码。

同时，接收端会对整个接收的数据帧进行校验，如果传输过程中没有任何错误发生，接收端计算得到的CRC_cal应该等于CRC_rx；如果出现传输错误时(有可能是信息序列出现误码，也有可能是发送的CRC本身出现传输误码)，CRC_cal将不等于CRC_rx。正如前面描述，CRC16是可以实现单比特误码纠错的一种线性分组编码，因此无论该单比特错误是出现在信息域，还是在作为冗余信息的CRC16校验码中，接收端都可以实现无误接收。只是当单比特误码出现在信息域时，接收端必须要将其校正过来，而如果该单比特误码出现在CRC16校验码中，则没有必要将其校正过来。

根据前面给出的结论，接收端计算得到的校验码CRC_cal仅仅与传输错误序列和生成多项式相关。观察CRC16并行计算公式，如果输入数据中D[i]出现单比特错误的话，其对应的CRC中对应的比特位将出现错误。例如，数据比特D[1]将影响校验码中的1、6、13位，这意味着D[1]如果出现错误，那么校验码的第1、6、13位的结果将反相。既然无错情况下计算得到的CRC_cal等于CRC_rx，那么下一个CRC计算值将等于0。如果出错的话，那么得到的CRC计算值将等于0X2042。可以证明，每一个数据比特单比特误码出现的CRC计算值都是唯一的，因此我们将数据单比特误码时的CRC_cal⊕CRC_rc总结为表1。

表1：数据单比特误码CRC计算值。

同样，除了数据比特可能出现误码以外，接收的CRC校验码也可能出现误码。当接收的CRC校验码出现某位误码时，显然最终得到的CRC计算值在该比特位置上将反相，因此，当接收的CRC校验码出现单比特误码时，其CRC_cal⊕CRC_rc如表2所示。

表2：接收校验码单比特误码CRC计算值。

[1] [2]  下一页