李世偉，馬家慶

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

1 引言

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

2 差錯控制技術

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

(1)奇偶校驗碼

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

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

(2)循環(huán)冗余校驗碼

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

(3)漢明碼

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

3 CRC編解碼算法

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

循環(huán)冗余校驗碼（CRC碼）屬于循環(huán)碼的范疇?；谄鋰烂艿睦碚摶A以及循環(huán)的特性，循環(huán)碼在差錯控制、糾錯性能控制等方面發(fā)揮了其優(yōu)越的特性[6]。循環(huán)碼在代數(shù)中具有嚴格的理論基礎，編碼和解碼模塊相對簡單，錯誤檢測能力卻非常強。循環(huán)碼的獨特特征是其循環(huán)性，循環(huán)意味著在循環(huán)移位之后，得到的碼組仍然是循環(huán)碼中的碼組。循環(huán)碼在如今的通信系統(tǒng)中，以其良好、便利的特性，成為數(shù)據(jù)傳輸領域最重要的差錯控制技術理論。

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

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

表1 標準CRC分類

4 算法實現(xiàn)

4.1 軟件實現(xiàn)過程

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

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

圖1 查表法算法流程

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

圖2 逐位運算法流程圖

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

4.2 編解碼過程

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

圖3 CRC編碼模塊

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

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

圖4 CRC解碼模塊

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

5 仿真驗證

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

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

圖5 編碼解碼模塊連接圖

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

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

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

圖7 輸入0x89仿真結果圖

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

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

6 結束語

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