王俊霞，張?zhí)祢U，強(qiáng)幸子，江曉磊

(重慶郵電大學(xué) 信號與信息處理重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

?

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

王俊霞，張?zhí)祢U，強(qiáng)幸子，江曉磊

(重慶郵電大學(xué) 信號與信息處理重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

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

非合作通信；線性分組碼；迭代列消元法；相關(guān)列

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

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

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

1 線性分組碼的基礎(chǔ)

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

(1)

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

(2)

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

2 線性分組碼參數(shù)盲識別原理

2.1 數(shù)學(xué)模型

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

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

圖1 不同碼字長度和同步時刻對應(yīng)的截獲矩陣

2.2 迭代列消元法

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

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

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

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

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

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

圖2 迭代列消元法流程圖

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

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

雖然高斯列消元法過程在各個窗內(nèi)分別進(jìn)行，但是不同窗內(nèi)的碼字相同位置是上下對齊的。對于無誤碼截獲矩陣，在不同的窗內(nèi)進(jìn)行高斯列消元法都可以將相關(guān)列化為全零列，且不同的窗對應(yīng)的轉(zhuǎn)移矩陣都相同。

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

(3)

若Yj為獨(dú)立列，則

P(Yij=0)=0.5

(4)

P(Yij=1)=0.5

(5)

若Yj為相關(guān)列，則

(6)

(7)

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

(8)

Y中獨(dú)立列對應(yīng)的0的比例減去1的比例滿足

(9)

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

圖3 獨(dú)立列和相關(guān)列對應(yīng)的W的值的概率分布圖

文中算法步驟：

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

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

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

3 仿真驗(yàn)證與分析

圖4 不同碼字長度和同步時刻對應(yīng)的相關(guān)列歸一化數(shù)目

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

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

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

4 小結(jié)

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

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

[2] 閆郁翰.信道編碼盲識別技術(shù)研究[D].西安：西安電子科技大學(xué),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變換的線性分組碼參數(shù)盲估計(jì)算法[J].電子與信息學(xué)報(bào),2012, 34(7):1642-1646.

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

[8] 張世會,張?zhí)祢U,閆振華,等.BCH碼分組交織參數(shù)盲識別[J].電視技術(shù),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— )，女，碩士生，主研信道編碼參數(shù)的盲識別；

張?zhí)祢U(1971— ),博士生導(dǎo)師，主研擴(kuò)頻信號的盲處理、神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)以及信號的同步處理；

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

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

責(zé)任編輯：薛 京

責(zé)任編輯：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

王俊霞，張?zhí)祢U，強(qiáng)幸子，等.一種線性分組碼參數(shù)的全盲識別算法[J]. 電視技術(shù)，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

國家自然科學(xué)基金項(xiàng)目(61371164)；重慶市市級重點(diǎn)實(shí)驗(yàn)室建設(shè)項(xiàng)目(CSTC2009CA2003)；重慶市杰出青年基金項(xiàng)目(CSTC2011jjjq40002)；重慶市教育委員會科研項(xiàng)目(KJ130524)；重慶市研究生科研創(chuàng)新項(xiàng)目(CYS14140)