大約束長度卷積碼編碼器的改進(jìn)與實(shí)現(xiàn)*

張濤濤，王滿喜，榮 輝，楊志飛

（1.電子信息系統(tǒng)復(fù)雜電磁環(huán)境效應(yīng)國家重點(diǎn)實(shí)驗(yàn)室，河南 洛陽 471003；2.中國洛陽電子裝備試驗(yàn)中心，河南 洛陽 471003）

0 引 言

對于卷積碼而言，并沒有可用的代數(shù)結(jié)構(gòu)構(gòu)造好的卷積碼編碼器?？紤]到生成多項(xiàng)式為G(X)=1+X+X2+X4+X8+X10的（15，5）BCH 碼 的 最小距離dg=7，對偶碼的生成多項(xiàng)式是h(X)=(X15-1)/g(X)=X5+X3+X+1且dg=4。符合生成多項(xiàng)式g(D)=1+D+D2+D4+D5+D8+D10且碼率為R=1/2的卷積碼有dfree≥min(7,8)。生成矩陣為 G(D)=[1+D+D2+D4+D51+D2]?？梢钥闯觯摼幋a器的最小自由距離為dfree=7，約束長度為5。類似的構(gòu)造可以產(chǎn)生碼率為1/2的卷積碼，然而構(gòu)造這類卷積碼有兩個(gè)困難。第一個(gè)難題是尋找具有最大自由距離的大約束長度的卷積碼，第二個(gè)難題是此限與循環(huán)碼的最小距離有關(guān)。該難題已由Juestesen解決[1]。Jusetesen的構(gòu)造限dfree≥dg，但它涉及到關(guān)于g(X )根的條件相當(dāng)復(fù)雜，且在二進(jìn)制情況下，僅僅可用來構(gòu)造奇數(shù)n值的卷積碼。Tanner的構(gòu)造得到限dfree≥dmin，其中dmin是相聯(lián)系的循環(huán)碼的最小距離[2]。

一般構(gòu)造大約束長度的卷積碼要考慮編碼器的性能。卷積碼編碼器的糾錯(cuò)能力與自由距離之間存在緊密聯(lián)系。具體來講，編碼器的性能與卷積碼的自由距離之間存在正相關(guān)關(guān)系。也就是說，編碼器的性能會隨自由距離的增加而得到改善。因此，要改善編碼器的性能，就要從卷積碼的自由距離入手，通過分析對比大約束長度卷積碼編碼器的自由距離，達(dá)到尋找好的大約束長度卷積碼編碼器的目的。一旦卷積碼的碼率確定了，就可以把卷積碼的自由距離和距離譜作為尋找好的卷積碼編碼器的指導(dǎo)。維特比譯碼和序列譯碼的性能主要受卷積碼的列距離特性的影響[3]。對于序列譯碼，卷積碼的列距離dl應(yīng)該隨著l增加，至少是非減少的[4-6]，由此得到具有良好距離特性的卷積碼。

1 已有的搜索算法

大多數(shù)情況下，搜索大約束長度卷積碼的工作量隨著卷積碼約束長度的增加而迅速增加。利用計(jì)算機(jī)搜索好的大約束長度的卷積碼是非常耗時(shí)的運(yùn)算，因此計(jì)算機(jī)搜索只能被限定在較短的約束長度。但是，即便對于小的約束長度，窮搜索的方法也是不可行的[7-8]。因此，需要提出新的篩選規(guī)則尋找好的卷積碼。Bahl、Cullum、Frazer和Jelinek提出了一種的基于維特比算法尋找dfree和Adfree的計(jì)算機(jī)搜索方法[9]，并由Larsen修改[10]該算法，假設(shè)接收到的序列全是零，把在柵格中的搜索限制在以一個(gè)非零信息分組開始的路徑，采用0量度代表一致，+1代表不一致，搜索具有最小量度的路徑。一旦在零狀態(tài)的幸存路徑的量度低于或等于其他所有路徑，算法就可以停止。所以，在全零狀態(tài)下的量度就等于dfree，這是因?yàn)闆]有一條其他幸存的路徑能以更小的量度匯合到全零狀態(tài)。對于惡性編碼器，由于狀態(tài)圖中的零環(huán)路，在全零狀態(tài)下的幸存路徑可能無法達(dá)到最小的量度。該算法能夠計(jì)算約束長度為20的卷積碼的dfree和最小自由距離為dfree的個(gè)數(shù)Adfree。對于更大的約束長度，算法要存儲的空間數(shù)隨著約束長度的增加呈指數(shù)倍數(shù)增加而無法滿足，因此必須嘗試其他方法來尋找dfree。

2 改進(jìn)的搜索算法

對于較大的約束長度，目前還沒有通用的計(jì)算dfree的方法。傳統(tǒng)的利用計(jì)算機(jī)搜索大約束長度的卷積碼的算法在文獻(xiàn)[11-12]中已有介紹，能做到的最大約束長度不超過30。為了能夠找到約束長度在30以上的卷積碼，需找到一種新的方法尋找更大約束長度的卷積碼。

單次尋找大約束長度最優(yōu)卷積碼的算法流程如圖1所示。

圖1 計(jì)算機(jī)搜索卷積碼的堆棧算法流程

通過對卷積碼自身特性和堆棧算法的研究，提出了快速尋找有限數(shù)量好的大約束長度的卷積碼方法。

（1）隨機(jī)設(shè)計(jì)首位和末位分別為1，生成多項(xiàng)式重量不同時(shí)為偶的編碼器。

（2）檢驗(yàn)（1）中設(shè)計(jì)的編碼器的距離分布特性。

（3）驗(yàn)證（1）中設(shè)計(jì)的編碼器的自由距離是否符合預(yù)估的上限和下限。

對于碼樹圖中的節(jié)點(diǎn)，需要設(shè)置一個(gè)結(jié)構(gòu)體。該結(jié)構(gòu)體中應(yīng)該包含有分裂到該節(jié)點(diǎn)的狀態(tài)、該節(jié)點(diǎn)的碼重、當(dāng)前節(jié)點(diǎn)的量度和當(dāng)前的狀態(tài)到全零狀態(tài)所需的最少分裂次數(shù)。算法開始時(shí)，放置一個(gè)初始狀態(tài)為1，碼重為2，當(dāng)前的狀態(tài)到全零狀態(tài)所需的最少分裂次數(shù)為編碼器的約束長度，節(jié)點(diǎn)的量度為碼重和當(dāng)前狀態(tài)到全零狀態(tài)所需最少分裂次數(shù)的和。對棧頂?shù)墓?jié)點(diǎn)進(jìn)行分裂，每次分裂都是分別進(jìn)行0和1的分裂。如果分裂后的節(jié)點(diǎn)的碼重滿足設(shè)定的上限，則把該節(jié)點(diǎn)存儲在堆棧，把堆棧的頂節(jié)點(diǎn)覆蓋，并根據(jù)每個(gè)節(jié)點(diǎn)的量度進(jìn)行完全排序，使較快回到全零狀態(tài)的節(jié)點(diǎn)排在棧頂，為下一次的分裂做好準(zhǔn)備。排序的目的主要是為了分裂較快回到全零狀態(tài)的節(jié)點(diǎn)。如果當(dāng)前的節(jié)點(diǎn)到達(dá)樹的終點(diǎn)且節(jié)點(diǎn)的碼重未超過設(shè)定的上限，則存儲該節(jié)點(diǎn)至另一塊內(nèi)存空間。如果存儲的節(jié)點(diǎn)狀態(tài)點(diǎn)到達(dá)了全零且碼重不大于設(shè)定上限、節(jié)點(diǎn)的數(shù)目小于設(shè)定的存儲數(shù)目，總的計(jì)算量小于Clim，則繼續(xù)分裂節(jié)點(diǎn)；否則，輸出存儲的節(jié)點(diǎn)。

該算法能夠停下來的二個(gè)條件：

（1）存儲滿足條件的節(jié)點(diǎn)等于設(shè)定的數(shù)目；

（2）總的計(jì)算量超過了Clim。

一旦該算法滿足上述結(jié)束條件，該算法就停止。只要是一個(gè)堆棧，堆棧的容量是確定的，就有可能出現(xiàn)堆棧滿的情況?？紤]到存放在堆棧底部的節(jié)點(diǎn)被選擇作為最優(yōu)路徑上的節(jié)點(diǎn)的可能性非常小，通常在堆棧滿的情況下，用堆棧頂部的進(jìn)行0分裂的節(jié)點(diǎn)覆蓋當(dāng)前的棧頂節(jié)點(diǎn)，而進(jìn)行1分裂后的節(jié)點(diǎn)覆蓋堆棧底部的節(jié)點(diǎn)。因此，該堆棧成為首尾相連的循環(huán)堆棧。每進(jìn)行一次分裂都要進(jìn)行排序。為了方便排序和堆棧的棧頂指向，需要設(shè)置一個(gè)堆棧指針始終指向棧頂。由于排序需要耗費(fèi)大量的時(shí)間，堆棧的長度不易較大。為了使碼樹能夠充分分裂，堆棧的長度也不易過小。綜合以上兩方面考慮，堆棧的大小應(yīng)該根據(jù)卷積碼的約束長度取一個(gè)較為合適的值。利用該搜索算法找到的部分具有較大約束長度的卷積碼如表1所示，其中生成多項(xiàng)式使用十六進(jìn)制表示。

3 仿真測試

卷積碼的性能必須通過加噪聲的信道進(jìn)行檢驗(yàn)，以檢驗(yàn)編碼器在不同信道比條件下的誤碼率。采用費(fèi)諾譯碼算法在受擾信道中檢驗(yàn)，以測定大約束長度卷積碼在噪聲干擾情況下對誤碼率的改善情況。圖2給出了約束長度為60和32的大約束長度卷積碼在不同信噪比下出現(xiàn)錯(cuò)誤幀的概率?？梢钥闯觯?dāng)約束長度固定時(shí)，隨著信噪比的增加，錯(cuò)誤幀的概率降低；當(dāng)信噪比固定時(shí)，隨著約束長度的增加，錯(cuò)誤幀的概率明顯得到改善。

表1 計(jì)算機(jī)搜索大約束長度卷積碼

圖2 不同信噪比下不同約束長度卷積碼性能對比

4 結(jié) 語

本文提出了一種改進(jìn)的大約束長度卷積碼搜索算法，利用該搜索算法可以找到約束長度大于30的卷積碼編碼器。利用費(fèi)諾譯碼算法對不同約束長度的卷積碼編碼器的性能進(jìn)行檢驗(yàn)，結(jié)果表明，通過該搜索算法找到的大約束長度卷積碼的在同等信噪比的情況下的誤碼率較低。