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

李世偉，馬家慶

（貴州大學(xué)電氣工程學(xué)院，貴陽(yáng)550025）

1 引言

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

2 差錯(cuò)控制技術(shù)

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

(1)奇偶校驗(yàn)碼

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

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

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

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

(3)漢明碼

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

3 CRC編解碼算法

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

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

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

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

表1 標(biāo)準(zhǔn)CRC分類

4 算法實(shí)現(xiàn)

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

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

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

圖1 查表法算法流程

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

圖2 逐位運(yùn)算法流程圖

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

4.2 編解碼過程

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

圖3 CRC編碼模塊

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

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

圖4 CRC解碼模塊

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

5 仿真驗(yàn)證

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

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

圖5 編碼解碼模塊連接圖

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

圖6 輸入0x55時(shí)的仿真結(jié)果

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

圖7 輸入0x89仿真結(jié)果圖

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

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

6 結(jié)束語(yǔ)

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