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

王俊霞，張?zhí)祢U，強幸子

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

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

王俊霞*，張?zhí)祢U，強幸子

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

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

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

1 引 言

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

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

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

2 線性分組碼的概念與性質

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

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

3.1 數學模型

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

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

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

(1)

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

3.2 門限的取值

當截獲矩陣為X(n0,t0)時，截獲矩陣的每一行都是由線性分組碼碼字c經過誤碼率為τ的二進制對稱信道產生的碼字x，則xhT=(c+e)hT=ehT。設無誤碼X(n0,t0)的校驗向量空間為{hr}，其余向量為{hw}，根據文獻[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 對偶碼字、隨機碼字、相關列及獨立列對應的Z的概率分布圖Fig.1 The corresponding Z′s probability distribution of dual code,random code,dependent column and independent column

3.3 迭代列消元法

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

迭代列消元法的步驟：

Step 1 假設截獲矩陣X大小是N×n，X中的第i行、j列元素記作Xij，XN×n的第i行記作Xi=(Xi1Xi2…Xin)，若選取窗W的大小是m×n，則迭代次數是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)進行高斯列消元法后的結果。

Step 3 依次迭代，每一次迭代都將窗Wt向下滑動m行，并且對窗內矩陣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))Τ和轉移矩陣A=(A(1)A(2)…A(c))Τ。

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

(9)

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

(10)

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

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

本文算法具體步驟如下：

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

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

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

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

4 仿真驗證

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

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

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

(a)本文算法

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

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

(a)BCH(15,7)

(b)BCH(15,11)

(c)BCH(63,16)

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

5 結束語

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

[1] 解輝,黃知濤,王豐華. 信道編碼盲識別技術研究進展[J].電子學報,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] 閆郁翰. 信道編碼盲識別技術研究[D].西安：西安電子科技大學,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變換的線性分組碼參數盲估計算法[J].電子與信息學報,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] 王蘭勛,佟婧麗,孟祥雅. 一種線性分組碼參數的盲識別方法[J].電視技術,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].電訊技術,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,易琛,張剛. 基于高斯列消元法的線性分組碼參數盲識別[J].系統(tǒng)工程與電子技術,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

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

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

王俊霞，張?zhí)祢U，強幸子.基于迭代列消元法的線性分組碼參數盲識別[J].電訊技術，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—)，女，河南焦作人，碩士研究生，主要研究方向為信道編碼參數的盲識別；

Email:1552268578@qq.com

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

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

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