任亞博 張 健 劉以農(nóng)

?

高誤碼率下Turbo碼交織器的恢復(fù)方法

任亞博*①②張 健②劉以農(nóng)①

①(清華大學(xué)工程物理系 北京 100084)②((中國(guó)工程物理研究院電子工程研究所 綿陽(yáng) 621900)

該文提出了一種針對(duì)高誤碼條件下Turbo碼交織器的恢復(fù)方法，應(yīng)用于碼率為1/3的并行級(jí)聯(lián)Turbo碼。信道編碼識(shí)別是非合作信號(hào)處理領(lǐng)域的重要內(nèi)容，Turbo碼交織器的恢復(fù)是其中的一個(gè)難點(diǎn)?，F(xiàn)有的識(shí)別方法可以有效地處理無(wú)誤碼時(shí)的問題，而實(shí)際通信中Turbo碼經(jīng)常應(yīng)用于信道質(zhì)量較差的情況，此時(shí)誤碼率會(huì)較高，且碼長(zhǎng)較長(zhǎng)，這些方法將失效。利用校驗(yàn)向量的特征，可將交織器的每個(gè)位置分離開來(lái)，單獨(dú)求解，使得交織器中每個(gè)位置的恢復(fù)僅依賴于幾個(gè)相關(guān)的位置，避免了誤碼累加效應(yīng)，從而解決了在高誤碼率，長(zhǎng)碼長(zhǎng)時(shí)的識(shí)別問題，其復(fù)雜度較低。在仿真結(jié)果中，對(duì)典型的長(zhǎng)度達(dá)10000的隨機(jī)交織器，接收序列10%誤碼率的情況下，實(shí)現(xiàn)了正確的恢復(fù)。

Turbo碼；交織器；恢復(fù)

1 引言

信道編碼用于糾正誤碼，在通信及存儲(chǔ)中有著廣泛的應(yīng)用；在非合作通信中，由于其編碼方式未知，就有了對(duì)信道編碼識(shí)別的研究，近年來(lái)，這已成為一個(gè)研究熱點(diǎn)。

Turbo碼作為一種逼近香農(nóng)限的碼，近年來(lái)在3G, 4G及衛(wèi)星通信中等得到了廣泛的應(yīng)用，Turbo碼的識(shí)別也隨之興起。Turbo碼完整的識(shí)別應(yīng)包括卷積碼的識(shí)別和隨機(jī)交織器的識(shí)別，這兩個(gè)問題可以分開處理，卷積碼的識(shí)別已有較成熟的研究成果，本文專注于隨機(jī)交織器的識(shí)別。文獻(xiàn)[10]中提出了一種樹狀分枝的方法，該方法基于最大似然原理，即使在相當(dāng)大噪聲時(shí)也可以恢復(fù)出交織器，但這一方法對(duì)Turbo碼還不夠，因?yàn)槠浼僭O(shè)識(shí)別的對(duì)象是交織排列后的輸出序列，而實(shí)際中接收到的是這一序列經(jīng)過(guò)編碼的序列。文獻(xiàn)[11]提出了一種基于Turbo碼譯碼的交織器恢復(fù)方法，該方法通過(guò)對(duì)比第位交織器正確恢復(fù)與不正確恢復(fù)時(shí)譯碼熵值的差異，來(lái)尋找第位的位置，是一種有效的方法，然而其算法中的Turbo譯碼，使其具有較高復(fù)雜度，隨著交織器長(zhǎng)度的增長(zhǎng)，例如達(dá)10000時(shí)，在5%的誤碼率下的恢復(fù)也要幾個(gè)小時(shí)，在10%的高誤碼率下幾乎無(wú)法恢復(fù)。文獻(xiàn)[12]提出了一種特別的方法，需假設(shè)信息序列無(wú)誤碼，通過(guò)將反饋卷積編碼器的生成有理式(分子與分母均為多項(xiàng)式)作泰勒級(jí)數(shù)展開，可恢復(fù)出下一時(shí)刻交織后的數(shù)據(jù)，進(jìn)而逐步恢復(fù)出整個(gè)交織器；當(dāng)信息序列有誤碼時(shí)，作者提出了“剔除”和“糾正”兩種策略，該策略對(duì)交織長(zhǎng)度較長(zhǎng)時(shí)，要求誤碼率非常低，其仿真表明，當(dāng)長(zhǎng)度為100時(shí)，有效識(shí)別的誤碼率在1%至2%。國(guó)內(nèi)文獻(xiàn)[13]提出了一種無(wú)誤碼條件下的盲識(shí)別方法，該法將編碼后的序列除以生成有理式，從而恢復(fù)出交織后的信息序列，進(jìn)行恢復(fù)出交織器，對(duì)有誤碼條件下的情況則沒有提及。文獻(xiàn)[14,15]中提出了對(duì)Turbo碼碼長(zhǎng)與交織器的識(shí)別，其容忍的誤碼率也不到1%，交織器的長(zhǎng)度只有幾百。

現(xiàn)有的識(shí)別方法不能同時(shí)滿足高誤碼率、長(zhǎng)交織器的情況，而實(shí)際情況中的1/3并行級(jí)聯(lián)Turbo碼具備糾10%以上的誤碼率的能力，且其交織器的長(zhǎng)度很長(zhǎng)。針對(duì)這種情況，本文提出了一種逐位恢復(fù)交織器的方法，使得交織器中單個(gè)位置的恢復(fù)僅依賴于幾個(gè)相關(guān)的位置，降低了問題的復(fù)雜度，最后的仿真結(jié)果印證了算法的有效性。

文章接下來(lái)的結(jié)構(gòu)如下：第2節(jié)簡(jiǎn)要介紹Turbo碼的編碼原理，定義文中使用的符號(hào)，識(shí)別的模型；第3節(jié)給出誤碼條件下的識(shí)別算法，并分析算法的復(fù)雜度與一些參數(shù)的取值；第4節(jié)是仿真的結(jié)果；第5節(jié)給出結(jié)論。

2 Turbo碼的識(shí)別模型

2.1 Turbo碼的編碼原理

典型的并行級(jí)聯(lián)Turbo碼的結(jié)構(gòu)如圖1所示。其中信息序列為，經(jīng)過(guò)編碼器1后得到的序列為；信息序列經(jīng)過(guò)交織后得到，交織器的長(zhǎng)度記為，編碼后的序列為; 3路序列經(jīng)過(guò)二進(jìn)制對(duì)稱信道后接收方得到的序列為,,。圖中表示噪聲，為一個(gè)0, 1序列，其中1的概率即為接收序列的誤比特率(BER)。

圖1 Turbo碼編碼器

本文中關(guān)于Turbo編碼的運(yùn)算均是在GF(2)或其擴(kuò)域上進(jìn)行的。為方便描述，本文中的,,,,,以及后文出現(xiàn)的均為多項(xiàng)式，其形式例如。而,,分別表示關(guān)于,,的誤碼多項(xiàng)式。表示將多項(xiàng)式的系數(shù)按照交織器的規(guī)則置換后得到的新的多項(xiàng)式，若交織器表示的交織規(guī)則為，則，因此恢復(fù)交織器就是要計(jì)算出的取值。

假設(shè)反饋卷積編碼器2的生成矩陣為，其中與為多項(xiàng)式，,,，每次編碼前其移位寄存器初始的狀態(tài)為0，則有式(1)成立

2.2識(shí)別的數(shù)學(xué)模型

將式(2)，式(3)，式(4)與式(1)結(jié)合有

誤碼條件下，如果誤碼率非常低(例如0.1%以下)，交織器的長(zhǎng)度比較短(例如只有幾百)，則序列中可能無(wú)誤碼，即，問題可轉(zhuǎn)化為無(wú)誤碼條件下的識(shí)別問題。在一些條件下，如果誤碼率達(dá)1%甚至10%，或者Turbo碼的交織器長(zhǎng)度達(dá)幾千甚至上萬(wàn)，這時(shí)就無(wú)法轉(zhuǎn)化為無(wú)誤碼下的問題。

3 誤碼條件下交織器的恢復(fù)方法

3.1誤碼條件下的交織器恢復(fù)方法

式(5)進(jìn)一步轉(zhuǎn)化則有

假設(shè)通信的信道為二進(jìn)制對(duì)稱信道(BSC)，其BER(轉(zhuǎn)移概率)為，即多項(xiàng)式中系數(shù)為1的概率為。

式(12)提供了一種通過(guò)歸納法求解的方法?？紤]到，通過(guò)對(duì)足夠多的碼字進(jìn)行統(tǒng)計(jì)可以得到概率，其也小于0.5，顯然對(duì)于任意的，應(yīng)有。為已知量，同時(shí)，由式(7)知，故如果假設(shè)已知，則也為已知量，此時(shí)對(duì)未知的進(jìn)行搜索，當(dāng)?shù)母怕首钚r(shí)，此時(shí)的即為最大似然的。于是有如下步驟恢復(fù)交織器的最大似然算法：

3.2算法的性能分析與參數(shù)取值

記

式中

于是整個(gè)交織器正確恢復(fù)的概率為

4 算法仿真結(jié)果

圖2 1%誤碼下交織器恢復(fù)

圖3 5%誤碼下交織器恢復(fù)

圖4 10%誤碼下交織器恢復(fù)

仿真中的計(jì)算量與其它參數(shù)的選擇如表1。表1反映出，當(dāng)交織器增長(zhǎng)，誤碼率增加時(shí)，識(shí)別所需要的碼字?jǐn)?shù)隨之增長(zhǎng)，這與理論分析一致。仿真中的計(jì)算來(lái)自于比特層次上的異或運(yùn)算，在主頻2.66 GHz的電腦上的運(yùn)算時(shí)間，BER=1%時(shí)，對(duì)長(zhǎng)度為1000的交織器識(shí)別時(shí)間不到1 s，而BER=10%，交織器長(zhǎng)為10000時(shí)，用時(shí)約10 min。

表1算法的參數(shù)選擇與計(jì)算量

圖5給出了當(dāng)碼字?jǐn)?shù)目固定時(shí)，不同誤碼率下的識(shí)別正確率，在10%的誤碼率下都達(dá)到了100%的識(shí)別正確率，其識(shí)別正確率隨著誤碼的增加而降低，識(shí)別錯(cuò)誤率隨著誤碼的增加而增加。圖中“＝1000，＝1200”及“=10000，=2000”兩條曲線很逼近，而“=1000，＝2000”的效果明顯優(yōu)于兩者，這說(shuō)明當(dāng)交織器的長(zhǎng)度增長(zhǎng)時(shí)，識(shí)別正確率會(huì)下降，但增大碼字?jǐn)?shù)目會(huì)提高識(shí)別正確率。

圖5 不同誤碼率下的識(shí)別正確率

5 結(jié)論

Turbo碼具有很強(qiáng)的糾錯(cuò)能力，近年來(lái)被廣泛應(yīng)用于低信噪比的信道中，對(duì)于1/3碼率的Turbo碼，本文提出的算法有效地解決了在10%的高誤碼下，隨機(jī)交織器的恢復(fù)問題。從算法分析與仿真中可以看出，算法的存儲(chǔ)量與計(jì)算量較小，在一般的電腦上即可運(yùn)行，其識(shí)別時(shí)間較短，有較強(qiáng)的實(shí)用性。

參考文獻(xiàn)

[1] 解輝, 黃知濤, 王豐華. 信道編碼盲識(shí)別技術(shù)研究進(jìn)展[J]. 電子學(xué)報(bào), 2013, 41(6): 1166-1176.

Xie Hui, Huang Zhi-tao, and Wang Feng-hua. Research progress of blind recognition of channel coding[J]., 2013, 41(6): 1166-1176.

[2] Moosavi R and Larsson E G. A fast scheme for blind identification of channel codes[C]. IEEE Global Telecommunications Conference 2011, Linkoping, Sweden, 2011: 1-5.

[3] Bringer J and Chabanne H. Code reverse engineering problem for identification codes[J]., 2012, 58(4): 2406-2412.

[4] 閆郁翰. 信道編碼盲識(shí)別技術(shù)研究[D]. [碩士論文], 西安電子科技大學(xué), 2012.

[5] Marazin M, Gautier R, and Burel G. Algebraic method for blind recovery of punctured convolutional encoders from an erroneous bitstream[J].,2012, 6(2): 122-131.

[6] 于沛東, 李靜, 彭華. 一種利用軟判決的信道編碼識(shí)別新算法[J]. 電子學(xué)報(bào), 2013, 41(2): 301-306.

Yu Pei-dong, Li Jing, and Peng Hua. A new algorithm for channel coding recognition using soft decision[J]., 2013, 41(2): 301-306.

[7] 劉建成, 楊曉靜. 基于校驗(yàn)統(tǒng)計(jì)的 (2, 1, m) 卷積碼盲識(shí)別[J]. 電子信息對(duì)抗技術(shù), 2013, 28(1): 1-4.

Liu Jian-cheng and Yang Xiao-jing. Blind recognition of (2,1,m) convolutional code based on parity-check Statistics[J]., 2013, 28(1): 1-4.

[8] Karimian Y and Attari M A. Recognition of channel encoder parameters from intercepted bitstream[C]. IEEE 2013 21st Iranian Conference on Electrical Engineering (ICEE), Mashhad, 2013: 1-5.

[9] Moosavi R and Larsson E G. Fast blind recognition of channel codes[J]., 2014, 62(5): 1393-1405.

[10] Barbier J. Reconstruction of Turbo-code encoders[J]. SPIE, 2005, 5819: 463-473.

[11] Cluzeau M, Finiasz M, and Tillich J P. Methods for the reconstruction of parallel Turbo codes[C]. IEEE International. Symposium on Information Theory, Austin, TX, USA, 2010: 2008-2012.

[12] Cote M and Sendrier N. Reconstruction of a Turbo-code interleaver from noisy observation[C]. IEEE International Symposium on Information Theory, Austin, TX, USA, 2010: 2003-2007.

[13] 張永光. 一種Turbo碼編碼參數(shù)的盲識(shí)別方法[J]. 西安電子科技大學(xué)學(xué)報(bào), 2011, 38(2): 167-172.

Zhang Yong-guang. Blind recognition method for the Turbo coding parameter[J]., 2011, 38(2): 167-172.

[14] 李嘯天, 李艷斌, 昝俊軍, 等. 一種基于矩陣分析的Turbo 碼長(zhǎng)識(shí)別算法[J]. 無(wú)線電工程, 2012, 42(4): 23-26.

Li Xiao-tian, Li Yan-bin, Zan Jun-jun,.. An algorithm for recognition of Turbo code length based on matrix analysis[J]., 2012, 42(4): 23-26.

[15] 李嘯天, 張潤(rùn)生, 李艷斌. 歸零Turbo 碼識(shí)別算法[J]. 西安電子科技大學(xué)學(xué)報(bào), 2013, 40(4): 161-166.

Li Xiao-tian, Zhang Run-sheng, and Li Yan-bin. Research on the recognition algorithm of Turbo codes on trellis termination[J]., 2013, 40(4): 161-166.

[16] Valembois A. Detection and recognition of a binary linear code[J]., 2001, 111(1): 199-218.

Reconstruction of Turbo-code Interleaver at High Bit Error Rate

Ren Ya-bo①②Zhang Jian②Liu Yi-nong①

①(,,100084,)②(,,621900,)

An algorithm to recover a Turbo-code interleaver is proposed at high Bit Error Rate (BER), and it is applied to the 1/3 parallel concatenated Turbo-code. The recognition of channel coding plays an important part in the field of non-cooperative signal processing; recovering a Turbo-code interleaver is one difficulty. There are already some effective algorithms for the noiseless condition, but in actual communication system, Turbo code is often used in a high noisy level, where the BER is high and the word length is long: these algorithms would be ineffective. Using the characteristic of the parity-heck vector, each position of the interleaver can be separated and solved independently. Thus, it makes the recovery of every position only rely on several correlative positions, which avoids the error accumulation effect. The algorithm solves the problem when the BER is high and the code length is long, and it also has low complexity. Simulations show that for a Turbo code with interleaver length 10000 and BER 10%, the algorithm runs successfully.

Turbo code; Interleaver; Reconstruction

TN911.22

A

1009-5896(2015)08-1926-05

10.11999/JEIT141556

任亞博 renyabo2005@126.com

2014-12-08收到，2015-03-23改回，2015-06-09網(wǎng)絡(luò)優(yōu)先出版

NSAF基金 (11176005)資助課題

任亞博： 男，1987年生，博士生，研究方向?yàn)樾诺谰幋a識(shí)別.

張 ?。?男，1968年生，研究員，博士生導(dǎo)師，研究方向?yàn)殡娮庸こ?、無(wú)線通信、太赫茲.

劉以農(nóng)： 男，1963年生，教授，博士生導(dǎo)師，研究方向?yàn)楹穗娮訉W(xué).