基于MATLAB的HDLC協(xié)議CRC算法仿真

【摘要】HDLC協(xié)議廣泛的應(yīng)用于網(wǎng)絡(luò)，無線傳輸及工業(yè)控制中，對于HDLC協(xié)議中幀校驗(yàn)FCS的算法，由于子協(xié)議的不同和芯片廠家的差異，導(dǎo)致變化多樣，很容易混淆。本文分析了HDLC協(xié)議中幀校驗(yàn)FCS的計(jì)算原理及基本算法，之后列舉了各種常見的變化算法，使用matlab作為仿真工具，對計(jì)算方法和計(jì)算結(jié)果進(jìn)行了驗(yàn)證。

【關(guān)鍵詞】HDLC，MatlabCRC算法仿真

七十年代初期，IBM公司率先提出了面向比特的同步數(shù)據(jù)鏈路控制規(guī)程SDLC（Synchrous Data Link Control），隨后，國際標(biāo)準(zhǔn)化組織ISO采納并發(fā)展了SDLC，并分別提出了自己的標(biāo)準(zhǔn)，即高級數(shù)據(jù)鏈路控制規(guī)程HDLC（High-level Data Link Control）。

HDLC的特點(diǎn)：協(xié)議不依賴于任何字符編碼集；數(shù)據(jù)報(bào)文透明傳輸；全雙工通信，有較高的數(shù)據(jù)鏈路傳輸效率；所有幀均采用CRC校驗(yàn)，傳輸可靠性高，目前網(wǎng)絡(luò)設(shè)計(jì)普遍使用HDLC作為數(shù)據(jù)鏈路管制協(xié)議[1]。實(shí)施HDLC的一般方法通常是采用ASIC器件和軟件編程等，但由于HDLC標(biāo)準(zhǔn)的文本較多，ASIC芯片出于專用性的目的難以通用于不同版本，缺乏應(yīng)用靈活性。例如CCITT、ANSI、ISO/IEC等都有各種版本的HDLC標(biāo)準(zhǔn)，器件生產(chǎn)商都還有各自的標(biāo)準(zhǔn)，對HDLC的CRC序列生成多項(xiàng)式等有不同的規(guī)定[2]。

本文重點(diǎn)分析了HDLC中CRC的計(jì)算原理，給出了眾多規(guī)定下的各種CRC算法及matlab仿真，明確了之間的區(qū)別和使用方法，并比較了使用硬件和軟件計(jì)算CRC的各自優(yōu)勢及應(yīng)用場景選擇。

一、HDLC幀結(jié)構(gòu)與CRC校驗(yàn)

HDLC規(guī)程主要由幀結(jié)構(gòu)、規(guī)程要素、規(guī)程類別三個(gè)部分組成[3]。HDLC的幀結(jié)構(gòu)在不同的標(biāo)準(zhǔn)下長度不一，但基本結(jié)構(gòu)相同，圖1表示出了ISO/IEC 3309標(biāo)準(zhǔn)規(guī)定的HDLC的基本幀結(jié)構(gòu)[4]。

其它的HDLC標(biāo)準(zhǔn)也有類似的幀結(jié)構(gòu)。每幀的起始和結(jié)束以\"7E\"做標(biāo)志，兩個(gè)\"7E\"之間為地址數(shù)據(jù)、控制數(shù)據(jù)、信息數(shù)據(jù)和幀校驗(yàn)序列。為了避免將數(shù)據(jù)中的\"7E\"誤為標(biāo)志，出現(xiàn)判斷幀頭錯(cuò)誤，需要在發(fā)送端和接收端需要進(jìn)行插0和減去0操作，避免連續(xù)的6個(gè)1出現(xiàn)。

在數(shù)據(jù)通訊領(lǐng)域，為了保證傳輸數(shù)據(jù)的正確性，必須采用檢錯(cuò)手段。CRC的檢錯(cuò)能力極強(qiáng)，開銷小，容易使用軟件和硬件實(shí)現(xiàn)，綜合考慮遠(yuǎn)遠(yuǎn)優(yōu)于奇偶校驗(yàn)及算術(shù)和校驗(yàn)等方式[5]。已經(jīng)廣泛的應(yīng)用在網(wǎng)絡(luò)通信、無線通信、圖像傳輸、數(shù)據(jù)轉(zhuǎn)換等很多領(lǐng)域。HDLC協(xié)議中采用了CRC16或CRC32校驗(yàn)，校驗(yàn)結(jié)果在發(fā)送端填寫在幀校驗(yàn)FCS字段中，接收端收到后傳輸幀后，計(jì)算包括幀校驗(yàn)字段在內(nèi)的CRC數(shù)值，然后和協(xié)議對應(yīng)的標(biāo)準(zhǔn)結(jié)果比較，得出是否正確傳輸?shù)慕Y(jié)論。

二、FCS的計(jì)算原理及相關(guān)算法

FCS的計(jì)算位于發(fā)射端添0前或者接收端刪0后，計(jì)算的是原始數(shù)據(jù)的CRC校驗(yàn)值。下面討論的均是針對于原始數(shù)據(jù)的計(jì)算方法。

CRC的理論基礎(chǔ)是線性編碼原理。在發(fā)送端，待發(fā)送的k位二進(jìn)制序列按約定規(guī)則對一個(gè)特定的最高次冪為r的多項(xiàng)式做不借位的除法，這個(gè)多項(xiàng)式可稱之為生成多項(xiàng)式，產(chǎn)生一個(gè)r位的校驗(yàn)碼。將此r位校驗(yàn)碼附在原始二進(jìn)制序列后發(fā)送出去；在接收端以相同的約定規(guī)則對接收數(shù)據(jù)包括校驗(yàn)碼進(jìn)行，對結(jié)果按照不同的標(biāo)準(zhǔn)進(jìn)行差錯(cuò)判斷。考慮到小于生成多項(xiàng)式長度的二進(jìn)制序列直接做多項(xiàng)式除法的結(jié)果肯定為其自身，這樣起不到校驗(yàn)的作用，所以在開始計(jì)算前首先將待發(fā)送的k位二進(jìn)制左移r位。

2.1最基本的定義算法

CRC的最基本的算法來源于本身的定義，以CCITT（現(xiàn)在的ITU）規(guī)定的CRC16算法為例，假設(shè)需要發(fā)送的數(shù)據(jù)D為“0xA1A2”，生成多項(xiàng)式G為X16+X12+X5+X1，按照定義，數(shù)據(jù)D左移16位后做不借位的除法，即異或運(yùn)算，計(jì)算過程如圖2所示：

從上面的實(shí)例可以總結(jié)出最基本的算法：被除數(shù)左移16位，當(dāng)被除數(shù)的最高位為1的時(shí)候，和生成多項(xiàng)式G逐位異或，由于G的最高位肯定是1，所以結(jié)果的首位肯定是0；當(dāng)被除數(shù)的最高位為0的時(shí)候，直接左移一位，這樣循環(huán)下來得到最后結(jié)果。

2.2比特型算法

上面的算法精簡下，即可得到比特型算法：被除數(shù)左移16位，當(dāng)最高位為1的時(shí)候，被除數(shù)左移1位后和去掉首位1的16位生成多項(xiàng)式G’做逐位異或，當(dāng)最高位為0的時(shí)候，直接左移1位，如此循環(huán)到最后。

2.3字節(jié)型算法

字節(jié)型算法的推導(dǎo)有兩種方法：概念推導(dǎo)和公式推導(dǎo)。概念的推導(dǎo)基于下面的思路：前一個(gè)字節(jié)的CRC計(jì)算結(jié)果是前一個(gè)字節(jié)×216后整除生成多項(xiàng)式后的余數(shù)（整除的商舍去，因?yàn)橛?jì)算CRC不需要商，只要余數(shù)），那么對于計(jì)算當(dāng)前字節(jié)和上一個(gè)字節(jié)整體的CRC的時(shí)候，需要把這個(gè)余數(shù)和當(dāng)前字節(jié)×216的值加在一起計(jì)算，上個(gè)字節(jié)的余數(shù)比當(dāng)前字節(jié)的權(quán)值高了8，所以需要×28，余數(shù)共16bit，可拆分為高字節(jié)和低字節(jié)，即余數(shù)等于高字節(jié)×28+低字節(jié)，加到當(dāng)前字節(jié)后，即為高字節(jié)×216+低字節(jié)×28，于是，按照CRC計(jì)算的原始定義，整體的CRC值是上個(gè)字節(jié)的CRC值高字節(jié)加上當(dāng)前字節(jié)后計(jì)算的CRC值再加上上個(gè)字節(jié)CRC值的低字節(jié)×28。

上面這句話的結(jié)論也可由公式推導(dǎo)出，和概念推導(dǎo)類似，只是使用計(jì)算式列出，更加明確些。有了這個(gè)結(jié)論，只要事先計(jì)算出字節(jié)的CRC表格（256個(gè)值），通過簡單的查表和加法，就可以得到任意長度的CRC結(jié)果。另外，還可以擴(kuò)展到半字節(jié)的算法，半字節(jié)的CRC表格（16個(gè)值）數(shù)量更少，相應(yīng)的加法變多，適合于內(nèi)存比較緊張的場合，如資源緊缺的單片機(jī)上使用。

三、CRC的MATLAB仿真

根據(jù)以上的CRC計(jì)算方法，下面給出發(fā)送端比特型和字節(jié)型的Matlab仿真程序。

3.1基本的比特型算法

wantsendtable=[’01’ ’02’]；%想要計(jì)算的序列

crcen=[’00’ ’00’]；

wantsendtable =[ wantsendtable，crcen]；%左移16位

wantsendtable=dec2bin（hex2dec （wantsendtable）， 4*length（wantsendtable））；%轉(zhuǎn)成2進(jìn)制

bitlen=length（wantsendtable）；

crc=bitxor（crc，b）；%查表的結(jié)果加上原來的CRC crc=bitand（crc，65535）； end

fprintf （’crc_16 LSB send firest value is %s＼n’，dec2hex（crc））；

運(yùn)行上面程序，打印出結(jié)果為E7DD。可以看到，和正常發(fā)送順序的CRC結(jié)果BBE7為比特反序關(guān)系。接收端的算法類似，結(jié)果為0。

變化2：CRC初值變?yōu)?xffff

計(jì)算方法和基本算法類似，只是CRC初始化不是0x0000而是0xffff，CRC的值會(huì)和初始化0x0000時(shí)不同，但是最后的接收端校驗(yàn)值依然為0。

變化3：CRC計(jì)算后取反

發(fā)送端按照基本算法計(jì)算出CRC值后逐位取反，再附在序列數(shù)據(jù)后發(fā)出，這樣在接收端仍按照基本算法驗(yàn)證，結(jié)果將會(huì)是0x1D0F，而不再是0，0x1D0F這個(gè)值是某些協(xié)議的結(jié)果正確驗(yàn)證碼[4]。

變化4：CRC計(jì)算后取反，低位先送

發(fā)送端按照先發(fā)低位的字節(jié)型算法得出CRC值后逐位取反，再附在序列數(shù)據(jù)后，整個(gè)序列按照低位先發(fā)送出，這樣在接收端按照先發(fā)低位算法驗(yàn)證，結(jié)果將會(huì)是0xF0B8，而不再是0，0xF0B8這個(gè)值也是某些協(xié)議的結(jié)果正確驗(yàn)證碼[6]。

四、應(yīng)用場合分析

HDLC協(xié)議中的CRC校驗(yàn)主要有兩種途徑來實(shí)現(xiàn)，硬件可編程邏輯器件校驗(yàn)與微處理器軟件校驗(yàn)。前者應(yīng)用在FPGA，CPLD中，利用可編程器件的配置靈活特點(diǎn)，使用硬件移位電路和異或門來實(shí)現(xiàn)，優(yōu)點(diǎn)是速度快，可靠性高，不用軟件干預(yù)；后者應(yīng)用于DSP、單片機(jī)和工控機(jī)上，特點(diǎn)是純軟件實(shí)現(xiàn)，更改方便，開發(fā)周期短。根據(jù)兩種方法的使用環(huán)境特點(diǎn)，比特性的算法更適合在可編程邏輯器件中實(shí)現(xiàn)，因?yàn)橐莆浑娐泛彤惢蜷T更適合硬件電路來流水線處理，具有更好的實(shí)時(shí)性；而對于查表的字節(jié)型算法，更適合在微處理器中實(shí)現(xiàn)，可節(jié)省更多的時(shí)間和軟件運(yùn)行周期。

五、結(jié)語

使用Matlab可對HDLC中的FCS校驗(yàn)進(jìn)行算法仿真，明確各種方法的計(jì)算過程和校驗(yàn)結(jié)果差異，更有利于工程研制中對于CRC的深刻理解和設(shè)計(jì)正確性驗(yàn)證。

參考文獻(xiàn)

[1]劉巖俊，閆海霞，魏仲慧.基于DSP和FPGA的HDLC協(xié)議通訊電路設(shè)計(jì)[J].電子測量技術(shù). 2009（6）

[2]陳晨，李志來，徐偉，金光.基于FPGA的高速同步HDLC通信控制器設(shè)計(jì)[J].電子設(shè)計(jì)工程.2010（8）175-178

[3]張德民.數(shù)據(jù)通信，P.194.北京：科學(xué)技術(shù)文獻(xiàn)出版社，1997.8

[4] ISO/IEC 3309： Information technology-Telecommunications and information exchange between systems-High-level data link control （HDLC） procedures-Frame structure， P.4. Switzerland： International Electrotechnical Commission，Jun 2002

[5]唐曉輝，楊雙，李云.一種基于FPGA的快速CRC算法及實(shí)現(xiàn)[J].桂林航天工業(yè)高等專科學(xué)校學(xué)報(bào). 2009（1）27-29

[6] Zarlink Semiconductor. MT8952B HDLC Protocol Controller， P.3-64. March 1997