Turbo碼S隨機交織器的實現(xiàn)*

錢 宏 李廣俠

(解放軍理工大學(xué)通信工程學(xué)院研究生4隊1) 南京 210007)(解放軍理工大學(xué)軍事衛(wèi)星通信重點實驗室2) 南京 210007)

Turbo碼S隨機交織器的實現(xiàn)*

錢 宏1)李廣俠2)

(解放軍理工大學(xué)通信工程學(xué)院研究生4隊1)南京 210007)(解放軍理工大學(xué)軍事衛(wèi)星通信重點實驗室2)南京 210007)

Turbo碼中交織器的設(shè)計直接影響著Turbo碼的性能。在討論Turbo碼交織器的設(shè)計準(zhǔn)則和類型的基礎(chǔ)上,著重介紹了S隨機交織器的原理,并給出了其一種基于冒泡排序算法的實現(xiàn)方法。仿真結(jié)果表明,中短長度的S隨機交織器性能優(yōu)良。

Turbo碼;S隨機交織器;冒泡排序算法

Class NumberTN911.22

1 引言

Turbo碼最早由法國的C.Berrou等人在1993年的ICC會議上提出[1],因其非常逼近香農(nóng)限的性能而引起了當(dāng)時通信領(lǐng)域的轟動。Turbo碼通過分量碼并行級聯(lián)實現(xiàn)了應(yīng)用短碼構(gòu)造長碼的方法;并且在編解碼過程中引入交織器,使碼字具有近似隨機的特性;同時,在接收端采用軟輸入軟輸出的迭代譯碼算法來逼近最大似然譯碼,實現(xiàn)了香農(nóng)提出的碼長趨近于無限長時的隨機編碼和最大似然譯碼的思想。Turbo碼的提出,標(biāo)志著信息論和編碼技術(shù)進入了一個新的階段。

理論分析和計算機模擬表明,交織器在Turbo碼的設(shè)計中起著十分重要的作用[2]。自 Turbo碼提出之后,眾多學(xué)者對不同的交織器用于Turbo碼時的性能進行了大量的分析和研究。本文探討了Turbo碼交織器的設(shè)計準(zhǔn)則,列舉了一些典型的交織器,并給出了其中的S隨機交織器的一種冒泡排序?qū)崿F(xiàn)方法。

2 Turbo碼交織器的設(shè)計準(zhǔn)則

交織器的性能影響了Turbo碼編碼器的編碼輸出距離特性,通過交織能夠改變碼重的分布,并降低子編碼器的輸入序列之間和外信息與信道輸入之間的相關(guān)性,進而在迭代譯碼過程中降低誤比特率。因此,在設(shè)計Turbo碼交織器時,應(yīng)遵循以下兩大準(zhǔn)則[3]:

1)碼重分布準(zhǔn)則。在AWGN信道下采用最大似然譯碼算法的線性糾錯碼的性能,和此種糾錯碼的最小漢明距離dm或自由距離df有關(guān)。Turbo碼作為一種線性碼,在AWGN信道下,誤比特率近似等于:

其中,dm是Turbo碼的最小漢明重量,Nmin是碼重等于dm的碼字的數(shù)量min是產(chǎn)生最小漢明重量碼字的輸入序列的平均漢明重量,N是交織器的長度。由上式可以看出,對于Turbo碼,當(dāng)交織器長度N固定時,要想獲得更好的糾錯性能,可以通過增加dm或者減小Nmin兩種途徑。當(dāng) Turbo碼中的RSC分量碼編碼器固定時,交織器的結(jié)構(gòu)決定了上述兩個參數(shù)。因此,Turbo碼交織器的設(shè)計就是盡量避免兩個RSC編碼器同時產(chǎn)生低漢明重的校驗碼字,盡可能地提高碼字的dm,減少低漢明重量碼字的數(shù)量Nmin,這就是碼重分布準(zhǔn)則。

2)迭代譯碼適應(yīng)性IDS準(zhǔn)則。對于第一個準(zhǔn)則,當(dāng)采用最大似然譯碼時,無疑是一個合適的標(biāo)準(zhǔn),但Turbo碼是采用迭代譯碼方法來逼近最大似然譯碼,在多數(shù)情況下,譯碼不是最大似然譯碼,因此必須對這一標(biāo)準(zhǔn)做一些補充。由此提出了第二個準(zhǔn)則,即Turbo碼的迭代譯碼適應(yīng)性準(zhǔn)則。

3 S隨機交織器的基本原理及其實現(xiàn)

根據(jù)設(shè)計思想的不同,交織器大致可以分為規(guī)則交織器和隨機交織器。規(guī)則交織器通常按照一定的規(guī)則映射來實現(xiàn)交織,常用的有行列交織器和螺旋交織器,比較易于實現(xiàn),但并不能很好地降低輸入信息的相關(guān)性,限制了Turbo碼性能的提高。

隨機交織器被期望能夠?qū)崿F(xiàn)隨機交織過程,但實際上采用的隨機交織器都是偽隨機交織器。應(yīng)該說,隨機交織器能產(chǎn)生性能較好的交織器,尤其是在產(chǎn)生長度比較長的交織器時,性能一般都比較好。但因為是采用隨機的方法,有時也會產(chǎn)生性能較差的交織器。正因為沒有什么特殊準(zhǔn)則要遵守,使得隨機交織器很容易產(chǎn)生,但是其性能得不到保障。

S隨機交織器,又叫半隨機交織器(Semi-random Interleaver),是在隨機交織器的基礎(chǔ)上引入了限制條件S,是一種結(jié)合隨機交織和非隨機交織特點的交織器[4]。S隨機交織器的設(shè)計步驟如下:

2)產(chǎn)生一個隨機數(shù)i,使得1≤i≤N。

3)把i與前面所產(chǎn)生的s個整數(shù)相比較,如果當(dāng)前的選擇與前面s個整數(shù)中的任何一個相距都不在±s的范圍內(nèi),則保留之;否則,重新產(chǎn)生隨機數(shù)i,直到上述條件滿足為止。

4)重復(fù)步驟2)、3),直到交織器的N個位置均被填滿。

S隨機交織器是部分基于漢明重原則設(shè)計的交織器。重量為2的輸入序列通常被認為是引起Turbo碼低漢明重碼字輸出的主要因素。設(shè)計S隨機交織器的出發(fā)點就是要打亂這些重量為2的輸入序列,減少這些輸入序列同時在兩個 RSC成員編碼器上產(chǎn)生低重量輸出的機會。經(jīng)過S隨機交織器后,使得重量為2的輸入序列交織前的距離d1和交織后的距離d2,滿足 d1+d2≥s+1,確保了最小的d1+d2值,而且隨著N的最大,這個最小值也會隨之增大?？梢钥吹街亓繛?的輸入序列被比較有效的分開了。

S隨機交織器的設(shè)計利用上述搜索算法來實現(xiàn),該算法的一個缺點是不能確保對于每一個s＜的值,都可以找到一個S隨機交織器;而且算法的搜索時間隨著s的增加而增加,當(dāng)N比較大時,這一搜索算法會耗費大量時間。鑒于此,我們提出了S隨機交織器的一種冒泡排序?qū)崿F(xiàn)方法。

為了實現(xiàn)長度為N的S隨機交織器,我們首先生成整數(shù)1～N的一個隨機排列A,然后對其使用冒泡排序算法。通常,冒泡算法中搜索的是一串?dāng)?shù)字中最大或最小的數(shù)[5]。而我們這里采用的冒泡算法中搜索的是滿足S隨機交織器限制條件的整數(shù),即與前面s個整數(shù)中的任何一個相距都不在±s范圍內(nèi)的整數(shù)。

僅采用冒泡算法并不能保證將初始序列A變成滿足S隨機交織器限制條件的序列。我們將初始序列A經(jīng)過冒泡算法后得到的序列記為A′,將A′分成上下兩部分,上半部分為使用冒泡算法后滿足限制條件的部分序列,記為序列B,余下部分記為序列C。在執(zhí)行完一次冒泡算法后,即序列C中不再存在滿足S隨機交織器限制條件的整數(shù)時,將序列C移至序列A′的頂端,并重新記為序列A,然后再執(zhí)行冒泡算法,直到整個序列A滿足S隨機交織器限制條件。

圖1 冒泡排序算法示例(N=10,s=2)

對應(yīng)于長度為N,擴展參數(shù)為s的S隨機交織器的冒泡排序算法,其步驟歸納如下:

1)生成整數(shù)1～N的一個隨機排列A;

2)將序列A的第一個數(shù)置于序列A′的頂端;

3)執(zhí)行冒泡算法,搜索序列 A余下的數(shù)中滿足S隨機交織器限制條件的數(shù),將其置于序列 A′的下端;

4)如果序列A中所有的數(shù)都置于序列A′中,則生成S隨機交織器;否則,將序列A中余下的數(shù)置于序列A′的頂端,并轉(zhuǎn)到步驟2)繼續(xù)執(zhí)行。

結(jié)合冒泡算法,我們的冒泡排序算法比較易于實現(xiàn)。圖1所示為冒泡排序算法的一個示例,生成一個長度N=10、擴展參數(shù)s=2的S隨機交織器。仿真結(jié)果顯示,使用冒泡排序算法,中短長度的S隨機交織器能夠在幾秒內(nèi)生成;而對于更長一些的S隨機交織器,可能需要執(zhí)行更多次數(shù)的冒泡算法,但也能夠在有限的時間(幾小時)內(nèi)生成。

4 S隨機交織器的性能仿真

為檢驗Turbo碼S隨機交織器的性能,我們分別對長度為274bit和600bit的分組交織器、隨機交織器和S隨機交織器做了性能仿真,仿真結(jié)果如圖2所示。仿真實驗在AWGN信道、BPSK調(diào)制下進行。所選取的Turbo碼分量碼為(13,15)8,譯碼采用Log-MAP算法,迭代次數(shù)為10次。長度為274bit的S隨機交織器的擴展參數(shù)s=11,長度為600bit的S隨機交織器的擴展參數(shù)s=17。

由圖2可以看出,采用分組交織器的Turbo碼性能較差,表現(xiàn)出很明顯的“誤碼平層”效應(yīng);采用隨機交織器的Turbo碼性能優(yōu)于采用分組交織器的Turbo碼,“誤碼平層”效應(yīng)有所改善;而采用S隨機交織器的T urbo碼性能最優(yōu),在高信噪比區(qū),與采用隨機交織器的 Turbo碼相比,有約0.2～0.3dB性能增益。

圖2 交織器性能比較

5 結(jié)語

交織器的設(shè)計是Turbo碼的核心技術(shù)之一,通過選取好的交織矩陣,可以提高Turbo碼的自由距離,減小低重量碼字個數(shù),最大限度發(fā)揮交織器的作用。本文介紹了Turbo碼交織器的設(shè)計準(zhǔn)則,并詳細介紹了其中的S隨機交織器的基本原理,給出了S隨機交織器的一種冒泡排序?qū)崿F(xiàn)方法。仿真結(jié)果表明,所設(shè)計的S隨機交織器性能優(yōu)于分組交織器和隨機交織器。

[1]C.Berrou,A.Glavieux,P.Thitimajshima.Near Shannon limit error-correcting coding and decoding:Turbo codest[C]//Inpron.1993 IEEE Int.Confon on Communication.Ceneva,Switzerland,1993:1064～1070

[2]J.Yuan,B.Vucetic,W.Feng.Combined Turbo Codes and Interleaver Design[C]//IEEE Transactions on Communications,1999,47:484～487

[3]H.R.Sajjadpour,Neil J.A.Saloane,Masoud Salehi,et al.Interleaver Design for Turbo Codes[C]//IEEE J.Select.Area comm.,2001,19(5):831～837

[4]蘇鶴祿,蔣宇中.Turbo碼交織器的設(shè)計[J].艦船電子工程,2006,26(1):157～160

[5]M.H.Alsuwaiyel.算法設(shè)計技巧與分析[M].吳偉,方世昌,等,譯.北京:電子工業(yè)出版社,2004

Implementation of Turbo Codes S-Random Interleaver

Qian Hong1)Li Guangxia2)
(Postgraduate Team 4 ICE,PLAUST1),Nanjing 210007)
(Military Satellite Communication LAB ICE,PLAUST2),Nanjing 210007)

The design of interleaver in Turbo codes directly affects the performance of Turbo codes.Based on discussing the design rules and types of interleaver,the theory of s-random interleaver is particularly introduced.The implementation of s-random interleaver based on bubble sorting method is given.Simulation result shows that the performance of s-random interleaver is excellent for short to medium interleaver length.

Turbo codes,S-random interleaver,bubble sorting method

TN911.22

2010年9月18日,

2010年10月15日

國家自然科學(xué)基金項目(編號:60972061);國家“863”計劃項目(編號:2008AA12A204)資助。

錢宏,男,碩士研究生,研究方向:衛(wèi)星通信與衛(wèi)星導(dǎo)航。李廣俠,男,博士,博士生導(dǎo)師,研究方向:衛(wèi)星通信與衛(wèi)星導(dǎo)航。