基于矩陣秩統(tǒng)計的卷積碼分組交織盲識別

陸 凱，張 旻，李歆昊

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

0 引言

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

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

1 分組交織的基本概念

1.1 分組交織的基本原理

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

圖1 輸入數(shù)據(jù)Fig.1 Input sequence

圖2 交織數(shù)據(jù)Fig.2 Interleaved sequence

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

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

1.2 卷積碼的分組交織的性質(zhì)

為保證卷積碼和分組交織器結(jié)合的最優(yōu)性能，卷積碼和分組交織之間滿足以下性質(zhì)［8］：

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

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

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

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

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

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

2 基于矩陣秩統(tǒng)計的卷積碼分組交織盲識別

2.1 卷積碼分組交織的性質(zhì)分析和推導(dǎo)

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

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

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

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

卷積碼是一種有記憶編碼，當(dāng)交織矩陣的列數(shù)大于卷積碼的約束長度時，提取各交織塊中同一行數(shù)據(jù)構(gòu)成一個p×q矩陣（q＞N，p＞q），該矩陣具有以下性質(zhì)：

定理1由連續(xù)的（n0，k0，m）卷積碼信息序列所構(gòu)成的p×q矩陣，當(dāng)矩陣的列數(shù)q＞n0（m+1），p＞q時，若卷積碼在矩陣中的位置一一對應(yīng)，則對該矩陣進(jìn)行單位化后左上角單位陣維數(shù)相等，且此時矩陣的秩不等于列數(shù)q［8］。

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

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

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

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

2.2 交織參數(shù)識別

2.2.1 基于矩陣秩統(tǒng)計的交織矩陣的行和列識別假設(shè)交織長度為L=m×n，把交織數(shù)據(jù)排列成矩陣形式，如圖3所示?，F(xiàn)對接收數(shù)據(jù)進(jìn)行采樣處理，當(dāng)采樣間隔為交織矩陣的行數(shù)m 時，采樣后的序列數(shù)據(jù)為：

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

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

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

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

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

2.2.2 交織起始點的確定

2.2.2.1 校驗矩陣的求解

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

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

2.2.2.2 起始點的識別

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

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

解交織得到：

C2序列會出現(xiàn)兩種情況：

①c1為交織塊的起始點

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

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

②c1不為交織塊的起始點

當(dāng)c1不為交織塊的起始點，長為L=m×n的數(shù)據(jù)包含兩個交織塊中的元素，假設(shè)該數(shù)據(jù)如下：

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

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）

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

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

2.3 識別過程

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

步驟1對接收的交織數(shù)據(jù)C0進(jìn)行采樣處理，獲取采樣序列C；

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

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

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

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

3 仿真實驗

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

實驗1：交織矩陣的行數(shù)和列數(shù)識別

通過遍歷采樣周期并對采樣數(shù)據(jù)求解線性相關(guān)列，結(jié)果如圖5所示。

由圖5可知，在采樣值為19時出現(xiàn)相關(guān)列，且出現(xiàn)相關(guān)列的矩陣的列數(shù)為26。按存在相關(guān)列時矩陣列數(shù)的周期倍構(gòu)建新的矩陣，求解新矩陣是否存在相關(guān)列，結(jié)果如圖6所示，得到的相關(guān)列值如表1所示。

表1 列數(shù)與相應(yīng)的相關(guān)列的檢測值Tab.1 The number of columns corresponding detection of related column

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

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

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

圖6表明，隨著誤碼率的增加，本文算法始終優(yōu)于文獻(xiàn)［2］“秩準(zhǔn)則”算法。

實驗3：起始點的識別

實驗條件如實驗1，對獲取的交織數(shù)據(jù)進(jìn)行交織起始點的識別，識別結(jié)果如圖8所示。

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

圖5 不同采樣值下的相關(guān)列Fig.5 Related column under different sampling

圖6 相關(guān)列的檢測值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 結(jié)論

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

［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］.電子信息對抗技術(shù)，2012，27（4）：9-12.

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

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

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

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