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

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

本設計即是采用Altera公司的CYCLONEII芯片EP2C35-672 FPGA，依靠Nios II軟核和硬件邏輯結合的速度優勢，實現基于Nios II的HDLC協議控制系統中CRC循環冗余校驗的自定義指令實現。

1 循環冗余校驗CRC

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

圖1 加入CRC校驗的碼序列

CRC校驗的編碼原理：

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

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

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

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

常見的生成多項式有：

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

2 CRC校驗的自定義指令實現

2.1 自定義指令

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

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

2.2 CRC算法研究

（1） 串行實現法

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

圖3 CRC串行算法原理圖

（2） 并行計算法

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

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

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

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

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

并行計算法的具體原理推導如下：

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

，即得到了這組數據最終的CRC運算結果。

2.3 CRC算法的VHDL實現

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

圖4為CRC并行計算法的仿真結果。

圖4 CRC并行算法仿真結果

2.4 使用Nios II的自定義指令提高系統性能

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

定制指令邏輯和Nios II的連接在SOPC Builder 中完成。Nios II CPU配置向導提供了一個可添加256條定制指令的圖形用戶界面，在該界面中導入設計文件，設置定制指令名，并分配定制指令所需的CPU時鐘周期數目。系統生成時，Nios II IDE為每條用戶指令產生一個在系統頭文件中定義的宏，可以在C（或C++）應用程序代碼中直接調用這個宏。表1為 Nios II軟件實現CRC算法和自定義指令實現性能對比。

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

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

3 結語

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

責任編輯：gt