基于FPGA的前向糾錯算法

摘要：研究數(shù)字音頻無線傳輸中的前向糾錯(FEC)算法的設(shè)計及實現(xiàn)，對前向糾錯中的主要功能模塊，如RS編解碼、交織器與解交織器等給出基本算法及基于現(xiàn)場可編程門陣列(FPGA)和硬件描述語言的解決方案。選用硬件描述語言VerilogHDL，在開發(fā)工具QuartusII4．2中完成軟核的綜合、布局布線和匯編，在Modelsim中進(jìn)行時序仿真驗證，最終下栽到開發(fā)板中進(jìn)行電路驗證及測試。
關(guān)鍵詞：RS碼；交織；現(xiàn)場可編程門陣列；前向糾錯

1 引言
目前，無線產(chǎn)品的廣泛應(yīng)用使無線音頻和視頻的高質(zhì)量傳輸成為可能。藍(lán)牙、無限局域網(wǎng)等無線傳輸設(shè)備比較復(fù)雜，成本較高，急需開發(fā)一種簡便的、僅用于流媒體的無線傳輸平臺，將音頻數(shù)據(jù)實時地發(fā)送到移動終端。由于音頻數(shù)據(jù)的實時性，不宜采用反饋重傳等造成很大時延的差錯控制方式。前向糾錯碼(FEC)的碼字是具有一定糾錯能力的碼型，它在接收端解碼后不僅可以發(fā)現(xiàn)錯誤，而且能夠判斷錯誤碼元所在的位置并自動糾錯。這種糾錯碼信息不需要儲存，不需要反饋，實時性好，故可選擇前向糾錯來實現(xiàn)差錯控制。

筆者設(shè)計的系統(tǒng)指標(biāo)如下：
●當(dāng)信道誤碼率為3x10-3時，經(jīng)過前向糾錯，誤碼率降到10-7以下；
●數(shù)據(jù)源使用的是S/PDIF民用數(shù)字音頻格式標(biāo)準(zhǔn)[1]；
●信號時延遠(yuǎn)小于人的分辨能力(40ms)；
●芯片資源耗用不超過20萬門；

RS碼即里德-所羅門碼，它是能夠糾正多個錯誤的糾錯碼，具有同時糾正突發(fā)性錯誤和隨機性錯誤的能力[2]，而且編解碼相對簡單。考慮到系統(tǒng)的誤碼率和資源耗用，擬采用RS碼作為前向糾錯碼。

在無線信道中，比特差錯經(jīng)常成串發(fā)生，這是由于持續(xù)時間較長的衰落谷點會影響到幾個連續(xù)的比特，而信道編碼僅在檢測和校正單個差錯和不太長的差錯串時才最有效。為了糾正這些成串發(fā)生的比特差錯及一些突發(fā)錯誤，可以運用交織技術(shù)來分散這些錯誤，使長串的比特差錯變成短串差錯，從而可以用前向碼對其糾錯。

用本系統(tǒng)傳輸數(shù)據(jù)時，在發(fā)端先對數(shù)據(jù)進(jìn)行RS編碼(外碼)，再進(jìn)行交織處理，最后再進(jìn)行RS編碼(內(nèi)碼)。收端次序和發(fā)端相反，先進(jìn)行內(nèi)碼解碼，接著進(jìn)行去交積處理完成錯誤分散，最后進(jìn)行外碼解碼，糾正內(nèi)碼未能糾正的錯誤。通過這種2維的RS編解碼，可以充分利用RS碼糾錯能力強的特點，降低系統(tǒng)的誤碼率。也可考慮使用迭代譯碼[3]。若1次2維譯碼的效果無法滿足需求，則將譯碼后的數(shù)據(jù)反饋回譯碼器，進(jìn)行1次迭代譯碼。迭代次數(shù)的增加會帶來相應(yīng)的資源開銷和時延的增加。

2 系統(tǒng)結(jié)構(gòu)及實現(xiàn)
糾錯編碼使用2維RS碼。內(nèi)碼采用(10，8)Rs碼，q=4，每個碼字含32bit數(shù)據(jù)。外碼采用(20，16)RS碼，q=8，每個碼字含128個數(shù)據(jù)。交織器大小為1 280bit。以1 280bit為1幀，幀之間預(yù)留信息時隙。

下面詳細(xì)介紹交織器，解交織器和(20，16)RS編碼器，解碼器模塊的原理及FPGA實現(xiàn)。(10，8)RS編碼器，解碼器的原理與(20，16)RS編碼器，解碼器基本相同。

2．1(20，16)RS編碼器
RS碼是BCH碼的重要子類。由于具有同時糾正突發(fā)性錯誤和隨機性錯誤的能力，且糾正突發(fā)性錯誤更有效，因而被廣泛地應(yīng)用。

(20，16)RS編碼器完成RS編碼功能，每輸入16個碼元，延遲1個時鐘原樣輸出，并在其后添加4個校驗碼元，構(gòu)成20個碼元的輸出碼字。因此數(shù)據(jù)輸入16個碼字后應(yīng)預(yù)留至少4個碼字的空隙，避免數(shù)據(jù)丟失。

(20，16)RS是(255，251)RS的縮短碼，它是在有限域GF(28)上運算得到的，把(255，251)RS的前235個碼元都當(dāng)作0就得到(20，16)RS碼。碼參數(shù)如下：
碼長N=20，信息位個數(shù)K=16，校驗位N-K=4，糾錯能力T=2，碼距D=5；
本原多項式：

生成多項式：

其中，α是(20，16)RS的本原域元素。
編碼采用除法方式實現(xiàn)，其原理如圖1所示。

整個電路實際上是GF(28)的除法電路。圖中乘單元的系數(shù)是生成多項式G(x)的對應(yīng)項系數(shù)，對應(yīng)的除法電路的除數(shù)是

被除數(shù)的系數(shù)是輸人數(shù)據(jù)的8bit碼元，按照輸入順序進(jìn)行降冪排列。第1個輸入碼元是x19的系數(shù)，最后1個輸入碼元是x4的系數(shù)。系數(shù)都是本原多項式P(x)生成的二元擴(kuò)域GF(28)中的元素。在16個碼字都輸入后，寄存器D1-D4中保存的數(shù)據(jù)分別是常數(shù)項，x項，x2項和x3項的系數(shù)，它們就是所得到的校驗碼。數(shù)據(jù)選擇電路用來對不同數(shù)據(jù)進(jìn)行選擇輸出。前16個時鐘，輸人數(shù)據(jù)按照順序輸出，后4個時鐘輸出計算得到的校驗碼。所有輸出數(shù)據(jù)較之輸入數(shù)據(jù)都要延遲1個時鐘周期，時鐘上升沿同步輸出。電路中的主要部分就是GFf(28)中的乘法單元和模加單元。

2．2(20,16)RS解碼器
該電路完成(20，16)RS碼的解碼工作，將20個8bit碼元解碼為16個8bit的碼元。同時輸出碼字起始信號、數(shù)據(jù)有效信號和校驗位有效信號。解碼器的原理如圖2所示。

RS碼時域譯碼法主要有P-G-z法、B-M法[4]和歐氏法。由于P-G-Z法要求解有限域上的逆矩陣，不利于實現(xiàn)，因此工程上很少使用。B-M法和歐氏法都是快速遞歸法，二者等效[5]，易于硬件實現(xiàn)，因此得到廣泛使用。在本次設(shè)計中，采用的解碼算法是B-M算法。

RS碼時域譯碼由以下幾步組成：
(1)伴隨式計算電路。伴隨式S1-S4是用于查錯和糾錯的主要參數(shù)。在伴隨式計算模塊中，先進(jìn)行余式計算，然后根據(jù)余式計算伴隨式并輸出。計算余式是指在GF(28)域中將以輸入碼元為系數(shù)的x的多項式作為被除數(shù)，除以本原多項式得到余式。1個碼元對應(yīng)1個余式。得到全部余式以后將各余式的x同冪次系數(shù)組合即得到伴隨式。

(2)差錯位置多項式系數(shù)計算電路。用于計算差錯位置多項式R(x)的系數(shù)A1和A2的值。為實現(xiàn)此目的，需要求解4個非線形方程。在設(shè)計中采用迭代的方法來完成這一要求。A1和A2是差錯位置多項式的2個系數(shù)。如果輸入數(shù)據(jù)無錯，那么A1=A2=0。如果有1個錯誤，則A2=0，只需計算求得A1的值。

(3)差錯位置計算電路。實現(xiàn)該過程時，用存儲器Ds記錄多項式D1和D2分別記錄記錄A1x和A2x2的值。每當(dāng)1個新的數(shù)據(jù)到來時，D1和D2都乘α(位置變化1位)，再把得到的新值代入Ds以驗證是否是方程的根。這樣，只需在每個數(shù)據(jù)到來的時刻判斷當(dāng)前Ds=0是否成立，就可判斷當(dāng)前數(shù)據(jù)是否有錯。

(4)誤碼元錯誤幅度計算電路。此模塊的功能是當(dāng)數(shù)據(jù)有錯時(由s進(jìn)行判斷)計算錯誤碼元的錯誤幅度。e是計算得到的錯誤幅度與相應(yīng)碼元相異或得到的值，可消除錯誤。如果當(dāng)前碼元無錯，那么e=0。

(5)輸入數(shù)據(jù)緩存FIFO。此模塊的功能是將原始碼字延遲一定周期輸出，以便與錯誤幅度的輸出同步。由雙端口RAM構(gòu)成的可復(fù)位。FIFO實現(xiàn)此功能。

(6)糾錯電路。此模塊完成最后的糾錯功能，通過與誤碼錯誤幅度e異或來實現(xiàn)。data_temp是從FIFO輸出的數(shù)據(jù)。data_out即為糾正錯誤后的數(shù)據(jù)輸出。以上整個糾錯過程有43個時鐘的延時。

(7)數(shù)據(jù)輸出電路。此模塊主要完成2項功能：生成糾錯失敗信號fail和輸出最終數(shù)據(jù)。fail信號的生成過程其實就是再求1次伴隨式s。的過程。若計算出的s1不為0，則說明糾錯不成功，將原始輸入數(shù)據(jù)原樣輸出，同時fail信號輸出高電平。否則，說明糾錯成功，將糾錯后的碼字輸出，。fail保持低電平。本過程有20個時鐘的延時。

上面設(shè)計的解碼電路的關(guān)鍵就是GF(28)域中乘除法單元的硬件實現(xiàn)[6]?；?a class="contentlabel" href="http://www.ex-cimer.com/news/listbylabel/label/FPGA">FPGA存儲器資源豐富的特點，設(shè)計中采用了查：ROM表的辦法來實現(xiàn)乘除功能。

整個電路系統(tǒng)都在同一系統(tǒng)時鐘CLK下工作，高電平復(fù)位。

2．3交織器組
本設(shè)計中，外編碼器的輸出按行進(jìn)入1280bit的交織器，1個交織器存儲32個外碼碼字，然后對交織器的內(nèi)容按列讀出。根據(jù)交織器的特性，需要將數(shù)據(jù)完全裝入后才能讀出。在讀出時，不能向交織器內(nèi)寫數(shù)據(jù)。數(shù)據(jù)的輸入是連續(xù)的，需要具有緩存功能的模塊對數(shù)據(jù)進(jìn)行緩存。采用1組2個交織器輪流讀寫的方法來保證數(shù)據(jù)的連續(xù)性。2個交織器的輸出也是輪流進(jìn)行的，當(dāng)1個交織器填充完畢進(jìn)行輸出時，來自外碼編碼器的數(shù)據(jù)將被存儲到另1個交織器中。交織器組的架構(gòu)如圖3所示。

本設(shè)計中，交織器的大小是1280bit，這主要是基于以下幾方面的考慮。
(1)交織器不宜過大。由于必須完全寫滿后再讀出，數(shù)據(jù)通過交織器的延遲與交織器大小成正比。因此，較大的交織器會影響整個系統(tǒng)的延時。所以，在保證效果的前提下，交織器要設(shè)計得盡量小。

(2)交織器的大小存在下限，即交織器有交織深度的最小限制[7]。以本設(shè)計為例，接收時第1級解碼為(20，16)，第2級為(10，8)，則第2級的每個碼字中不應(yīng)有2個碼元來自于第1級解碼器的輸出。否則，如果第1級解碼器有未成功的解碼(多于2個錯誤碼元)，則第2級解碼器的輸入碼元中存在多于1個的錯誤碼元的概率大大增加。因此，在本設(shè)計中，交織器的下限為第1級解碼器的輸出碼字的10倍，也就是160字節(jié)。設(shè)計采用的交織器大小恰為下限。

3 系統(tǒng)驗證及結(jié)論
系統(tǒng)的整體實現(xiàn)與時序驗證均使用Altera0uartusIl4．2和Modelsim5．7完成。FEC系統(tǒng)中各個模塊及頂層控制部分全部使用VerilogHDI。設(shè)計。實現(xiàn)時選擇的目標(biāo)器件是Altera Cyclone公司的EPlC20F400C7。

對整個測試系統(tǒng)的編譯結(jié)果如下：

在各種信道誤碼率和不同頻率下進(jìn)行了電路測試，測試結(jié)果如表1所示。

根據(jù)以上分析，本設(shè)計達(dá)到了性能指標(biāo)。當(dāng)誤碼率適當(dāng)降低時，糾錯效果的提升非常明顯。該系統(tǒng)在對S/PDIF格式的音頻數(shù)據(jù)進(jìn)行編碼和解碼時共延時3ms。若工作于更高頻率，則延時可按比例減小。采用雙相標(biāo)識碼串行輸入作為數(shù)據(jù)來源時，數(shù)據(jù)吞吐量最大可達(dá)到32Mb/s，若采用其他數(shù)據(jù)來源，數(shù)據(jù)吞吐量最大可達(dá)178Mb/s。因此，此系統(tǒng)不僅可對音頻信號進(jìn)行前向糾錯編解碼，還可應(yīng)用于數(shù)據(jù)量更大的視頻信號等的其他數(shù)據(jù)傳輸。