摘 要：針對(duì)CAN協(xié)議中提出的串行CRC檢驗(yàn)原理，給出其實(shí)現(xiàn)方法及硬件語言VHDL代碼。為了提高CRC編碼的生成速度和CRC檢驗(yàn)的效率，介紹了CRC檢驗(yàn)的并行原理。最后給出了為滿足CAN協(xié)議的VHDL代碼。經(jīng)過測(cè)試，串、并行運(yùn)算均滿足設(shè)計(jì)要求。 關(guān)鍵字：CAN、CRC、串行、并行 [b][align=center]The VHDL Implementation for CRC in CanBus Protocol Hou Dian-Hua Chen Xing[/align][/b] 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 引言 　　信息在傳遞過程中，可能因某種原因使傳輸?shù)臄?shù)據(jù)發(fā)生錯(cuò)誤。為減少和避免這類錯(cuò)誤的發(fā)生，除提高硬件的可靠性外，在數(shù)據(jù)的編碼上也應(yīng)提供檢錯(cuò)和糾錯(cuò)的支持。常見的校驗(yàn)碼有奇偶校驗(yàn)碼、海明校驗(yàn)碼和循環(huán)冗余校驗(yàn)CRC（Cyclic Redundancy Check）碼，它們都是將被校驗(yàn)的數(shù)據(jù)代碼按k位一組分組，每組添加r個(gè)校驗(yàn)位，形成n位一組的代碼，故又稱為（n，k）分組校驗(yàn)碼。其中CRC碼既可檢錯(cuò)又可糾錯(cuò)（與生成多項(xiàng)式的選取有關(guān)），是以數(shù)據(jù)塊為對(duì)象進(jìn)行校驗(yàn)的一種高效、可靠的檢錯(cuò)和糾錯(cuò)方法，由于它的編解碼簡(jiǎn)單、糾錯(cuò)能力強(qiáng)且誤判概率很低，因而在工業(yè)測(cè)控及通信系統(tǒng)中得到了廣泛的應(yīng)用。 　　CAN協(xié)議中，為了保證幀傳輸?shù)目煽啃院洼^高的檢錯(cuò)效率，其采用了以下幾種檢錯(cuò)方式：位錯(cuò)誤、填充錯(cuò)誤、CRC錯(cuò)誤、格式錯(cuò)誤及應(yīng)答錯(cuò)誤檢測(cè)。如果，用m表示報(bào)文受損率，那么通過以上檢錯(cuò)方式，它對(duì)于受損報(bào)文檢測(cè)不到其受損的概率為：，因而CAN總線極高的檢錯(cuò)率使得它目前被廣泛應(yīng)用到工業(yè)控制、通信、汽車甚至軍事等多個(gè)領(lǐng)域。CRC檢驗(yàn)作為CAN協(xié)議中一種重要的且行之有效的檢錯(cuò)方式，它的生成多項(xiàng)式可以檢驗(yàn)7級(jí)，具有編碼簡(jiǎn)單且誤判率低的優(yōu)點(diǎn)。 2 CRC編碼原理 　　循環(huán)冗余碼屬于多項(xiàng)式生成碼，編譯碼設(shè)備都不太復(fù)雜，檢（糾）錯(cuò)能力較強(qiáng)。它的規(guī)律在于編碼后含n位碼元的一個(gè)碼組中有k位信息元和r=n-k位監(jiān)督元，二者混合形成規(guī)律性，監(jiān)督元是隨著所傳輸?shù)男畔⒃淖兊摹Ｆ涔ぷ髟砣鐖D1所示，圖中P為輸入數(shù)據(jù)，G為生成多項(xiàng)式對(duì)應(yīng)的編碼。 [align=center] 圖1 CRC校驗(yàn)原理圖 Fig.1The Schematic diagram of CRC[/align] 　　假定需傳輸?shù)臄?shù)據(jù)P=110，也就是信息元，此時(shí)k=3，與它對(duì)應(yīng)的多項(xiàng)式為 　　 　　n=7且對(duì)應(yīng)的（其最低4位為零，以便拼裝4位監(jiān)督位）。用生成多項(xiàng)式g（x）去除，在運(yùn)算中使用的均為模2的特殊運(yùn)算。求CRC碼所采用模2加減運(yùn)算法則，即是不帶進(jìn)位和借位的按位加減，這種加減運(yùn)算實(shí)際上就是邏輯上的異或運(yùn)算，加法和減法等價(jià)，乘法和除法運(yùn)算與普通代數(shù)式的乘除法運(yùn)算是一樣，符合同樣的規(guī)律。如：。則有： 　　 　　取余數(shù)Q=101，所傳輸?shù)臄?shù)據(jù)為，n=7，該數(shù)據(jù)前三位是信息元，后四位是CRC序列。 　　接收端收到數(shù)據(jù)時(shí)，為進(jìn)行校驗(yàn)，仍用g（x）去除接收到信息所對(duì)應(yīng)的多項(xiàng)式，由表達(dá)式（4）可以得到： 　　 　　兩個(gè)相同的數(shù)的模2和為0，所以若接收數(shù)據(jù)無誤時(shí)，應(yīng)能被個(gè)g（x）整除。在此工作機(jī)制下，上述循環(huán)碼不但可檢查出n-k-1個(gè)獨(dú)立錯(cuò)誤，還可以檢查出長度b3 CRC編碼的硬件語言實(shí)現(xiàn) 　　CRC編碼的硬件語言實(shí)現(xiàn)，可以采用串行算法和并行算法兩種實(shí)現(xiàn)方式。串行算法即是移位算法，有的文獻(xiàn)稱之為比特流算法，需編碼的位流按位逐位輸入，位流輸入完成后生成檢驗(yàn)碼，檢驗(yàn)碼緊隨需檢驗(yàn)的位流發(fā)出或接收到。并行方式中需檢驗(yàn)的位流每k位輸入到檢驗(yàn)碼生成電路中，因而檢驗(yàn)碼的生成效率大大高于串行方式。以下針對(duì)CAN協(xié)議中CRC編碼的生成多項(xiàng)式進(jìn)行闡述。 　　3.1 CRC編碼的串行實(shí)現(xiàn) 　　由循環(huán)碼的編碼方法可知，循環(huán)碼的編碼可以由除法電路實(shí)現(xiàn)。除法電路的主體由多級(jí)移位寄存器和模2加法器組成。由循環(huán)碼的譯碼與糾錯(cuò)方法可知，譯碼器主要由一個(gè)除法器和緩沖移位寄存器構(gòu)成。若接收有誤，可經(jīng)過幾次移位后，在相應(yīng)的錯(cuò)碼位上輸出“1”作為檢錯(cuò)，并可以通過與緩沖移位寄存器輸出的錯(cuò)碼模2加后來糾正錯(cuò)誤。 　　CAN2.0A標(biāo)準(zhǔn)中，某數(shù)據(jù)幀（無數(shù)據(jù)場(chǎng)）前19位為0110001000111001000，對(duì)于生成多項(xiàng)式g（x）可從有關(guān)資料上查閱取得，它必須滿足下述要求： 　�。�1）任何一位發(fā)生錯(cuò)誤都應(yīng)使余數(shù)不為0; 　�。�2）不同位發(fā)生錯(cuò)誤應(yīng)使余數(shù)不同; 　�。�3）對(duì)余數(shù)繼續(xù)作模2除時(shí)，應(yīng)是余數(shù)循環(huán)本處取 　　 　　為完成求得CRC序列，可以使用一個(gè)15位移位寄存器CRC_RG（14：0）。若以NXTBIT標(biāo)記該位流的下一位，它由從幀起始至數(shù)據(jù)場(chǎng)結(jié)束的無填充位的序列給定。CRC序列的計(jì)算如下： 　　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序列開始或者存在一個(gè)出錯(cuò)狀態(tài)） 　　得到CRC序列為：000001000110101，發(fā)送/接收數(shù)據(jù)場(chǎng)的最后一位后，CRC_RG包含CRC序列，CRC序列后面是CRC界定符，它只包含一個(gè)隱位（高電平）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編碼的并行計(jì)算 　　目前已采用CRC并行算法是查表法及基于查表法而導(dǎo)出的一些方法。這些方法均需要存儲(chǔ)長度較大的CRC余數(shù)表,隨著并行度的增加,余數(shù)表的長度大大增加（按指數(shù)增加），其現(xiàn)實(shí)性亦隨之大大降低。 　　該算法事先把待校驗(yàn)的信息碼P的所有CRC碼全部計(jì)算出來，放在一個(gè)表里，編碼時(shí)只要根據(jù)P從表中找出對(duì)應(yīng)的值進(jìn)行處理即可。其硬件實(shí)現(xiàn)示意框圖如圖2所示。編碼解碼前清零CRC寄存器。編碼時(shí)待信息碼P輸入結(jié)束，CRC寄存器的值即為校驗(yàn)碼Q;解碼校驗(yàn)時(shí)待傳送碼P輸入結(jié)束時(shí)，若CRC寄存器中的值為零，則表明傳輸無誤。該算法執(zhí)行速度快，適合于高速通信場(chǎng)合，但由于需要大容量的存儲(chǔ)表，花費(fèi)的硬件資源較串行算法要大得多。 [align=center] 圖2 并行算法示意圖 Fig.2 The Schematic drawing of Parallel Algorithm[/align] 　　為使（n，k）碼能具體指出數(shù)據(jù)在傳輸中出錯(cuò)的位，數(shù)據(jù)位數(shù)k和校驗(yàn)位數(shù)r之間應(yīng)滿足海明不等式：k+r<2[sup]r[/sup]-1 。為簡(jiǎn)明起見，這里假設(shè)欲傳送的數(shù)據(jù)代碼P按4位一組分組（即k=4），則r≥3，若選定生成多項(xiàng)式g（x）=x[sup]3[/sup]+x[sup]2[/sup]+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 總結(jié) 　　本文在分析了CRC計(jì)算原理的基礎(chǔ)上，仔細(xì)運(yùn)用VHDL的特點(diǎn)進(jìn)行串、并行CRC算法建模從而實(shí)現(xiàn)的設(shè)計(jì)，不僅具備采用公式法設(shè)計(jì)所具有的優(yōu)點(diǎn)，還能很好地適用于各種數(shù)據(jù)塊大小不同、生成多項(xiàng)式選取不同的CRC編、解碼運(yùn)用場(chǎng)合，明顯減輕設(shè)計(jì)開發(fā)工作量，大幅縮短產(chǎn)品的研發(fā)周期。此外，由于生成結(jié)果占用的硬件資源很少，只需利用系統(tǒng)集成芯片中剩余的少量資源即可實(shí)現(xiàn)，在當(dāng)前大量的系統(tǒng)設(shè)計(jì)實(shí)現(xiàn)趨向單芯片化的大潮下，更具生命力。 參考文獻(xiàn) 　　[1] 王海光，并行CRC算法硬件實(shí)現(xiàn)研究與VHDL設(shè)計(jì)[J]. 漳州師范學(xué)院學(xué)報(bào)（自然科學(xué)版），2007年第4期（總第58期），51-56. 　　[2] 李永忠，通用并行CRC計(jì)算原理及其硬件實(shí)現(xiàn)方法[J]. 西北民族學(xué)院學(xué)報(bào)（自然科學(xué)版），2 0 0 2年3月第23卷總第43期，33-37. 　　[3] 蔣安平，循環(huán)冗余校驗(yàn)碼（CRC）的硬件并行實(shí)現(xiàn)[J]. 微電子學(xué)與計(jì)算機(jī)，2007年第24卷第2期，107-109，112.