循环冗余校验(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计算值。

因此，对CRC16单比特误码纠错就变成了通过CRC计算值找到相应的单比特出错序号。此外，还可以同时区别错误来源，如果是数据单比特出错，则需要完成单比特纠错；如果是校验码出错，则无需对校验码进行单比特纠错。

CRC16单比特误码纠错FPGA实现

前面对对CRC16单比特误码纠错原理进行了分析，接下来讨论利用FPGA完成CRC16的单比特误码纠错实现。此FPGA实现可以采用查表法和One-Hot编码法。

1．查表法

根据表1和表2，CRC16单比特误码情况总共有32种，其中16种对应数据单比特误码，另外16种对应校验码单比特误码。由于每种错误情况都是唯一的，所以如果采用16比特的CRC计算值作为索引进行查表得到单比特出错序号，那么需要2¹⁶=65536个索引值；如果查表结果是16比特输出(每个比特位置对应一个单比特误码)，总共需要1Mbit查找表空间。因此，这里采用CRC计算值的高8位作为索引值来构造查找表。但是，这样做需要处理两个难点：索引值重叠和校验码单比特误码CRC值重复。对于前者，当数据单比特误码序号为0、1、2时，将与校验码单比特误码序号4、5、6以及12、13、14重叠，因此在实现时还需要CRC值的低8位。如果低8位为全0，则为校验码单比特误码，否则为数据单比特误码。对于校验码单比特误码CRC值重复，在利用CRC值进行查表时，首先需要选择是高8位还是低8位，以得到索引值。

通过以上分析可知，这里需要构造一个索引深度为256的稀疏表。该表格只有在1、2、3、4、6、8、13、16、18、27、32、36、51、64、72、102、128、129、137、145和204才有匹配项，其余地址全部为零。匹配项设计如图2所示。

图2：CRC单比特误码表项结构。

匹配表项中包括内容为：错误标志、数据误码标志、校验码误码标志、CRC值低8位、纠错码型。其中纠错码型为16位，其中只有一个比特有效，该比特出现的位置表示需要对接收数据在该位置上进行单比特误码纠错。这里给出一种单比特误码纠错情况：如果计算得到CRC值为0X8108，将其高8位作为查表索引，得到接收数据误码、无校验码误码，对应的纠错码型为0X0008，意味着需要对输入数据的bit 3进行纠错。这里需要注意的是，由于索引地址16、32、64在数据单比特误码和CRC校验码单比特误码中会同时出现，因此这几个索引地址的匹配项中数据误码标志和校验码误码标志同时为1，此时需要根据CRC低8比特值是否为0来判定是数据误码还是校验码误码。

如果查找命中上述索引项，表示当前出现单比特误码，根据数据误码标志和校验码误码标志确定是否实现单比特纠错，如果需要进行纠错则将接收数据与纠错码型进行异或，从而完成单比特纠错过程。

如果命中地址0，表示当前没有出现任何误码；如果命中其余匹配项，表示当前出现多比特错误。整个查找纠错过程参见图3。

图3：查表法处理流程。

2．One-Hot编码法

基于One-Hot编码的实现是利用表1、表2中单比特误码的唯一性，只不过采用逻辑实现得到纠错码型和数据误码标志以及CRC校验值误码标志。下面给出部分代码：

reg[15:0] crc_correction ; // One-Hot纠错码型

reg[15:0] crc_val ; // CRC计算值

// 判断数据比特0是否出现单比特误码

always @(posedge clk or negedge rst_n)

if(rst_n == 1'b0)

crc_correction[0] <= 1'b0;

else if(crc_en == 1'b1 && crc_val==16'h1201)

crc_correction [0] <= 1'b1;

else

crc_correction [0] <= 1'b0;

// 判断数据比特1－15是否出现单比特误码。同比特0单比特误码判断机制相同。

...

// 数据无误码标志，标志为1表示当前接收数据没有任何误码

always @(posedge clk or negedge rst_n)

if(rst_n == 1'b0)

rx_ok <= 1'b0;

else if(crc_en == 1'b1 && crc_val == 16'h0)

rx_ok <= 1'b1;

else

rx_ok <= 1'b0;

// 数据单比特误码标志和多比特误码标志

always @(posedge clk or negedge rst_n)

if(rst_n == 1'b0) begin

crc_data_1_bit <= 1'b0;

crc_data_m_bit <= 1'b0;

end

else if((crc_correction[0] + crc_correction[1] + crc_correction[2] + crc_correction[3] +

crc_correction[4] + crc_correction[5] + crc_correction[6] + crc_correction[7] +

crc_correction[8] + crc_correction[9] + crc_correction[10] + crc_correction[11] +

crc_correction[12] + crc_correction[13] + crc_correction[14] + crc_correction[15] ) == 1'b1) begin // 出现单比特错误

crc_data_1_bit <= 1'b1;

crc_data_m_bit <= 1'b0;

end

else if(rx_ok == 1'b0) begin // 出现多比特错误

crc_data_1_bit <= 1'b0;

crc_data_m_bit <= 1'b1;

end

// 校正单比特数据。需要根据时序对输入数据进行同步 ,_dly1表示对信号同步一拍；_dly2

// 表示对信号同步2拍。syn_data表示单比特误码纠错以后的同步数据。

always @(posedge clk or negedge rst_n)

if(rst_n == 1'b0)

syn_data <= 16'b0;

else if(crc_en == 1'b1 && crc_data_1_bit == 1'b1)

syn_data <= rx_data_dly2 ^ crc_correction_dly1;

else if(rx_ok_dly1 == 1'b1)

syn_data <= rx_data_dly2;

else

syn_data <= 16'b0;

本文小结

本文给出了CRC16单比特误码纠错的算法分析，并给出了查表法和One-Hot编码的FPGA实现。查表法和One-Hot编码这两种方法各有特点。查表法需要256*26比特的块RAM来存储稀疏单比特误码表，根据ALTERA的器件结构，如果采用M4K RAM完成存储表项，仅需要2个M4K RAM；而One-Hot编码不需要块RAM。从代码复杂度上看，查表法代码量少，结构比较清晰；One-Hot编码代码量较大，实现结构较为复杂。无论采用何种方法均可以实现CRC16单比特误码纠错算法。

由于ATM、GFP、RFC2823的帧结构需要CRC16完成帧头校验计算，在接收端需要通过比较CRC16计算值完成定帧功能，因此CRC16的单比特误码纠错功能非常重要，它可以提高系统对噪声的容忍特性。目前有大量的文献说明了CRC的并行实现以提高电路性能，但是几乎没有对CRC单比特误码纠错进行原理说明和具体的实现分析，因此本文具有一定的参考价值。

附：参考文档
1. ITU-T, Generic Framing Procedure (GFP), ITU-T Recommendation G.7041/Y.1301, 08/2005
2. RFC 2823, PPP over Simple Data Link (SDL)using SONET/SDH with ATM-like framing, 05/2000
3. 《现代通信原理》，清华大学出版社，曹志刚、钱亚生，08/1992
4. Single Bit Error Correction Implementation in CRC16, Sunil Shukla, Neil W. Bergmann, IEEE, 2004
5. 《通信原理》，北京邮电大学出版社，周炯槃等，11/2005