论文部分内容阅读
[摘要]讨论循环冗余校验码的原理，以ATM中的CRC为例，用FPGA实现并行计算
[关键词]CRC FPGA 并行
中图分类号：TP2文献标识码：A 文章编号：1671－7597（2008）0310011－01
一、CRC的数学原理
在一个(n,k)循环码中，仅存在一个r=n-k次的生成多项式G(x)，其最高位和最低位系数恒为1，其他各项系数为0或1。将由信息帧组成的信息码多项式M(x)(次数为k)，乘以xR，除以G(x)得到余式R(x)，由高到低取R(x)的系数，就得到CRC，即：
在接收端通过相同的方法计算CRC，与接收到的CRC做比较，如果一致，就认为在传输过程中没有发生误码，反之，则在传输过程中有错误发生。
二、CRC并行计算的分析推导
CRC编译码的计算涉及到模2的加（减）、乘、除，最终都归结为数字信号的位移和异或操作。由于CRC码的校验位就是模2除的余数，则设寄存器的存数表示余数，异或门表示模2运算，则通用的串行CRC校验电路就可以由如图1所示线性反馈以为寄存器实现。g（i）的通断由生成多项式的对应的系数是0还是1决定，1通0断。
例如ATM信头里的CRC校验的生成多项式是g(x)=x8+x2 +x+1，由其系数[0:8]:111000001可将其串行编码电路简化为下图所示
可以看出，各移位寄存器当前的存数即为CRC余数值，当进行串行CRC运算时，当前的CRC余数值只与当前信息码的最前一位的输入值和前一状态的CRC余数值有关。有此可以推断，在进行8比特的并行CRC运算时，8比特信息码一次输入并行运算电路所产生的CRC值应该和8比特信息码依次输入串行运算电路所产生的CRC值完全相同。基于这一思想，根据串行CRC运算电路可以推导出并行CRC的运算方法。
分别表示移位寄存器状态值和信息码输入序列，
分别表示并行的8比特数据。
这样就推倒出了CRC[0]并行计算8比特后得到的值，其他几个寄存器可以用类似的方法获得。可见，本次CRC值只和本次8位信息码的若干位和上次8位并行信息码所产生的CRC余数的若干位有关。
三、ATM协议中CRC并行计算的FPGA实现
在ATM协议中有若干个CRC校验，例如ATM信元头的校验，AAL2中CPS头的校验，AAL5最后的CRC32校验，因为在FPGA内部的数据处理都是基于8比特或是16比特，所以串行的CRC计算显然是不适用的，根据前述的推倒就可以很方便的计算8比特数据的并行CRC校验。Verilog代码如下：
always @ （posedge clk or posedge rst）
begin
if（rst）
crc ＜= 8'h0；
else if（init_val_en）
crc ＜= init_val；
else if（crc_en）
crc ＜= next_crc；
end
assign next_crc[0] = crc[7] ^ crc[6] ^ crc[0] ^ d[7] ^ d[6] ^ d[0]；
assign next_crc[1] = crc[6] ^ crc[1] ^ crc[0] ^ d[6] ^ d[1] ^ d[0]；
assign next_crc[2] = crc[6] ^ crc[2] ^ crc[1] ^ crc[0] ^ d[6] ^ d[2] ^ d[1] ^ d[0]；
assign next_crc[3] = crc[7] ^ crc[3] ^ crc[2] ^ crc[1] ^ d[7] ^ d[3] ^ d[2] ^ d[1]；
assign next_crc[4] = crc[4] ^ crc[3] ^ crc[2] ^ d[4] ^ d[3] ^ d[2]；
assign next_crc[5] = crc[5] ^ crc[4] ^ crc[3] ^ d[5] ^ d[4] ^ d[3]；
assign next_crc[6] = crc[6] ^ crc[5] ^ crc[4] ^ d[6] ^ d[5] ^ d[4]；
assign next_crc[7] = crc[7] ^ crc[6] ^ crc[5] ^ d[7] ^ d[6] ^ d[5]；
与之类似，AAL5的CRC32因为也是8比特的整数倍，所以可以计算出每一位的表达式后，得到并行计算的CRC模块。有区别的是对于AAL2中CPS头的5比特CRC计算。因为是要根据19比特来计算出5比特的CRC校验码，所以无法整除，但是也可以用并行的来计算，可以先计算两次并行8比特的，再计算一次并行3比特的，这样就能够很快得到最后的校验码。可以看出，只要理解的CRC并行计算的思想，所有的情况都可以用类似的方法来计算，而不必用耗时的串行计算方法。
参考文献：
[1]夏闻宇，复杂数字电路与系统的Verilog-HDL设计技术，北京航空航天大学出版社，1999.
[2]曹志刚、钱亚生，现代通信原理，清华大学出版社，2000.
[3]王新梅、肖国镇，纠错码－原理与方法，西安电子科技大学出版社，2001.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
[关键词]CRC FPGA 并行
中图分类号：TP2文献标识码：A 文章编号：1671－7597（2008）0310011－01
一、CRC的数学原理
在一个(n,k)循环码中，仅存在一个r=n-k次的生成多项式G(x)，其最高位和最低位系数恒为1，其他各项系数为0或1。将由信息帧组成的信息码多项式M(x)(次数为k)，乘以xR，除以G(x)得到余式R(x)，由高到低取R(x)的系数，就得到CRC，即：
在接收端通过相同的方法计算CRC，与接收到的CRC做比较，如果一致，就认为在传输过程中没有发生误码，反之，则在传输过程中有错误发生。
二、CRC并行计算的分析推导
CRC编译码的计算涉及到模2的加（减）、乘、除，最终都归结为数字信号的位移和异或操作。由于CRC码的校验位就是模2除的余数，则设寄存器的存数表示余数，异或门表示模2运算，则通用的串行CRC校验电路就可以由如图1所示线性反馈以为寄存器实现。g（i）的通断由生成多项式的对应的系数是0还是1决定，1通0断。
例如ATM信头里的CRC校验的生成多项式是g(x)=x8+x2 +x+1，由其系数[0:8]:111000001可将其串行编码电路简化为下图所示
可以看出，各移位寄存器当前的存数即为CRC余数值，当进行串行CRC运算时，当前的CRC余数值只与当前信息码的最前一位的输入值和前一状态的CRC余数值有关。有此可以推断，在进行8比特的并行CRC运算时，8比特信息码一次输入并行运算电路所产生的CRC值应该和8比特信息码依次输入串行运算电路所产生的CRC值完全相同。基于这一思想，根据串行CRC运算电路可以推导出并行CRC的运算方法。
分别表示移位寄存器状态值和信息码输入序列，
分别表示并行的8比特数据。
这样就推倒出了CRC[0]并行计算8比特后得到的值，其他几个寄存器可以用类似的方法获得。可见，本次CRC值只和本次8位信息码的若干位和上次8位并行信息码所产生的CRC余数的若干位有关。
三、ATM协议中CRC并行计算的FPGA实现
在ATM协议中有若干个CRC校验，例如ATM信元头的校验，AAL2中CPS头的校验，AAL5最后的CRC32校验，因为在FPGA内部的数据处理都是基于8比特或是16比特，所以串行的CRC计算显然是不适用的，根据前述的推倒就可以很方便的计算8比特数据的并行CRC校验。Verilog代码如下：
always @ （posedge clk or posedge rst）
begin
if（rst）
crc ＜= 8'h0；
else if（init_val_en）
crc ＜= init_val；
else if（crc_en）
crc ＜= next_crc；
end
assign next_crc[0] = crc[7] ^ crc[6] ^ crc[0] ^ d[7] ^ d[6] ^ d[0]；
assign next_crc[1] = crc[6] ^ crc[1] ^ crc[0] ^ d[6] ^ d[1] ^ d[0]；
assign next_crc[2] = crc[6] ^ crc[2] ^ crc[1] ^ crc[0] ^ d[6] ^ d[2] ^ d[1] ^ d[0]；
assign next_crc[3] = crc[7] ^ crc[3] ^ crc[2] ^ crc[1] ^ d[7] ^ d[3] ^ d[2] ^ d[1]；
assign next_crc[4] = crc[4] ^ crc[3] ^ crc[2] ^ d[4] ^ d[3] ^ d[2]；
assign next_crc[5] = crc[5] ^ crc[4] ^ crc[3] ^ d[5] ^ d[4] ^ d[3]；
assign next_crc[6] = crc[6] ^ crc[5] ^ crc[4] ^ d[6] ^ d[5] ^ d[4]；
assign next_crc[7] = crc[7] ^ crc[6] ^ crc[5] ^ d[7] ^ d[6] ^ d[5]；
与之类似，AAL5的CRC32因为也是8比特的整数倍，所以可以计算出每一位的表达式后，得到并行计算的CRC模块。有区别的是对于AAL2中CPS头的5比特CRC计算。因为是要根据19比特来计算出5比特的CRC校验码，所以无法整除，但是也可以用并行的来计算，可以先计算两次并行8比特的，再计算一次并行3比特的，这样就能够很快得到最后的校验码。可以看出，只要理解的CRC并行计算的思想，所有的情况都可以用类似的方法来计算，而不必用耗时的串行计算方法。
参考文献：
[1]夏闻宇，复杂数字电路与系统的Verilog-HDL设计技术，北京航空航天大学出版社，1999.
[2]曹志刚、钱亚生，现代通信原理，清华大学出版社，2000.
[3]王新梅、肖国镇，纠错码－原理与方法，西安电子科技大学出版社，2001.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”