基于矩陣秩統計的卷積碼分組交織盲識別

陸 凱，張 旻，李歆昊

（1.解放軍電子工程學院，安徽 合肥 230037；2.安徽省電子制約技術重點實驗室，安徽 合肥 230037）

0 引言

交織器由于能極大限度的改變信息結構，把信道突發錯誤分散到多個碼字中，使糾錯碼的作用體現出來，被廣泛應用于數字衛星廣播、深空探測和移動通信等系統中［1］。在非合作對抗領域，對于存在交織的編碼數據，想要得到原始信息，首先需要解決交織參數的識別問題，然后才能根據解交織后的數據進行后續的編碼識別，最終譯碼得到原始數據，因此交織的盲識別技術研究對于智能通信以及信息截獲領域具有十分重要的意義。

分組交織是交織編碼的一種重要方式，對其盲識別研究越來越引起同行的重視，各種識別方法不斷涌現。如文獻［2］首先提出了基于“秩準則”的分組交織的交織長度的盲識別方法；文獻［3-5］在文獻［2］的基礎上通過引入高斯消元法提高了識別算法的容錯性，使之更適用于實際情況；文獻［6］提出利用碼重分布特性的方法對基于低碼率線性分組碼的分組交織長度進行識別。但是這些方法僅僅識別了交織長度，沒有進一步對交織矩陣的行數、列數進行研究；文獻［7］在矩陣分析法獲取交織長度的基礎上，提出反向糾錯思想，窮舉條件規定范圍內所有可能的分組碼和交織模式，識別了交織矩陣的行數、列數以及交織起始點，但是存在運算數據量巨大，識別正確率不高等問題，使得算法使用受限。因此，現有的識別算法難以滿足非合作情況下的盲識別需求。本文針對此問題，提出了基于矩陣秩統計的卷積碼分組交織盲識別方法。

1 分組交織的基本概念

1.1 分組交織的基本原理

分組交織按一種規則排列成矩陣形式，然后再按另一種順序讀出，從而打亂原有編碼序列，重新組合成一組長序列，具體如圖1和圖2所示。

圖1 輸入數據Fig.1 Input sequence

圖2 交織數據Fig.2 Interleaved sequence

其交織映射函數可以表示為［9］：

式（1）中，L 為交織長度，n為交織矩陣的列數，mod表示伽羅華域運算。

1.2 卷積碼的分組交織的性質

為保證卷積碼和分組交織器結合的最優性能，卷積碼和分組交織之間滿足以下性質［8］：

1）L ≥n（m+1），即交織的長度必須大于卷積碼的約束長度；

2）分組交織的長度是卷積碼的碼長的倍數；

3）交織器的起始點是卷積碼的起始點；

4）塊內連續性：在分組交織中卷積碼的一個碼長內的數據一定在一個分組塊中，無論怎么變換，也不會使碼字變化到另一個分組中，因此，可以利用此性質求解交織長度；

5）塊間連續性：相鄰的交織塊之間具有時間連續性，信息序列變化時也只在本分組塊之間變化，所以在恢復交織后，碼字之間的約束關系是不變的。

卷積碼分組交織的盲識別就是利用這些性質，完成對交織矩陣的行數、列數以及交織起始點的識別。

2 基于矩陣秩統計的卷積碼分組交織盲識別

2.1 卷積碼分組交織的性質分析和推導

對于接收的卷積碼分組交織數據，交織長度為L=m×n，m 和n 分別為交織矩陣的行數和列數。由式（1）可知，在同一個交織矩陣中，同一行中相鄰的數據，列讀出后的距離變成了交織塊的行數m，如圖3所示（其中a，b，…，x 不同字母表示不同的交織塊）。

圖3 交織采樣模型Fig.3 Intertwinedsampling model

由圖3可知，在每一個交織塊中任意一行的數據 都 是 一 段 連 續 的 卷 積 碼 信 息 序 列cpn+1cpn+2…cpn+n。根據（n0，k0，m）卷積碼的性質，當信息序列的長度大于卷積碼的約束長度時，該信息序列必然存在校驗向量HN×1，使得［8］：

式（2）中，N =n0（m+1）為該卷積碼的約束長度。由卷積碼分組交織的性質可知，每一個分組交織塊的起始點都是卷積碼的起始點，因此對各交織塊的同一行數據，數據的位置與卷積碼的位置存在特定的一一對應關系，可以得到：

卷積碼是一種有記憶編碼，當交織矩陣的列數大于卷積碼的約束長度時，提取各交織塊中同一行數據構成一個p×q矩陣（q＞N，p＞q），該矩陣具有以下性質：

定理1由連續的（n0，k0，m）卷積碼信息序列所構成的p×q矩陣，當矩陣的列數q＞n0（m+1），p＞q時，若卷積碼在矩陣中的位置一一對應，則對該矩陣進行單位化后左上角單位陣維數相等，且此時矩陣的秩不等于列數q［8］。

定理2 對（n0，k0，m）卷積碼所構成的p×q矩陣（q＞n0（m+1），p＞q），如果卷積碼的起始點與矩陣每行的起始點重合時，則單位化后左上角單位陣的維數最?。?］。

由定理1和定理2可以推導出，對不同交織塊中同一行數據建立的矩陣T 進行單位化處理，化簡成 ［IkP ］的形式，可得：

得到該矩陣為非滿秩，rank（T）＜n。則該矩陣可以得到一組編碼約束方程為：

由此約束方程可以得到該段序列中卷積碼的校驗矩陣HN×1［10］。

2.2 交織參數識別

2.2.1 基于矩陣秩統計的交織矩陣的行和列識別假設交織長度為L=m×n，把交織數據排列成矩陣形式，如圖3所示。現對接收數據進行采樣處理，當采樣間隔為交織矩陣的行數m 時，采樣后的序列數據為：

其中a，b，…，x，y，… 不同字母表示不同的交織塊；pn 表示交織塊中的第p 行；anp+i表示采樣數據的起始點。

將序列C 排列成矩陣形式，當矩陣寬度為2n時，會形成如式（6）的矩陣D：

由交織塊中的列數為n，以矩陣D 的第一行為例，當矩陣寬度為2n 時，a 交織塊中得到的第p 行數據apn+iapn+（i+1）…apn+n排列在矩陣D 中第一行的長度為n-i+1，c交織塊中排列在矩陣D 中的數據cpn+1…cpn+（i-1）的長度為i-1，第一行的總長度為2n，所以會存在長度為n的完整的b 交織塊中的一行數據bpn+1bp+2…bpn+n。同理，其他行中也存在完整的交織塊的一行數據，且這些不同的完整交織塊的同一行數據在矩陣D 中的位置相對應，如式（6）中虛線表示的數據，該數據組成的矩陣存在相關列。

根據定理1和式（4）可知D 中虛線所示數據組成的矩陣為非滿秩，而非滿秩矩陣是矩陣D 的一部分，所以可以推導出矩陣D 也為非滿秩。

由此，對交織后的數據進行遍歷采樣處理并構建矩陣，當構建矩陣非滿秩時（即存在相關列），以此采樣周期獲取的數據構建新的矩陣，新矩陣的列數為非滿秩時矩陣列數的周期倍，判別矩陣是否存在相關列，若存在，則此時的采樣間隔為交織矩陣的行數，非滿秩矩陣列數的周期為交織塊的列數，實現了交織長度的識別L=m×n。對矩陣秩統計的求解可以通過高斯消元法來完成的［4］。

2.2.2 交織起始點的確定

2.2.2.1 校驗矩陣的求解

將采樣后的序列C 排列成矩陣形式，當矩陣寬度為2n 時，會形成如式（6）的矩陣D，可表示為D=［T1，T2，T3］其中：

式（1）中，T2矩陣是由完整的不同交織塊中相同行組成的數據，為非滿秩矩陣，由式（4）可知，T2矩陣可以化簡成 ［IkP ］的形式。因此在交織矩陣行列識別出來的基礎上，可以利用該特性，對矩陣D 進行高斯消元法化簡，求解出卷積碼的校驗矩陣HN×1［10］。

2.2.2.2 起始點的識別

由于交織塊的行數和列數已知，假設交織塊的行長為m，列數為n，送入L=m×n解交織器進行解交織處理，如：

圖4 解交織的模型Fig.4 Deinterleaver model

解交織得到：

C2序列會出現兩種情況：

①c1為交織塊的起始點

當c1為交織塊的起始點，由于交織塊的參數已知，因此解交織后就是原始卷積碼數據。由卷積碼的性質可知，一段約束長度為N 的卷積碼數據［ci…ci+N-1］·HN×1=0（其中i表示卷積碼的起始點，N 為卷積碼的約束長度），因此，利用一個長度為N 的滑動窗（窗內包含N 個序列數據），從解交織后數據起始位開始滑動，滑動窗每次移動的距離為一個卷積碼的碼長n0，如：

（C1Cm+1…）1×N與校驗向量HN×1相乘，得到的值為0。因此通過滑動窗的移動，可以獲得周期為碼長n0的0序列。

②c1不為交織塊的起始點

當c1不為交織塊的起始點，長為L=m×n的數據包含兩個交織塊中的元素，假設該數據如下：

其中a，b不同字母表示不同的交織塊。解交織后數據為：

C3= （apn+iapn+i+1…apn+nbpn+1bpn+2…bpn+i-1…

a（m-1）n+ia（m-1）n+i+1…amnb（m-1）n+1b（m-1）n+2…b（m-1）n+i-1…a（p-1）n+i+1a（p-1）n+i+2…apn+nbpn+1bpn+2…bpn+i）

由此可以看出，解交織后的數據中a、b 兩個交織塊中的元素出現了交叉。由于兩個交織塊中的數據之間不存在約束關系，利用校驗矩陣驗證時［apn+i…apn+nbpn+1…bpn+N-n+i-1］·HN×1不 一 定 等 于0。因此利用一個長度N 的滑動窗移動的時候，無法獲得周期為碼長n0的0序列。

這樣就通過遍歷交織數據起始位的方法，并用校驗向量和滑動窗內數據的乘積能夠獲取周期性的0輸出序列的方法來判別分組交織的起始點。

2.3 識別過程

對交織矩陣的行數、列數以及交織起始點的識別的具體步驟如下：

步驟1對接收的交織數據C0進行采樣處理，獲取采樣序列C；

步驟2 對C 序列遍歷構建矩陣，利用高斯消元法求解相關列，判定矩陣是否存在線性約束關系，如果不存在，改變采樣間隔，返回步驟1；

步驟3 把C 序列構建新的矩陣，新矩陣的列數為步驟2中存在相關列時矩陣列數的周期倍，判別新矩陣是否存在相關列，如果存在，則此時判斷交織矩陣的行數為該采樣周期，且此時非滿秩矩陣列數的周期為交織塊的列數，如果不存在，則改變采樣間隔，返回步驟1；

步驟4利用C 序列按交織矩陣的列數的2倍構建矩陣，求解校驗向量H，然后截取一段交織后的信息序列，把該序列流的前L 比特數據依次作為交織起始點進行解交織處理；

步驟5 利用一個長度為N 的矩陣框，從解交織后數據起始位開始截取數據與校驗矩陣相乘，如果得到的值全為零，得到此時的起始點就是交織起始點，反之，不是起始點。

3 仿真實驗

實驗中卷積碼選取多項式為（15，17）的（2，1，4）非系統卷積碼，分組交織選擇行數為19，列數為26的交織塊，仿真獲取交織數據長度為500 000bit，起始點選擇為296bit。

實驗1：交織矩陣的行數和列數識別

通過遍歷采樣周期并對采樣數據求解線性相關列，結果如圖5所示。

由圖5可知，在采樣值為19時出現相關列，且出現相關列的矩陣的列數為26。按存在相關列時矩陣列數的周期倍構建新的矩陣，求解新矩陣是否存在相關列，結果如圖6所示，得到的相關列值如表1所示。

表1 列數與相應的相關列的檢測值Tab.1 The number of columns corresponding detection of related column

由表1可知，檢測值在［26，52，78，104，130］等列時出現相關列，此時存在相關列的矩陣列數的周期為26。根據論文2.2節分析可以判斷最終的交織塊行長m 為19，列寬n為26，因此可得交織長度為19×26=494。

實驗2：不同誤碼條件下交織塊的行數和列數識別率

實驗條件如實驗1，改變接收序列的誤碼率，對本文算法各進行100次蒙特卡羅仿真試驗，并與文獻［2］的“秩準則”算法進行比較，結果如圖7所示。

圖6表明，隨著誤碼率的增加，本文算法始終優于文獻［2］“秩準則”算法。

實驗3：起始點的識別

實驗條件如實驗1，對獲取的交織數據進行交織起始點的識別，識別結果如圖8所示。

由圖8可知，在高誤碼率條件下仍然具有很好的交織起始點的識別率。

圖5 不同采樣值下的相關列Fig.5 Related column under different sampling

圖6 相關列的檢測值Fig.6 Detection of related column of matrix

圖7 兩種方法的容錯性對比Fig.7 Comparison of the two methods of fault tolerance

圖8 不同誤碼率條件下起始點的識別率Fig.8 Recognition rate under different starting points BER

4 結論

本文提出了基于矩陣秩統計的分組交織盲識別方法。該方法首先利用分組交織器中相鄰的碼元交織后距離為交織矩陣的行數的關系，通過對采樣后數據進行矩陣秩統計求解交織矩陣的行數和列數，然后采用校驗矩陣對解交織后的數據驗證的方式識別交織器起始點，實現交織器的盲識別。仿真實驗表明該方法有很好的穩定性和魯棒性，有一定的工程使用價值。

［1］Sung-Joon Park，Jun-Ho Jeon.Interleaver Optimization of Convolutional Turbo Code for 802.16 Systems［J］.IEEE Communications Letters.2009，5（13）：339-341.

［2］Burel G，Gautier R.Blind estimation of encoder interleaver characteristics in a non-cooperative context［C］／／Processing of the IASTED International Conference on Communication，Internet and Information Technology Scottsdale，AZ，USA：ACTA Press，2003：275-280.

［3］Sicot G，Houcke S.Blind detection of interleaver parameters［J］.Signal Processing，2009，89（4）：450-462.

［4］Sicot G，Houcke S.Blind detection of interleaver parameters［C］／／IEEE International Conference on Acoustics，Speech and Signal Processing-Proceedings.Philadelphia，USA：IEEE，2005：829-832.

［5］Lu L，Li K H，Guan Y L.Blind detection of interleaver parameters for non-binary coded data streams［C］／／IEEE International Conference on Computing Dresden，2009：1-4.

［6］鄭鵬鵬，張玉，楊曉靜.基于低碼率線性分組碼的分組交織長度識別［J］.電子信息對抗技術，2012，27（4）：9-12.

［7］鄭鵬鵬，張玉，楊曉靜.基于矩陣模型的線性分組碼及分組交織識別［J］.計算機工程，2012 38（17）：84-86.

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

［9］劉東華，梁光明.Turbo碼設計與應用［M］.北京：電子工業出版社，2011.

［10］楊曉靜，劉建成，張玉.基于求解校驗序列的（n，k，m）卷積碼盲識別［J］.宇航學報，2013，34（4）：568-573.