基于FPGA的CRC編解碼算法研究

李世偉，馬家慶

（貴州大學電氣工程學院，貴陽550025）

1 引言

當今社會手機、計算機普及程度高，極大提高了人們的生活水平。在通信過程中，人們需要各種信息在傳輸過程中不會發生錯誤，盡量避免受到干擾，保證高質量的傳輸。然而在實際應用中，由于數據傳輸使到的無線信道的復雜性，包括信道的時變、衰減等特性，以及有限的帶寬資源，信號在傳輸過程中會受到信道環境噪聲的干擾。除此之外，信道在傳輸數據過程中由于信道特性衰落，會導致傳輸效率降低。上述兩種因素是導致接收端出現誤碼的主要原因[1]。如果傳輸的信息是圖片，誤碼會嚴重降低圖片的像素，使圖片變得模糊；而如果是各種數據文件，誤碼可能就會造成文件出現亂碼，甚至全部作廢。為解決此類問題，差錯控制應用而生，它是指對傳輸數據進行編碼,在數據傳輸過程中檢測出誤碼的位置，對最終傳輸性的數據在編碼后進行正確性判斷，從而將差錯控制在可接受的范圍內[2]。

2 差錯控制技術

在通信系統數據傳輸中，常用的差錯控制技術包括奇偶校驗碼和循環冗余校驗碼技術，均屬于檢錯碼的范疇；另一種是利用糾錯碼原理，對應的差錯控制技術主要是漢明碼。簡介如下：

(1)奇偶校驗碼

奇偶校驗碼是檢錯碼的一種，如其名，奇偶校驗碼包括奇校驗和偶校驗技術，其中，在增加冗余位后，根據數據二進制碼字中“1”的數量是奇數還是偶數，相應地分別稱之為奇校驗和偶校驗。其中奇校驗被規定應用于同步傳輸中，而偶校驗被規定應用于異步傳輸過程中。

在通信系統中，奇偶校驗碼所應用的數據單位是“位”，數據以二進制傳輸。在增加冗余位后，判斷“1”的數量是偶數還是奇數，將附加冗余位的數據進行傳輸，傳輸完成后，判斷接收端接收的數據中，“1”數量是奇數個還是偶數個，對比是否與數據輸入的奇偶數相同，以此判斷傳輸過程是否發成了碼字錯誤。奇偶校驗碼的校驗能力較低，不適用于塊數據的傳輸，改良方案為垂直水平奇偶校驗碼（也稱為縱橫奇偶校驗或方陣碼）。由于增加了縱向的校驗，明顯提高了奇偶校驗碼的檢錯能力，使能夠檢測出所有3位以及3位以下的錯誤，較好地降低數據的誤碼率[3]。

(2)循環冗余校驗碼

循環冗余校驗（Cyclic Redundancy Check,CRC）是在計算機網絡通信傳輸過程被使用最多的檢錯控制技術。其基本思想是在數據后面附加上若干位與數據相關的冗余碼，起到多數據進行“加密傳輸”的作用。根據不同的CRC標準，所附加的冗余碼的位數不同。總體而言，循環冗余校驗技術的檢錯能力很強[4]。

(3)漢明碼

漢明碼是基于糾錯碼的差錯控制技術，它在1950年被提出。其指導思想是：在被校驗的數據中增加幾位校驗位。當某一數據位出錯時，引起幾位校驗位的值的改變，不同代碼出錯，得到不同的校驗結果（即非法編碼）。這樣，不僅可發現錯誤,而且還能確定錯誤的位置，達到糾正錯誤的目的。

3 CRC編解碼算法

上述三種差錯控制技術中，奇偶校驗碼的校驗能力較低，對數據傳輸正確性的提升不大；漢明碼能夠很好保證數據在傳輸過程中的正確性，但檢驗過程繁瑣，編解碼麻煩，并不適用于一般的通信系統中。只有循環冗余校驗碼技術，因其碼字標準多樣，可針對不同位數的傳輸采用不同標準，同時，所用的編解碼理論也比較簡單，故在實際通信系統中得到了廣泛的應用[5]。

循環冗余校驗碼（CRC碼）屬于循環碼的范疇。基于其嚴密的理論基礎以及循環的特性，循環碼在差錯控制、糾錯性能控制等方面發揮了其優越的特性[6]。循環碼在代數中具有嚴格的理論基礎，編碼和解碼模塊相對簡單，錯誤檢測能力卻非常強。循環碼的獨特特征是其循環性，循環意味著在循環移位之后，得到的碼組仍然是循環碼中的碼組。循環碼在如今的通信系統中，以其良好、便利的特性，成為數據傳輸領域最重要的差錯控制技術理論。

目前CRC的分類包括非標準CRC和標準CRC。標準CRC是被國際標準化組織規定的標準生成多項式標準；非標準CRC是用戶根據自己的需求設定的生成多項式[7]。非標準的CRC碼的運算原理大致與標準CRC碼相同，只是為了滿足不同用途而采用不同于標準的CRC生成多項式，這種非標準的CRC由于只針對特定的需求，故有低成本的優點，在保證數據準確性的前提下，又能合理的減輕計算機的數據處理壓力，因此也得到了廣泛的應用。

標準CRC的各種不同分類表達式描述如表1。以CRC-16為例，它是由兩段字節組成，在多項式開始生成時，CRC寄存器中各位都預置為1，再和8位數據異或。異或后將寄存器中數據從高到低移位處理，最高位數據補0。最低位數值若為1，則把寄存器與預存多項式二進制碼異或；若不為0，則無需異或。重復上述步驟，做8次移位，第一個8位數據處理完成，之后用CRC寄存器的值與下一個8位數據異或并移位，最終即得到所需要的CRC值[8]。

表1 標準CRC分類

4 算法實現

4.1 軟件實現過程

實現CRC算法的方法包括硬件和軟件實現，但由于硬件實現產生的電路結構復雜，使得系統的集成度降低，設計成本較高，故不常采用。而軟件實現，相對于硬件來說，提高了集成度，在提高通信效率的同時，有效降低了設計的成本，是常見的實現CRC算法的方法[9]。用來實現CRC檢驗算法的方法有查表法和逐位運算法。

查表法實現CRC校驗的流程圖如圖1所示。此方法需要提前將輸入的數據序列計算好對應的CRC值，存放在儲存器中。程序運行時，根據輸入數值的不同，通過查詢儲存器中對應的數值，以對應輸出輸入數據的CRC碼。采用查表法可以明顯提升對CRC碼計算的速度，但是需要大量的儲存器對數據進行儲存，若輸出的數據序列沒有提前計算、放入儲存器中，則得不到相應的結果[10]。

圖1 查表法算法流程

逐位運算法實現CRC校驗的流程如圖2所示。此法先對二進制數據序列的最高位進行判斷，判斷后將數據左移一位，以此逐位運算，最終將反饋的數據作為結果輸出。

圖2 逐位運算法流程圖

通過對比，逐位運算法相對于查表法來說，運行速度更快，且不需要那么多的存儲器，故在實驗中選用逐位運算法來實現CRC算法。

4.2 編解碼過程

編碼模塊如圖3所示。編碼模塊操作的對象是系統輸入的8位二進制數據。由于采用的是CRC-16的生成多項式的標準，故利用模2除的運算可以計算出該8位數據特有的16位CRC校驗碼，并附在8位數據之后，對數據起到“加密傳輸”的作用，同時，也將次24位CRC碼傳輸給解碼模塊，對其進行解碼與正確性判斷。

圖3 CRC編碼模塊

編碼模塊是系統的關鍵部分，對輸入數據生成對應的校驗碼，用組合而成的CRC碼數據來做CRC校驗的輸入。其中，clk是時鐘信號，data_in是8位的輸入數據，coded_done是編碼完成的標志信號，crc_out是8位輸入數據經過模2運算得到的獨有的16位校驗碼，data_out是需要傳輸給解碼模塊的24位CRC碼。

解碼模塊的工作過程和編碼模塊完全相反，如圖4所示。它需要將編碼模塊生成的24位CRC碼進行解碼。解碼過程中，24位的CRC對CRC-16的生成多項式進行模2除法運算，看是否能夠整除，或者最終除式的余數是否為0。如能整除或者余數為0，對余數是否為0做出判斷；余數為0，則整個CRC編解碼過程沒有發生錯誤，除式得出的商數與輸入的8位數據相同，數據無差錯傳輸完成。

圖4 CRC解碼模塊

圖中，clk是系統所需的時鐘；rst_n是復位信號輸入；error是判斷信號，對24位CRC碼解碼后的數據正確性做出判斷；decoded_data是解碼所得到的需要系統傳輸的8位初始數據。

5 仿真驗證

為驗證上述CRC編碼和解碼功能，按如圖5所示的方式連接兩模塊。

實驗程序在QuartusII 13.0中編寫，經編譯、分析、綜合后，生成對應的RTL電路圖，打開Modelsim查看仿真結果。

圖5 編碼解碼模塊連接圖

在程序中修改輸入數據0x55，即二進制序列01010101。此時輸出數據為01fe，對應二進制序列0000000111111110。仿真結果如圖6所示。

圖6 輸入0x55時的仿真結果

解碼過程與編碼過程完全相反，在解碼器模塊中，將編碼所得的CRC值解碼后與輸入數據0x55作對比。如果兩個數據相同，則error輸出為0，說明整個編解碼過程正確；如果兩個數據不同，error輸出為1，表明整個編解碼過程發生了錯誤，有誤碼產生。更改輸入數據為0x89，重新對程序進行編譯，并打開M odelsim查看。仿真結果如圖7。

圖7 輸入0x89仿真結果圖

從圖中可以看出error的輸出數據為0，表明結果正確，輸出即是經過編碼后的8位輸入數據。crc out處輸出的值（校驗碼）為0x8335，data out處對應的CRC值為0x898335，判斷輸出error輸出為0。

為確保編解碼器設計的正確性，重復進行多次數據驗證。經過驗證，結果均為正確，證明此編解碼器設計的正確性。

6 結束語

基于對循環冗余校驗碼(CRC)編解碼器基本理論和方法的介紹，借助于FPGA，編寫VerilogHDL代碼實現了CRC算法過程。經過仿真實驗驗證正確無誤，方案正確。本設計的優點是速度快，靈活性好，通過改變代碼，可作為不同輸入數據的CRC編解碼器使用。