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

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

?

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

任亞博*①②張 ?、趧⒁赞r(nóng)①

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

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

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

1 引言

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

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

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

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

2 Turbo碼的識別模型

2.1 Turbo碼的編碼原理

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

圖1 Turbo碼編碼器

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

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

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

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

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

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

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

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

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

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

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

記

式中

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

4 算法仿真結(jié)果

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

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

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

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

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

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

圖5 不同誤碼率下的識別正確率

5 結(jié)論

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

參考文獻

[1] 解輝, 黃知濤, 王豐華. 信道編碼盲識別技術(shù)研究進展[J]. 電子學(xué)報, 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ù)研究[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] 于沛東, 李靜, 彭華. 一種利用軟判決的信道編碼識別新算法[J]. 電子學(xué)報, 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] 劉建成, 楊曉靜. 基于校驗統(tǒng)計的 (2, 1, m) 卷積碼盲識別[J]. 電子信息對抗技術(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ù)的盲識別方法[J]. 西安電子科技大學(xué)學(xué)報, 2011, 38(2): 167-172.

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

[14] 李嘯天, 李艷斌, 昝俊軍, 等. 一種基于矩陣分析的Turbo 碼長識別算法[J]. 無線電工程, 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] 李嘯天, 張潤生, 李艷斌. 歸零Turbo 碼識別算法[J]. 西安電子科技大學(xué)學(xué)報, 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年生，博士生，研究方向為信道編碼識別.

張 ?。?男，1968年生，研究員，博士生導(dǎo)師，研究方向為電子工程、無線通信、太赫茲.

劉以農(nóng)： 男，1963年生，教授，博士生導(dǎo)師，研究方向為核電子學(xué).