高誤碼率下Turbo碼交織器的恢復方法

任亞博 張 健 劉以農

?

高誤碼率下Turbo碼交織器的恢復方法

任亞博*①②張 健②劉以農①

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

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

Turbo碼；交織器；恢復

1 引言

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

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

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

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

2 Turbo碼的識別模型

2.1 Turbo碼的編碼原理

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

圖1 Turbo碼編碼器

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

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

2.2識別的數學模型

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

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

3 誤碼條件下交織器的恢復方法

3.1誤碼條件下的交織器恢復方法

式(5)進一步轉化則有

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

式(12)提供了一種通過歸納法求解的方法。考慮到，通過對足夠多的碼字進行統計可以得到概率，其也小于0.5，顯然對于任意的，應有。為已知量，同時，由式(7)知，故如果假設已知，則也為已知量，此時對未知的進行搜索，當的概率最小時，此時的即為最大似然的。于是有如下步驟恢復交織器的最大似然算法：

3.2算法的性能分析與參數取值

記

式中

于是整個交織器正確恢復的概率為

4 算法仿真結果

圖2 1%誤碼下交織器恢復

圖3 5%誤碼下交織器恢復

圖4 10%誤碼下交織器恢復

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

表1算法的參數選擇與計算量

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

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

5 結論

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

參考文獻

[1] 解輝, 黃知濤, 王豐華. 信道編碼盲識別技術研究進展[J]. 電子學報, 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] 閆郁翰. 信道編碼盲識別技術研究[D]. [碩士論文], 西安電子科技大學, 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]. 電子學報, 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] 劉建成, 楊曉靜. 基于校驗統計的 (2, 1, m) 卷積碼盲識別[J]. 電子信息對抗技術, 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碼編碼參數的盲識別方法[J]. 西安電子科技大學學報, 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]. 西安電子科技大學學報, 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網絡優先出版

NSAF基金 (11176005)資助課題

任亞博： 男，1987年生，博士生，研究方向為信道編碼識別.

張 健： 男，1968年生，研究員，博士生導師，研究方向為電子工程、無線通信、太赫茲.

劉以農： 男，1963年生，教授，博士生導師，研究方向為核電子學.