基于FPGA的前向糾錯算法

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

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

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

RS碼即里德-所羅門(mén)碼，它是能夠糾正多個(gè)錯誤的糾錯碼，具有同時(shí)糾正突發(fā)性錯誤和隨機性錯誤的能力[2]，而且編解碼相對簡(jiǎn)單?？紤]到系統的誤碼率和資源耗用，擬采用RS碼作為前向糾錯碼。

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

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

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

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

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

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

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

生成多項式：

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

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

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

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

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

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

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

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

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

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

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

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

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

整個(gè)電路系統都在同一系統時(shí)鐘CLK下工作，高電平復位。

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

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

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

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

對整個(gè)測試系統的編譯結果如下：

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

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