基于并行流水線技術(shù)的RS255/RS233譯碼器設(shè)計(jì)

RS糾錯(cuò)編碼是目前最有效、應(yīng)用最廣泛的差錯(cuò)控制編碼之一，是一種糾錯(cuò)能力很強(qiáng)的多進(jìn)制BCH碼，也是一類典型的代數(shù)幾何碼。它是由里德(Reed)和索洛蒙(Solomon)應(yīng)用MS多項(xiàng)式于1960年首先構(gòu)造出來(lái)的。

RS碼被廣泛用于差錯(cuò)控制系統(tǒng)中，以提高數(shù)據(jù)的可靠性，而且可以用來(lái)構(gòu)造其他碼類，如級(jí)聯(lián)碼。在無(wú)線通信、衛(wèi)星通信、磁或光存儲(chǔ)以及網(wǎng)絡(luò)通信中RS碼也有較為廣泛的應(yīng)用。RS碼不僅具有良好的隨機(jī)糾錯(cuò)和突發(fā)糾錯(cuò)能力，而且有低復(fù)雜度的編譯碼算法，因此被國(guó)際電信聯(lián)盟(ITU)推薦為光纖子系統(tǒng)的前向糾錯(cuò)(FEC)碼。RS(225，223)碼被CCSDS選為常規(guī)分包遙測(cè)信道糾錯(cuò)編碼和高級(jí)在軌系統(tǒng)前向和反向鏈路的糾錯(cuò)編碼，是實(shí)現(xiàn)CCSDS標(biāo)準(zhǔn)低差錯(cuò)率信道糾錯(cuò)編碼的關(guān)鍵部件。只要每個(gè)碼字(255個(gè)符號(hào))中出現(xiàn)的錯(cuò)誤不超過(guò)16個(gè)符號(hào)，它就能將其糾正。

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

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

1.1 RS(255，223)碼

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

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

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

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

由于RS碼為分組碼，故其譯碼算法主要由伴隨式計(jì)算、關(guān)鍵方程求解和錢搜索和Forney算法3部分構(gòu)成，譯碼器結(jié)構(gòu)如圖1所示。

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

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

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

此后，由錯(cuò)誤位置多項(xiàng)式與錯(cuò)誤特征多項(xiàng)式來(lái)求得錯(cuò)誤位置與錯(cuò)誤值。求解錯(cuò)誤位置本設(shè)計(jì)采用窮舉算法——錢搜索算法來(lái)完成。同時(shí)，使用Forney公式求得錯(cuò)誤值。最后，用延時(shí)后的接收值減去錯(cuò)誤值，得到最后的譯碼輸出。Forney公式可以表示為：

其中，ei代表發(fā)生在i位置上的錯(cuò)誤值，σodd(x)代表錯(cuò)誤位置多項(xiàng)式奇數(shù)次項(xiàng)之和。

2并行流水結(jié)構(gòu)方案

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

2.1 伴隨式計(jì)算

8倍并行伴隨多項(xiàng)式的求解算法，是在迭代算法的基礎(chǔ)上展開實(shí)現(xiàn)，其推導(dǎo)過(guò)程如下：

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


2.2 關(guān)鍵方程求解

本設(shè)計(jì)中關(guān)鍵方程的求解采用ME算法。BM算法具有反饋結(jié)構(gòu)，不適合使用流水結(jié)構(gòu)，而ME算法可采用流水結(jié)構(gòu)。其算法描述如下：

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

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

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

當(dāng)i階余式Ri(x)的階數(shù)小于t時(shí)，迭代算法結(jié)束。算法結(jié)束時(shí)的Ri(x)即為錯(cuò)誤特征多項(xiàng)式ω(x)，而Li(x) 即為所求的錯(cuò)誤位置多項(xiàng)式δ(x)。

ME算法在每一次迭代時(shí)進(jìn)行的運(yùn)算為：

具體推導(dǎo)請(qǐng)見(jiàn)參考文獻(xiàn)[8-9]。

單級(jí)迭代電路結(jié)構(gòu)如圖3所示。

由ME算法推導(dǎo)可知，使用脈動(dòng)電路結(jié)構(gòu)實(shí)現(xiàn)ME算法時(shí)，至多使用2級(jí)迭代電路即可降低R(x)多項(xiàng)式階數(shù)1階。因此，脈動(dòng)電路結(jié)構(gòu)采用32階流水結(jié)構(gòu)電路即可保證迭代算法完成收斂得到最后結(jié)果。電路結(jié)構(gòu)如圖4所示。

2.3 錢搜索和Forney算法

錢搜索模塊接收KES模塊的錯(cuò)誤位置多項(xiàng)式信號(hào)δ(x)，利用錢搜索算法逐個(gè)檢查符號(hào)位是否發(fā)生錯(cuò)誤，輸出錯(cuò)誤位置和錯(cuò)誤位置多項(xiàng)式的奇數(shù)項(xiàng)之和，供EE模塊計(jì)算錯(cuò)誤圖案和糾錯(cuò)。

設(shè)錯(cuò)誤位置多項(xiàng)式δ(x)可以表達(dá)為奇數(shù)項(xiàng)和偶數(shù)項(xiàng)之和：

并行錢搜索電路子結(jié)構(gòu)如圖5所示。圖中m表示并行模塊編號(hào)數(shù)，m=1，2，…，8。所有的乘法器均是常數(shù)乘法器，8倍并行結(jié)構(gòu)由圖5所示的8個(gè)同樣的結(jié)構(gòu)組成。

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

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

3 仿真驗(yàn)證與綜合

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

因本譯碼器可糾正16個(gè)錯(cuò)誤，超過(guò)16個(gè)錯(cuò)誤便不可糾正，在仿真時(shí)譯碼輸入樣本采用了2種：一種樣本不超過(guò)16個(gè)錯(cuò)誤，另一種樣本超過(guò)16個(gè)錯(cuò)誤。仿真結(jié)果表明，此譯碼器能在不超過(guò)16個(gè)錯(cuò)誤的樣本下正常譯碼。

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

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