一種線性分組碼參數的全盲識別算法

王俊霞，張天騏，強幸子，江曉磊

(重慶郵電大學 信號與信息處理重慶市重點實驗室，重慶 400065)

?

一種線性分組碼參數的全盲識別算法

王俊霞，張天騏，強幸子，江曉磊

(重慶郵電大學 信號與信息處理重慶市重點實驗室，重慶 400065)

提出了一種基于迭代列消元法的線性分組碼參數全盲識別算法。該方法首先對截獲二進制碼流構造截獲矩陣，然后對截獲矩陣進行迭代列消元法，利用相關列的歸一化數目最大值來識別碼字長度和同步時刻。同時，對截獲矩陣進行迭代列消元法后的矩陣，選取其中一個小矩陣窗內相關列都是全零列，將其對應的轉移矩陣中的列向量橫向放入校驗矩陣，完成校驗矩陣的識別。此外，根據相關列和獨立列中的碼元0的比例減去1的比例的統計特性差異，提出了判別相關列和獨立列的門限。仿真結果證明，在誤碼率為0.01時，該文算法仍能取得很好的效果。

非合作通信；線性分組碼；迭代列消元法；相關列

近年來，信道編碼盲識別已成為非合作信號處理領域一個新的研究方向，其在智能通信、信息截獲和信息對抗領域具有廣泛應用[1]。在數字通信系統中，為了提高數據傳輸的可靠性，通常會采用信道編碼技術，通過人為增加冗余比特，使系統具有自動檢錯或糾錯的能力[2]。此外，由于線性分組碼具有簡單的編碼、譯碼結構和較好的糾錯性能[3]，因此，在非合作通信中，研究如何根據截獲碼流識別出線性分組碼編碼參數具有十分重要的現實意義。

從目前公開發表的文獻來看，Planquette G[4]首先提出了利用截獲序列構造截獲矩陣，根據截獲矩陣的秩來識別碼字長度和同步時刻的方法，但是利用秩準則識別線性分組碼參數，容錯率很低。Antoine Valembois[5]首先提出二元線性分組碼的檢測和識別問題是NP問題，而且利用對偶碼空間來識別線性分組碼參數，并結合“低碼重”思想，該方法有一定的容錯能力，但是候選校驗向量的數目與假設碼長的指數倍數成正比，計算量很大。文獻[6]提出了利用walsh-hadamard變換識別線性分組碼參數，該方法具有一定的容錯能力，但是計算量大，對計算機內存要求很高。文獻[7]利用實際碼重和隨機碼重分布的特性不同識別碼長，但是該方法僅適用于低碼率線性分組碼。文獻[8]提出了用高斯列消元法識別線性分組碼參數，如碼字長度、同步時刻，計算量較小，但是容錯率有待進一步提高。

針對以上線性分組碼盲識別存在的問題，文中提出一種利用迭代列消元法的線性分組碼參數盲識別方法，根據相關列的歸一化數目來識別碼字長度和同步時刻。文中采用迭代列消元法，使錯誤碼元僅僅在窗內傳播，對窗外碼元沒有影響。此外，文中提出根據相關列與獨立列中0的比例減去1的比例的概率密度分布的差異，設置門限可區分相關列和獨立列，而非傳統秩準則中將全零列看作相關列，因此容錯率有進一步提高。

1 線性分組碼的基礎

定義1[9]：將k位信息位分為一組進行獨立處理，變為長度為n(n>k)位的編碼稱為(n,k)線性分組碼，碼率r=k/n，校驗位長n-k。若校驗位是信息位的線性組合，則稱該編碼為(n,k)線性分組碼。

(1)

如果將N(N≥k)個碼字堆疊成N×n的矩陣，對其高斯列消元法后，相關列可化為全零列，且轉移矩陣為

(2)

式(2)右側區域列向量，即為“相關列”對應的列向量，是n-k個校驗向量，并且互不相關，將其橫向放入校驗矩陣中，此時得到的校驗矩陣每一行都與生成矩陣正交。

2 線性分組碼參數盲識別原理

2.1 數學模型

假設發送端為(n0,k0)線性分組碼，經過二進制對稱信道傳輸，該信道是無記憶、誤比特率τ?1/2的對稱信道，且所有碼字在發送端等概率發送的，截獲二進制比特流為X。非合作方需要估計線性分組碼參數，如碼字長度、校驗矩陣，而且由于截獲序列的任意性，需要估計出完整碼字的同步時刻d0。

假設該線性分組碼的碼字長度為n，同步時刻為d，即完整碼字起始點為d+1，則截斷X前面d比特，以長度為n分成N個碼字Xi,i=1,2,…,N，其中，N=?(L-d)/n」，?」為取整符號，然后將每個碼字作為截獲矩陣的一行，構成截獲矩陣X(n,d)，如圖1所示，陰影部分表示位于不同完整碼字的相同位置的一個比特位。

圖1 不同碼字長度和同步時刻對應的截獲矩陣

2.2 迭代列消元法

迭代列消元法的具體流程圖如圖2所示，迭代列消元法步驟如下：

1) 假設截獲矩陣X的大小為N×n的，Xij表示X中第i行、第j列的元素，Xi=(Xi1Xi2…Xin)表示XN×n的第i行，選取小矩陣窗W的大小為m×n，則迭代次數為c=?N/m」。

2) 首先將窗W1放置在截獲矩陣XN×n的前m行，選取的矩陣記作L(1)=(X1X2…Xm)T，M(1)表示對L(1)進行高斯列消元法之后的行階梯矩陣，則M(1)=L(1)·A(1)，高斯列消元法的結果全部體現在A(1)中。

3) 將窗W1向下滑動m行，窗口記為W2，窗W2內的矩陣為L(2)=(Xm+1Xm+2…X2m)T，同第一次迭代一樣將L(2)經過高斯列消元法化為行階梯形式的矩陣M(2)，則M(2)=L(2)A(2)。

4) 依次迭代，每一次迭代都將窗Wi向下滑動m行，并且對窗內矩陣L(t)=(Xm(t-1)+1Xm(t-1)+2…Xmt)Τ進行高斯列消元法化為行階梯形式，則可以得到M(t)=L(t)A(t)，t=1,…,c。

5) 記錄迭代列消元法后的矩陣M=(M(1)M(2)…M(c))Τ和轉移矩陣A=(A(1)A(2)…A(c))Τ。

圖2 迭代列消元法流程圖

接下來分析在含誤碼情況下，錯誤碼元對高斯列消元法的影響，以及如何求取相關列的數目。對于含誤碼矩陣X(n0,d0)，當錯誤碼元發生在窗Wi內的前k0行時，則在Wi內的矩陣進行高斯列消元法，會使某一列本不該加的而加到其他列上，或者某一列本該加的而未加到其他列上，此時錯誤碼元的傳播范圍大，不僅會影響小矩陣窗內相關列的碼字重量，而且會影響Wi對應的轉移矩陣。但是當錯誤碼元發生在窗Wi內的后2n0-k0行時，僅僅會影響該行對應的相關列的重量[10]。因此，使用迭代列消元法有效地減小了錯誤碼元的傳播范圍。

文中算法選取窗的大小為2n×n，原因一是滑動窗所選取的矩陣，每一行為一個碼字，窗內應該盡量包含k維完整碼字；原因二是小矩陣窗的行取值越小，錯誤碼元的影響就越小。

雖然高斯列消元法過程在各個窗內分別進行，但是不同窗內的碼字相同位置是上下對齊的。對于無誤碼截獲矩陣，在不同的窗內進行高斯列消元法都可以將相關列化為全零列，且不同的窗對應的轉移矩陣都相同。

由于對截獲矩陣進行迭代列消元法后，會使窗內前k行碼元0、碼元1受高斯列消元法的影響很大，但是k未知，并且k

(3)

若Yj為獨立列，則

P(Yij=0)=0.5

(4)

P(Yij=1)=0.5

(5)

若Yj為相關列，則

(6)

(7)

式中：i=1,2,…,N1；ωt(h)表示校驗向量h的重量。

(8)

Y中獨立列對應的0的比例減去1的比例滿足

(9)

如圖3所示，取參數值分別為N1=500，τ=0.01，ωt(h)=4時，獨立列和相關列對應的0的比例減去1的比例的值的概率密度分布圖，設置門限T，如果Wj>T，則認為Yj是相關列，Wj

圖3 獨立列和相關列對應的W的值的概率分布圖

文中算法步驟：

輸入：長度為L的截獲序列X，選取截獲矩陣碼長的最小值nmin=3和最大值nmax=2n0-1。

1)初始化n=nmin，d=0；

2) 按照2.1節對以(n,d)構造大小為N×n的截獲矩陣X(n,d)=(X1X2…XN)Τ，其中，Xi表示X(n,d)的第i行，對其進行迭代列消元法，可以得到迭代列消元法后的矩陣M=(M(1)M(2)…M(c))Τ和轉移矩陣A=(A(1)A(2)…A(c))Τ；

3 仿真驗證與分析

圖4 不同碼字長度和同步時刻對應的相關列歸一化數目

圖5 采用文中算法和文獻[6]對BCH(7,4)識別的仿真圖

圖6a是采用文中算法對(15,5)按照誤碼率從0到0.12，步長為0.002，200次蒙特卡洛仿真結果；圖6b是采用文中算法對(15,11)按照誤碼率從0到0.04，步長為0.002，200次蒙特卡洛仿真結果；圖6c是采用文中算法對(31,21)按照誤碼率從0到0.02，步長為0.002，F50次蒙特卡洛仿真結果。由圖6可知，線性分組碼(15,5)在誤碼率為0.04，正確識別率能達到80%，線性分組碼(15,11)在誤碼率為0.01，正確識別率能達到80%，線性分組碼(31,21)在誤碼率為0.003，正確識別率能達到80%。可知，碼率越低，識別性能越好，并且文中算法適合各種碼率的線性分組碼。

圖6 采用文中算法對幾種線性分組碼識別的仿真圖

4 小結

文中對截獲矩陣進行迭代列消元法后，根據相關列和獨立列對應的0的比例減去1的比例的值的統計特性差異，設置門限，判斷出相關列歸一化數目，從而識別出正確碼字長度和同步時刻。此外，根據迭代列消元法相關列對應的轉移矩陣中的列向量為校驗向量，所以尋找小矩陣窗內相關列為全零列，認為其不包含誤碼，選擇其對應的校驗向量放入校驗矩陣中。文中算法在僅僅已知是線性分組碼的情況下，可同時識別出碼字長度、同步時刻及校驗矩陣。

[1] 解輝,黃知濤,王豐華.信道編碼盲識別技術研究進展[J].電子學報，2013,41(6):1166-1176.

[2] 閆郁翰.信道編碼盲識別技術研究[D].西安：西安電子科技大學,2012.

[3]FENGGL,TZENGKK.AnewprocedurefordecodingcyclicandBCHcodesuptoactualminimumdistance[J].IEEEtransactionsoninformationtheory,1994, 40(5):1364-1374.

[4]PLANQUETTEG.Identificationofbinarycodestreams[D].France:UniversityofRennesI,1996.

[5]VALEMBOISA.Detectionandrecognitionofabinarylinearcode[J].DiscreteAppliedMathematics, 2001,111(S1/S2):199-218.

[6] 楊曉煒,甘露.基于Walsh-Hadamard變換的線性分組碼參數盲估計算法[J].電子與信息學報,2012, 34(7):1642-1646.

[7] 王蘭勛,佟婧麗,孟祥雅.一種線性分組碼參數的盲識別方法[J].電視技術,2014,38(9):188-192.

[8] 張世會,張天騏,閆振華,等.BCH碼分組交織參數盲識別[J].電視技術,2015,39(15):88-93.

[9]LINS，COSTELLODJ.Errorcontrolcoding[M].2nded.NewJersey,USA:PrenticeHall,2005: 67-95.

[10]SICOTG,HOUCKES,BARBIERJ.Blinddetectionofinterleaverparameters[J].Signalprocessing,2009,89(4):450-462.

王俊霞(1992— )，女，碩士生，主研信道編碼參數的盲識別；

張天騏(1971— ),博士生導師，主研擴頻信號的盲處理、神經網絡實現以及信號的同步處理；

強幸子(1986— )，碩士生，主研擴頻信號的盲處理；

江曉磊(1992— )，女，碩士生，主研導航信號的捕獲與跟蹤。

責任編輯：薛 京

責任編輯：2016-05-10

Blind recognition algorithm of linear block codes

WANG Junxia, ZHANG Tianqi, QIANG Xingzi, JIANG Xiaolei

(ChongqingKeyLaboratoryofSignalandInformationProcessing(CQKLS&IP),ChongqingUniversityofPostsandTelecommunications(CQUPT),Chongqing400065,China)

In order to solve the blind identification problem of linear block code, an iterative column elimination algorithm is proposed in this paper. First of all, a matrix is filled with intercepted bit stream received from binary symmetric channel, and then an iterative column elimination algorithm is introduced which attempts to eliminate parity bits in codewords of noisy data. Second, the length and synchronization of codewords are estimated when the normalized number of dependent column reaches the maximum. Third, After an iterative column elimination algorithm is applied in the intercepted matrix made of the right length and synchronization, we choose a window whose dependent columns is all zeros column, so the corresponding column in the transition matrix is placed in parity-check matrix. What is more, the threshold is introduced, according to the statistical characteristics differences between dependent column and independent column theoretically. Finally, the simulation results show that the probability of correct recognition in the proposed algorithm is good when the bit error rate is one percent.

non-cooperative communication; linear block codes; iterative column elimination algorithm; dependent column

王俊霞，張天騏，強幸子，等.一種線性分組碼參數的全盲識別算法[J]. 電視技術，2016,40(12)：109-114. WANG J X, ZHANG T Q, QIANG X Z，et al.Blind recognition algorithm of linear block codes[J]. Video engineering，2016,40(12)：109-114.

TN911.22

A

10.16280/j.videoe.2016.12.021

國家自然科學基金項目(61371164)；重慶市市級重點實驗室建設項目(CSTC2009CA2003)；重慶市杰出青年基金項目(CSTC2011jjjq40002)；重慶市教育委員會科研項目(KJ130524)；重慶市研究生科研創新項目(CYS14140)