基于線性分組碼的偽隨機交織識別

廖 斌，張 玉，楊曉靜

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

0 引言

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

1 基于線性分組碼的偽隨機交織識別基礎

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

1.1 “秩準則”算法

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

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

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

1.3 偽隨機交織器原理

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

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

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

1.4 識別模型

假設信道為二元對稱信道（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，通過分析識別出其交織長度、交織起始點和交織置換關系，完成偽隨機交織識別，從而恢復出原始數(shù)據(jù)C。

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

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

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

2.1 交織長度和交織起始點的識別

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

例如，（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)，當數(shù)據(jù)分析矩陣A的列值na與交織長度L相等，或為交織長度L的整數(shù)倍，即滿足na＝a·L（a∈N＋）時，由于監(jiān)督碼元恰好都處在同一列上，這樣數(shù)據(jù)矩陣具有缺秩的特性，即

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

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

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

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

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

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

2.2 偽隨機交織置換關系的識別

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

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

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

2.3 算法步驟

基于線性分組碼的偽隨機交織識別算法包括兩個部分：識別交織交織長度和交織起始點和識別交織置換關系識別。

1）識別交織長度和交織起始點

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

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

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

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

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

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

2）識別交織置換關系

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

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

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

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

3 仿真實驗

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

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

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

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

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

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

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

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

4 結(jié)論

本文提出了基于線性分組碼的偽隨機交織識別算法，首先利用“秩準則”識別交織長度、交織起始點，在此基礎上提出反轉(zhuǎn)誤碼率最小準則識別交織置換關系。仿真實驗結(jié)果表明了本文方法在誤碼率小于0.008時的識別準確率可達100%，當誤碼率達到0.009時，其識別準確率超過90%，誤碼率在0.01時，識別準確率在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］.電子學報，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］.電訊技術，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］劉勝美，趙春明，李燦偉.盲速率判決技術在OFDM系統(tǒng)中的應用［J］.電子與信息學報，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.