RS系列編譯碼器的設計與FPGA實現(xiàn).doc

RS系列編譯碼器的設計與FPGA實現(xiàn)摘要本文介紹了RS(255，223)編譯碼器的實現(xiàn)，其中RS編碼器的設計中，利用有限域常數(shù)乘法器的特性對編碼電路進行優(yōu)化，將所有的乘法器轉化為加法器。RS譯碼器采用歐幾里德算法，同時考慮到并行結構所需的硬件資源較多，譯碼器均采用串行結構實現(xiàn)。這些技術的采用大大提高了RS編譯碼器的效率，在保證速度的同時最大限度地減少了資源占用。關鍵詞RS碼；卷積碼；歐幾里德算法；FPGA1引言RS碼是一種有很強糾錯能力的多進制BCH碼，也是一類典型的代數(shù)幾何碼。它首先由里德(Reed)和索洛蒙(Solomon)應用MS多項式于1960年構造出來的。它不但可以糾正隨機差錯，而且對突發(fā)錯誤的糾錯能力也很強，因此廣泛用于差錯控制系統(tǒng)中，以提高數(shù)據(jù)傳輸?shù)目煽啃?。如今，RS(255，223)已被美國航天局和歐洲空間站在太空衛(wèi)星通信的級聯(lián)碼系統(tǒng)中作為標準的外碼以采用。2RS(255，223)編碼器設計2.1RS(255，223)編碼原理RS(n，k)碼是一種非二進制的BCH碼，工程上的RS糾錯編碼方式為RS(255，223)，該碼的基本特性如下：碼類型：系統(tǒng)碼，非透明碼字長度：每個RS碼字中包含n=2J-1=255個RS符號=2558bit；檢驗位數(shù)：n-k=2t糾錯能力：可糾任一個RS碼字中的t=16個RS符號差錯；碼最小距離：dmin=2t+1碼的符號：有限域GF（2J）中的元素，每個RS符號由J=8bit構成，即GF（2）上的8維行向量；碼字中信息符號數(shù)目：k=n-2t=223個；碼字格式：d1d2d3did223p1p2pkp32，其中di為第i個數(shù)據(jù)符號，pk為第k個校驗符號；域生成多項式：有限域GF(28)在其特征域GF(2)上的生成多項式為：F（X）=X8+X4+X3+X2+1其中F（X）為域生成多項式，X為多項式變量；碼生成多項式：g(x)=(x+a)(x+a2).(x+a32)式中，g(x)是碼生成多項式；ai是GF(a8)中一個元素。2.2RS(255，223)編碼的FPGA實現(xiàn)應用Matlab中的符號乘法，得到RS（255，223）生成多項式中的32項乘法系數(shù)。結合域生成多項式生成的監(jiān)督矩陣表a0，a1，a2a254，通過查表得到32項碼生成多項式的系數(shù)a18，a251，a215a11，即因此，RS（255，223）編碼器示意圖如圖1所示。圖1RS（255，223）編碼器示意圖由于GF(28)上的RS碼是2m進制碼，GF(28)中的每個元素均可表示成它的自然基底1，的線性組合：以乘a8為例可以表示為：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+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)綜上推導，我們可以把所有的乘法器變化為加法器，即模二和的形式。如圖2所示。用輸入數(shù)據(jù)信息實例進行了仿真。即輸入信息為0，1，2222，時，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。圖2的加法器表示3RS(255，223)譯碼器設計譯碼器的實現(xiàn)主要包括下面四個流程：伴隨式計算、關鍵方程求解、錢搜索計算錯誤位置、福尼算法計算錯誤值。原理參考文獻1-4。3.1伴隨式計算定義伴隨多項式為其系數(shù)為其中，n=255，i=132，為x8+x4+x3+x2+1=0所生成的GF(28)中的本原元。3.2關鍵方程求解定義錯誤位置多項式為錯位值多項式為結合上一步求出的伴隨多項式，根據(jù)RS碼的性質，我們有稱它為關鍵方程。上式可寫成由Euclid算法3可以知道(x)是S(x)與x2t+1的最大公因子。同時，由簡單的證明可知，只要假設U-1=1，U0=0，V-1=0，V0=1，即可利用每一次求到的qj(x)，來求出當前時刻的Uj(x)和Vj(x)，因此可以得到Euclid譯碼算法流程圖如圖3所示。當求出(x)和(x)后，利用它們可以求出錯誤值，從而利用錢搜索，可找出錯誤位置，求出錯誤圖樣，從而實現(xiàn)譯碼。3.3錢搜索計算錯誤位置在上一步關鍵方程中求得(x)后，接下來的問題是從工程觀點看，如何簡單地求出它的根即錯誤位置。1964年錢聞天提出了一個求(x)根的使用方法，解決了這個問題。解(x)的根，就是確定R(x)中哪幾位產(chǎn)生了錯誤。設R(x)=rn-1xn-1+rn-2xn-2+r1x+r0，為了要檢驗第k位rn-k是否錯誤，相當于譯碼器要確定n-k是否是錯誤位置數(shù)，這等于檢驗-(n-k)是否是(x)的根。若-(n-k)是(x)的根，則這樣依此對每一個rn-k(k=1，2，n)進行檢驗，就求得了(x)的根，這個過程稱為錢搜索。圖3Euclid譯碼算法流程3.4福尼算法計算錯誤值RS譯碼的最后一步就是求錯誤值Yi。設實際產(chǎn)生的錯誤個數(shù)t，則由可知：所以由于恒等式左邊最高次數(shù)為2，故上式成為求(x)的導數(shù)形式另x=xi-1，則上式成為所以令x=xi-1，則上式成為所以錯誤值注意上式可寫成其中xi是錯誤位置對應的本原形式，(x)和(x)分別是錯誤位置多項式和錯誤值多項式，(x)為(x)的一次導數(shù)。其中，1，3為錯誤位置多項式奇數(shù)項系數(shù)3.5RS(255，223)譯碼的FPGA實現(xiàn)3.5.1伴隨式計算的實現(xiàn)伴隨式計算電路結構如圖4所示。圖4中R0R254為譯碼輸入。為了節(jié)省硬件資源，同時考慮到每個伴隨式系數(shù)在計算上相互沒有關系，故采用串行計算得到Si。具體做法為：首先將譯碼輸入R0R254寫入到一個片內RAM，每計算一個伴隨式，將其從RAM中串行讀出，并進行迭代運算。圖4伴隨式計算電路3.5.2關鍵方程求解的實現(xiàn)在歐幾里德(Euclid)算法3中，用到了多項式的除法和乘法運算，為了節(jié)省資源，必須利用一個有效的刷新辦法對該除法器和乘法器進行實時刷新，使得每進行一次迭代后，除法器和乘法器中的內容及時更新，我們把3中的算法結構上做如下的改進：在做多項式除法和乘法之前，先進行數(shù)據(jù)的并串轉換。這樣只要一個多項式除法器和一個乘法器就可完成該算法，在保證運算速度的同時也最大限度地節(jié)省了硬件資源。在下面的部分給出這兩個模塊的實現(xiàn)。1)多項式除法器假設多項式A(x)除以B(x)的商為q(x)，余數(shù)為r(x)。若某次迭代時A(x)的階數(shù)為m，B(x)的階數(shù)為n，mn。由多項式除法原理可知，q(x)=Bn-1Amxm-n，每次同m-n一起輸出；而r(x)=A(x)-B(x)q(x)是一個降次的過程，每降一次都需要將A(x)用r(x)刷新，直到它的階數(shù)小于B(x)的階數(shù)時，表明此次除法運算結束，用B(x)和r(x)分別對A(x)和B(x)進行同步刷新，繼續(xù)進行下一次除法運算。當r(x)的階數(shù)小于或等于t時，算法中的除法迭代運算結束。在實現(xiàn)中有兩點需要注意：第一點是我們用兩組固定長度的寄存器來存放A(x)和B(x)的系數(shù)，除了第一次初始化的時候需要給出它們的階數(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所示。2)多項式乘法器多項式乘法器：將多項式除法運算的結果q和deg(q)實時輸入多項式乘法器，A(x)賦初值1，B(x)賦初值0，每完成一次除法運算，多項式除法器模塊給此模塊一個控制信號，A(x)與B(x)互換。迭代運算時代門關閉，輸出無效；當除法迭代結束時，多項式除法器模塊的控制信號控制門打開，輸出有效。多項式乘法器如圖6所示。3.5.3錢搜索計算錯誤位置的實現(xiàn)在工程上，錢搜索過程可用圖7所示的電路實現(xiàn)，它的工作過程如下：(1)t個寄存器寄存1，2，t，當錯誤個數(shù)<；t，則+1=+2=t=0。(2)rn-1正要從緩沖存儲器讀出之前，t個乘法器由移位脈沖控制乘法運算，且1，22，tt存在寄存器中，并送入A中進行運算和檢驗。若等于-1，則A輸出一個信號，控制門打開，把錯誤值Yn-1與緩存器輸出的rn-1相減，得到rn-1-Yn-1=cn-1。(3)rn-1譯完后，再進行一次相乘，此時12，2(2)2，t(t)2存在寄存器中，并在A中進行相加運算和檢驗，對rn-2進行糾錯。(4)其余碼元同(2)一樣糾錯。圖5多項式除法器流程圖圖6多項式乘法器流程圖圖7Chien搜索電路(并行)以上的計算是并行計算的，我們在處理中，為了節(jié)省硬件資源而采用串行計算，需要把每次迭代的數(shù)儲存起來，在這里使用了一個片內RAM，實時更新里面的內容，同時RAM的數(shù)據(jù)地址表示移位次數(shù)。當116都移位完成之后，輸出RAM數(shù)據(jù)為0的數(shù)據(jù)地址即移位次數(shù)表示錯誤位置。改進的串行計算部分電路圖如圖8所示。圖8Chien搜索部分電路3.5.4福尼算法計算錯誤值的實現(xiàn)福尼算法計算錯誤值可以采用與錢搜索類似的電路實現(xiàn)。同樣，在計算錯誤值多項式時，我們也采用串行計算，刷新片內RAM并累加得到，整個福尼算法的電路如圖9所示。圖9福尼算法電路4編解碼性能測試與仿真（1）選取具有代表性的測試數(shù)據(jù)序列，把編碼結果與matlab計算結果比較完全正確。（2）把編碼器與譯碼器級聯(lián)，確認譯碼器輸出結果完全正確。（3）將編碼器一組輸出碼字的任意16位出錯作為譯碼器的輸入，經(jīng)過仿真16位均被糾正。（4）實現(xiàn)卷積(4，3，3)與RS(255，223)級聯(lián)，確認輸出結果正確。如圖10所示，為卷積(4，3，3)與RS(255，223)級聯(lián)的仿真圖。圖中rsin為RS編碼器輸入，rsout為編碼器輸出，jlianout為RS(255，223)+卷積(4，3，3)級聯(lián)編碼輸出，corr_code為RS(255，223)+卷積(4，3，3)級聯(lián)譯碼輸出。圖10RS(255，223)+卷積(4，3，3)級聯(lián)編碼輸出時序5FPGA資源分析本文RS(255，223)編譯碼器的設計通過Altera公司的Quartus軟件開發(fā)平臺上完成了功能仿真、編譯綜合并優(yōu)化、布局布線、時序仿真等工作。本文選用Cyclone系列器件的EP2C8T144C8，分別將上述譯碼器實