錢(qián) 宏 李廣俠

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

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

錢(qián) 宏1)李廣俠2)

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

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

Turbo碼;S隨機(jī)交織器;冒泡排序算法

Class NumberTN911.22

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 S隨機(jī)交織器的性能仿真

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

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

圖2 交織器性能比較

5 結(jié)語(yǔ)

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

[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ì)[J].艦船電子工程,2006,26(1):157～160

[5]M.H.Alsuwaiyel.算法設(shè)計(jì)技巧與分析[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日

國(guó)家自然科學(xué)基金項(xiàng)目(編號(hào):60972061);國(guó)家“863”計(jì)劃項(xiàng)目(編號(hào):2008AA12A204)資助。

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