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

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

基于迭代列消元法的線性分組碼參數(shù)盲識別*

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

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

針對線性分組碼參數(shù)盲識別容錯性能差的問題，提出基于迭代列消元法的線性分組碼參數(shù)盲識別方法。首先對截獲矩陣應(yīng)用迭代列消元法，將其相關(guān)列對應(yīng)各個窗內(nèi)的轉(zhuǎn)移矩陣中的列向量作為候選校驗向量，再根據(jù)截獲矩陣對偶碼空間歸一化維數(shù)來識別碼字長度和同步時刻，最后將對偶碼字進(jìn)行初等行變換識別校驗矩陣。仿真結(jié)果證明，與以往盲識別方法相比，所提方法容錯性能好，適用于各種碼率的線性分組碼的碼字長度、同步時刻和生成多項式識別。

非合作通信；線性分組碼；盲識別；迭代列消元法

1 引 言

信道編碼的盲識別是非合作信號處理領(lǐng)域的一個新的研究方向，在智能通信、信息對抗和信息截獲領(lǐng)域有著廣泛應(yīng)用[1]。通常在數(shù)字通信系統(tǒng)中采用信道編碼技術(shù)提高數(shù)據(jù)傳輸?shù)目煽啃訹2]。因為線性分組碼有簡單的編、譯碼結(jié)構(gòu)以及較好的糾錯性能[3]，所以，在非合作通信中，如何根據(jù)截獲序列識別線性分組碼參數(shù)有非常重要的意義。

從公開發(fā)表的文獻(xiàn)來看，線性分組碼參數(shù)盲識別的方法主要有秩準(zhǔn)則法[4]、對偶碼空間法[5-6]、碼重分析法[7]、高斯列消元法[8-9]等。秩準(zhǔn)則法計算量小，但是容錯性能很差。對偶碼空間法容錯性能好，但是計算量與碼長指數(shù)倍成正比，并且對計算機(jī)內(nèi)存要求很高，其門限僅適合中短碼。碼重分析法和關(guān)聯(lián)規(guī)則法僅適用于低碼率線性分組碼。高斯列消元法容錯性能有待進(jìn)一步提高。

針對以上線性分組碼盲識別存在的問題，本文采用迭代列消元法算法，對線性分組碼參數(shù)進(jìn)行了有效的識別。針對矩陣進(jìn)行高斯列消元法時錯誤碼元傳播影響大的問題，文中采用迭代高斯列消元法，使錯誤碼元僅僅在窗內(nèi)傳播，而不會影響窗外碼元，使錯誤碼元的傳播范圍大大減小。文中識別相關(guān)列時，并非根據(jù)秩準(zhǔn)則的全零列，而是根據(jù)相關(guān)列、獨(dú)立列中的0的比例減去1的比例統(tǒng)計特性不同，使得容錯率進(jìn)一步提高。相比文獻(xiàn)[6]中的Walsh-Hadamard變換算法，其候選校驗向量為2n個，本文中候選校驗向量為迭代列消元法后的截獲矩陣的相關(guān)列對應(yīng)各個窗的轉(zhuǎn)移矩陣中的列向量，候選校驗向量的數(shù)目大大減少。此外，根據(jù)對偶碼字、隨機(jī)碼字以及相關(guān)列、獨(dú)立列的0的比例減去1的比例統(tǒng)計特性不同，文中提出了有效的判決門限，實現(xiàn)了在較高誤碼率情況下線性分組碼參數(shù)盲識別。

2 線性分組碼的概念與性質(zhì)

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

3 基于迭代列消元法的線性分組碼參數(shù)盲識別原理

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

假設(shè)發(fā)送端碼字是(n0,k0)線性分組碼，經(jīng)過二進(jìn)制對稱信道傳輸，截獲的二進(jìn)制比特流為X。非合作方需要估計出線性分組碼的參數(shù)，如碼字長度、同步時刻t0及校驗矩陣。

假設(shè)線性分組碼碼字長度是n，同步時刻是d，則將X前面d個比特截斷，以碼字長度n分為N個碼字Xi,i=1,2,…,N，N=?(L-d)/n」，?」是取整符號，并且將每個碼字構(gòu)成截獲矩陣X(n,d)的一行。

定義H(n,d)表示X(n,d)對應(yīng)的所有校驗向量張成的對偶碼空間，dim表示求空間維數(shù)的運(yùn)算，則根據(jù)文獻(xiàn)[6]，滿足

(1)

式中：α∈+。由式(1)可知，真實碼字長度和同步時刻(n0,t0)對應(yīng)的對偶碼空間歸一化維數(shù)最大，所以為了求對偶碼空間維數(shù)，需要求對偶碼空間內(nèi)的校驗向量。

3.2 門限的取值

當(dāng)截獲矩陣為X(n0,t0)時，截獲矩陣的每一行都是由線性分組碼碼字c經(jīng)過誤碼率為τ的二進(jìn)制對稱信道產(chǎn)生的碼字x，則xhT=(c+e)hT=ehT。設(shè)無誤碼X(n0,t0)的校驗向量空間為{hr}，其余向量為{hw}，根據(jù)文獻(xiàn)[5]，如果h∈{hr}，則有

P(xhT=1)=0.5[1-(1-2τ)ωt(h)]，

(2)

P(xhT=0)=0.5[1+(1-2τ)ωt(h)] 。

(3)

式中：ωt(h)表示h的碼字重量。

如果h∈{hw}，則有

P(xhT=1)=0.5，

(4)

P(xhT=0)=0.5 。

(5)

對于大小為N×n的截獲矩陣X(n0,t0)，Xi表示X的第i行，則X(n,d)hT中0的比例減去1的比例為

(6)

定義y～(a,σ2)表示y服從均值為a、方差為σ2的正態(tài)分布，如果h∈{hr}，則

Z～(2P0-1,4P0(1-P0)/N) 。

(7)

式中：P0=0.5[1+(1-2τ)ωt(h)]。

如果h∈{hw}，則

Z～(0,1/N)。

(8)

圖1 對偶碼字、隨機(jī)碼字、相關(guān)列及獨(dú)立列對應(yīng)的Z的概率分布圖Fig.1 The corresponding Z′s probability distribution of dual code,random code,dependent column and independent column

3.3 迭代列消元法

文獻(xiàn)[8]提出的高斯列消元法，由于其錯誤碼元的傳播范圍大，文中提出的迭代列消元法設(shè)置窗，在窗內(nèi)分別進(jìn)行高斯列消元法，使錯誤碼元僅在窗內(nèi)傳播。

迭代列消元法的步驟：

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

Step 2 將窗W1放在截獲矩陣XN×n的前m行，選取的矩陣為L(1)=(X1X2…Xm)Τ，若M(1)表示對L(1)高斯列消元后的行階梯矩陣，則有M(1)=L(1)A(1)，其中，A(1)記錄對L(1)進(jìn)行高斯列消元法后的結(jié)果。

Step 3 依次迭代，每一次迭代都將窗Wt向下滑動m行，并且對窗內(nèi)矩陣L(t)=(Xm(t-1)+1Xm(t-1)+2…Xmt)Τ高斯列消元化為行階梯矩陣，則有M(t)=L(t)A(t)，t=1,2，…,c。

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

文中算法W取值為2n×n，原因一為滑動窗所選取的矩陣，每一行為一個完整碼字，窗內(nèi)包含k維碼字；原因二為W的行取值越小，錯誤碼元的傳播范圍越小。

(9)

式中：1≤j≤n0-k0，α(j,m)∈{0,1}。若α(j,m)=1，則Pj與bm相關(guān)；若α(j,m)=0，則Pj與bm無關(guān)。對無誤碼矩陣X(n0,t0)進(jìn)行迭代列消元法后，相關(guān)列Pj(1≤j≤n0-k0)可化為全零列，且轉(zhuǎn)移矩陣為

(10)

式(10)右側(cè)區(qū)域的列向量是相關(guān)列對應(yīng)的第i個窗的列向量，是校驗向量，并且互不相關(guān)，其作為對偶碼空間的基向量，張成X(n0,t0)的n0-k0維對偶碼空間。

在迭代列消元法中，窗Wi(第i次迭代)中的錯誤不會傳遞到窗Wi+1(第i+1次迭代)，因為高斯列消元法在不同的窗內(nèi)分別進(jìn)行，所以錯誤碼元只在小矩陣窗內(nèi)傳遞，而不會影響其他窗內(nèi)碼字。在無誤碼的情況下，相關(guān)列對應(yīng)的各個窗的轉(zhuǎn)移矩陣的列向量為校驗向量；在有誤碼的情況下，整個截獲矩陣的相關(guān)列對應(yīng)各個窗的轉(zhuǎn)移矩陣的列向量可能為校驗向量，也可能是非校驗向量，如果迭代次數(shù)c足夠大，整個截獲矩陣的相關(guān)列對應(yīng)各個窗的轉(zhuǎn)移矩陣的列向量會包含所有的校驗向量。本文中將整個截獲矩陣的相關(guān)列對應(yīng)各個窗的轉(zhuǎn)移矩陣的列向量作為候選校驗向量，然后再根據(jù)截獲矩陣與校驗向量、非校驗向量乘積得到的向量中0的比例減去1的比例的統(tǒng)計特性不同，識別出校驗向量。

本文算法具體步驟如下：

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

步驟1 初始化碼字長度n=nmin，d=0，候選校驗向量H1=φ。

步驟2 按照3.1節(jié)對每一種假設(shè)(n,d)構(gòu)造大小為N×n的截獲矩陣X(n,d)=(X1X2…XN)Τ，Xi表示X(n,d)的第i行。取m=2n，對X(n,d)進(jìn)行迭代列消元法，可以得到迭代列消元法后的矩陣M=(M(1)M(2)…M(c))T和轉(zhuǎn)移矩陣A=(A(1)A(2)…A(c))Τ。

步驟5 求出每一種假設(shè)(n,d)下的對偶碼空間歸一化維數(shù)dim(H3)/n，并且放入向量S中。

4 仿真驗證

截獲序列為發(fā)送端為BCH(7,4)，二進(jìn)制對稱信道的誤碼率τ=0.01，截獲時的同步時刻t0=3。已知其編碼方式為線性分組碼，用本文算法對截獲序列進(jìn)行盲識別，選取的參數(shù)均為N=1 000，T1=0.25，T2=0.5。

圖2所示是采用本文算法對以不同碼字長度和同步時刻構(gòu)成的截獲矩陣識別，求得其對應(yīng)的對偶碼空間歸一化維數(shù)的仿真結(jié)果。當(dāng)n=7、d=3時對偶碼空間歸一化維數(shù)最大，等于3/7，即對偶碼空間維數(shù)為3，此時得到的對偶碼空間基向量恰巧為BCH(7,4)的對偶碼空間基向量。當(dāng)n=7時，在d=3附近，對偶碼空間維數(shù)大于0，小于3/7。當(dāng)n≠7時，對偶碼空間維數(shù)等于零，與先前理論分析一致。

圖2 對偶碼空間歸一化維數(shù)Fig.2 The normalized dual space dimension

(a)本文算法

(b) Walsh-Hadamard算法圖3 采用本文算法和Walsh-Hadamard算法對BCH(7,4)的仿真結(jié)果Fig.3 Simulation results of the proposed algorithm and Walsh-Hadamard algorithm

圖4(a)是采用本文算法對BCH(15,7)，誤碼率0～0.1，步長為0.002進(jìn)行500次蒙特卡洛的仿真結(jié)果。圖4(b)是采用本文算法對BCH(15,11)，誤碼率0～0.05，步長為0.002進(jìn)行500次蒙特卡洛的仿真結(jié)果。圖4(c)是采用本文算法對BCH(63,16)誤碼率0～0.04，步長為0.002進(jìn)行50次蒙特卡洛的仿真結(jié)果。圖4(d)是采用本文算法對BCH(127,36)誤碼率0～0.02，步長為0.002進(jìn)行10次蒙特卡洛的仿真結(jié)果。仿真結(jié)果表明，BCH(15,7)在誤碼率為0.052時，碼字長度、同步時刻、校驗矩陣的正確識別率仍能達(dá)到90%以上；BCH(63,16)在誤碼率為0.022時，碼字長度、同步時刻、校驗矩陣的正確識別率能仍能達(dá)到80%以上；BCH(127,36)在誤碼率為0.01時，碼字長度、同步時刻正確識別率仍能達(dá)到80%以上。本文算法能夠?qū)Ω鞣N碼長和碼率的碼字進(jìn)行有效識別，對低碼率的識別效果更好，而且碼率越高，碼字長度、同步時刻、校驗矩陣正確識別率越接近。

(a)BCH(15,7)

(b)BCH(15,11)

(c)BCH(63,16)

(d)BCH(127,36)圖4 采用本文算法對不同線性分組碼識別的仿真結(jié)果Fig.4 Simulation results of the proposed algorithm

5 結(jié)束語

本文算法將迭代列消元法后的截獲矩陣的相關(guān)列對應(yīng)各個窗內(nèi)的轉(zhuǎn)移矩陣的列向量作為候選校驗向量，相比Walsh-Hadamard算法，候選校驗向量數(shù)目大大較少，且不受計算機(jī)內(nèi)存的限制，從而能夠識別碼長較長的線性分組碼。在僅僅已知編碼方式是線性分組碼的情況下，采用本文算法對其多種線性分組碼進(jìn)行識別，有較好的容錯性能。此外，本文算法根據(jù)對偶碼字、隨機(jī)碼字、獨(dú)立列和相關(guān)列的0的比例減去1的比例統(tǒng)計特性差異，提出了有效的判決門限，具有一定的工程應(yīng)用價值。下一步希望研究一種計算復(fù)雜小且對高碼率線性分組碼參數(shù)有較好識別效果的算法。

[1] 解輝,黃知濤,王豐華. 信道編碼盲識別技術(shù)研究進(jìn)展[J].電子學(xué)報,2013，41(6):1166-1176. XIE Hui,HUANG Zhitao,WANG Fenghua. Research progress of blind recognition of channel coding[J].Electronica Sinica Acta,2013，41(6):1166-1176.(in Chinese)

[2] 閆郁翰. 信道編碼盲識別技術(shù)研究[D].西安：西安電子科技大學(xué),2012. YAN Yuhan. Study on blind recognition of channel coding[D].Xi′an:Xidian University,2012.(in Chinese)

[3] FENG G L,TZENG K K. A new procedure for decoding cyclic and BCH codes up to actual minimum distance[J].IEEE Transactions on Information Theory,1994,40(5):1364-1374.

[4] PLANQUETTE G. identification of binary code streams[D] .Rennes,France:University of Rennes I,1996.

[5] VALEMBOIS A. Detection and recognition of a binary linear code[J].Discrete Applied Mathematics,2001,111(1/2):199-218.

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

YANG Xiaowei,GAN Lu. Blind estimation algorithm of the linear block codes parameters based on WHT[J].Journal of Electronics & Information Technology,2012,34(7):1642-1646.(in Chinese)

[7] 王蘭勛,佟婧麗,孟祥雅. 一種線性分組碼參數(shù)的盲識別方法[J].電視技術(shù),2014,38(9):188-192. WANG Lanxun,TONG Jingli,MENG Xiangya. Blind recognition method of linear block codes parameters[J].Video Engineering,2014,38(9):188-192.(in Chinese)

[8] 李燦,張?zhí)祢U,劉瑜. 基于伽羅華域高斯列消元法的RS碼盲識別[J].電訊技術(shù),2014，54(7):926-931. LI Can,ZHANG Tianqi,LIU Yu. Blind recognition of RS codes based on Golois Field columns Gaussian elimination[J].Telecommunication Engineering,2014，54(7):926-931.(in Chinese)

[9] 張?zhí)祢U,易琛,張剛. 基于高斯列消元法的線性分組碼參數(shù)盲識別[J].系統(tǒng)工程與電子技術(shù),2013,35(7):1514-1519. ZHANG Tianqi,YI Chen,ZHANG Gang.Blind identification of parameters of linear block codes based on columns Gaussian elimation[J].Systems Engineering and Electronics,2013,35(7):1514-1519.(in Chinese)

[10] LIN S,COSTELLO D J. Error control coding[M].2nd ed. New Jersey,USA:Prentice Hall,2005:67-95.

[11] SICOT G,HOUCKES,BARBIER J. Blind detection of interleaver parameters[J].Signal Processing,2009,89(4):450-462.

Blind Recognition of Linear Block Code Parameters Based on Iterative Column Elimination Algorithm

WANG Junxia,ZHANG Tianqi，QIANG Xingzi
(Chongqing Key Laboratory of Signal and Information Processing,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)

To improve the fault tolerance performance of blind identification of linear block code parameters,an iterative column elimination algorithm is proposed. First,the iterative column elimination algorithm is applied in the intercept matrix,and then the corresponding column in the transition matrix of a dependent column is placed in candidate parity-check matrix. In addition,the codeword length and synchronization are estimated when the normalized dual space dimension reaches the maximum. Finally,check matrix is estimated through elementary row transformation of dual code. The simulation results show that compared with previous blind identification method,the proposed method has good fault tolerance,and can recognize codeword length,synchronization and generator polynomial for linear block codes with different rate.

non-cooperative communication;linear block code;blind recognition;iterative column elimination algorithm

2016-05-17；

2016-08-03 Received date:2016-05-17；Revised date：2016-08-03

國家自然科學(xué)基金資助項目(61671095，61371164，61275099)；重慶市教育委員會科研項目(KJ130524,KJ1600427,KJ1600429);信號與信息處理重慶市市級重點實驗室建設(shè)項目(CSTC2009CA2003)

10.3969/j.issn.1001-893x.2017.02.013

王俊霞，張?zhí)祢U，強(qiáng)幸子.基于迭代列消元法的線性分組碼參數(shù)盲識別[J].電訊技術(shù)，2017,57(2):197-202.[WANG Junxia,ZHANG Tianqi，QIANG Xingzi.Blind recognition of linear block code parameters based on iterative column elimination algorithm[J].Telecommunication Engineering,2017,57(2):197-202.]

TN911.22

A

1001-893X(2017)02-0197-06

王俊霞(1992—)，女，河南焦作人，碩士研究生，主要研究方向為信道編碼參數(shù)的盲識別；

Email:1552268578@qq.com

張?zhí)祢U(1971—)，男，四川眉山人，博士，教授，主要研究方向為語音信號處理、通信信號的調(diào)制解調(diào)、盲處理、神經(jīng)網(wǎng)絡(luò)實現(xiàn)以及FPGA、VLSI實現(xiàn);

強(qiáng)幸子(1986—)，男，陜西咸陽人，碩士研究生，主要研究方向為通信信號處理。

*通信作者：1552268578@qq.com Corresponding author：1552268578@qq.com