裡德-索羅蒙解碼器實現方法

2023-07-05 13:39:51 3

專利名稱：：裡德-索羅蒙解碼器實現方法
技術領域：
：本發明涉及數字通信技術，特別涉及一種裡德-索羅蒙解碼器實現方法。
背景技術：
：為了降低數位訊號在傳輸或存儲等過程中錯誤的概率，糾錯碼被大量使用在各種環境中。通過檢測收到的碼組是否有錯，接收端可以通知發送端重新發送出錯的碼；更高級的糾錯碼，所謂的「前向糾錯碼」(FEC，ForwardErrorCorrection)，可以檢測並更正接收的碼組中的錯誤而不需要發送端重新發送。Galois有限域定義了一個數域，其中包含了有限個元素。包含q個元素的Galois域通常記成GF(q)。在FEC編碼，特別是1(徹6(1-5010111011，裡德-索羅蒙)碼中，Galois域非常有用。例如信息碼的一串二進位序列被組成了多個符號，每個符號包含M位，那每個符號是GF(2M)的一個元素。這些符號再次被組成多個塊，每個塊包含k個符號，記為{πν」Hi1,…％}，HV1為第一個符號(第一個發送)，m。為最後一個符號(最後一個符號)，記t=(n-k)/2。這樣信息碼每個塊的發送序列可以記成一個(k-Ι)階的多項式k~\formulaseeoriginaldocumentpage4為了在接收端能檢測/糾正錯誤，冗餘符號被添加到了信息碼正常符號的末尾，使得數據塊的符號從k個增加到了η個。這η個符號的數據塊被稱為一個碼字，該碼字記成一個(η-1)階的多項式c(X)=X2tm(X)+ρ(X)ρ⑴為附加的校驗符號，是一個階為(2t_l)的多項式，它按照下列方法生成p(X)=X2tm(X)modg(χ)g(X)為Galois域上的生成多項式，其定義為formulaseeoriginaldocumentpage4其中α為GF(2M)上本原多項式的根。編碼器根據原始的k階多項式和生成多項式生成ρ(X)，並把它附加在原始序列的末尾，這樣形成的一個碼字記為RS(n，k)。由編碼過程可以知道，生成多項式的根必定是任意一個由該生成多項式生成的有效的碼多項式的根。接收端把生成多項式的根代入接收序列中，如果生成多項式的根也是接收序列的根，這表明在傳輸過程中沒有出錯；否則表明在傳輸中碼字發生了錯誤。RS(裡德-索羅蒙)解碼器結構如圖1所示，伴隨多項式生成模塊(syndromecomputation)進行伴隨式計算，錯誤位置和錯誤值多項式生成模塊(ModifiedEuclidAlgorithm,MEA)基於改進的歐幾裡德算法生成錯誤位置和錯誤值多項式，錯誤值檢測模塊基於錢搜索(Chiensearch)檢測錯誤值，錯誤值計算模塊基於Forney算法(Forneyalgorithm)計算錯誤值，碼字緩存和錯誤糾正模塊(decjxif)進行包緩存。RS解碼器的解碼過程如下。1.假設接收序列構成的碼多項式記為r(X)，由於生成多項式的根也是有效的碼多項式的根，因此可以把生成多項式的根代入r(X)formulaseeoriginaldocumentpage5如果對所有的i，都存在Si為0，這表示碼字在傳輸過程中沒有發生錯誤；反之則表明在傳輸過程中碼字發生了錯誤。2.對由伴隨式構成的伴隨多項式formulaseeoriginaldocumentpage5滿足如下的關鍵方程S(X)σ(X)ξω(X)其中σ(X)表示錯誤位置多項式，ω(X)表示錯誤值多項式。如果求解出這兩個多項式，那就能恢復發送的正確符號。該關鍵方程可以改寫成如下形式ω(X)=X2tμ(X)+S(X)歐幾裡德定理表明錯誤值多項式ω⑴是X2t和S(X)的最大公約式，因此可以採用歐幾裡德算法計算錯誤位置多項式和錯誤值多項式。3.當找到ο⑴和ω⑴後，利用錢搜索尋找ο⑴的根。根對應的位置即為出現符號錯誤的位置，然後利用Forney算法計算該位置對應的錯誤的符號的值。4.把所在位置收到的符號的值和計算得到的符號值進行有限域上的加法就得到正確的符號。對錯誤位置多項式ο(X)、錯誤值多項式ω(X)這兩個多項式的求解，改進的歐幾裡德算法的計算流程如圖2所示。圖中S(χ)表示由多個伴隨式構成的伴隨多項式，R(X)，Q(X)，λ(Χ),μ(X)為四個多項式。首先初始化R0(X)=x2t,Q0(X)=χ·S(χ)，A0(X)=0,μ0(Χ)=1,i=0；Ii=deg[Ri(X)]-deg[Qi(X)]其中i為迭代次數，Ii為R(X)和Q(X)兩個多項式的階數之差。然後開始進行迭代計算當Ii彡0時，Ri(X)=H(X)-(^)A1(X)=H1(Z)-Qi⑴和μi⑴保持不變；當Ii<0時，formulaseeoriginaldocumentpage6formulaseeoriginaldocumentpage6formulaseeoriginaldocumentpage6formulaseeoriginaldocumentpage6當多項式R(X)的最高階數小於t時，formulaseeoriginaldocumentpage6否則繼續迭代直到滿足退出要求。傳統的改進歐幾裡德算法的實現如圖3所示。計算得到的伴隨多項式從伴隨多項式生成模塊串行輸出，進入錯誤位置和錯誤值多項式生成模塊(MEA)。MEA初始化R(X)=X2t,λ(X)=0、μ(X)=1、deg(R(X))=2t，刪除S(X)中從最高階項到第一個非0係數項之間所有的項得到新的多項式S'(X)，然後用該多項式初始化Q(X)，計算出Q(X)階數(1叩(0。初始化完畢後，根據1(幻和Q(X)階數的大小重新計算四個多項式的值和R(X)的階數，如果R(X)的階數小於t，計算結束，否則重新計算四個多項式的值，以此迭代，直到R(X)的階數小於t。錢搜索和Forney算法最主要的步驟是求一個多項式對GF(2M)上所有元素的值。計算過程如圖4所示。一共有(t+Ι)個計算單元，分成奇數項和偶數項兩組。初始時把第i項的係數Ci裝入寄存器中，每個時鐘把寄存器中的值乘上α1後的值存入寄存器中。把所有單元輸出相加後得到該多項式對GF(2μ)內某個元素的值。但是，現有的RS解碼器算法存在著一些不足。1.隨著大容量存儲和高速數字傳輸系統的出現，採用傳統的迭代結構實現的改進的歐幾裡德算法、單路錢搜索和Forney算法已經不能滿足高速系統的要求。比如在IOGEPON(EthernetPassiveOpticalNetwork，以太無源光網絡)系統中採用基於RS(255，223)的流編碼，兩符號塊間隔最小只有32個時鐘周期。2.傳統的伴隨式計算只能支持單符號，不能同時支持多符號運算。3.傳統的基於改進的歐幾裡德算法的解碼器採用迭代求解錯誤位置和錯誤值多項式，但迭代的次數依賴於碼字中出現錯誤符號的個數，因此經過不同的碼組經過解碼器可能存在不同的延時，這不能滿足某些應用環境的要求。比如在EPON(EthernetPassiveOpticalNetwork,以太無源光網絡)系統中，由於OLT(光線路終端)或者ONU(光網絡單元)會周期性的發送MPCP(MultipointControlProtocol，多點控制協議)協議幀，該協議幀的一個域包含了該設備當前的時間戳，該幀在底層經過RS編碼後發送出去。接收端經過RS解碼器恢復出原來的幀，計算該幀內的時間戳與接收到該幀時的本地時間戳的差，然後比較前後兩次差的差值。如果差值超過了某個給定的門限，那麼將會導致ONU無法註冊。因此如果解碼器的延時不固定，在某些情況下會因為誤判而導致ONU無法註冊。4.傳統的基於改進的歐幾裡德算法的解碼器需要計算並比較多項式的階次，這增加了系統的面積和複雜性。
發明內容本發明要解決的技術問題是提供一種裡德_索羅蒙解碼器實現方法，可以同時對多個符號進行解碼，解碼延時小且固定，結構規整。為解決上述技術問題，本發明的裡德-索羅蒙解碼器實現方法，包括伴隨多項式生成模塊、錯誤位置多項式生成及錯誤值多項式生成模塊、錯誤值檢測模塊、錯誤值計算模塊、錯誤糾正模塊，其特徵在於，錯誤位置多項式生成及錯誤值多項式生成模塊採用以下方式分別設置控制器、運算器、四個移位寄存器，其中移位寄存器一存放多項式R(X)的各階係數，移位寄存器二存放多項式Q(X)的各階係數，移位寄存器三存放多項式λ(χ)的各階係數，移位寄存器四存放多項式μ(X)的各階係數，移位寄存器一和移位寄存器二有2t+l個單元，從左到右分別存放x°x2t的係數，移位寄存器三和移位寄存器四有t+Ι個單元，從左到右分別存放x°Xt的係數，t=(n-k)/2,η為一個碼字的符號數，k為信息碼的符號數，控制器根據R(X)、Q(X)兩個多項式的最高階係數和兩個多項式的階數差控制運算器對所述四個多項式按照算法流程執行如下操作一.首先初始化，將控制器中的R(X)同Q(X)多項式的階次差置為+1；將控制器中的迭代次數i初始化為0；四個寄存器分別初始化為R(X)=X2t、Q(X)=X-S(X),λ(X)=ο、μ⑴為集合{Χ≤ο≤j(t，j為整數}中的任意一個元素，S(X)為由所述伴隨多項式生成模塊生成的伴隨多項式。二.控制器中迭代次數i遞增1，如果移位寄存器一最右端的單元中的R(X)的最高階係數為0，並且移位寄存器二最右端的單元中的Q(X)的最高階係數為0，則4個移位寄存器都右移一次，階次差不變；如果移位寄存器一最右端的單元中R(X)的最高階係數為0，並且移位寄存器二最右端的單元中Q(X)的最高階係數不為0，則移位寄存器一和移位寄存器三兩個移位寄存器都右移一次，同時階次差減一；如果移位寄存器一最右端的單元中R(X)的最高階係數不為0，並且移位寄存器二最右端的單元中Q(X)的最高階係數為0，則移位寄存器二和四都右移一次，同時階次差加如果移位寄存器一最右端的單元中R(X)的最高階係數和移位寄存器二最右端的單元中Q(X)的最高階係數都不為0，並且階次差不小於0，則運算器按照Ri(X)=Iv1Rg⑴--…^(X)，Ai⑴=Iviλη⑴-agμη⑴進行運算，將得到的結果分別寫入移位寄存器一、移位寄存器三，同時將移位寄存器一和三都右移一次，同時階次差減一；如果移位寄存器一最右端的單元中R(X)的最高階係數和移位寄存器二最右端的單元中Q(X)的最高階係數都不為0，並且階次差小於0，則運算器按照氏⑴=Iv1Rh(X)-Bi^1Qi-!(X)，λi(X)=bHλ(X)-Bi^1μ(X)，Qi(X)=Rh(X),μi(X)=λ(X)進行運算，將得到的結果分別寫入各移位寄存器，同時將移位寄存器一和三都右移一次，同時階次差置為原階次差的補碼減一；如果迭代次數i達到2t則進行步驟三；否則進行步驟二。三.將移位寄存器一中存放的多項式R(X)的各階係數輸出作為錯誤值多項式的各階係數，將移位寄存器三中存放的多項式λ(X)的各階係數輸出作為錯誤位置多項式的各階係數。本發明的裡德-索羅蒙解碼器實現方法，在對錯誤位置多項式、錯誤值多項式求解時，通過控制器、運算器、四個移位寄存器實現，由於取消了傳統歐幾裡德算法中階次計算與比較邏輯，綜合面積小，由於採用流水結構，系統頻率高，數據吞吐量大，結構規整，易於硬體實現，延時小且固定，可以同時對裡德-索羅蒙碼的多個符號進行解碼。下面結合附圖及具體實施方式對本發明作進一步詳細說明。圖1是RS解碼器結構示意圖；圖2是改進的歐幾裡德算法的計算流程；圖3是傳統的改進歐幾裡德算法的實現方法示意圖；圖4是求一個多項式對GF(2m)上所有元素的值的計算過程示意圖；圖5是本發明的裡德_索羅蒙解碼器實現方法錯誤位置多項式、錯誤值多項式求解一實施方式示意圖；圖6是本發明的裡德-索羅蒙解碼器實現方法一實施方式的多符號式伴隨式計算框圖；圖7是本發明的裡德-索羅蒙解碼器實現方法一實施例的多符號式伴隨式計算框圖；圖8是本發明的裡德-索羅蒙解碼器實現方法一實施例的歐幾裡德算法的實現結構圖；圖9是本發明的裡德-索羅蒙解碼器實現方法一實施例的歐幾裡德算法控制單元狀態圖；圖10是本發明的裡德-索羅蒙解碼器實現方法一實施例的求一個多項式對GF(2m)上所有元素的值的奇數次項之和的實現圖；圖11是本發明的裡德-索羅蒙解碼器實現方法一實施例的求一個多項式對GF(2m)上所有元素的值的偶數次項之和的實現圖。具體實施例方式從改進的歐幾裡德算法的計算流程可知，對錯誤位置多項式ο(X)、錯誤值多項式ω(X)這兩個多項式的求解，改進的歐幾裡德算法只依賴於R(X)和Q(X)兩個多項式的最高階係數和兩個多項式的階數之差。本發明的裡德_索羅蒙解碼器實現方法，是基於改進後的歐幾裡德算法，經過優化後，一實施方式實現示意圖如圖5所示。分別設置一控制器、一運算器、四個移位寄存器，其中移位寄存器一存放多項式R(X)的各階係數，移位寄存器二存放多項式Q(X)的各階係數，移位寄存器三存放多項式λ(X)的各階係數，移位寄存器四存放多項式y(X)的各階係數，移位寄存器一和移位寄存器二有2t+l個單元，從左到右分別存放χ°x2t的係數，移位寄存器三和移位寄存器四有t+Ι個單元，從左到右分別存放χ°Xt的係數，t=(n-k)/2,η為一個碼字的符號數，k為信息碼的符號數，控制器根據R(X)，Q(X)兩個多項式的最高階係數和兩個多項式的階數差控制運算器對四個多項式按照算法流程執行如下操作1.首先初始化，將控制器中的R(X)同Q(X)多項式的階次差置為+1；將控制器中的迭代次數i初始化為O；四個寄存器分別初始化為R(X)=X2t、Q(X)=X*s(x)、λ⑴=0、μΟ為集合{Xj|0彡j彡t，j為整數}中的任意一個元素，比如u(X)=X0S(X)為由伴隨式生成模塊生成的由多個伴隨式構成的伴隨多項式。2.控制器中迭代次數i遞增1，如果移位寄存器一最右端的單元中的R(X)的最高階係數為0，並且移位寄存器二最右端的單元中的Q(X)的最高階係數為0，則4個移位寄存器都右移一次，階次差不變；如果移位寄存器一最右端的單元中R(X)的最高階係數為0，並且移位寄存器二最右端的單元中Q(X)的最高階係數不為0，則移位寄存器一和移位寄存器三兩個移位寄存器都右移一次，同時階次差減一；如果移位寄存器一最右端的單元中R(X)的最高階係數不為0，並且移位寄存器二最右端的單元中Q(X)的最高階係數為0，則移位寄存器二和四都右移一次，同時階次差加如果移位寄存器一最右端的單元中R(X)的最高階係數和移位寄存器二最右端的單元中Q(X)的最高階係數都不為0，並且階次差不小於0，則運算器按照Ri(X)=Iv1Rg⑴--…^(X)，Ai⑴=Iviλη⑴-agμη⑴進行運算，將得到的結果分別寫入移位寄存器一、移位寄存器三，然後再將移位寄存器一和三都右移一次，階次差減一；如果移位寄存器一最右端的單元中R(X)的最高階係數和移位寄存器二最右端的單元中Q(X)的最高階係數都不為0，並且階次差小於0，則運算器按照氏⑴=Iv1Rh(X)-Bi^1Qi-!(X)，λi(X)=bHλ(X)-Bi^1μ(X)，Qi(X)=Rh(X),μi(X)=λ(X)進行運算，將得到的結果分別寫入各移位寄存器，同時將移位寄存器一和三都右移一次，同時階次差置為原階次差的補碼減一；如果迭代次數i達到2t則，進行步驟3；否則進入步驟2。3.將移位寄存器一中存放的多項式R(X)的各階係數輸出作為錯誤值多項式ω(X)的各階係數，將移位寄存器三中存放的多項式λ(X)的各階係數輸出作為錯誤位置多項式ο(X)的各階係數。4.輸入錢搜索模塊及Forney算法模塊。本發明的裡德_索羅蒙解碼器實現方法，由於取消了歐幾裡德算法中階次計算與比較邏輯，綜合面積小；由於採用流水結構，系統頻率高，數據吞吐量大；結構規整，易於硬體實現；延時小且固定。上述是本發明的裡德-索羅蒙解碼器實現方法中錯誤值多項式ω(X)和錯誤位置多項式O(X)的計算方法，在進行上述計算前，伴隨多項式S(X)的計算可以採用多符號式，如圖6所示。首先初始化伴隨式存儲單元Si為0。接收端每個時鐘收到多個符號，每個時鐘將收到的N個符號及在伴隨式存儲單元中的上次計算得到的結果分別同{α(N-m,α(N-2)i...，α1,α°,aNi}相乘，其中α為本原多項式的根，α1為該裡德-索羅蒙碼的生成多項式的第i個根，N為每個時鐘輸入數據的符號個數，N大於1，輸出的結果相加後作為本次伴隨式的結果，以此迭代，直到當前數據塊接收完畢，輸出一個數據塊的伴隨多項式S(X)結果，同時再次把伴隨式存儲單元清為0。對GF(2m-1)域，在計算伴隨多項式時，如果接收的碼字長度不等於2M，需要在每一個塊的塊頭插入零元素，直到新的碼字含有2M個符號。新的碼字順序分成N組，每組有P個符號，每個時鐘輸入N個符號。在進行錯誤值多項式ω(X)和錯誤位置多項式σ(X)的計算之後，進行錢搜索和Forney算法，錢搜索和Forney算法，本質上都是計算某個多項式對Galois有限域所有元素的值，因此該算法依賴於有限域上元素的個數。例如對RS(255，223)碼，最少需要255個時鐘才能遍歷完畢，解碼延時較大，會影響系統性能。由於根據錢搜索和Forney算法計算錯誤位置和錯誤值時需要計算多項式對Galois域所有元素的值，為了加快計算過程，降低整個系統的延時，可以採用並行處理的方式。首先根據系統允許的最大延時和Galois域中元素的個數計算需要把當前元素分成多少組，比如分成N組，每組含有P個元素，在第一個時鐘，計算X從到CIn-1的多項式的值，第二個時鐘計算從^^到α.1的多項式的值，……，直到所有的元素都計算完。把GF(q)空間平均分成N組，每組含有P個元素，這樣該域中的每一個元素可以寫成如下形式α1=aPm+n，0≤m≤N-1，0≤η≤P-I對某一個階數為ν的函數，formulaseeoriginaldocumentpage10formulaseeoriginaldocumentpage10通過同時計算N組的值，可以大大加快掃描速度，降低整個系統的延時。下面是一較佳實施例。在IOGEPON系統中採用了基於流的RS(255，223)作為前向糾錯編碼。該系統對解碼器有如下要求1.數據吞吐量大。解碼器以每個時鐘8個符號的速率勻速接收數據，系統每級流水的最大處理延時不能超過32個時鐘；2.解碼器延時小且固定；3.解碼器在硬體實現時面積小。由於輸入數據每255個符號作為一個數據塊，為了實現方便，每塊前添加一個值為零的符號湊成256個符號作為一個新碼字，然後按照每8個符號一個字把這個數據塊分組，一共分成32個字順次輸入伴隨式計算模塊中。這保證可以在32個周期內計算完伴隨式。formulaseeoriginaldocumentpage10formulaseeoriginaldocumentpage10該公式的實現框圖如圖7所示。在輸入一個數據塊(碼字)之前，將伴隨多項式存儲單元初始化為零，在第一個時鐘輸入新碼字的八個符號，分別同a°k、alk、……，a7k，相乘，其中α為GF(2m)上本原多項式的根，ak為RS編碼生成多項式的第k個根，多項式存儲單元的值同a8k相乘，並將上述相乘得到的值相加存入多項式存儲單元，……，依次，下一個時鐘輸入新碼字的零外八個符號，這樣僅經過32個時鐘周期，一個數據塊的伴隨多項式S(X)即計算完畢。初始化錯誤位置和錯誤值多項式生成模塊(歐幾裡德算法)進行迭代計算。該錯誤位置和錯誤值多項式生成模塊的實現結構如圖8所示。該圖中共有(3t+2)個計算單元和一個控制器。上半部分的(2t+l)個計算單元用於作為兩個長度為2t+l移位寄存器，其中一個作為移位寄存器一存放多項式R(X)的各階係數，另一個作為移位寄存器二存放多項式Q(X)的各階係數，下半部分的(t+Ι)個計算單元用於作為兩個長度為t+Ι移位寄存器，其中一個作為移位寄存器三存放多項式λ(X)的各階係數，另一個作為移位寄存器四存放多項式μ(X)的各階係數；控制器根據R(X)和Q(X)最高階係數是否為0和這兩個多項式的階數差控制所有計算單元。根據不同的狀態，控制器會輸出下面幾種操作方式，如表1所示。表1tableseeoriginaldocumentpage11本實施例中，歐幾裡德算法的控制器狀態如圖9所示。圖中，a_z表示R(X)的最高階的係數是否為0。a_z為1表示為0，否則不為0；b_z表示Q(x)的最高階的係數是否為0。b_z為1表示為0，否則不為0；deg表示兩個多項式的階數差，為有符號整數；i表示循環次數。當計算完成後，R(X)，λ⑴分別輸入Forney模塊和錢搜索模塊。為了在32個時鐘內能搜索完GF(255)內所有的元素，至少需要8個模塊並行掃描。因此把GF(255)分成8個組，每組有32個元素(其中有一個組加入了一個冗餘元素以湊成256個元素)。=σ(α8+1)=EWmi....8m+.Vv...formulaseeoriginaldocumentpage12由於在進行Forney計算時，需要奇次項的和，因此在計算的時候把奇數次項和偶數次項分開。其實現框圖如圖10、圖11所示。圖10為奇數次項之和的實現圖，圖11為偶數次項之和的實現圖。最後把奇數次項和偶數次項合併後得到完整多項式的和。σ(α=σeven(α8幽)+oodd(a8幽)+σ0本發明提出的裡德-索羅蒙解碼器實現方法可以在支持高速數字傳輸系統的同時提供固定低解碼延時。可以同時對裡德-索羅蒙碼的多個符號進行解碼，解碼延時小且固定，結構規整，適合硬體實現，適用於高速數字傳輸系統，特別是高速PON(PassiveOpticalNetwork，以太無源光網絡)系統中。權利要求一種裡德-索羅蒙解碼器實現方法，包括伴隨多項式生成模塊、錯誤位置多項式生成及錯誤值多項式生成模塊、錯誤值檢測模塊、錯誤值計算模塊、錯誤糾正模塊，其特徵在於，錯誤位置多項式生成及錯誤值多項式生成模塊採用以下方式分別設置控制器、運算器、四個移位寄存器，其中移位寄存器一存放多項式R(X)的各階係數，移位寄存器二存放多項式Q(X)的各階係數，移位寄存器三存放多項式λ(X)的各階係數，移位寄存器四存放多項式μ(X)的各階係數，移位寄存器一和移位寄存器二有2t+1個單元，從左到右分別存放x0～x2t的係數，移位寄存器三和移位寄存器四有t+1個單元，從左到右分別存放x0～xt的係數，t＝(n-k)/2，n為一個碼字的符號數，k為信息碼的符號數，控制器根據R(X)、Q(X)兩個多項式的最高階係數和兩個多項式的階數差控制運算器對所述四個多項式按照算法流程執行如下操作一.首先初始化，將控制器中的R(X)同Q(X)多項式的階次差置為+1；將控制器中的迭代次數i初始化為0；四個寄存器分別初始化為R(X)＝X2t、Q(X)＝X·S(X)、λ(X)＝0、μ(X)為集合{Xj|0≤j≤t，j為整數}中的任意一個元素，S(x)為由所述伴隨多項式生成模塊生成的伴隨多項式；二.控制器中迭代次數i遞增1，如果移位寄存器一最右端的單元中的R(X)的最高階係數為0，並且移位寄存器二最右端的單元中的Q(X)的最高階係數為0，則4個移位寄存器都右移一次，階次差不變；如果移位寄存器一最右端的單元中R(X)的最高階係數為0，並且移位寄存器二最右端的單元中Q(X)的最高階係數不為0，則移位寄存器一和移位寄存器三兩個移位寄存器都右移一次，同時階次差減一；如果移位寄存器一最右端的單元中R(X)的最高階係數不為0，並且移位寄存器二最右端的單元中Q(X)的最高階係數為0，則移位寄存器二和四都右移一次，同時階次差加一；如果移位寄存器一最右端的單元中R(X)的最高階係數和移位寄存器二最右端的單元中Q(X)的最高階係數都不為0，並且階次差不小於0，則運算器按照Ri(X)＝bi-1Ri-1(X)-ai-1Qi-1(X)，λi(X)＝bi-1λi-1(X)-ai-1μi-1(X)進行運算，將得到的結果分別寫入移位寄存器一、移位寄存器三，同時將移位寄存器一和三都右移一次，同時階次差減一；如果移位寄存器一最右端的單元中R(X)的最高階係數和移位寄存器二最右端的單元中Q(X)的最高階係數都不為0，並且階次差小於0，則運算器按照Ri(X)＝bi-1Ri-1(X)-ai-1Qi-1(X)，λi(X)＝bi-1λi-1(X)-ai-1μi-1(X)，Qi(X)＝Ri-1(X)，μi(X)＝λi-1(X)進行運算，將得到的結果分別寫入各移位寄存器，同時將移位寄存器一和三都右移一次，同時階次差置為原階次差的補碼減一；如果迭代次數i達到2t則進行步驟三；否則進行步驟二；三.將移位寄存器一中存放的多項式R(X)的各階係數輸出作為錯誤值多項式的各階係數，將移位寄存器三中存放的多項式λ(X)的各階係數輸出作為錯誤位置多項式的各階係數。2.根據權利要求1所述的裡德_索羅蒙解碼器實現方法，其特徵在於，伴隨多項式S(X)生成時，初始化伴隨式存儲單元Si為0，每個時鐘將收到的N個符號及在伴隨式存儲單元中的上次計算得到的結果分別同{廣-1」，^-2)、.，？，^，^}相乘，其中a為本原多項式的根，a1為該裡德_索羅蒙碼的生成多項式的第i個根，N為每個時鐘輸入數據的符號個數，N大於1，輸出的結果相加後作為本次伴隨式的結果，以此迭代，直到當前數據塊接收完畢，輸出一個數據塊的伴隨多項式S(X)結果，同時再次把伴隨式存儲單元清為0。3.根據權利要求2所述的裡德-索羅蒙解碼器實現方法，其特徵在於，在計算伴隨多項式時，如果接收的碼字長度不等於2M，M為組成一個符號的二進位序列個數，則在每一個碼字塊頭插入零元素，直到新的碼字含有2M個符號，新的碼字順序平均分成N組，每個時鐘從每組分別輸入一個符號共N個符號。4.根據權利要求1所述的裡德_索羅蒙解碼器實現方法，其特徵在於，n=255，k=223，t=16。全文摘要本發明公開了一種裡德-索羅蒙解碼器實現方法，在對錯誤位置多項式、錯誤值多項式求解時，通過控制器、運算器、四個移位寄存器實現，可以同時對裡德-索羅蒙碼的多個符號進行解碼，解碼延時小且固定，結構規整。文檔編號H03M13/15GK101834616SQ20091005694公開日2010年9月15日申請日期2009年3月12日優先權日2009年3月12日發明者李東川,王星,胡新宇申請人:普然通訊技術(上海)有限公司;普然技術公司