通信系統(tǒng)中，為確保數(shù)據(jù)傳輸和存儲(chǔ)的可靠性，引入了信道編碼。一是可使得編碼后的碼流頻譜適應(yīng)信道頻率特性，二是可檢測(cè)并糾正傳輸中的誤碼。前者屬于譜成形技術(shù)，后者屬于差錯(cuò)控制技術(shù)。循環(huán)冗余校驗(yàn)（CRC）屬于后者，它是通過(guò)增加冗余信息，達(dá)到發(fā)現(xiàn)誤碼的目的。CRC校驗(yàn)由于檢錯(cuò)能力強(qiáng)，被廣泛用于各種數(shù)據(jù)校驗(yàn)中。

可編程片上系統(tǒng)（SOPC）是一種特殊的嵌入式系統(tǒng)，它可將處理器、存儲(chǔ)器、外設(shè)接口和多層次用戶(hù)電路等系統(tǒng)設(shè)計(jì)需要的功能模塊集成到一塊芯片上。Nios II是Altera公司的SOPC解決方案，是一個(gè)運(yùn)行在FPGA上的32位RSIC處理器。Nios II系列軟核處理器最大的特點(diǎn)之一是可靈活地增加用戶(hù)指令，可以把系統(tǒng)中用軟件處理耗時(shí)多的關(guān)鍵算法用硬件邏輯電路來(lái)實(shí)現(xiàn)，大大提高系統(tǒng)的效率。

本設(shè)計(jì)即是采用Altera公司的CYCLONEII芯片EP2C35-672 FPGA，依靠Nios II軟核和硬件邏輯結(jié)合的速度優(yōu)勢(shì)，實(shí)現(xiàn)基于Nios II的HDLC協(xié)議控制系統(tǒng)中CRC循環(huán)冗余校驗(yàn)的自定義指令實(shí)現(xiàn)。

1 循環(huán)冗余校驗(yàn)CRC

循環(huán)冗余校驗(yàn)碼檢錯(cuò)能力強(qiáng)。校驗(yàn)的基本思想是利用線(xiàn)性編碼理論，在發(fā)送端根據(jù)傳送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生（n-k）位校驗(yàn)監(jiān)督碼，并附在信息碼后，構(gòu)成一個(gè)n位的二進(jìn)制碼序列來(lái)發(fā)送，如圖1。接收端則對(duì)收到的信息采用和發(fā)端相同的算法進(jìn)行校驗(yàn)，若有錯(cuò)，發(fā)端重新發(fā)送數(shù)據(jù) 。

圖1 加入CRC校驗(yàn)的碼序列

CRC校驗(yàn)的編碼原理：

（1） 首先將待發(fā)送數(shù)據(jù)序列D（x） 乘以Xk ，其中k 為生成多項(xiàng)式G （x） 的最高次冪；

（2） 將乘得的結(jié)果Xk?D （x） 用生成多項(xiàng)式G （x） 去除；

（3） 忽略其商，僅將其余數(shù)R （x） 取出，并與Xk ?D（x） 相加，形成n位輸出碼數(shù)據(jù)序列D′（x）， 即：D′（x） = Xk?D （x） + R （x）；

最終得到的余式R（x）即為CRC校驗(yàn)碼。它跟在信息碼后一并發(fā)往信道。

常見(jiàn)的生成多項(xiàng)式有：

對(duì)不同的類(lèi)型，CRC的檢錯(cuò)能力是有差異的。冗余位越多，檢錯(cuò)能力越強(qiáng)，但實(shí)現(xiàn)起來(lái)就會(huì)相對(duì)復(fù)雜，并且占用的開(kāi)銷(xiāo)也會(huì)增大。實(shí)際中，總是基于產(chǎn)品的應(yīng)用領(lǐng)域綜合考慮來(lái)做出最合適的選擇。

2 CRC校驗(yàn)的自定義指令實(shí)現(xiàn)

2.1 自定義指令

自定義指令就是用戶(hù)讓Nios II軟核完成的功能，功能由電路模塊來(lái)實(shí)現(xiàn)，電路模塊用硬件描述語(yǔ)言（HDL）描述，連接到Nios II軟核的算術(shù)邏輯部件上，如圖2。這樣，用戶(hù)指令就可以把系統(tǒng)中用軟件處理耗時(shí)多的關(guān)鍵算法用硬件邏輯電路來(lái)實(shí)現(xiàn)。Nios II處理器支持256個(gè)具有固定或可變時(shí)鐘周期操作的定制指令，允許設(shè)計(jì)人員利用擴(kuò)展CPU 指令集，通過(guò)提升那些對(duì)時(shí)間敏感的應(yīng)用軟件的運(yùn)行速度，來(lái)提高系統(tǒng)性能。

圖2 定制指令邏輯連接到Nios II的ALU

2.2 CRC算法研究

（1） 串行實(shí)現(xiàn)法

串行算法實(shí)現(xiàn)原理比較簡(jiǎn)單，如圖3。只需要移位寄存器和異或門(mén)這些基本的邏輯器件，所以很適合硬件電路。但是串行法一個(gè)時(shí)鐘周期只能計(jì)算一位數(shù)據(jù)，只適用于數(shù)據(jù)串行傳輸?shù)膱?chǎng)合，接入并行處理的CPU時(shí)會(huì)大大降低效率。

圖3 CRC串行算法原理圖

（2） 并行計(jì)算法

并行算法可以在一個(gè)時(shí)鐘內(nèi)對(duì)多位數(shù)據(jù)進(jìn)行編碼，提高計(jì)算速度。信息碼一次并行輸入，經(jīng)過(guò)必要的處理時(shí)間即可輸出編碼結(jié)果，大大縮短了處理時(shí)間，具有很大的優(yōu)越性。目前采用的CRC并行算法有查表法等，這些方法有一定的優(yōu)勢(shì)，但也有缺點(diǎn)。本設(shè)計(jì)所采取的是并行計(jì)算法，不僅保持了并行算法的優(yōu)勢(shì)，而且還克服了查表法的缺點(diǎn)。

◆ 與查表法比較，這種方法消除了查表法所必須的CRC余數(shù)表，減少了資源占用，降低了成本。不再需要存放余數(shù)表的高速存儲(chǔ)器，減少了時(shí)延，提高了計(jì)算速度。

◆ 可以全部用FPGA的內(nèi)部資源實(shí)現(xiàn)，總的輸出時(shí)延為兩級(jí)異或門(mén)時(shí)延和寄存器的鎖存時(shí)延之和，約為5-10ns，而查表法的總時(shí)延達(dá)到了100ns，因此計(jì)算法可以用于處理時(shí)鐘速率很高的場(chǎng)合。

◆ 查表法的并行度局限于8位。而計(jì)算法可以靈活地實(shí)現(xiàn)各種并行度的CRC計(jì)算。由于可以采用更大的并行度（如32位并行計(jì)算，甚至64位的并行計(jì)算），因此降低了處理時(shí)鐘周期，并且與CPU的接入也更加方便。

總之，這種并行實(shí)現(xiàn)方式適用于各種數(shù)據(jù)寬度CRC 校驗(yàn)，而且隨著并行輸入數(shù)據(jù)寬度的加寬，運(yùn)算速度也加快。它的缺點(diǎn)：由于并行計(jì)算是通過(guò)多級(jí)反饋實(shí)現(xiàn)的，故復(fù)雜的反饋組合電路會(huì)帶來(lái)較大的門(mén)延遲，但QuartusII開(kāi)發(fā)環(huán)境通過(guò)優(yōu)化組合電路的結(jié)構(gòu)，可以很大程度上降低延遲，使電路適用于較高的時(shí)鐘頻率。

并行計(jì)算法的具體原理推導(dǎo)如下：

設(shè)為第i個(gè)數(shù)據(jù)移位j次后寄存器的最終狀態(tài)，為第i個(gè)數(shù)據(jù)移位j次后寄存器的狀態(tài)，為輸入數(shù)據(jù)的第j個(gè)數(shù)據(jù)，為生成多項(xiàng)式的第i位數(shù)值，j的取值范圍由一次可校驗(yàn)的總數(shù)據(jù)位數(shù)決定，k為生成多項(xiàng)式的最高次冪，這里，j = 0、1、2 …… 32，k為16。其遞推公式為：并且令；按照遞推公式對(duì)移位寄存器的每一位進(jìn)行計(jì)算，直到j(luò)=0，此次計(jì)算才結(jié)束，所有值都計(jì)算完畢后，得到中間結(jié)果：，其中為0或1；由于輸入數(shù)據(jù)的高低位與寄存器高低位相反，因此需再進(jìn)行一次倒排序才可得到正確的輸出數(shù)據(jù)：

，即得到了這組數(shù)據(jù)最終的CRC運(yùn)算結(jié)果。

2.3 CRC算法的VHDL實(shí)現(xiàn)

據(jù)上述原理推算了32位并行數(shù)據(jù)CRC異或邏輯關(guān)系，并用VHDL實(shí)現(xiàn)了并行CRC算法，添加到Nios II配置表中形成自定義指令，在C程序中通過(guò)函數(shù)調(diào)用就能以很高的速率完成復(fù)雜的CRC運(yùn)算，極大地提高了系統(tǒng)的效率。

圖4為CRC并行計(jì)算法的仿真結(jié)果。

圖4 CRC并行算法仿真結(jié)果

2.4 使用Nios II的自定義指令提高系統(tǒng)性能

CRC校驗(yàn)算法需要大量的邏輯運(yùn)算，如果用軟件實(shí)現(xiàn)要占很多個(gè)時(shí)鐘周期，系統(tǒng)的效率降低，而用硬件完成則僅需幾個(gè)時(shí)鐘周期。

定制指令邏輯和Nios II的連接在SOPC Builder 中完成。Nios II CPU配置向?qū)峁┝艘粋€(gè)可添加256條定制指令的圖形用戶(hù)界面，在該界面中導(dǎo)入設(shè)計(jì)文件，設(shè)置定制指令名，并分配定制指令所需的CPU時(shí)鐘周期數(shù)目。系統(tǒng)生成時(shí)，Nios II IDE為每條用戶(hù)指令產(chǎn)生一個(gè)在系統(tǒng)頭文件中定義的宏，可以在C（或C++）應(yīng)用程序代碼中直接調(diào)用這個(gè)宏。表1為 Nios II軟件實(shí)現(xiàn)CRC算法和自定義指令實(shí)現(xiàn)性能對(duì)比。

表1 Nios II軟件實(shí)現(xiàn)CRC算法和自定義指令實(shí)現(xiàn)性能對(duì)比

可見(jiàn)，對(duì)于2字節(jié)數(shù)據(jù)，自定義指令的運(yùn)算速度是軟件法的2～10倍，且使用的資源大大降低。表1中的自定義指令是對(duì)16位數(shù)據(jù)而言的。我們所采用的幀結(jié)構(gòu)，數(shù)據(jù)段有2字節(jié)，控制段1字節(jié)，地址段1字節(jié)，因此CRC計(jì)算時(shí)采用32位。從仿真圖4中可以看到，從輸入數(shù)據(jù)到計(jì)算完成用了7～8ns，而工作頻率50MHz的Nios II系統(tǒng)一個(gè)時(shí)鐘周期為20ns。這樣，完全可以在一個(gè)周期內(nèi)完成計(jì)算，加上裝載及返回時(shí)所需的額外周期，根據(jù)表1的數(shù)據(jù)進(jìn)行近似的線(xiàn)性分析，可知最終一次CRC校驗(yàn)需要16～20個(gè)周期，比軟件法提高了4～40倍，大大提高了系統(tǒng)處理的速度。

3 結(jié)語(yǔ)

CRC校驗(yàn)由于檢錯(cuò)能力強(qiáng)，被廣泛應(yīng)用在各種數(shù)據(jù)校驗(yàn)中。本文研究了CRC并行算法，并且通過(guò)增加自定義指令的方法，把用軟件處理耗時(shí)多的CRC校驗(yàn)算法在Nios II系統(tǒng)中用硬件邏輯電路來(lái)實(shí)現(xiàn)，極大提高了系統(tǒng)的效率。實(shí)驗(yàn)結(jié)果也表明了該方法的優(yōu)勢(shì)。

責(zé)任編輯：gt