基于FPGA的前向糾錯(cuò)算法

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

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

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

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

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

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

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

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

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

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

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

生成多項(xiàng)式：

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

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

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

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

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

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

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

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

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

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

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

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

上面設(shè)計(jì)的解碼電路的關(guān)鍵就是GF(28)域中乘除法單元的硬件實(shí)現(xiàn)[6]。基于FPGA存儲(chǔ)器資源豐富的特點(diǎn)，設(shè)計(jì)中采用了查：ROM表的辦法來實(shí)現(xiàn)乘除功能。

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

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

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

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

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

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

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

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