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

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

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

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

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

圖1 加入CRC校驗的碼序列

CRC校驗的編碼原理：

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

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

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

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

常見的生成多項式有：

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

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

2.1 自定義指令

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

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

2.2 CRC算法研究

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

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

圖3 CRC串行算法原理圖

（2） 并行計算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語

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

責(zé)任編輯：gt