廖 斌，張 玉，楊曉靜

（解放軍電子工程學(xué)院，安徽 合肥 230037）

0 引言

在數(shù)字通信中，信道中的噪聲和干擾將引起通信系統(tǒng)的性能惡化，交織技術(shù)由于具有抵御突發(fā)錯誤的能力而得到廣泛應(yīng)用［1－4］，這使得交織識別成為信息截獲領(lǐng)域?qū)崿F(xiàn)信息還原的必不可少的步驟。現(xiàn)有交織主要分為行列式交織、卷積交織和偽隨機(jī)交織。目前，關(guān)于交織識別的研究主要集中在行列式交織和卷積交織的交織長度和交織起始點(diǎn)的盲識別上。文獻(xiàn)［5］首先提出了基于“秩準(zhǔn)則”的行列式交織的交織長度的盲識別；文獻(xiàn)［6—7］在文獻(xiàn)［5］的基礎(chǔ)上通過引入高斯消元法提高了識別算法的容錯性，使之更適用于實(shí)際情況；文獻(xiàn)［8—10］討論了卷積交織的參數(shù)盲識別問題?？梢?，已有的文獻(xiàn)主要集中在行列式交織和卷積交織這兩種交織器的的盲識別上，而對偽隨機(jī)交織的識別研究未見報(bào)道。因此，本文提出的基于線性分組碼的偽隨機(jī)交織識別算法具有重要的意義。

1 基于線性分組碼的偽隨機(jī)交織識別基礎(chǔ)

交織中常用的糾錯編碼包括線性分組碼、卷積碼、RS碼等。（n，k）線性分組碼是指將每k個信息位分為一組，通過編碼矩陣G變成長度為n（n＞k）位的編碼，監(jiān)督位是信息位的線性組合，監(jiān)督位數(shù)位（n－k）。

1.1 “秩準(zhǔn)則”算法

“秩準(zhǔn)則”算法根據(jù)交織中線性分組碼的信息碼元與監(jiān)督碼元的線性相關(guān)性，通過將截獲碼元序列排成列數(shù)不同的矩陣并求秩，尋找缺秩矩陣所對應(yīng)的列數(shù)及截獲序列的起點(diǎn)來識別交織長度和交織起始點(diǎn)。

1.2 反轉(zhuǎn)誤碼率最小準(zhǔn)則

反轉(zhuǎn)誤碼率最小準(zhǔn)則主要應(yīng)用于信號速率盲監(jiān)測［11］。反轉(zhuǎn)誤碼率最小準(zhǔn)則是指將截獲序列按可能的編碼、交織等方式等進(jìn)行譯碼、解交織處理后再按對應(yīng)的方式進(jìn)行編碼、交織，將所得的新序列與原截獲序列進(jìn)行比較，選擇使兩個序列中相異碼元數(shù)最小即反轉(zhuǎn)誤碼率最小時所對應(yīng)的編碼、交織方式作為截獲序列的編碼、交織方式。

1.3 偽隨機(jī)交織器原理

一個長度為N的交織器在數(shù)學(xué)上可以描述為一個N 階置換［1－2］。設(shè)∏N表示一個N 階置換，即

其中，1≤∏i≤N （0≤i≤1），且∏i≠∏j（i≠j）。

m序列常用于偽隨機(jī)交織器的設(shè)計(jì)?；趍序列的偽隨機(jī)交織就是通過m序列產(chǎn)生的偽隨機(jī)序列作為交織器的地址索引完成序列的置換。移位寄存器每移位一次，n個寄存器輸出的數(shù)據(jù)構(gòu)成一個狀態(tài)，一個狀態(tài)對應(yīng)一個信息符號。因?yàn)閙序列是周期為p＝2n－1的周期序列，所以交織長度L就是m序列的周期p。這樣共有p個信息符號對應(yīng)m序列p個狀態(tài)，將這p個狀態(tài)轉(zhuǎn)化為十進(jìn)制數(shù)，再對這些十進(jìn)制數(shù)按照某一規(guī)律進(jìn)行置換，將它們對應(yīng)的信息符號按照這個置換順序發(fā)送，就實(shí)現(xiàn)了偽隨機(jī)交織。例如，3級移位寄存器的特征多項(xiàng)式為f（x）＝1＋x＋x3，產(chǎn)生的一個周期m序列為：1 0 1 1 1 0 0，則該 m 序列升序交織示意圖如圖1所示。

1.4 識別模型

假設(shè)信道為二元對稱信道（BSC），信道誤碼率為Pe（0≤Pe≤0.5）。

記截獲到的數(shù)據(jù)序列為Z＝｛z1，z2，…，zn｝，發(fā)送端的數(shù)據(jù)序列為C＝｛c1，c2，…，cn｝，信道誤碼圖案為E＝｛e1，e2，…，en｝，則有

式（2）中，⊕表示模2加。

在信息截獲中，偵察方并不知道截獲數(shù)據(jù)序列的交織參數(shù)，本文研究的內(nèi)容就是根據(jù)截獲的Z，通過分析識別出其交織長度、交織起始點(diǎn)和交織置換關(guān)系，完成偽隨機(jī)交織識別，從而恢復(fù)出原始數(shù)據(jù)C。

圖1 交織長度為7的m序列偽隨機(jī)交織器Fig.1 The m sequence pseudo－random interleaver with the interleaving sizeof 7

2 基于線性分組碼的偽隨機(jī)交織識別

基于線性分組碼的偽隨機(jī)交織識別包括對交織長度、交織起始點(diǎn)和交織置換關(guān)系的識別。2.1節(jié)利用“秩準(zhǔn)則”識別偽隨機(jī)交織的交織長度和交織起始點(diǎn)，2.2節(jié)利用反轉(zhuǎn)誤碼率最小準(zhǔn)則實(shí)現(xiàn)偽隨機(jī)交織器的交織置換關(guān)系的識別。

2.1 交織長度和交織起始點(diǎn)的識別

本小節(jié)利用“秩準(zhǔn)則”實(shí)現(xiàn)對偽隨機(jī)交織的交織長度和交織起始點(diǎn)的識別。根據(jù)所采用的糾錯碼的性質(zhì)和交織器的特點(diǎn)，尋找由截獲到的序列構(gòu)成的數(shù)據(jù)分析矩陣中最大數(shù)目的“相關(guān)列”［7］，根據(jù)取到最大的“相關(guān)列”所對應(yīng)的數(shù)據(jù)分析矩陣的列數(shù)及截獲序列的起點(diǎn)作為交織長度和交織起始點(diǎn)。

例如，（n，k）線性分組碼是由一個滿秩的生成矩陣G將k bit的信息碼元編成n bit的糾錯碼元。

其中，Pn－k稱作該（n，k）線性分組碼的監(jiān)督矩陣，pij∈ ｛0，1｝（1≤i≤k，1≤j≤n－k）。由C＝M·G可知，

由式（3）可知，生成的碼序列C中的一部分碼元ci是其他碼元的線性組合，而交織器的作用只是改變序列中碼元的位置，并不改變信息內(nèi)容。因此，線性分組碼經(jīng)過交織后這種性質(zhì)仍然存在。將截獲的信息序列排成一個列值為na的數(shù)據(jù)分析矩陣A?？梢园l(fā)現(xiàn)，當(dāng)數(shù)據(jù)分析矩陣A的列值na與交織長度L相等，或?yàn)榻豢楅L度L的整數(shù)倍，即滿足na＝a·L（a∈N＋）時，由于監(jiān)督碼元恰好都處在同一列上，這樣數(shù)據(jù)矩陣具有缺秩的特性，即

而當(dāng)數(shù)據(jù)矩陣A的列值na與交織長度L不滿足相等或倍數(shù)的關(guān)系時，此時的A是一個二元隨機(jī)混排矩陣，它的秩為1，如圖2所示（圖中，監(jiān)督碼元所在位置用灰色標(biāo)注），據(jù)此可以得到交織長度L。而當(dāng)數(shù)據(jù)矩陣A的第一個元素恰好是交織序列的起始點(diǎn)時，這時ρ將取到最小值，故可以在得到交織長度L的條件下，再遍歷尋找序列移位時使ρ最小的移位量，從而找到交織起始點(diǎn)d。

圖2 不同列值na下的數(shù)據(jù)分析矩陣ig.2 The data analysis matrix withdifferent columns of na

當(dāng)信道中存在誤碼時，由于誤碼的影響，可能使得“相關(guān)列”間的約束關(guān)系被破壞而不能正確估計(jì)交織長度，本文采用有限域上的高斯約當(dāng)消元法［7］進(jìn)行改進(jìn)。具體做法是將數(shù)據(jù)矩陣A化成下三角陣AL，根據(jù)下三角陣AL的下半部分ALd的列向量的漢明重量計(jì)算Q（Q為滿足有誤碼的門限條件下的相關(guān)列的列數(shù)），Q的計(jì)算公式為［7］：

其中，card｛·｝表示集合的勢，φ（k）是矩陣ALd的第k列的漢明重量與ALd所有列向量的漢明重量的均值的比值，β為檢測門限。檢測門限β的選取與誤碼率有關(guān)，通常選取的檢測門限β為（0.2，0.6）［6－7］。

定義：矩陣ALd中Q與總列數(shù)na的比值為x，

由前面的分析可知，當(dāng)x取到最大值時，此時的數(shù)據(jù)分析矩陣列數(shù)na就為所要識別的交織長度L，數(shù)據(jù)分析矩陣列數(shù)na的第一個碼元所在位置定為交織起始點(diǎn)，由此實(shí)現(xiàn)對偽隨機(jī)交織長度和交織起始點(diǎn)的識別。

2.2 偽隨機(jī)交織置換關(guān)系的識別

由1.3節(jié)分析的基于m序列的偽隨機(jī)交織的原理可知，決定偽隨機(jī)交織置換關(guān)系的是偽隨機(jī)交織器中m序列的長度和產(chǎn)生m序列的線性反饋移位寄存器（LFSR）中各寄存器的初態(tài)。由于偽隨機(jī)交織的特點(diǎn)，特別是在截獲數(shù)據(jù)長度有限或交織長度較大的情況下，直接觀察出交織置換規(guī)律很困難。本文借鑒通信系統(tǒng)中用于速率盲監(jiān)測的方法［8］，提出一種基于反轉(zhuǎn)誤碼率最小準(zhǔn)則下的偽隨機(jī)交織置換關(guān)系識別方法。

在2.1節(jié)中，已經(jīng)得到了偽隨機(jī)交織的長度和交織起始點(diǎn)，在此基礎(chǔ)上，根據(jù)p＝2n－1反推得到線性反饋移位寄存器（LFSR）的級數(shù)p，則該LFSR的初態(tài)共有2p－1個（全0狀態(tài)排除）。設(shè)LFSR的初態(tài)集合為I＝ ｛I1，I2，…，I2p－1｝，因?yàn)閭坞S機(jī)交織置換關(guān)系由LFSR中各寄存器的初態(tài)決定，則對應(yīng)的交織置換關(guān)系共有2p－1種，設(shè)交織置換關(guān)系的集合為S＝ ｛S1，S2，…，S2p－1｝。對一個周期為L ＝2p－1的偽隨機(jī)交織器，其LFSR所用的初態(tài)Ik必有Ik∈I，其對應(yīng)的交織置換關(guān)系必有Sk∈S。根據(jù)交織長度L＝2p－1尋找可能的編碼方式B＝｛B1，B2，…，BR｝，則必有截獲序列所用的編碼方式Bj∈B，則交織與編碼相結(jié)合的方式共有R·（2p－1）種。

遍歷R·（2p－1）種交織與編碼相結(jié)合的方式對截獲序列Z進(jìn)行解交織、譯碼后得到R·（2p－1）種信息序列C′＝ ｛C′1，C′2，…，C′R·（2p－1）｝。對得到的信息序列C′再根據(jù)譯碼方式進(jìn)行對應(yīng)的編碼、交織得到R·（2p－1）種對應(yīng)的編碼序列Z′＝ ｛Z′1，Z′2，…，Z′R·（2p－1）｝。 將 Z′ ＝ ｛Z′1，Z′2，…，Z′R·（2p－1）｝與截獲序列 Z進(jìn)行模2和運(yùn)算，得到的反轉(zhuǎn)誤碼率（RESR）集合為 W′ ＝ ｛W′1，W′2，…，W′R·（2p－1）｝。當(dāng)編碼方式與交織置換關(guān)系識別錯誤時，所得到的C′進(jìn)行再編碼、交織所得的編碼序列Z′可看做一個隨機(jī)序列，其與原截獲序列Z比較所得的反轉(zhuǎn)誤碼率（RESR）較大；而當(dāng)編碼方式和交織置換關(guān)系識別準(zhǔn)確時，所得到的C′進(jìn)行再編碼所得的編碼序列Z′與原截獲序列Z基本相同，兩者之間的反轉(zhuǎn)誤碼率（RESR）很小。因此，求使式（7）最小的（Bj，Sk）中的Sk即為所求的交織置換關(guān)系。

2.3 算法步驟

基于線性分組碼的偽隨機(jī)交織識別算法包括兩個部分：識別交織交織長度和交織起始點(diǎn)和識別交織置換關(guān)系識別。

1）識別交織長度和交織起始點(diǎn)

設(shè)定檢測門限β，na的最小檢測值為namin、最大檢測值為namax，na從namin到namax變化，d從0到na－1變化，兩個識別參數(shù)構(gòu)成二維循環(huán)，每次循環(huán)中進(jìn)行如下步驟：

步驟1設(shè)初值：設(shè)Q的初始值為0，Q與na的比值x為0；

步驟2預(yù)處理：將截獲序列排成數(shù)據(jù)矩陣并通過高斯約當(dāng)消元法化成下三角陣AL；

步驟3求列漢明重量和均值：取下三角陣的下半部分ALd計(jì)算各列的漢明重量，并求出均值；

步驟4比較、記錄：由公式（5），（6）計(jì)算Q和x，并記錄對應(yīng)的na，d。

當(dāng)所有循環(huán)結(jié)束時，尋找最大的x和對應(yīng)的na，d，得到交織長度和交織起始點(diǎn)值。

2）識別交織置換關(guān)系

步驟1求交織置換關(guān)系集合：由識別出的交織長度反推得到LFSR的級數(shù)p和對應(yīng)的交織置換關(guān)系的集合S＝ ｛S1，S2，…，S2p－1｝；

步驟2遍歷解交織、譯碼：遍歷R·（2p－1）種交織與編碼相結(jié)合的方式對截獲序列Z進(jìn)行解交織、譯碼，得到R·（2p－1）種信息序列C′＝ ｛C′1，C′2，…，C′R·（2p－1）｝；

步驟3求反轉(zhuǎn)誤碼率：對C′進(jìn)行再編碼、交織得到Z′，與Z進(jìn)行模2和運(yùn)算得到反轉(zhuǎn)誤碼率集合W′；

步驟4匹配置換關(guān)系：尋找使式（7）最小的Sk，判定為交織置換關(guān)系。

3 仿真實(shí)驗(yàn)

由于篇幅限制，本文研究的前提條件是假定編碼方式已經(jīng)得到識別，對編碼方式的識別不再討論。

仿真實(shí)驗(yàn)1：驗(yàn)證算法的有效性。仿真實(shí)驗(yàn)采用（15，7）線性分組碼，采用4級的LFSR，特征多項(xiàng)式為f（x）＝x4＋x＋1，置換關(guān)系對應(yīng)的寄存器初態(tài)為（0001），截獲序列Z的首位是發(fā)送端序列C中的第9位，即交織起始點(diǎn)d＝9，檢測門限β＝0.5，誤碼率Pe＝0.001。交織長度與交織起始點(diǎn)的仿真識別結(jié)果如圖3，交織置換關(guān)系的仿真識別結(jié)果如圖4。

圖3表明：在交織長度為15，交織起始點(diǎn)為9的情況下，x＝0.600為最大值，與實(shí)驗(yàn)條件一致，表明識別正確。圖4表明：在置換關(guān)系對應(yīng)的初態(tài)（0001）時，反轉(zhuǎn)誤碼率最小，識別結(jié)果與實(shí)驗(yàn)條件相同，識別正確。

圖3 不同交織長度和交織起始點(diǎn)下的x值Fig.3 The values of x with different interleaving size and interleaving delay

圖4 置換關(guān)系識別結(jié)果Fig.4 The result of the recognition about interleaving permutation

仿真實(shí)驗(yàn)2：算法容錯性能比較。仿真實(shí)驗(yàn)采用（7，3）線性分組碼，采用6級的LFSR，特征多項(xiàng)式為f（x）＝x6＋x＋1，置換關(guān)系對應(yīng)的寄存器初態(tài)為（000001），截獲序列Z的首位是發(fā)送端序列C中的第9位，即交織起始點(diǎn)d＝9，檢測門限β＝0.5。誤碼率Pe從0到0.02，以0.001為步進(jìn)變化，仿真結(jié)果如圖5所示。

圖5 不同誤碼率下的識別正確率Fig.5 The accuracy of recognition with different bit error rates

由圖5可知，本文方法在誤碼率小于0.008時的識別準(zhǔn)確率可達(dá)100%，當(dāng)誤碼率達(dá)到0.009時，其識別準(zhǔn)確率超過90%，誤碼率在0.01時，識別準(zhǔn)確率在75%以上，具有較好的容錯性能。

4 結(jié)論

本文提出了基于線性分組碼的偽隨機(jī)交織識別算法，首先利用“秩準(zhǔn)則”識別交織長度、交織起始點(diǎn)，在此基礎(chǔ)上提出反轉(zhuǎn)誤碼率最小準(zhǔn)則識別交織置換關(guān)系。仿真實(shí)驗(yàn)結(jié)果表明了本文方法在誤碼率小于0.008時的識別準(zhǔn)確率可達(dá)100%，當(dāng)誤碼率達(dá)到0.009時，其識別準(zhǔn)確率超過90%，誤碼率在0.01時，識別準(zhǔn)確率在75%以上，具有較好的容錯性能。

［1］John G.Proakis.Digital Communications（Fourth Edition）［M］.Beijing：Publishing House of Electronics Industry，2008：467－469.

［2］Ramsey J L.Realization of optimum interleavers［J］.IEEE Transactions on Information Theory，1970（3）：338－345.

［3］Forney G Jr.Burst－correcting codes for the classic bursty channel ［J］.IEEE Transactions on Communication Technology，1971，19（5）：772－781.

［4］張永光，樓才義.信道編碼及其識別分析［M］.北京：電子工業(yè)出版社，2010：108－117.

［5］Burel G，Gautier R.Blind estimation of encoder interleaver characterstics in a non－cooperative context［C］／／Proceedings of the IASTED International conference on communication，Internet and Information Technology Scottsdale，AZ，USA：ACTA Press，2003.275－280.

［6］Guillaume Sicot，Sbastien Houcke.Blind detection of interleaver parameters.Proceeding of the ICASSP 2005［C］.Philadephia，USA：IEEE Press，2005.829－832.

［7］Guillaume Sciot，Sebastien Houche，Johann Barbier.Blind detection of interleaver parameters［J］.Signal Processing，2009，89（4）：450－462.

［8］Liru Lu，Kwok Hung Li，Yong Liang Guan.Blind identification of convolutional interleaver parameters ［C］／／ICICS 2009proceedings of 7thInternational conference on Information，Communications and Signal Processsing.Piscataway，NJ，USA：IEEE Press，2009，1－5.

［9］甘露，劉宗輝，廖紅舒，等.卷積交織參數(shù)的盲估計(jì)［J］.電子學(xué)報(bào)，2011，39（9）：2173－2177.GAN Lu，LIU ZhongHui，LIAO HongShu，et al.Blind estimation of the parameters of convolutional interleave［J］.Acta Electronica Sinica，2011，39（9）：2173－2177.

［10］張玉，張偉杰，楊曉靜.數(shù)字通信中卷積交織盲識別方法［J］.電訊技術(shù)，2011，51（5）：62－66.ZHANG Yu，ZHANG WeiJie，YANG XiaoJing.A blind recognition method of convolutional interleaving in digital communication［J］.Telecommunication Engineering，2011，51（5）：62－66.

［11］劉勝美，趙春明，李燦偉.盲速率判決技術(shù)在OFDM系統(tǒng)中的應(yīng)用［J］.電子與信息學(xué)報(bào)，2006，28（3）：396－399.LIU Shengmei，ZHAO Chunming，Li Canwei.Blind rate detection applied in the IPR－OFDM system ［J］.Journal of Electronics ＆ Information Technology，2006，28（3）：396－399.