基于歐氏算法和頻譜結構分析相結合的RS硬件解碼方案

差錯控制編碼技術(shù)對改善誤碼率、提高通信的可靠性具重要作用。RS碼既可以糾正隨機錯誤，又可以糾正突發(fā)錯誤，具有很強的糾錯能力，在通信系統中應用廣泛。由于RS碼的譯碼復雜度高，數字運算量大，常見(jiàn)的硬件及軟件譯碼方案大多不能滿(mǎn)足高速率的傳輸需求，一般適用于10Mbps以下。本文提出的歐氏算法和頻譜結構分析相結合的RS硬件解碼方案，適用于FPGA單片實(shí)現，速率高、延遲小、通用性強、使用靈活。筆者在FPGA芯片上實(shí)現了GF（2 8）上符號速率為50Mbps的流式解碼方案，最大延時(shí)為640ns，參數可以根據需要靈活設置。

　　1 RS碼的結構

　　碼字長(cháng)度為N=q-1(q=2i)，生成多項式為，αi∈GF(q) 的RS碼有最小碼距δ=2t+1，能夠糾正t個(gè)隨機或突發(fā)錯誤[1]。本文列舉的方案測試中采用的RS碼主要參數為N=255、m0=0、t=8，其中 GF（2 8）的生成多項式為g（x）=x8+x4+x3+x2+1。由于RS碼的編碼邏輯結構比較簡(jiǎn)單，文中僅給出仿真結果。

　　2 RS碼的譯碼算法

　　RS譯碼算法一般分為三步：伴隨式計算、關(guān)鍵方程獲得和錯誤圖樣的求解。其中關(guān)鍵方程的獲得是RS譯碼中最困難、最為關(guān)鍵的一步。

　　在利用伴隨式求解關(guān)鍵方程時(shí)，BM算法和Euclidean（歐氏）算法是兩種較好的選擇。BM算法涉及大量的變量存儲和復雜的邏輯控制，適用于軟件編程而不適合硬件實(shí)現。歐氏算法數據存儲量少、控制便捷，適合硬件實(shí)現。且采用歐氏算法確定關(guān)鍵方程所需時(shí)間與錯誤個(gè)數成正比，因此從處理時(shí)間上考慮，歐氏算法也是較好的選擇。

　　在獲得關(guān)鍵方程后，采用時(shí)域處理方法，需要大量的運算單元和控制電路，在硬件實(shí)現中是不可取的。而采用頻譜結構分析方法，利用最短線(xiàn)性移位寄存器綜合及離散傅氏逆變換進(jìn)行處理，邏輯簡(jiǎn)單、耗時(shí)少，適合硬件實(shí)現。雖然在傅氏變換時(shí)需要較多的邏輯單元，但對GF（2n）在n10的情況下，變換域譯碼器要比時(shí)域譯碼器簡(jiǎn)單得多。因而本文提出歐氏算法和頻譜結構分析相結合的方案，并在實(shí)踐中獲得了較好的效果。

　　Euclidean算法[3]步驟如下：

　?。?）按所列方法進(jìn)行迭代

　　3 方案流程

　　方案流程框圖如圖1所示。

　　3.1 伴隨式S0,S1,…，S2t-1的計算

　　令r1,r2，…，rn為接收到的RS碼字，根據系統碼監督矩陣的特性，可構造如圖2所示伴隨式計算電路Si=（（（r1αi+r2）αi+r3）αi…+rn，從而實(shí)際伴隨式序列的計算。

　　3.2 利用伴隨式確定關(guān)鍵方式

　　Euclidean算法的難點(diǎn)主工在于迭代計算過(guò)程中存在的被除數多項式和除數多項式長(cháng)度的不確定性，使每次計算中產(chǎn)生的商序列的長(cháng)度不等，以及因此可能涉及到的不定長(cháng)多項式的相乘和相加問(wèn)題，增加了硬件設計的難度。系統采用了嵌套雙循環(huán)的方法，利用'時(shí)鐘產(chǎn)生2'控制外循，'時(shí)鐘產(chǎn)生1'控制內循環(huán)，從而優(yōu)化了算法，得到了問(wèn)題的解決方案。在獲得伴隨式的基礎上，圖3電路可具體完成Euclidean算法對關(guān)鍵方程的求解 σ（x）=σtxt+σt-1xt-1+…+σ1x+1。

　　3.3 利用最短線(xiàn)性移位寄存器綜合和離散傅氏變換獲取錯誤圖樣

　　在得到關(guān)鍵方程后，首先應進(jìn)行錯誤位置（關(guān)鍵方程的根）的確定，這樣可減小電路的規模；利用錢(qián)搜索[1]（工程上求解σ（x）根的實(shí)用方法）的方法可以簡(jiǎn)捷的確定錯誤位置。然后，啟動(dòng)最短線(xiàn)性移位寄存器綜合和離散傅氏逆變換，經(jīng)過(guò)N次（運算所在域的長(cháng)度）迭代，即可求得對應各個(gè)錯誤位置的錯誤圖樣，如圖4所示。用錯誤圖樣對接收碼字進(jìn)行糾錯，就可得到正確的信息序列。

　　3.4 RS編譯碼在FPGA上的實(shí)現

　　有限域的乘法、加法運算單元和各模塊的控制邏輯設計是系統成功的關(guān)鍵。涉及有限域的各個(gè)運算單元的運算速度制約了譯碼器的速度，而控制邏輯引導了譯碼的流程。硬件電路的軟件開(kāi)發(fā)工具給設計復雜電路提供了簡(jiǎn)捷思路。系統采用了QUARTUS與第三方軟件相結合的方法，用VHDL語(yǔ)言設計了大部分功能模塊。特別是在乘法器設計中，乘數確定、被乘數不定的有限域乘法器，經(jīng)邏輯綜合和優(yōu)化設計后，運算速度可分別在6.8ns和11.6ns內完成，完全可以滿(mǎn)足系統符號速率50Mbps的要求。應該指出，系統速度的進(jìn)一步提高受到求逆運算的限制，求逆運算沒(méi)有明確的數學(xué)結構（通常采用查表的方法），這是制約運算速度的瓶頸。但針對流式譯碼算法，上述結構已能滿(mǎn)足要求。

　　4 仿真結果

　　4.1 編碼器的仿真

　　仿真的時(shí)鐘頻率為50MHz，在EN為高電平時(shí)輸入信息有效。為簡(jiǎn)單起見(jiàn)，采用系統碼的縮短型，即信息為（00，00，…，00，02，01，02）.編碼器的仿真結果如圖5所示。其中，IN為輸入信息， CLK為系統時(shí)鐘，C為編碼輸出（輸入和輸出均為16進(jìn)制）。

4.2 譯碼器的仿真

　　首先，給出系統的仿真全貌，如圖6所示。其中C為接收到的RS碼，SP為伴隨式 S15,shang為運用歐氏算法得到的商序列，SeryDA為S序列，anssd和ERTD分別對應碼字可能存在的第四個(gè)錯誤位置和錯誤值，仿真中的接收碼在位置（105，106，107，108，109，110，111，112）上錯誤均為（01）HEX。

　　伴隨式的計算結果：S15，S14，…，S1，S0為（FD，8D），CE，4A，51，B2，A1，CA，C4，0D，73，56，A6，F5，01），圖6和圖7中的sp即為S15。

　　這里重點(diǎn)給出利用伴隨式計算關(guān)鍵方程的電路仿真結果，如圖7所示。當輸入伴隨式結果以后，運算電路啟動(dòng)，在計算商序列的同時(shí)進(jìn)行聯(lián)接多項式的迭代運算。歐氏算法的商序列shang為：（FF，58），（37，92），（50，45），（E9，C7），（F4，B9），（5D，33），（87，8F）。當滿(mǎn)足終止條件以后顯示標志QQC，同時(shí)，給出關(guān)鍵方程系數如圖7中（AI，AH，AG，AF，AE，AD，AC，AB，AA）即（00，19，2E，EC，A8，AD，41，E6，95），對應有限域上的表達式為：

　　δ（x）=α193x7+α130x6+α122x5+α144x4+α252x3+α191x2+α160x+α184; 有解為（α105，α106，α107，α108，α109，α110，α111），與假定錯誤位置完全一致。然后求解S序列，同時(shí)針對各錯誤位置進(jìn)行 IDFT，就可以得到對應的錯誤值。圖6中anssd和ERTD表示位置108上存在的錯誤為（01）HEX。

　　系統仿真表明，譯碼器獲得的錯誤位置和錯誤圖案與實(shí)際假設的錯誤位置（105，106，107，108，109，110，111）和錯誤值（01）HEX完全一致。

　　基于A(yíng)PEX架構的可編程單芯片RS編譯碼硬件解決方案在中國普天集團西安藍牙通訊設備有限公司的二次群無(wú)線(xiàn)擴頻通信機的改造項目中得到了應用。它可用于離散譯碼、流式譯碼，在添加一級緩存的基礎上，同樣適用于連續譯碼。