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

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

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

?

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

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

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

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

圖1 不同碼字長(zhǎng)度和同步時(shí)刻對(duì)應(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)表示對(duì)L(1)進(jìn)行高斯列消元法之后的行階梯矩陣，則M(1)=L(1)·A(1)，高斯列消元法的結(jié)果全部體現(xiàn)在A(1)中。

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

4) 依次迭代，每一次迭代都將窗Wi向下滑動(dòng)m行，并且對(duì)窗內(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 迭代列消元法流程圖

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

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

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

由于對(duì)截獲矩陣進(jìn)行迭代列消元法后，會(huì)使窗內(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ú)立列對(duì)應(yīng)的0的比例減去1的比例滿足

(9)

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

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

文中算法步驟：

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

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

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

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

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

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

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

圖6 采用文中算法對(duì)幾種線性分組碼識(shí)別的仿真圖

4 小結(jié)

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

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

[2] 閆郁翰.信道編碼盲識(shí)別技術(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ù)的盲識(shí)別方法[J].電視技術(shù),2014,38(9):188-192.

[8] 張世會(huì),張?zhí)祢U,閆振華,等.BCH碼分組交織參數(shù)盲識(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ù)的盲識(shí)別；

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

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

江曉磊(1992— )，女，碩士生，主研導(dǎo)航信號(hà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ù)的全盲識(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

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