关键字：CAN、CRC、串行、并行
Hou Dian-Hua Chen Xing
Abstract: In the light of Serial CRC examination principle which proposed in the CAN protocol,this paper introduces the implementation method and the VHDL code. In order to enhance the production speed of CRC code and the efficiency of CRC examination, introduces the CRC examination parallel principle. Finally introduces the VHDL code.
Key words: CAN、CRC、Serial、Parallel
1 引言
信息在传递过程中，可能因某种原因使传输的数据发生错误。为减少和避免这类错误的发生，除提高硬件的可靠性外，在数据的编码上也应提供检错和纠错的支持。常见的校验码有奇偶校验码、海明校验码和循环冗余校验CRC（Cyclic Redundancy Check）码，它们都是将被校验的数据代码按k位一组分组，每组添加r个校验位，形成n位一组的代码，故又称为（n，k）分组校验码。其中CRC码既可检错又可纠错（与生成多项式的选取有关），是以数据块为对象进行校验的一种高效、可靠的检错和纠错方法，由于它的编解码简单、纠错能力强且误判概率很低，因而在工业测控及通信系统中得到了广泛的应用。
CAN协议中，为了保证帧传输的可靠性和较高的检错效率，其采用了以下几种检错方式：位错误、填充错误、CRC错误、格式错误及应答错误检测。如果，用m表示报文受损率，那么通过以上检错方式，它对于受损报文检测不到其受损的概率为：
，因而CAN总线极高的检错率使得它目前被广泛应用到工业控制、通信、汽车甚至军事等多个领域。CRC检验作为CAN协议中一种重要的且行之有效的检错方式，它的生成多项式可以检验7级，具有编码简单且误判率低的优点。
2 CRC编码原理
循环冗余码属于多项式生成码，编译码设备都不太复杂，检（纠）错能力较强。它的规律在于编码后含n位码元的一个码组中有k位信息元和r=n-k位监督元，二者混合形成规律性，监督元是随着所传输的信息元而改变的。其工作原理如图1所示，图中P为输入数据，G为生成多项式对应的编码。
图1 CRC校验原理图
Fig.1The Schematic diagram of CRC
假定需传输的数据P=110，也就是信息元，此时k=3，与它对应的多项式为
n=7且对应的
（其最低4位为零，以便拼装4位监督位）。用生成多项式g（x）去除
，在运算中使用的均为模2的特殊运算。求CRC码所采用模2加减运算法则，即是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。如：
。则有：
取余数Q=101，所传输的数据为
，n=7，该数据前三位是信息元，后四位是CRC序列。
接收端收到数据时，为进行校验，仍用g（x）去除接收到信息所对应的多项式
，由表达式（4）可以得到：
两个相同的数的模2和为0，所以若接收数据无误时，
应能被个g（x）整除。在此工作机制下，上述循环码不但可检查出n-k-1个独立错误，还可以检查出长度b<n-k的突发错误。
3 CRC编码的硬件语言实现
CRC编码的硬件语言实现，可以采用串行算法和并行算法两种实现方式。串行算法即是移位算法，有的文献称之为比特流算法，需编码的位流按位逐位输入，位流输入完成后生成检验码，检验码紧随需检验的位流发出或接收到。并行方式中需检验的位流每k位输入到检验码生成电路中，因而检验码的生成效率大大高于串行方式。以下针对CAN协议中CRC编码的生成多项式进行阐述。
3.1 CRC编码的串行实现
由循环码的编码方法可知，循环码的编码可以由除法电路实现。除法电路的主体由多级移位寄存器和模2加法器组成。由循环码的译码与纠错方法可知，译码器主要由一个除法器和缓冲移位寄存器构成。若接收有误，可经过几次移位后，在相应的错码位上输出“1”作为检错，并可以通过与缓冲移位寄存器输出的错码模2加后来纠正错误。
CAN2.0A标准中，某数据帧（无数据场）前19位为0110001000111001000，对于生成多项式g（x）可从有关资料上查阅取得，它必须满足下述要求：
（1）任何一位发生错误都应使余数不为0;
（2）不同位发生错误应使余数不同;
（3）对余数继续作模2除时，应是余数循环本处取
为完成求得CRC序列，可以使用一个15位移位寄存器CRC_RG（14：0）。若以NXTBIT标记该位流的下一位，它由从帧起始至数据场结束的无填充位的序列给定。CRC序列的计算如下：
CRC_RG=0 //初始化寄存器
REPEAT
CRCNXT = NXTBITE XOR CRC_RG（14）;
CRC_RG（14：1） = CRC_RG（13：0）;//寄存器左移一位
CRC_RG（0） = 0;
IF CRCNXT THEN
CRC_RG（14：0） = CRC_RG（14：0） EXOR （4599H）;
END IF
UNTIL（CRC序列开始或者存在一个出错状态）
得到CRC序列为：000001000110101，发送/接收数据场的最后一位后，CRC_RG包含CRC序列，CRC序列后面是CRC界定符，它只包含一个隐位（高电平）1。
串行算法的VHDL程序代码如下：
Library ieee;
Use ieee.std_logic_1164.all;
Use ieee.std_logic_unsigned.all;
Use ieee.std_logic_arith.all;
Entity can_vhdl_crc is
port （
clk : in std_logic;
data : in std_logic;
enable : in std_logic;
initialize : in std_logic;
crc : out std_logic_vector（14 downto 0））;
End entity can_vhdl_crc;
Architecture rtl of can_vhdl_crc is
Type xhdl_46 is array（0 ot 7） of std_logic_vector（7 downto 0）;
Signal crc_next : std_logic;
Signal crc_tmp : std_logic_vector（14 DOWNTO 0）;
Signal crc_xhdl1 : std_logic_vector（14 DOWNTO 0）;
begin
crc <= crc_xhdl1;
crc_next <= data xor crc_xhdl1（14） ;
crc_tmp <= crc_xhdl1（13 downto 0） & ‘0‘ ;
process （clk）
begin
if （clk‘event and clk = ‘1‘） then
if （initialize = ‘1‘） then
crc_xhdl1 <= "000000000000000";
else
if （enable = ‘1‘） then then
if （crc_next = ‘1‘） then
crc_xhdl1 <= crc_tmp xor "100010110011001";
else
crc_xhdl1 <= crc_tmp ;
end if;
end if;
end if;
end if;
end process;
end Architecture rtl;
3.2 CRC编码的并行计算
目前已采用CRC并行算法是查表法及基于查表法而导出的一些方法。这些方法均需要存储长度较大的CRC余数表,随着并行度的增加,余数表的长度大大增加（按指数增加），其现实性亦随之大大降低。
该算法事先把待校验的信息码P的所有CRC码全部计算出来，放在一个表里，编码时只要根据P从表中找出对应的值进行处理即可。其硬件实现示意框图如图2所示。编码解码前清零CRC寄存器。编码时待信息码P输入结束，CRC寄存器的值即为校验码Q;解码校验时待传送码P输入结束时，若CRC寄存器中的值为零，则表明传输无误。该算法执行速度快，适合于高速通信场合，但由于需要大容量的存储表，花费的硬件资源较串行算法要大得多。
图2 并行算法示意图
Fig.2 The Schematic drawing of Parallel Algorithm
为使（n，k）码能具体指出数据在传输中出错的位，数据位数k和校验位数r之间应满足海明不等式：k+r<2r-1 。为简明起见，这里假设欲传送的数据代码P按4位一组分组（即k=4），则r≥3，若选定生成多项式g（x）=x3+x2+1则可得采用并行算法求Q的VHDL程序如下：
library ieee;
use ieee.std_logic_1164.all;
entity crc_jym1 is
generic（m_wide:integer:=3;
r_wide:integer:=2）;
port（m_in:in std_logic_vector（m_wide downto 0）;
r_out:out std_logic_vector（r_wide downto 0））;
end crc_jym1;
architecture a of crc_jym1 is
constant crc_wide:integer:=m_wide+r_wide+1;
constant g_wide:integer:=r_wide+1;
signal mm:std_logic_vector（crc_wide downto 0）;
constant g:std_logic_vector（g_wide downto 0）:="1101";
begin
process（m_in）
variable d:std_logic_vector（g_wide downto 0）;
variable r:std_logic_vector（r_wide downto 0）;
begin
r:=（others=>‘0‘）;
mm<=m_in&r;
d:=mm（crc_wide downto（crc_wide-g_wide））;
for i in（crc_wide-g_wide-1）downto 0 loop
if d（g_wide）=‘0‘then
r:=d（r_wide downto 0）;
else
for j in r_wide downto 0 loop
r（j）:=d（j）xor g（j）;
end loop;
end if;
d:=r&mm（i）;
end loop;
if d（g_wide）=‘0‘then
r:=d（r_wide downto 0）;
else
for j in r_wide downto 0 loop
r（j）:=d（j）xor g（j）;
end loop;
end if;
r_out<=r;
end process;
end a;
4 总结
本文在分析了CRC计算原理的基础上，仔细运用VHDL的特点进行串、并行CRC算法建模从而实现的设计，不仅具备采用公式法设计所具有的优点，还能很好地适用于各种数据块大小不同、生成多项式选取不同的CRC编、解码运用场合，明显减轻设计开发工作量，大幅缩短产品的研发周期。此外，由于生成结果占用的硬件资源很少，只需利用系统集成芯片中剩余的少量资源即可实现，在当前大量的系统设计实现趋向单芯片化的大潮下，更具生命力。
参考文献
[1] 王海光，并行CRC算法硬件实现研究与VHDL设计[J]. 漳州师范学院学报（自然科学版），2007年第4期（总第58期），51-56.
[2] 李永忠，通用并行CRC计算原理及其硬件实现方法[J]. 西北民族学院学报（自然科学版），2 0 0 2年3月第23卷总第43期，33-37.
[3] 蒋安平，循环冗余校验码（CRC）的硬件并行实现[J]. 微电子学与计算机，2007年第24卷第2期，107-109，112.
