基于MATLAB的HDLC協議CRC算法仿真

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

【關鍵詞】HDLC，MatlabCRC算法仿真

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

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

本文重點分析了HDLC中CRC的計算原理，給出了眾多規定下的各種CRC算法及matlab仿真，明確了之間的區別和使用方法，并比較了使用硬件和軟件計算CRC的各自優勢及應用場景選擇。

一、HDLC幀結構與CRC校驗

HDLC規程主要由幀結構、規程要素、規程類別三個部分組成[3]。HDLC的幀結構在不同的標準下長度不一，但基本結構相同，圖1表示出了ISO/IEC 3309標準規定的HDLC的基本幀結構[4]。

其它的HDLC標準也有類似的幀結構。每幀的起始和結束以\"7E\"做標志，兩個\"7E\"之間為地址數據、控制數據、信息數據和幀校驗序列。為了避免將數據中的\"7E\"誤為標志，出現判斷幀頭錯誤，需要在發送端和接收端需要進行插0和減去0操作，避免連續的6個1出現。

在數據通訊領域，為了保證傳輸數據的正確性，必須采用檢錯手段。CRC的檢錯能力極強，開銷小，容易使用軟件和硬件實現，綜合考慮遠遠優于奇偶校驗及算術和校驗等方式[5]。已經廣泛的應用在網絡通信、無線通信、圖像傳輸、數據轉換等很多領域。HDLC協議中采用了CRC16或CRC32校驗，校驗結果在發送端填寫在幀校驗FCS字段中，接收端收到后傳輸幀后，計算包括幀校驗字段在內的CRC數值，然后和協議對應的標準結果比較，得出是否正確傳輸的結論。

二、FCS的計算原理及相關算法

FCS的計算位于發射端添0前或者接收端刪0后，計算的是原始數據的CRC校驗值。下面討論的均是針對于原始數據的計算方法。

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

2.1最基本的定義算法

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

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

2.2比特型算法

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

2.3字節型算法

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

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

三、CRC的MATLAB仿真

根據以上的CRC計算方法，下面給出發送端比特型和字節型的Matlab仿真程序。

3.1基本的比特型算法

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

crcen=[’00’ ’00’]；

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

wantsendtable=dec2bin（hex2dec （wantsendtable）， 4*length（wantsendtable））；%轉成2進制

bitlen=length（wantsendtable）；

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

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

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

變化2：CRC初值變為0xffff

計算方法和基本算法類似，只是CRC初始化不是0x0000而是0xffff，CRC的值會和初始化0x0000時不同，但是最后的接收端校驗值依然為0。

變化3：CRC計算后取反

發送端按照基本算法計算出CRC值后逐位取反，再附在序列數據后發出，這樣在接收端仍按照基本算法驗證，結果將會是0x1D0F，而不再是0，0x1D0F這個值是某些協議的結果正確驗證碼[4]。

變化4：CRC計算后取反，低位先送

發送端按照先發低位的字節型算法得出CRC值后逐位取反，再附在序列數據后，整個序列按照低位先發送出，這樣在接收端按照先發低位算法驗證，結果將會是0xF0B8，而不再是0，0xF0B8這個值也是某些協議的結果正確驗證碼[6]。

四、應用場合分析

HDLC協議中的CRC校驗主要有兩種途徑來實現，硬件可編程邏輯器件校驗與微處理器軟件校驗。前者應用在FPGA，CPLD中，利用可編程器件的配置靈活特點，使用硬件移位電路和異或門來實現，優點是速度快，可靠性高，不用軟件干預；后者應用于DSP、單片機和工控機上，特點是純軟件實現，更改方便，開發周期短。根據兩種方法的使用環境特點，比特性的算法更適合在可編程邏輯器件中實現，因為移位電路和異或門更適合硬件電路來流水線處理，具有更好的實時性；而對于查表的字節型算法，更適合在微處理器中實現，可節省更多的時間和軟件運行周期。

五、結語

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

參考文獻

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

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

[3]張德民.數據通信，P.194.北京：科學技術文獻出版社，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算法及實現[J].桂林航天工業高等專科學校學報. 2009（1）27-29

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