一類卷積碼的隨機交織參數盲識別方法*

涂 榫，王偉瑋，劉曉龍

（解放軍78009部隊,四川 成都 610066）

一類卷積碼的隨機交織參數盲識別方法*

涂 榫，王偉瑋，劉曉龍

（解放軍78009部隊,四川 成都 610066）

針對卷積碼隨機交織參數的盲識別問題，重點對隨機交織關系進行研究，提出了一種針對(2,1,m)卷積碼隨機交織參數進行盲識別的方法。該方法通過建立矩陣分析模型，在獲取卷積碼編碼參數和交織長度的基礎上，利用列刪除矩陣的秩準則算法確定子碼交織關系，進而利用基構造法和窮舉比對法確定隨機交織關系，實現了對(2,1,m)系統/非系統卷積碼隨機交織參數的盲識別。實驗仿真表明，在僅獲取含誤碼的卷積碼交織后數據序列的情況下，實際數據的編碼、交織參數識別分析結果正確。

卷積碼；隨機交織；盲識別；矩陣分析

0 引 言

數字通信系統中，通信編碼都會遇到多徑衰落和其他突發噪聲的影響，而干擾產生的錯誤是突發的。在傳輸前對編碼信息進行交織，分離相鄰的碼元，可使信道的突發錯誤在時間上得以擴散，從而使譯碼器可將它們當作隨機錯誤處理，以增強譯碼的準確率。目前，常用的交織方式有分組交織（矩陣交織、隨機交織）和卷積交織，而交織技術已在實際通信中大量使用。交織識別已經成為糾錯碼識別的關鍵，因此研究交織技術具有重要的價值。

在實際衛星通信中，信道編碼通常使用卷積碼和隨機交織級聯的方式。隨機交織是按照某種交織（置換）關系，對交織長度內的碼元重新進行排序，實質上也是分離相鄰的碼元。由于置換關系無規律可循，分離后的相鄰碼元之間的距離可能毫無規律，因此分析難度較大。目前，常用的卷積碼為(2,1,m)非系統碼和刪余碼。

卷積碼隨機交織的盲識別方法尚不多見。文獻[1-2]僅對交織長度、起點和碼率進行了盲識別，尚未對交織關系進行分析。文獻[3]利用反轉誤碼率最小準則對線性分組碼偽隨機交織進行識別。該方法將截獲序列按可能的編碼、交織等方式進行譯碼后再進行編碼、交織，將所得新序列與原截獲序列進行比較。由于該方法需遍歷所有的可能，運算量較大，效率較低，且僅能對基于m序列的偽隨機交織關系進行識別。文獻[4]使用的遍歷、比對的方法則僅能對標準的(2,1,m)卷積碼的隨機交織進行識別，且該方法不便于程序實現。

針對以上盲識別方法的局限性，本文提出了一種新的方法，即在識別交織長度的基礎上，采用列刪除矩陣的秩準則算法確定子碼交織關系，再利用基構造法和窮舉比對法確定隨機交織關系。該算法不僅適用于標準的、非標準的(2,1,m)卷積碼隨機交織的識別，而且使可能的交織方式個數相比于文獻[3-4]大幅降低，減少了遍歷次數，提高了盲識別效率。

1 卷積碼隨機交織識別分析

設隨機交織前使用的糾錯編碼方式為(n,k,m)卷積碼，信息序列經卷積編碼后生成序列c，c經隨機交織后產生傳輸序列L，交織長度L。

為保證編碼和交織結合的最優性能，隨機交織和卷積碼之間滿足如下條件：

（1）交織長度L大于或等于編碼約束長度，且一般是卷積碼碼長n的整數倍。

（2）交織塊以卷積序列的一個分組起點為起點。

（3）塊內連續性，即一個交織塊內的L位，交織前是連續的L位卷積序列。

（4）塊間連續性，即塊與塊之間是按時間順序排列的，不會出現倒序。

（5）同組同塊性，即卷積碼的同一碼字在同一交織塊內。

交織分析需要識別的未知參數包括交織長度L、交織起點i、交織前的卷積碼編碼參數及交織關系。

1.1 建立矩陣分析模型

將接收序列u按行寫入的方式構成一個p×q矩陣，行數p至少為交織長度的2倍（序列u長度應大于p2），列數q取值小于行數p。

1.2 交織長度L的確定

定理1：由卷積碼性質可得，序列c所構成的p×q矩陣，當列數q為交織長度L的整數倍（也為碼長n的整數倍）時，矩陣的秩小于列數q。

引理1：序列u是序列c經隨機交織而產生的，序列u構成的p×q矩陣是由序列p×q構成的p×q矩陣（q為交織長度L的整數倍）經列置換產生的，而初等列變換不影響矩陣的秩。

由引理1知，序列u構成的矩陣的秩小于列數q。此外，由引理1知，對于標準化后左上角單位陣的維數相等、秩小于列數的矩陣，其列數為交織長度L的整數倍，則對不滿秩矩陣的列值取最大公約數，即可得到L。

受實際信道誤碼率的影響，p×q矩陣是由含錯交織序列ue構成。因此，矩陣中的元素不一定滿足編碼序列本身的校驗關系，且這種校驗關系可能會被完全破壞，從而導致矩陣滿秩。

對于(n,k)線性分組碼碼字按行寫入構成的p×n矩陣X(p＞n)，定義其碼字空間C⊥的零空間（對偶空間）為C⊥，即C⊥={h|?c∈C,hcT=0}。于是，有以下定理[5]：

定理2：對于任意的q維二元域行向量h，有?h?C⊥，w(hXT)的均值在p/2附近；反之，?h∈C⊥，w(hXT)小于p×(1-(1-2τ)w(h))/2。其中：w(h)表示信道誤碼率，w(h)表示向量h的漢明重量。

推論1：定理2對卷積碼仍然適用，即對(n,k,m)卷積碼碼字按行寫入構成的p×q矩陣X（p＞q, q≥n×(m+1),q為n整數倍），結論仍成立。

推論2：由引理1和推論1可知，含錯編碼序列ue按行寫入構成的p×q矩陣X（q為交織長度L的整數倍），結論仍成立。

對于矩陣X，利用伽羅華域上的高斯約當消元法，對X進行初等行列變換，化成一個下三角矩陣，則有P·X·Q=A，其中A是一個下三角矩陣，其上半部分近似為一個單位陣，矩陣X的具體變換可參考文獻[6]。

記Q(:,i)、A(:,i)分別表示矩陣Q和A的第i列，矩陣P對X僅做行變換，則有w(X·Q(:,i)=w(A(:,i))。

如果A(:,i)的漢明重量為零或者小于一個檢測門限閥值Tres，即：

根據推論2，Q(:,i)屬于X的零空間，也是方程組X的一個解向量，滿足式（1）的所有Q(:,i)構成方程組X的一個基礎解系，也構成含錯編碼序列ue的校驗矩陣。設滿足式（1）的列數為η，此時矩陣X的秩為q-η，對不滿秩矩陣的列值取最大公約數，就可得到交織長度i。

1.3 交織起點i的確定

引理2[4]：序列u按行寫入構成的p×q矩陣（p＞2L,q為L整數倍），當交織起點與矩陣每行起點重合時，其標準化矩陣的秩最小。

對于構造的分析矩陣，列數取交織長度L的整數倍，然后對矩陣移位L-1次，當交織塊起點正確時，矩陣中相關的列最多，秩最小，根據最小秩確定交織起點。

對于含錯序列ue，采用上文中提到的容錯處理技術求取構造矩陣的秩。

交織塊的塊內連續性保證了交織塊內不含有兩個或兩個以上的子交織塊，即保證了交織起點具有唯一性。實際通信中，可能存在交織塊中含子交織塊的情況，子交織塊數量即為可能的交織起點個數。這時需對每個可能的交織起點分別確定交織關系。

1.4 卷積碼碼長n和信息位長k的確定

在確定交織長度L和交織起點i的基礎上，令[u]2L、[u]L分別為序列u按行構成的2L×2L維、L×L維分析矩陣，其秩分別為r([u]2L)和r([u]L)。于是，可按式（2）確定n、k。

1.5 交織關系的確定

實際通信中，使用卷積碼和隨機交織級聯的方式時，常用的卷積碼為(2,1,m)非系統碼和刪余碼，本文重點對(2,1,m)非系統碼進行討論。假定每一時間單位輸入卷積碼編碼器的信息元均參與子碼（各支路）的運算，同時存儲在第一個存儲器內。這和實際應用的各類(2,1,m)碼的編碼器相吻合。

設(2,1,m)卷積碼的生成多項式G(D)=[g(1,1)(D), g(1,2)(D)]，監督多項式H(D)=[h(1,1)(D),h(1,2)(D)]，生成元g=(11xx……xx)(x表示0或1)，則可采用改進高斯法[7]快速求取監督元。根據文獻[8]，g(1,1)(D)=h(1,2)(D)，g(1,2)(D)=h(1,1)(D)，則監督元h=(xx……xx11)(x表示0或1)。

引理3[9]：當不知道卷積碼子監督多項式的次數時，為求取系數，可把它們的次數適當假設得大一些，然后約去公因式，得到次數最低的多項式，即為子監督多項式。

根據引理3，設(2,1,m)卷積碼的監督元為h，當卷積碼構成p×q矩陣(p＞q,q≥2(m+1),q=2a,a為整數)，其監督元信號空間的一組基｛φi｝如下，維數為a-m：

這里，將生成這組基的方法定義為基構造法。

推論3：監督元h=(xx……xx11)的(2,1,m)卷積碼，按行寫入方式構成p×q矩陣(p＞q,q＞2(m+1)) q=2a,a為整數)，刪除列值區間在2(m+1)+1～2a的任意兩列，則刪除最后兩列形成的列刪除矩陣的秩是所有刪除組合中秩值最小的。

證明：刪除矩陣最后兩列后，監督元信號空間的一組基{φi}的個數為a-m-1，φi(i∈[0～a-m-2])為φi（i ∈［0~a-m -2］）刪除最后兩位0得到。監督元的0意味著該位不參與校驗，不會影響約束關系；而φa-m-1的最后兩位是1，刪除意味著φa-m-1表示的約束關系被破壞。刪除后，矩陣的秩為a+m-1，其余刪除組合分以下兩種情況進行討論：

①刪除同一子碼的兩列

設刪除的兩列列值為2(m+1)+2ε-1、2(m+1)+2ε(ε∈[1～a-m-2])，則φε對應位置的值為11，φi（i＜ε）對應位置的值為00。若φi（i＞ε）對應位置的值全為00或11時（若是11，可通過二元域上線性變換變為00），刪除后矩陣的秩為a+m-1，原理同上；若φi（i＞ε）對應位置的值不全為00或11，刪除兩列時，有且僅有2個約束關系會被破壞，故刪除后矩陣的秩為a+m。

②刪除不同子碼的兩列

設刪除的兩列分屬第i、j個子碼(i,j∈[m+2～a],i≠j)，則除φi、φj以外，其余約束關系對應位置的元素可通過初等變換變為0，φi、φj的約束關系被破壞，刪除后矩陣的秩為a+m。

1.5.1 子碼交織關系的確定

交織長度L的子碼交織關系確定方法如下：

①序列u按行構成p×2L(p＞2L)維矩陣，從L+1列至2L列遍歷刪除兩列。當列刪除矩陣的秩最小時，刪除的兩列屬交織前的同一子碼，即確定了交織長度L中第L/2個子碼的交織關系（L中共含L/2個子碼），并令k=1。如果秩最小值不唯一，需遍歷每種可能分別進行討論。

②刪除已確定的兩列，對列刪除后的p×(2L-2k)維矩陣按步驟1求最小秩，確定L中第L/2-k個子碼的交織關系，令k=k+1，并記列刪除矩陣為Xi（i表示矩陣列數值）。

③若列刪除矩陣的列數≥L+4，重復步驟2；若列數為L+2，結束。

1.5.2 卷積碼編碼存儲m的確定

①序列u按行構成p×L(p＞L)維矩陣，令k=1。

②按子碼交織關系刪除第L/2-k+1個子碼的兩列，記列刪除矩陣為Xi（i表示矩陣列數值）。若刪除后的p×(L-2k)維矩陣不滿秩，令k=k+1，重復步驟2；若滿秩，記滿秩時矩陣的列數為q，則m=q/2。

1.5.3 隨機交織關系的確定

引理4：交織后卷積碼的監督元，與交織前卷積碼的監督元經交織變換后一致。

（1）根據容錯處理技術，求取矩陣X2(m+1)的監督元μ。根據引理4，該監督元是由交織前序列c的監督元v經過交織置換后形成的。結合μ和子碼交織關系，產生所有可能的v和部分隨機交織關系。

具體方法如下：

若μ中屬同一子碼的兩位相等（都為0或1），則v中對應子碼的兩位即可確定；若μ中屬同一子碼的兩位不等，則v中對應子碼的兩位為01或10，即產生兩種可能；若μ中共計k個子碼不等，則v共有2k種可能，分別記錄每種可能和每種可能對應的部分隨機交織關系。

（2）窮舉所有可能的v，對交織前、后的監督元分別在二元域上張成監督元空間。如果v估計正確，則監督元具有一一對應的關系，反之會出現不匹配情況。

具體步驟如下：

①依次窮舉所有可能的v，令k=1。

②對X2(m+1)+2k按照容錯處理技術求取交織后監督元空間的一組基，維數為k+1；在二元域上通過線性變換張成的監督元空間個數為2k+1-1，記為α。通過基構造法，由v張成交織前監督元空間的個數也為2k+1-1，記為β。

③遍歷β，結合部分隨機交織關系，在α內尋找匹配的監督元。根據β中子碼內元素不等的位置，對匹配的兩個監督元，檢驗已確定的交織關系，并確定新的交織關系。

如果監督元不能一一匹配或不滿足部分隨機交織關系，返回步驟①；否則，令k=k+1，返回步驟②，直至隨機交織關系全部確定。

至此，(2,1,m)卷積碼隨機交織的各個參數已全部確定。如果實際中誤碼率過高，在容錯處理技術的基礎上，可采用迭代加權累計的方法[10]求取交織長度、起點及監督元。

2 誤碼率及參數對正確識別率的影響

交織關系的盲識別正確率與卷積碼編碼參數、交織長度和信道誤碼率有關。誤碼率越高，交織長度越長，卷積碼約束長度越長，則識別率越低。(2,1,6)卷積碼在交織長度為18的情況下，識別率和誤碼率的關系如圖1所示。針對(2,1,6)碼，本文方法在誤碼率小于0.001時，識別準確率可達70%以上。(2,1,6)卷積碼在誤碼率為0.5×10-3情況下，識別率和交織長度的關系如圖2所示。

圖1 不同比特誤碼率下的隨機交織檢測概率

圖2 不同交織長度下的隨機交織檢測概率

3 仿真實驗

設信道轉移概率為0.001，以某1/2碼率的隨機交織卷積碼接收序列為例，取一段輸出數據序列作為識別序列進行分析。

確定矩陣行數p=200，取定列值范圍(2,190)，按列數變化將識別序列以按行寫入方式構成矩陣，依次計算矩陣的秩，記下秩不等于列數的列值，依次為(36,54,72…)，列值和矩陣的秩如表1所示。交織長度為記錄列值的最大公約數，故L=18。

表1 列值與矩陣的秩

分析起點時，取矩陣列值q=36，依次對進行移位并求秩，移位數和矩陣的秩如表2所示。當序列移9位時，矩陣的秩最小，即為隨機交織的起點。

表2 移位數與矩陣的秩

根據式（2），卷積碼碼率為1/2，即

取矩陣列值q=36，遍歷刪除X36列值區間為19～36的任意兩列。當刪除第21、30列時，列刪除矩陣X34的秩為23，刪除其余兩列時，秩均為24；繼續對列刪除矩陣X34進行兩列刪除的處理，當刪除第8、12列（相當于原X36矩陣的第9、14列）時，列刪除矩陣X32的秩最??；依次進行計算，同時記錄各個Xi矩陣，可確定每個子碼的交織關系，最終確認的子碼交織關系為：

其中，13/14表示在交織長度內，交織后的第1位來自于交織前的第13位或第14位，即來自于交織前的第7個子碼中的任一位。

分析卷積碼編碼存儲m時，取矩陣列值q=18，依次刪除X18子碼交織關系中數字最大的兩列并求秩。根據首次滿秩時的矩陣列數值，可確定m=6，編碼約束度na=2(m+1)=14。同時，記錄每個列刪除矩陣Xi，列刪除矩陣的列值和矩陣的秩如表3所示。

表3 列刪除矩陣的列值與矩陣的秩

求取X14的監督元μ=[11011110111100]，根據子碼交織關系，發現共有兩個碼字內的比特不等，故交織前監督元v共有4種可能：

依次檢驗這4種可能。這里，以對v1的檢驗為例進行說明，其余3種的檢驗類似。

①v1確定子碼交織關系中的(3/4,11/12,3/4,11/12)為(3,12,4,11)；

②求取X16的2個監督元，張成的監督元空間為h1-h3（共3個）；通過基構造法，由v1張成的交織前監督元空間為H1-H3；通過已確定的部分隨機交織關系，可得到如下所示的一一對應關系：

從一一對應關系中又可確定部分新的隨機交織關系為：(13/14,5/6,13/14,5/6)→(14,6,13,5)。

③求取X18的3個監督元，張成的交織前后監督元空間共7個，一一對應關系如下所示：

于是，確定部分新的隨機交織關系為：

(7/8,15/16,7/8,15/16)→(7,15,8,16)。

類似地，求取X20的交織前后監督元空間，可確定部分新的隨機交織關系為：(17/18,9/10,9/10,17/ 18)→(18,9,10,17)；求取X22的交織前后監督元空間共31個，根據已確定隨機交織關系進行驗證時，無法實現一一匹配，故判斷v1不正確。

最終，求取的交織關系和原卷積碼生成多項式如表4所示。

從表4可看出，兩種有解情況的原碼子生成多項式剛好互換，交織置換關系中1個碼元內2個比特的位置也正好互換?？梢?，若先按置換關系解交織，再以生成多項式進行譯碼，則兩種情況得到的原信息序列是完全一樣的。

表4 交織關系和生成多項式

4 結 語

卷積碼隨機交織盲識別技術是一個新興的研究方向，由于其置換關系具有隨機性，故造成對其進行盲識別分析的技術難度較大。筆者提出利用基構造法和窮舉比對法確定隨機交織關系的方法，完整解決了(2,1,m)類卷積碼隨機交織參數的盲識別問題。該方法計算復雜度較低，數據利用率較高，容錯性能較好。仿真實驗表明，在10-3誤碼率情況下，本文算法能實現對隨機交織長度為18的(2,1,6)非系統卷積碼交織參數的有效估計，在衛星通信領域具有一定的實用價值。

[1] Sicot G,Houcke S,Barbier J.Blind Detection of Iinterleaver Parameters[J].Signal Processing,2009,89(04):450-462.

[2] Burel G,Gautier R.Blind Estimation of Encoder and Interleaver Characteristics in a Non Cooperative Context[M].Nrnaonal Onfrn on Ommnaon,2003.

[3] 廖斌,張玉,楊曉靜.基于線性分組碼的偽隨機交織識別[J].探測與控制學報,2013,35(04):53-57. LIAO Bin,ZHANG Yu,Yang Xiao-jing.Blind Recognition of the Pseudo-random Interleaver Based on Linear Block Code[J].Journal of Detection & Control,2013,35(04):53-57.

[4] 張永光,樓才義.信道編碼及其識別分析[M].北京:電子工業出版社,2010. ZHANG Yong-guang.LOU Cai-yi.Channel Coding and Identification[M].Beijing:Electronic Industry Press,2010.

[5] Valembois A. Detection and Recognition of A Binary Linear Code[J].Discrete Applied Mathemati cs,2001,111(1-2):199-218.

[6] 劉宗輝.交織和分組碼參數盲估計與識別技術[D].成都:電子科技大學,2011. LIU Zong-hui.Blind Estimation and Recognition Technology of Interleaving and Block Code Parameters[D].Chengdu:University of Electronic Science and Technol,2011.

[7] 底強,蘇彥兵,劉杉堅.基于改進高斯法的卷積碼盲識別方法[J].通信技術,2012,45(10):68-70. DI Qiang,SU Yan-bing,LIU Shan-jian.Blind Recognition of Convolution Code based on Improved Gauss Algorithm[J].Communications Technology,2012, 45(10):68-70.

[8] 劉健.信道編碼的盲識別技術研究[D].西安:西安電子科技大學,2010. LIU Jian.Research on Blind Recognition Technology for Channel Coding[D].Xi'an:Xidian University,2011.

[9] 劉玉君.求解非系統卷積碼監督矩陣算法的研究[J].信息工程大學學報,2008,9(04):427-430. LIU Yu-jun.Studies on the Algorithms for Acquiring the Check Matrix of Nonsystematic Convolution Codes[J].Journal of Information Engineering University,2008,9(04):427-430.

[10] 彭淼.信道編碼參數盲估計技術研究[D].成都:四川大學,2013. PENG Miao.Research on Blind Estimation Parameters of Channel Coding[D].Chengdu:Sichuan University,2013.

涂 榫（1982—），男，碩士，助理工程師，主要研究方向為衛星通信信號處理和信道編碼識別；

王偉瑋（1982—），男，碩士，助理工程師，主要研究方向為衛星通信信號處理和信道編碼識別；

劉曉龍（1983—），男，碩士研究生，主要研究方向為衛星通信信號處理和信道編碼識別。

Blind Recognition Algorithm based on Random Interwoven Parameter of A Convolution Code

TU Sun, WANG Wei-wei, LIU Xiao-Long
（Unit 78009 of PLA,Chengdu Sichuan 610066,China）

Aiming at the problem of blindly recognize convolution code random interwoven, mainly study on the relationships of random interwoven is mainly studied, and a method of random interwoven parameter with(2,1,m)convolution code is proposed. The method first build the matrix analysis model, then on the basis of obtaining the parameter of convolution code and the length of interwoven, use the way of the minimum rank of delete column matrix to confirm the sub-code interwoven relationships, and use base construction and exhaustive comparison to ensure random interwoven relationships, finally recognize (2,1,m)systematic/ nonsystematic convolution code random interwoven parameter blindly. Experimental simulation results show that, in the case of only known after-mixed convolution code data sequences which contain errors, the actual data’s encoding, recognition analysis results of interwoven parameter are correct.

convolution code;random interwoven;blind recognition;matrix analysis

TN911

A

1002-0802(2016)-07-0836-06

10.3969/j.issn.1002-0802.2016.07.008

2016-03-08;

2016-06-09 Received date:2016-03-08;Revised date:2016-06-09