rs系列編譯碼器的設計與fpga實現(xiàn)

1、<p>　　RS系列編譯碼器的設計與FPGA實現(xiàn)</p><p>　　摘 要 本文介紹了RS(255，223)編譯碼器的實現(xiàn)，其中RS編碼器的設計中，利用有限域常數(shù)乘法器的特性對編碼電路進行優(yōu)化，將所有的乘法器轉(zhuǎn)化為加法器。RS譯碼器采用歐幾里德算法，同時考慮到并行結(jié)構(gòu)所需的硬件資源較多，譯碼器均采用串行結(jié)構(gòu)實現(xiàn)。這些技術(shù)的采用大大提高了RS編譯碼器的效率，在保證速度的同時最大限度地減少了資源占用。

2、</p><p>　　關鍵詞 RS碼；卷積碼；歐幾里德算法；FPGA</p><p><b>　　1 引言</b></p><p>　　RS碼是一種有很強糾錯能力的多進制BCH碼，也是一類典型的代數(shù)幾何碼。它首先由里德(Reed)和索洛蒙(Solomon)應用MS多項式于1960年構(gòu)造出來的。它不但可以糾正隨機差錯，而且對突發(fā)錯誤的糾錯能力也

3、很強，因此廣泛用于差錯控制系統(tǒng)中，以提高數(shù)據(jù)傳輸?shù)目煽啃?。如今，RS(255，223)已被美國航天局和歐洲空間站在太空衛(wèi)星通信的級聯(lián)碼系統(tǒng)中作為標準的外碼以采用。</p><p>　　2 RS(255，223)編碼器設計</p><p>　　2.1 RS(255，223)編碼原理</p><p>　　RS(n，k)碼是一種非二進制的BCH碼，工程上的RS糾錯編碼

4、方式為RS(255，223)，該碼的基本特性如下：</p><p>　　·碼類型：系統(tǒng)碼，非透明</p><p>　　·碼字長度：每個RS碼字中包含n=2J-1=255個RS符號=255×8bit；</p><p>　　·檢驗位數(shù)：n-k=2t</p><p>　　·糾錯能力：可糾任一個RS碼

5、字中的t=16個RS符號差錯；</p><p>　　·碼最小距離：dmin=2t+1</p><p>　　·碼的符號：有限域GF（2J）中的元素，每個RS符號由J=8bit構(gòu) 成，即GF（2）上的8維行向量；</p><p>　　·碼字中信息符號數(shù)目：k=n-2t=223個；</p><p>　　·碼字

6、格式：d1d2d3…di…d223 p1p2…pk…p32，其中di為第i個數(shù)據(jù)符號，pk為第k個校驗符號；</p><p>　　·域生成多項式：有限域GF(28)在其特征域GF(2)上的生成多項式為：</p><p>　　F（X）=X8+X4+X3+X2+1</p><p>　　其中F（X）為域生成多項式，X為多項式變量；</p><

7、p>　　· 碼生成多項式：g(x)=(x+a)(x+a2)...(x+a32)</p><p>　　式中，g(x) 是碼生成多項式；</p><p>　　ai是GF(a8)中一個元素。</p><p>　　2.2 RS(255，223)編碼的FPGA實現(xiàn)</p><p>　　應用Matlab中的符號乘法，得到RS（255，2

8、23）生成多項式中的32項乘法系數(shù)。結(jié)合域生成多項式 生成的監(jiān)督矩陣表[a0，a1，a2……a254]，通過查表得到32項碼生成多項式的系數(shù)[a18，a251，a215……a11]，即</p><p>　　因此，RS（255，223）編碼器示意圖如圖1所示。</p><p>　　圖1 RS（255，223）編碼器示意圖</p><p>　　由于GF(28)上的RS

9、碼是2m進制碼，GF(28)中的每個元素均可表示成它的自然基底1， 的線性組合：</p><p>　　以乘 a8為例可以表示為：</p><p>　　a8(a0+a1a+a2a2+a3a3+a4a4+a5a5+a6a6+a7a7)=a7(a5+a2+a)+a6(a4+a+1)+a5(a7+a2+a+1)+a4(a7+a6+a3+a2+1)+a3(a7+a6+a5+a3)+a2(a6+a5+

10、a4+a2)+a1(a5+a4+a3+a)+a0(a4+a3+a2+1)=a7(a5+a4+a3)+a6(a4+a3+a2)+a5(a7+a3+a2+a1)+a4(a6+a2+a1+a0)+a3(a4+a3+a1+a0)+a2(a7+a5+a4+a2+a0)+a1(a7+a6+a5+a1)+a0(a6+a5+a4+a0)</p><p>　　綜上推導，我們可以把所有的乘法器變化為加法器，即模二和的形式。如圖2所示

11、。</p><p>　　用輸入數(shù)據(jù)信息實例進行了仿真。即輸入信息為0，1，2…222，時，32個校驗位輸出為102，212，116，164，159，61，229，39，17，244，245，67，253，18，156，217，115，73，31，174，27，140，69，159，104，219，254，187，173，169，10，116。</p><p>　　圖2 的加法器表示&l

12、t;/p><p>　　3 RS(255，223)譯碼器設計</p><p>　　譯碼器的實現(xiàn)主要包括下面四個流程：伴隨式計算、關鍵方程求解、錢搜索計算錯誤位置、福尼算法計算錯誤值。原理參考文獻[1]-[4]。</p><p><b>　　3.1 伴隨式計算</b></p><p><b>　　定義伴隨多項式為&l

13、t;/b></p><p><b>　　其系數(shù)為</b></p><p>　　其中，n=255，i=1~32，α為x8+x4+x3+x2+1=0所生成的GF(28)中的本原元。 </p><p>　　3.2 關鍵方程求解</p><p>　　定義錯誤位置多項式為</p><p><b

14、>　　錯位值多項式為</b></p><p>　　結(jié)合上一步求出的伴隨多項式，根據(jù)RS碼的性質(zhì)，我們有</p><p><b>　　稱它為關鍵方程。</b></p><p><b>　　上式可寫成</b></p><p>　　由Euclid算法[3]可以知道ω(x)是S(x)與x2

15、t+1的最大公因子。同時，由簡單的證明可知，只要假設U-1=1，U0=0，V-1=0，V0=1，即可利用每一次求到的qj(x)，來求出當前時刻的Uj(x)和Vj(x)，因此可以得到Euclid譯碼算法流程圖如圖3所示。當求出σ(x)和ω(x)后，利用它們可以求出錯誤值，從而利用錢搜索，可找出錯誤位置，求出錯誤圖樣，從而實現(xiàn)譯碼。</p><p>　　3.3 錢搜索計算錯誤位置</p><p&g

16、t;　　在上一步關鍵方程中求得σ(x)后，接下來的問題是從工程觀點看，如何簡單地求出它的根即錯誤位置。1964年錢聞天提出了一個求σ(x)根的使用方法，解決了這個問題。</p><p>　　解σ(x)的根，就是確定R(x)中哪幾位產(chǎn)生了錯誤。設R(x)=rn-1xn-1+rn-2xn-2+…+r1x+r0，為了要檢驗第k位rn-k是否錯誤，相當于譯碼器要確定αn-k是否是錯誤位置數(shù)，這等于檢驗α-(n-k)是否是

17、σ(x)的根。若α-(n-k)是σ(x)的根，則</p><p>　　這樣依此對每一個rn-k(k=1，2，…，n)進行檢驗，就求得了σ(x)的根，這個過程稱為錢搜索。</p><p>　　圖3 Euclid譯碼算法流程</p><p>　　3.4 福尼算法計算錯誤值</p><p>　　RS譯碼的最后一步就是求錯誤值Yi。設實際產(chǎn)生的錯

18、誤個數(shù)γ≤t，則</p><p><b>　　由</b></p><p><b>　　可知：</b></p><p><b>　　所以</b></p><p>　　由于恒等式左邊最高次數(shù)為2γ，故上式成為</p><p>　　求σ(x)的導數(shù)形式<

19、/p><p>　　另x=xi-1，則上式成為</p><p><b>　　所以</b></p><p>　　令x= xi-1，則上式成為</p><p><b>　　所以錯誤值</b></p><p><b>　　注意上式可寫成</b></p>

20、<p>　　其中xi是錯誤位置對應的本原形式，σ(x)和ω(x)分別是錯誤位置多項式和錯誤值多項式，σ’(x)為σ(x)的一次導數(shù)。</p><p><b>　　其中</b></p><p>　　，σ1，σ3……為錯誤位置多項式奇數(shù)項系數(shù)</p><p>　　3.5 RS(255，223)譯碼的FPGA實現(xiàn)</p>

21、<p>　　3.5.1伴隨式計算的實現(xiàn)</p><p>　　伴隨式計算電路結(jié)構(gòu)如圖4所示。</p><p>　　圖4中R0~R254為譯碼輸入。為了節(jié)省硬件資源，同時考慮到每個伴隨式系數(shù)在計算上相互沒有關系，故采用串行計算得到Si。具體做法為：首先將譯碼輸入R0~R254寫入到一個片內(nèi)RAM，每計算一個伴隨式，將其從RAM中串行讀出，并進行迭代運算。</p><

22、;p>　　圖4 伴隨式計算電路</p><p>　　3.5.2關鍵方程求解的實現(xiàn)</p><p>　　在歐幾里德(Euclid)算法[3]中，用到了多項式的除法和乘法運算，為了節(jié)省資源，必須利用一個有效的刷新辦法對該除法器和乘法器進行實時刷新，使得每進行一次迭代后，除法器和乘法器中的內(nèi)容及時更新，我們把[3]中的算法結(jié)構(gòu)上做如下的改進：在做多項式除法和乘法之前，先進行數(shù)據(jù)的并串轉(zhuǎn)換

23、。這樣只要一個多項式除法器和一個乘法器就可完成該算法，在保證運算速度的同時也最大限度地節(jié)省了硬件資源。在下面的部分給出這兩個模塊的實現(xiàn)。</p><p><b>　　1) 多項式除法器</b></p><p>　　假設多項式A(x)除以B(x)的商為q(x)，余數(shù)為r(x)。若某次迭代時A(x)的階數(shù)為m，B(x)的階數(shù)為n，m≥n。由多項式除法原理可知，q(x)=B

24、n-1Amxm-n，每次同m-n一起輸出；而r(x)=A(x)-B(x)q(x)是一個降次的過程，每降一次都需要將A(x)用r(x)刷新，直到它的階數(shù)小于B(x)的階數(shù)時，表明此次除法運算結(jié)束，用B(x)和r(x)分別對A(x)和B(x)進行同步刷新，繼續(xù)進行下一次除法運算。當r(x)的階數(shù)小于或等于t時，算法中的除法迭代運算結(jié)束。在實現(xiàn)中有兩點需要注意：第一點是我們用兩組固定長度的寄存器來存放A(x)和B(x)的系數(shù)，除了第一次初始化

25、的時候需要給出它們的階數(shù)外，以后每次它們的階數(shù)都是由r(x)或上一次的B(x)的階數(shù)直接賦值，而由于每次r(x)是串行得到的，其階數(shù)能通過判斷每次的值是否為零累加得到；第二點是每次在對存放B(x)系數(shù)的寄存器進行更新時，應將B(x)的最高位和A(x)的最高位對齊，從而方便r(x)的求解，同時在用B(x)對存放A(x)系數(shù)的寄存器進行更新時應注意該操作帶來的影響。整個多項式除法器的實現(xiàn)如圖5所示。</p><p>

26、<b>　　2) 多項式乘法器</b></p><p>　　多項式乘法器：將多項式除法運算的結(jié)果q和deg(q)實時輸入多項式乘法器，A(x)賦初值1，B(x)賦初值0，每完成一次除法運算，多項式除法器模塊給此模塊一個控制信號，A(x)與B(x)互換。迭代運算時代門關閉，輸出無效；當除法迭代結(jié)束時，多項式除法器模塊的控制信號控制門打開，輸出有效。多項式乘法器如圖6所示。</p>

27、<p>　　3.5.3錢搜索計算錯誤位置的實現(xiàn)</p><p>　　在工程上，錢搜索過程可用圖7所示的電路實現(xiàn)，它的工作過程如下：</p><p>　　(1) t個寄存器寄存σ1，σ2，…，σt，當錯誤個數(shù)γ&lt;t，則σγ+1=σγ+2=…=σt=0。</p><p>　　(2) rn-1正要從緩沖存儲器讀出之前，t個乘法器由移位脈沖控制乘法

28、運算，且σ1α，σ2α2，…，σtαt存在σ寄存器中，并送入A中進行運算和檢驗。若等于-1，則A輸出一個信號，控制門打開，把錯誤值Yn-1與緩存器輸出的rn-1相減，得到rn-1-Yn-1=cn-1。</p><p>　　(3) rn-1譯完后，再進行一次相乘，此時σ1α2，σ2(α2)2，…，σt(αt)2存在σ寄存器中，并在A中進行相加運算和檢驗，對rn-2進行糾錯。</p><p>

29、　　(4) 其余碼元同(2)一樣糾錯。</p><p>　　圖5 多項式除法器流程圖</p><p>　　圖6 多項式乘法器流程圖</p><p>　　圖7 Chien搜索電路(并行)</p><p>　　以上的計算是并行計算的，我們在處理中，為了節(jié)省硬件資源而采用串行計算，需要把每次迭代的數(shù)儲存起來，在這里使用了一個片內(nèi)RAM，實時更

30、新里面的內(nèi)容，同時RAM的數(shù)據(jù)地址表示移位次數(shù)。當σ1~σ16都移位完成之后，輸出RAM數(shù)據(jù)為0的數(shù)據(jù)地址即移位次數(shù)表示錯誤位置。改進的串行計算部分電路圖如圖8所示。</p><p>　　圖8 Chien搜索部分電路</p><p>　　3.5.4福尼算法計算錯誤值的實現(xiàn)</p><p>　　福尼算法計算錯誤值可以采用與錢搜索類似的電路實現(xiàn)。</p>

31、<p>　　同樣，在計算錯誤值多項式時，我們也采用串行計算，刷新片內(nèi)RAM并累加得到，整個福尼算法的電路如圖9所示。</p><p><b>　　圖9 福尼算法電路</b></p><p>　　4 編解碼性能測試與仿真</p><p>　?。?）選取具有代表性的測試數(shù)據(jù)序列，把編碼結(jié)果與matlab計算結(jié)果比較完全正確。</p

32、><p>　　（2）把編碼器與譯碼器級聯(lián)，確認譯碼器輸出結(jié)果完全正確。</p><p>　?。?）將編碼器一組輸出碼字的任意16位出錯作為譯碼器的輸入，經(jīng)過仿真16位均被糾正。</p><p>　?。?）實現(xiàn)卷積(4，3，3)與RS(255，223)級聯(lián)，確認輸出結(jié)果正確。</p><p>　　如圖10所示，為卷積(4，3，3)與RS(255，2

33、23)級聯(lián)的仿真圖。圖中rsin為RS編碼器輸入，rsout為編碼器輸出，jlianout為RS(255，223) +卷積(4，3，3)級聯(lián)編碼輸出，corr_code為RS(255，223) +卷積(4，3，3)級聯(lián)譯碼輸出。</p><p>　　圖10 RS(255，223) +卷積(4，3，3)級聯(lián)編碼輸出時序</p><p>　　5 FPGA資源分析</p>&l

34、t;p>　　本文RS(255，223)編譯碼器的設計通過Altera公司的QuartusⅡ軟件開發(fā)平臺上完成了功能仿真、編譯綜合并優(yōu)化、布局布線、時序仿真等工作。本文選用CycloneⅡ系列器件的EP2C8T144C8，分別將上述譯碼器實際占用FPGA資源情況如表1所示。</p><p>　　表1 編譯碼器片內(nèi)資源占用情況</p><p><b>　　6 結(jié)論</b

35、></p><p>　　本文介紹了RS(255，223)編譯碼器的設計以及FPGA實現(xiàn)，并通過了QuartusⅡ的功能仿真，布局布線和時序仿真。在30MHz的時鐘頻率下編譯碼器的數(shù)據(jù)吞吐率為240Mbps，譯出一楨數(shù)據(jù)255byte需1.2ms，相比與目前的一些文獻，占用的硬件資源較少且速度較快。FPGA的仿真測試表明譯碼的技術(shù)指標均符合要求，該設計不僅可以和別的FEC技術(shù)結(jié)合，提供強大的糾錯能力，而且也可

36、以專門用于ASIC設計中。</p><p><b>　　參考文獻</b></p><p>　　[1]王新梅，肖國鎮(zhèn).糾錯碼原理與方法[M].西安：西安電子科技大學出版社.1996</p><p>　　[2]SHI Junfeng，WANG Yu，SUN Huixian. The implementation and verification o

37、f RS(255，223) decoder according to CCSDS specification[J]. Chin.J.Space Sci.. 2005.25(4)：309-314</p><p>　　[3]張輔云，葛建華. RS譯碼的Eculid算法及其FPGA實現(xiàn)[J].中國有線電視，2003(14)：6-9</p><p>　　[4]曹志剛，錢亞生.現(xiàn)代通信原理[M].北