基于并行流水線技術的RS255/RS233譯碼器設計

RS糾錯編碼是目前最有效、應用最廣泛的差錯控制編碼之一，是一種糾錯能力很強的多進制BCH碼，也是一類典型的代數幾何碼。它是由里德(Reed)和索洛蒙(Solomon)應用MS多項式于1960年首先構造出來的。

RS碼被廣泛用于差錯控制系統中，以提高數據的可靠性，而且可以用來構造其他碼類，如級聯碼。在無線通信、衛星通信、磁或光存儲以及網絡通信中RS碼也有較為廣泛的應用。RS碼不僅具有良好的隨機糾錯和突發糾錯能力，而且有低復雜度的編譯碼算法，因此被國際電信聯盟(ITU)推薦為光纖子系統的前向糾錯(FEC)碼。RS(225，223)碼被CCSDS選為常規分包遙測信道糾錯編碼和高級在軌系統前向和反向鏈路的糾錯編碼，是實現CCSDS標準低差錯率信道糾錯編碼的關鍵部件。只要每個碼字(255個符號)中出現的錯誤不超過16個符號，它就能將其糾正。

近年來，關于RS(255，223)碼譯碼器實現的算法得到了廣泛的關注，但是這些算法的實現速度都不太快，即便有速度稍高的，其占用硬件資源也較多，而一些占用硬件資源較少的算法速度卻很慢。本文采用基于ME算法的8倍并行設計方案，結合流水線技術，克服了上述算法的缺陷，利用盡可能少的硬件資源獲得了極高的譯碼速度。

1 RS(255，223)碼及其譯碼原理

1.1 RS(255，223)碼

因其碼元取自GF(q)，RS編解碼過程中的所有運算都是在GF(q)的有限域上面進行。RS(n，k)碼的編碼過程是將k個輸入信息碼字，用生成多項式產生(n，k)個冗余的糾錯信息碼字，與原碼字合成形成n個信息碼字進行傳輸。譯碼是在接收端，對接收的n個碼字信息進行糾錯處理，恢復k個信息碼字。對于1個長度為am-1符號的RS碼，每個碼字都可以看成是有限域GF(am)中的1個元素。最小碼距為d的碼字，其RS碼生成多項式具有如下形式：

其中ai是GF(am)中的1個元素。

對于RS(255，223)碼而言，q=256，a=2，碼字符號在GF(28)中。m=8，是每個RS符號的碼元數；n=28-1，是每個RS碼字的符號數；k=223，是RS碼中信息位的符號數；t=16，是RS碼字內符號的糾錯能力；d=33，是最小碼距。

1.2 RS(255，223)碼譯碼原理

由于RS碼為分組碼，故其譯碼算法主要由伴隨式計算、關鍵方程求解和錢搜索和Forney算法3部分構成，譯碼器結構如圖1所示。

首先，根據接收碼字乘以校驗矩陣得到其伴隨多項式，對于RS(225，223)碼，其伴隨式求解式可以表示為：

求得伴隨式以后，則利用伴隨多項式求解關鍵方程：錯誤位置多項式σ(x)和錯誤特征多項式ω(x)，如下所示：

求解關鍵方程現可采用的算法主要有BM(Belekamp-Messey)算法和ME(Modified Euclidean)算法。之后便得到錯誤位置多項式σ(x)與錯誤特征多項式ω(x)。

此后，由錯誤位置多項式與錯誤特征多項式來求得錯誤位置與錯誤值。求解錯誤位置本設計采用窮舉算法——錢搜索算法來完成。同時，使用Forney公式求得錯誤值。最后，用延時后的接收值減去錯誤值，得到最后的譯碼輸出。Forney公式可以表示為：

其中，ei代表發生在i位置上的錯誤值，σodd(x)代表錯誤位置多項式奇數次項之和。

2并行流水結構方案

本設計采用8倍并行流水方案。將255個碼元8倍并行后，只需要32個周期便完成所有32個伴隨多項式系數的求解。然后將32個伴隨多項式系數順序輸出到下一級，在此基礎上采用流水線結構，周期剛好滿足且不會浪費資源。本設計中所有乘法器都是采用GF(28)有限域乘法器。

2.1 伴隨式計算

8倍并行伴隨多項式的求解算法，是在迭代算法的基礎上展開實現，其推導過程如下：

式(6)中，R255=0；i=1，2，…，2t-1，2t。其電路結構如圖2所示。


2.2 關鍵方程求解

本設計中關鍵方程的求解采用ME算法。BM算法具有反饋結構，不適合使用流水結構，而ME算法可采用流水結構。其算法描述如下：

其中，S(x)為輸入的伴隨多項式。

ME算法為1種迭代算法，目的在于求i階余式Ri(x)，相應的多項式ri(x)與Li(x)滿足：

ri(x)A(x)+Li(x)S(x)=Ri(x)(8)

當i階余式Ri(x)的階數小于t時，迭代算法結束。算法結束時的Ri(x)即為錯誤特征多項式ω(x)，而Li(x) 即為所求的錯誤位置多項式δ(x)。

ME算法在每一次迭代時進行的運算為：

具體推導請見參考文獻[8-9]。

單級迭代電路結構如圖3所示。

由ME算法推導可知，使用脈動電路結構實現ME算法時，至多使用2級迭代電路即可降低R(x)多項式階數1階。因此，脈動電路結構采用32階流水結構電路即可保證迭代算法完成收斂得到最后結果。電路結構如圖4所示。

2.3 錢搜索和Forney算法

錢搜索模塊接收KES模塊的錯誤位置多項式信號δ(x)，利用錢搜索算法逐個檢查符號位是否發生錯誤，輸出錯誤位置和錯誤位置多項式的奇數項之和，供EE模塊計算錯誤圖案和糾錯。

設錯誤位置多項式δ(x)可以表達為奇數項和偶數項之和：

并行錢搜索電路子結構如圖5所示。圖中m表示并行模塊編號數，m=1，2，…，8。所有的乘法器均是常數乘法器，8倍并行結構由圖5所示的8個同樣的結構組成。

EE(錯誤值計算)模塊根據CS模塊輸出的δodd(x)以及KES模塊輸出的ω(x)計算出錯誤圖案。

EE模塊需要求解w(ai)，電路結構推導過程和求解δ(ai)的過程一樣，電路結構也基本相同，這里不再累述。

3 仿真驗證與綜合

上述譯碼器采用自頂向下的設計流程劃分模塊，用Verilog HDL完成RTL代碼的編寫，然后在Mentor公司的ModelSim SE 6.1b仿真驗證工具下編寫測試代碼進行仿真驗證。仿真結果如圖6所示，譯碼器能正確實現譯碼功能。

因本譯碼器可糾正16個錯誤，超過16個錯誤便不可糾正，在仿真時譯碼輸入樣本采用了2種：一種樣本不超過16個錯誤，另一種樣本超過16個錯誤。仿真結果表明，此譯碼器能在不超過16個錯誤的樣本下正常譯碼。

譯碼器在Quartus II 8.0上進行綜合和優化，采用Altera公司Cyclone系列的EP2C15AF256C8芯片為目標器件。譯碼器的工作時鐘頻率可達85 MHz，數據吞吐率可達5 440 Mb／s，占用邏輯單元數為13 947個(片內共14 448，占用率為97％)，RAM占用16 698位(片內共239 616位，占用率為7％)。譯碼器性能對比如表1所列。

與參考文獻[4]相比，由于本譯碼器采用了并行結構在增加了不到3倍的硬件資源的情況下，吞吐率時鐘比(吞吐率／時鐘)提高了8倍，而且縮短了3／4的澤碼延遲。與參考文獻[5]相比，本文所采用的譯碼器增加了不到3倍的硬件資源，提高了8倍的吞吐率時鐘比。由于參考文獻[5]采用串行譯碼結構，本文所采用的并行流水譯碼結構較串行譯碼結構縮減了19／20的譯碼延遲。