一種基于矩陣分析的Turbo碼長(zhǎng)識(shí)別算法

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

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

0 引言

Turbo碼以其在低信噪比應(yīng)用環(huán)境中所展現(xiàn)的優(yōu)異糾錯(cuò)性能，在3G移動(dòng)通信和衛(wèi)星通信等領(lǐng)域得到了廣泛應(yīng)用。因此，在通信偵察中如何從通信信號(hào)解調(diào)之后得到的數(shù)據(jù)碼流中準(zhǔn)確快速地分析出Turbo碼的編碼結(jié)構(gòu)及編碼參數(shù)，是不可避免且亟待解決的技術(shù)問題。目前國(guó)內(nèi)外有關(guān)信道編碼識(shí)別技術(shù)的研究主要針對(duì)于線性分組碼及卷積碼，有關(guān)Turbo碼的研究主要集中于其編譯碼性能的優(yōu)化，對(duì)于其識(shí)別技術(shù)的研究還處于探索階段。深入研究了Turbo碼的歸零方式和生成矩陣，提出了一種基于矩陣秩特征的Turbo碼長(zhǎng)識(shí)別算法，并通過仿真驗(yàn)證了算法的容錯(cuò)性能及識(shí)別效率。

1 Turbo碼基本原理

1.1 Turbo碼編碼結(jié)構(gòu)

Turbo碼的典型編碼結(jié)構(gòu)為WCDMA協(xié)議中所采用的編碼結(jié)構(gòu)，如圖1所示。

圖1 WCDMA協(xié)議中Turbo碼編碼結(jié)構(gòu)

1.2 Turbo碼歸零方式

歸零碼元為所有的信息比特經(jīng)過分量編碼器以后繼續(xù)輸入的歸零比特，目的是迫使編碼器回到全零狀態(tài)。當(dāng)k位信息碼元完成編碼之后首先斷開第3路，輸入3個(gè)碼元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個(gè)編碼器RSC1和第2個(gè)編碼器RSC2結(jié)構(gòu)完全相同，歸零模式也相同，僅以RSC1的歸零為例。

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

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

由式(4)可得:

2 生成矩陣分析

2.1 第2路生成矩陣G2

考慮圖1所示分量編碼器結(jié)構(gòu)，設(shè)最左邊加法器后的數(shù)據(jù)為uk，則有如下關(guān)系:

將式(6)合并:

由式(7)可得:

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

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

2.2 第3路生成矩陣G3

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

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

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

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

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

2.3 第1路生成矩陣G1

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

2.4 Turbo碼整體生成矩陣

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

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

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

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

如卷積碼定義中所述，當(dāng)前碼組中校驗(yàn)比特不僅與當(dāng)前碼組信息比特有關(guān)，還與之前碼組的信息比特有關(guān)，而這種碼組之間的影響就是由寄存器實(shí)現(xiàn)的，因?yàn)榧拇嫫鞅Ａ袅酥按a組的信息。而對(duì)于Turbo碼來說，在每一幀編碼完成之后對(duì)寄存器進(jìn)行歸零則抹去了本幀的信息，將不會(huì)對(duì)之后幀的編碼產(chǎn)生影響，各幀按照同一生成矩陣獨(dú)立編碼，完全等同于線性分組碼的編碼特點(diǎn)。

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

3 碼長(zhǎng)識(shí)別

3.1 傳統(tǒng)識(shí)別算法

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

對(duì)于碼長(zhǎng)為n的線性分組碼所構(gòu)成的p×q矩陣(p＞2n，q＜p)，若q為n或n的整數(shù)倍，則此時(shí)矩陣的秩不等于列數(shù)q。

3.2 改進(jìn)識(shí)別算法

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

對(duì)碼長(zhǎng)為n的歸零Turbo碼建立q×q分析矩陣，若q為n或n的整數(shù)倍，則此時(shí)矩陣的秩不等于列數(shù)q。

以此結(jié)論為基礎(chǔ)改進(jìn)識(shí)別算法，將識(shí)別矩陣統(tǒng)一為方陣，這樣在q較小時(shí)將明顯減小分析矩陣運(yùn)算量，提高識(shí)別速率。該識(shí)別算法的具體步驟如下:

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

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

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

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

4 仿真實(shí)驗(yàn)分析

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

仿真實(shí)驗(yàn)1:交織幀長(zhǎng)度k=40 bit、誤碼率為0.004的條件下，碼長(zhǎng)識(shí)別仿真圖如圖2所示。

圖2 k=40 bit條件下仿真

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

仿真實(shí)驗(yàn) 2:交織幀長(zhǎng)度 k=40 bit，60 bit，80 bit的條件下，分別對(duì)不同誤碼率下的識(shí)別概率進(jìn)行蒙特卡洛仿真，識(shí)別概率曲線如圖3所示。

圖3 各交織幀長(zhǎng)度下識(shí)別概率曲線

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

由仿真可知，較之傳統(tǒng)算法，此改進(jìn)算法識(shí)別效率明顯提高。在不同碼長(zhǎng)情況下，傳統(tǒng)算法與改進(jìn)算法在同一臺(tái)計(jì)算機(jī)下運(yùn)行耗時(shí)如表2所示。

表2 傳統(tǒng)算法與改進(jìn)算法耗時(shí)比較

由表2可以看出，改進(jìn)算法的運(yùn)行時(shí)間僅為傳統(tǒng)算法的1/3左右。

5 結(jié)束語

Turbo碼在編碼器結(jié)構(gòu)上不同于一般線性分組碼及卷積碼，其編碼結(jié)構(gòu)較為復(fù)雜，故對(duì)其進(jìn)行數(shù)學(xué)分析也較為困難。從數(shù)學(xué)角度推導(dǎo)其生成矩陣，有助于加深理解其編碼特征，為其識(shí)別算法的研究提供理論基礎(chǔ)。利用分析矩陣秩特征的方法進(jìn)行Turbo碼長(zhǎng)識(shí)別，算法簡(jiǎn)單且具有一定的容錯(cuò)性能，但計(jì)算量偏大。通過減小分析矩陣大小，并且設(shè)置合適的判決規(guī)則可以減小計(jì)算量，提高算法運(yùn)行速度，滿足實(shí)際工程應(yīng)用當(dāng)中有效性與可靠性相統(tǒng)一的原則。 ■

［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］.鄭州:河南科學(xué)技術(shù)出版社，2001.

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

［4］張永光，樓才義.信道編碼及其識(shí)別分析［M］.北京:電子工業(yè)出版社，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ìn)制線性分組碼的盲識(shí)別［J］.無線電工程，2009，39(1):19－24.