一種基于矩陣分析的Turbo碼長識別算法

李嘯天，李艷斌，昝俊軍，杜宇峰

(中國電子科技集團公司第五十四研究所，河北石家莊 050081)

0 引言

Turbo碼以其在低信噪比應用環境中所展現的優異糾錯性能，在3G移動通信和衛星通信等領域得到了廣泛應用。因此，在通信偵察中如何從通信信號解調之后得到的數據碼流中準確快速地分析出Turbo碼的編碼結構及編碼參數，是不可避免且亟待解決的技術問題。目前國內外有關信道編碼識別技術的研究主要針對于線性分組碼及卷積碼，有關Turbo碼的研究主要集中于其編譯碼性能的優化，對于其識別技術的研究還處于探索階段。深入研究了Turbo碼的歸零方式和生成矩陣，提出了一種基于矩陣秩特征的Turbo碼長識別算法，并通過仿真驗證了算法的容錯性能及識別效率。

1 Turbo碼基本原理

1.1 Turbo碼編碼結構

Turbo碼的典型編碼結構為WCDMA協議中所采用的編碼結構，如圖1所示。

圖1 WCDMA協議中Turbo碼編碼結構

1.2 Turbo碼歸零方式

歸零碼元為所有的信息比特經過分量編碼器以后繼續輸入的歸零比特，目的是迫使編碼器回到全零狀態。當k位信息碼元完成編碼之后首先斷開第3路，輸入3個碼元xk+1xk+2xk+3并從第1路輸出，編碼器RSC1輸出為zk+1zk+2zk+3;之后斷開第2路，連接第3路，在編碼器RSC2前輸入xk+1'xk+2'xk+3'并從第1路輸出，編碼器輸出為zk+1'zk+2'zk+3'。

下面說明Turbo碼歸零序列的確定。鑒于第1個編碼器RSC1和第2個編碼器RSC2結構完全相同，歸零模式也相同，僅以RSC1的歸零為例。

xk+3輸入完成后=0，==0===0，寄存器回到全零狀態。以上算法均在模2下進行。

式(2)和式(3)給出歸零碼元與信息碼元之間的關系。其中，ai，bi，ci取值與 k有關，k確定時其取值便確定?？啥x歸零生成矩陣Rk為k×3矩陣，且滿足=·[IkRk]，Ik為k階單位陣。假設 k=7，則

由式(4)可得:

2 生成矩陣分析

2.1 第2路生成矩陣G2

考慮圖1所示分量編碼器結構，設最左邊加法器后的數據為uk，則有如下關系:

將式(6)合并:

由式(7)可得:

根據上面所得輸入與輸出關系，可定義分量編碼器RSC1的生成矩陣Tk+3為(k+3)×(k+3)矩陣(考慮歸零碼元)，可得:

綜上可得:可得G2= [IkRk]·Tk+3，為 k×(k+3)矩陣。

2.2 第3路生成矩陣G3

由于交織本身是一種數據置換，即可以用信息序列乘以初等變換矩陣來實現。如同余方程為:

如果取A0=1，同余序列為:

利用此序列產生交織長度k=7的偽隨機交織方式，交織前序列為 x1x2x3x4x5x6x7，則交織后序列為x5x1x4x7x3x6x2。此交織方式可初等矩陣表示:

定義交織矩陣Sk為k×k初等矩陣，則

可得 G3=Sk· [IkRk]·Tk+3，為 k×(k+3)矩陣。

2.3 第1路生成矩陣G1

第1路輸出為信息碼元加6位歸零碼元。第2路歸零碼元的生成矩陣可直接由矩陣Rk表示。第3路歸零碼元在信息碼元經過交織器后接入，為·Sk·Rk，可得第3路歸零碼元生成矩陣為Sk·Rk。綜上可得第1路生成矩陣G1= [IkRkSk·Rk]，為k×(k+6)矩陣。

2.4 Turbo碼整體生成矩陣

G1，G2，G3中各列分別對應3路中各輸出碼元，將3路生成矩陣各列按照復用方式組合成為Turbo碼整體生成矩陣G，可得

考慮WCDMA協議中的交叉復用模式，則由G1，G2，G3可得 Turbo碼整體生成矩陣:

為k×(3k+12)矩陣。由此可以看出，當Turbo碼的分量編碼器參數、交織器參數和歸零模式確定時，其生成矩陣便已確定。

由上述分析可以看出，歸零Turbo碼生成矩陣G不同于卷積碼的半無限長生成矩陣，是有限長且固定的，因此歸零Turbo碼從整體的角度來看等效為一種特殊的線性分組碼?？紤]生成矩陣G中G1的存在，歸零Turbo碼還是一種系統的線性分組碼。不同于一般的線性分組碼，Turbo碼的碼長比較長。WCDMA協議中交織幀的長度k取值范圍為40≤k≤5114，Turbo碼長大約為k的3倍為幾百至幾萬比特。由此可見，歸零Turbo碼更類似于一種特殊的LDPC碼，其生成矩陣也類似于LDPC碼的稀疏生成矩陣。

如卷積碼定義中所述，當前碼組中校驗比特不僅與當前碼組信息比特有關，還與之前碼組的信息比特有關，而這種碼組之間的影響就是由寄存器實現的，因為寄存器保留了之前碼組的信息。而對于Turbo碼來說，在每一幀編碼完成之后對寄存器進行歸零則抹去了本幀的信息，將不會對之后幀的編碼產生影響，各幀按照同一生成矩陣獨立編碼，完全等同于線性分組碼的編碼特點。

對于刪余Turbo碼，不同的刪余模式可以等效為對生成矩陣G的不同列進行刪除，刪除之后G仍為固定，可以認為刪余Turbo碼仍然等效為線性分組碼，其生成矩陣為G的子矩陣。

3 碼長識別

3.1 傳統識別算法

將截獲的碼流按不同列數排列成分析矩陣，當矩陣列數正好為Turbo碼長或其倍數時，由于各碼組是由同一生成矩陣生成，碼組之間的線性關系導致矩陣秩不等于矩陣列數，從而有如下引理［4］:

對于碼長為n的線性分組碼所構成的p×q矩陣(p＞2n，q＜p)，若q為n或n的整數倍，則此時矩陣的秩不等于列數q。

3.2 改進識別算法

傳統方法要求分析矩陣的行數p＞2n，q＜p，(q為矩陣列數，n為碼長)。當n較大而q較小時，p必然較大，導致矩陣分析耗時較長。而由矩陣論的知識可知，分析矩陣的秩不可能大于q，故p對矩陣秩的影響不是很大，可適當減小以求加快識別速率，從而有如下結論:

對碼長為n的歸零Turbo碼建立q×q分析矩陣，若q為n或n的整數倍，則此時矩陣的秩不等于列數q。

以此結論為基礎改進識別算法，將識別矩陣統一為方陣，這樣在q較小時將明顯減小分析矩陣運算量，提高識別速率。該識別算法的具體步驟如下:

②設截獲到的Turbo碼流為c，從起點c1開始連續取i×i比特碼元，將所取碼流按行排列成i×i矩陣C，計算矩陣秩r(i)。

③ 設b(i)=i－r(i)，以 i為橫坐標，b(i)為縱坐標畫出識別圖。如識別圖存在至少一根明顯譜線(約為周圍譜線長度5倍以上)，則可認為碼長已包含于內;否則i分別取+1，……，重復步驟②和步驟③繼續搜索，直至滿足上述條件。

④若b(i)中最大值的位置唯一，設b(i)中最大值為b1，其位置為i1，第二大值為b2，其位置為i2，若abs(i1－i2)=i1或i2，且b2也為明顯譜線，則可認為碼長n=abs(i1－i2)。若不滿足abs(i1－i2)=i1或i2，或雖然滿足但b2不為明顯譜線，則可認為碼長n=i1;

⑤若b(i)中最大值的位置不唯一，其位置由小到大為 i1，i2……，則可認為碼長 n=i2－i1。

4 仿真實驗分析

對上述識別算法進行仿真，選取交織幀長分別為40 bit、60 bit和 80 bit，得出碼長識別仿真圖，并采用蒙特卡洛仿真分析不同交織幀長度下識別概率與誤碼率之間的關系。

仿真實驗1:交織幀長度k=40 bit、誤碼率為0.004的條件下，碼長識別仿真圖如圖2所示。

圖2 k=40 bit條件下仿真

從圖2中可以看出，存在2個明顯譜線:i1=132 bit，i2=264 bit，abs(i1－ i2)=i1=132 bit，故可認為碼長n=132 bit，由前面論述可知碼長n=3×k+12，可知識別結果正確。

仿真實驗 2:交織幀長度 k=40 bit，60 bit，80 bit的條件下，分別對不同誤碼率下的識別概率進行蒙特卡洛仿真，識別概率曲線如圖3所示。

圖3 各交織幀長度下識別概率曲線

由圖3可以看出，識別算法在10－3誤碼率條件下有著良好的識別效果，交織幀長度k＜80 bit、誤碼率小于0.004條件下識別正確率基本可達100%。隨著誤碼率的提高，識別概率降低。同一誤碼率下交織長度越短(碼長越短)識別概率越高，原因是在相同誤碼率下，碼長越長，分析矩陣越大，所含誤碼個數越多，對分析矩陣秩的影響越大，從而導致識別概率越低;另外，由圖3可以看出，改進算法在提高識別效率的同時，容錯性能也明顯提高，在交織幀長k=40 bit條件下，保證識別概率高于接近100%的最高誤碼率由0.001提升為0.007，其原因可以理解為減小了分析矩陣行數，從而降低了分析矩陣所含誤碼數。

由仿真可知，較之傳統算法，此改進算法識別效率明顯提高。在不同碼長情況下，傳統算法與改進算法在同一臺計算機下運行耗時如表2所示。

表2 傳統算法與改進算法耗時比較

由表2可以看出，改進算法的運行時間僅為傳統算法的1/3左右。

5 結束語

Turbo碼在編碼器結構上不同于一般線性分組碼及卷積碼，其編碼結構較為復雜，故對其進行數學分析也較為困難。從數學角度推導其生成矩陣，有助于加深理解其編碼特征，為其識別算法的研究提供理論基礎。利用分析矩陣秩特征的方法進行Turbo碼長識別，算法簡單且具有一定的容錯性能，但計算量偏大。通過減小分析矩陣大小，并且設置合適的判決規則可以減小計算量，提高算法運行速度，滿足實際工程應用當中有效性與可靠性相統一的原則。 ■

［1］BERROU C，GLAVIEUX A，THITIMAJSHIMA P.Near Shannon Limit Error－Correcting Coding and Decoding:Turbo Codes［J］.IEEE International Conference on Communication，1993(2):1064 －1070.

［2］劉玉君.信道編碼［M］.鄭州:河南科學技術出版社，2001.

［3］王新梅，肖國鎮.糾錯碼—原理與方法(修訂版)［M］.西安:西安電子科技大學出版社，2001.

［4］張永光，樓才義.信道編碼及其識別分析［M］.北京:電子工業出版社，2010.

［5］3GPP TS 25.212 V3.9.0.Multiplexing and Channel Coding(FDD)［S］，2002.

［6］BLAHUT R.Algebraic Codes for Data Trans missiom［M］.UK:Cambridge University Press，2003.

［7］昝俊軍，李艷斌.低碼率二進制線性分組碼的盲識別［J］.無線電工程，2009，39(1):19－24.