RS系列編譯碼器的設計與FPGA實現

2024年2月15日發(作者：侃侃)

RS系列編譯碼器的設計與FPGA實現

摘 要 本文介紹了RS(255，223)編譯碼器的實現，其中RS編碼器的設計中，利用有限域常數乘法器的特性對編碼電路進行優化，將所有的乘法器轉化為加法器。RS譯碼器采用歐幾里德算法，同時考慮到并行結構所需的硬件資源較多，譯碼器均采用串行結構實現。這些技術的采用大大提高了RS編譯碼器的效率，在保證速度的同時最大限度地減少了資源占用。 關鍵詞 RS碼；卷積碼；歐幾里德算法；FPGA

1 引言 RS碼是一種有很強能力的多進制BCH碼，也是一類典型的代數幾何碼。它首先由里德(Reed)和索洛蒙(Solomon)應用MS多項式于1960年構造出來的。它不但可以糾正隨機差錯，而且對突發錯誤的能力也很強，因此廣泛用于差錯控制系統中，以提高數據傳輸的可靠性。如今，RS(255，223)已被美國航天局和歐洲空間站在太空衛星通信的級聯碼系統中作為標準的外碼以采用。

2 RS(255，223)編碼器設計

RS(255，223)編碼原理 RS(n，k)碼是一種非二進制的BCH碼，工程上的RS編碼方式為RS(255，223)，該碼的基本特性 ·碼類型：系統碼，非透明 ·碼字長度：每個RS碼字中包含n=2J-1=255個RS符號=255×8bit； ·檢驗位數：n-k=2t ·能力：可糾任一個RS碼字中的t=16個RS符號差錯； ·碼最小距離：dmin=2t+1 ·碼的符號：有限域GF中的元素，每個RS符號由J=8bit構 成，即GF上的8維行向量； ·碼字中信息符號數目：k=n-2t=223個； ·碼字格式：d1d2d3…di…d223 p1p2…pk…p32，其中di為第i個數據符號，pk為第k個校驗符號； ·域生成多項式：有限域GF(28)在其特征域GF(2)上的生成多項式為：F=X8+X4+X3+X2+1 其中F為域生成多項式，X為多項式變量； · 碼生成多項式：g(x)=(x+a)(x+a2)...(x+a32) 式中，g(x)

是碼生成多項式； ai是GF(a8)中一個元素。

RS(255，223)編碼的FPGA實現 應用Matlab中的符號乘法，得到RS生成多項式中的32

項乘法系數。結合域生成多項式 生成的監督矩陣表[a0，a1，a2……a254]，通過查表得到32項碼生成多項式的系數[a18，a251，a215……a11]，即 因此，RS編碼器示意圖如圖1所示。圖1 RS編碼器示意圖 由于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所示。 用輸入數據信息實例進行了仿真。即輸入信息為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。圖2 的加法器表示

3 RS(255，223)譯碼器設計 譯碼器的實現主要包括下面四個流程：伴隨式計算、關鍵方程求解、錢搜索計算錯誤位置、福尼算法計算錯誤值。原理參考文獻[1]-。

伴隨式計算 定義伴隨多項式為其系數為

其中，n=255，i=1~32，α為x8+x4+x3+x2+1=0所生成的GF(28)中的本原元。

關鍵方程求解 定義錯誤位置多項式為錯位值多項式為結合上一步求出的伴隨多項式，根據RS碼的性質，我們有稱它為關鍵方程。上式可寫成 由Euclid算法可以知道ω(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)后，利用它們可以求出錯誤值，從而利用錢搜索，可找出錯誤位置，求出錯誤圖樣，從而實現譯碼。

錢搜索計算錯誤位置 在上一步關鍵方程

中求得σ(x)后，接下來的問題是從工程觀點看，如何簡單地求出它的根即錯誤位置。1964年錢聞天提出了一個求σ(x)根的使用方法，解決了這個問題。 解σ(x)的根，就是確定R(x)中哪幾位產生了錯誤。設R(x)=rn-1xn-1+rn-2xn-2+…+r1x+r0，為了要檢驗第k位rn-k是否錯誤，相當于譯碼器要確定αn-k是否是錯誤位置數，這等于檢驗α-(n-k)是否是σ(x)的根。若α-(n-k)是σ(x)的根，則 這樣依此對每一個rn-k(k=1，2，…，n)進行檢驗，就求得了σ(x)的根，這個過程稱為錢搜索。圖3

Euclid譯碼算法流程

福尼算法計算錯誤值 RS譯碼的最后一步就是求錯誤值Yi。設實際產生的錯誤個數γ≤t，則由可知：所以由于恒等式左邊最高次數為2γ，故上式成為求σ(x)的導數形式另x=xi-1，則上式成為所以令x= xi-1，則上式成為所以錯誤值注意上式可寫成

其中xi是錯誤位置對應的本原形式，σ(x)和ω(x)分別是錯誤位置多項式和錯誤值多項式，σ’(x)為σ(x)的一次導數。

其中，σ1，σ3……為錯誤位置多項式奇數項系數

RS(255，223)譯碼的FPGA實現伴隨式計算的實現 伴隨式計算電路結構如圖4所示。圖4中R0~R254為譯碼輸入。為了節省硬件資源，同時考慮到每個伴隨式系數在計算上相互沒有關系，故采用串行計算得到Si。具體做法為：首先將譯碼輸入R0~R254寫入到一個片內RAM，每計算一個伴隨式，將其從RAM中串行讀出，并進行迭代運算。圖4 伴隨式計算電路關鍵方程求解的實現 在歐幾里德(Euclid)算法中，用到了多項式的除法和乘法運算，為了節省資源，必須利用一個有效的刷新辦法對該除法器和乘法器進行實時刷新，使得每進行一次迭代后，除法器和乘法器中的內容及時更新，我們把中的算法結構上做如下的改進：在做多項式除法和乘法之前，先進行數據的并串轉換。這樣只要一個多項式除法器和一個乘法器就可完成該算法，在保證運算速度的同時也最大限度地節省了硬件資源。在下面的部分給出這兩個模塊的實現。 1) 多項式除法器 假設

多項式A(x)除以B(x)的商為q(x)，余數為r(x)。若某次迭代時A(x)的階數為m，B(x)的階數為n，m≥n。由多項式除法原理可知，q(x)=Bn-1Amxm-n，每次同m-n一起輸出；而r(x)=A(x)-B(x)q(x)是一個降次的過程，每降一次都需要將A(x)用r(x)刷新，直到它的階數小于B(x)的階數時，表明此次除法運算結束，用B(x)和r(x)分別對A(x)和B(x)進行同步刷新，繼續進行下一次除法運算。當r(x)的階數小于或等于t時，算法中的除法迭代運算結束。在實現中有兩點需要注意：第一點是我們用兩組固定長度的寄存器來存放A(x)和B(x)的系數，除了第一次初始化的時候需要給出它們的階數外，以后每次它們的階數都是由r(x)或上一次的B(x)的階數直接賦值，而由于每次r(x)是串行得到的，其階數能通過判斷每次的值是否為零累加得到；第二點是每次在對存放B(x)系數的寄存器進行更新時，應將B(x)的最高位和A(x)的最高位對齊，從而方便r(x)的求解，同時在用B(x)對存放A(x)系數的寄存器進行更新時應注意該操作帶來的影響。整個多

項式除法器的實現如圖5所示。 2) 多項式乘法器 多項式乘法器：將多項式除法運算的結果q和deg(q)實時輸入多項式乘法器，A(x)賦初值1，B(x)賦初值0，每完成一次除法運算，多項式除法器模塊給此模塊一個控制信號，A(x)與B(x)互換。迭代運算時代門關閉，輸出無效；當除法迭代結束時，多項式除法器模塊的控制信號控制門打開，輸出有效。多項式乘法器如圖6所示。錢搜索計算錯誤位置的實現在工程上，錢搜索過程可用圖7所示的電路實現，它的工作過程 (1)

t個寄存器寄存σ1，σ2，…，σt，當錯誤個數γt，則σγ+1=σγ+2=…=σt=0。

(2) rn-1正要從緩沖存儲器讀出之前，t個乘法器由移位脈沖控制乘法運算，且σ1α，σ2α2，…，σtαt存在σ寄存器中，并送入A中進行運算和檢驗。若等于-1，則A輸出一個信號，控制門打開，把錯誤值Yn-1與緩存器輸出的rn-1相減，得到rn-1-Yn-1=cn-1。 (3) rn-1譯完后，再進行一次相乘，此時σ1α2，σ2(α2)2，…，σt(αt)2存在σ寄存器中，并在A中進行