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

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