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

王蘭勛，佟婧麗，孟祥雅

(河北大學(xué)電子信息工程學(xué)院，河北保定 071002)

在實(shí)際數(shù)字通信信道中，為了抗擊噪聲的影響，提高數(shù)據(jù)傳輸可靠性，需要進(jìn)行信道編碼技術(shù)，即在信息序列中增加冗余碼元，使接收序列具有糾檢錯(cuò)能力。對信息截獲方而言，如何根據(jù)接收的序列盲識別出信道編碼體制和參數(shù)是當(dāng)前編碼研究領(lǐng)域中一個(gè)嶄新的研究課題，具有重要的現(xiàn)實(shí)意義和應(yīng)用價(jià)值［1－2］。

目前，根據(jù)公開發(fā)表文獻(xiàn)知，大部分信道編碼識別的研究主要集中在卷積碼的盲識別上，針對線性分組碼盲識別研究的文獻(xiàn)相對較少。文獻(xiàn)［3］根據(jù)碼重分布距離公式估計(jì)二進(jìn)制線性分組碼的碼長，通過矩陣化簡得到生成矩陣，在低誤碼率下識別效果較好。文獻(xiàn)［4］提出了碼重分布信息熵算法識別線性分組碼碼長，適用于較高誤碼環(huán)境，但沒有考慮截獲序列非同步的情況。文獻(xiàn)［5］提出了利用比特頻率檢測法識別碼長和起始點(diǎn)，更適合于較低誤碼率的環(huán)境且所用數(shù)據(jù)量較大。文獻(xiàn)［6］提出了利用漢明距離識別碼長和起始點(diǎn)，所需數(shù)據(jù)量較少，但適應(yīng)于誤碼率較低的線性分組碼。文獻(xiàn)［7］提出了一種基于統(tǒng)計(jì)顯著水平的快速識別法，首次解決了BCH縮短碼的識別問題。文獻(xiàn)［8］提出一種利用歐幾里得算法識別最大公因式的方法，該方法無繁瑣計(jì)算。文獻(xiàn)［7－8］只針對BCH碼而言，針對性較強(qiáng)。文獻(xiàn)［9］提出一種通過解調(diào)輸出的軟判決序列來求解含錯(cuò)方程的方法，所需數(shù)據(jù)量較大。

上述算法或者是數(shù)據(jù)量較大、針對性較強(qiáng)，不能識別同步點(diǎn)，或者是在低誤碼條件下才能達(dá)到較好的識別效果。針對以上方法的不足，本文提出碼重相似度算法識別碼長和同步點(diǎn)(本文碼字起始點(diǎn)簡稱同步點(diǎn))。在此基礎(chǔ)上，通過計(jì)算碼字深度值，選取非零不同深度值對應(yīng)的碼字?jǐn)[成矩陣形式，即為生成矩陣。最后對碼重相似度識別方法進(jìn)行仿真分析，并討論該方法的容錯(cuò)性，與其他方法進(jìn)行了比較，仿真結(jié)果表明文中方法在較高誤碼率為0.01條件下能夠有效識別中短碼，容錯(cuò)性較好，且所需數(shù)據(jù)量較少。

1 線性分組碼的相關(guān)定義及其描述

定義1:(n，k)線性分組碼是GF(q)上的n維線性空間中的k維子空間，由qk個(gè)碼字集合構(gòu)成，而k個(gè)獨(dú)立向量構(gòu)成的一組基底完全可以線性表示這qk個(gè)碼字，將這組基底寫成矩陣形式，即為生成矩陣G，G表示形式不唯一，但都是k行n列矩陣［10］。若G有如下形式:G=［Ik，P］，稱G為典型生成矩陣。對于循環(huán)碼，生成多項(xiàng)式的向量形式可由典型生成矩陣的第k行的第k列到第n列表示。本文以二進(jìn)制線性分組碼為例，即q=2。

定義2:一個(gè)碼字的重量等于該碼字中非零元素的個(gè)數(shù)。對于(n，k)二進(jìn)制線性分組碼，其碼字重量為碼字中含“1”的個(gè)數(shù)，也稱碼重［10］。設(shè)qi是 (n，k)分組碼中碼重為i的碼字個(gè)數(shù)，則重量分布表示為{q0，q1，…，qn}。碼重分布概率Pi是重量為i的碼字個(gè)數(shù)在碼字總數(shù)中出現(xiàn)的概率。

定義3:令c=(b1，b2，…，bn)是二元域上碼長為n的線性分組碼C的一個(gè)碼字，定義D(c)=(b2－b1，…，bnbn－1)，稱D為c的微分運(yùn)算［11］。碼字c的深度是滿足Dz(c)=(0n－z)的最小非負(fù)整數(shù)z，若這樣的z不存在，則c的深度為n。其中Dz(c)表示對c進(jìn)行z次微分運(yùn)算。記Dj以j為深度的碼字個(gè)數(shù)，集合 {D0，D1，…，Dn}稱為碼c的深度分布。下標(biāo)集{j|1＜j＜n，Dj≠0}稱為碼c的深度譜。

定理:有限域GF(q)上，任意一個(gè)(n，k)線性碼c的深度譜中都有且僅有k個(gè)非零值，深度互不相同的任意多個(gè)碼字向量是線性無關(guān)的［11］。

2 碼重相似度盲識別方法

線性分組碼碼字之間存在較強(qiáng)的線性約束關(guān)系，相比于隨機(jī)序列，并不是所有任意組合的碼字都會(huì)出現(xiàn)，導(dǎo)致碼重分布不平衡，其碼重分布概率與隨機(jī)序列的碼重分布概率之間差異很大，低碼率分組碼的這種差異程度更明顯，因此本文主要針對低碼率線性分組碼進(jìn)行識別。將兩序列的碼重分布概率看成兩個(gè)向量，采用向量間的相似度衡量兩個(gè)碼重分布概率之間的差異程度。本文根據(jù)隨機(jī)序列與實(shí)際序列碼重分布概率間差異最大這一特性，提出一種基于碼重相似度識別線性分組碼碼長和同步點(diǎn)的方法。

在統(tǒng)計(jì)學(xué)中，積矩相關(guān)ρW1W2的平方稱為判定系數(shù)R，用判定系數(shù)來衡量實(shí)際與隨機(jī)序列分布的相似度，則W1與W2的相似度表達(dá)式為

式中:COV(W1，W2)表示W(wǎng)1與W2的協(xié)方差;D(W1)與D(W2)分別為W1與W2的方差，即

將式(3)～(5)帶入式(2)，將式(2)結(jié)果帶入式(1)得判定系數(shù)即相似度

同步點(diǎn)已知，識別碼長步驟如下:

1)初始化實(shí)際接收序列的碼長n。

2)接收序列按碼長n分為M個(gè)碼字。n的變化范圍設(shè)為1～S，S為最大可能的值。S的選取要根據(jù)實(shí)際應(yīng)用需求綜合考慮。

4)利用式(6)求R。判斷R值是否最小，若最小，則識別碼長或碼長整數(shù)倍，當(dāng)首次出現(xiàn)谷值時(shí)對應(yīng)碼長為真實(shí)碼長;否則，n=n+1，轉(zhuǎn)到步驟2)，以此循環(huán)，直到R最小為止。

碼長已知，識別同步點(diǎn)步驟如下:

1)初始化接收序列的同步點(diǎn)m，從任意m位開始，以確定的碼長n劃分為M個(gè)碼字。

2)同識別碼長步驟3)。

3)利用式(6)求R。判斷R值是否最小，若最小，則識別同步點(diǎn)，否則，m=m+1，轉(zhuǎn)到步驟1)，以此循環(huán)，直到R最小為止，m的變化范圍是1～n+1。

3 深度分布性質(zhì)識別生成矩陣

用上述方法識別出碼長或同步點(diǎn)后，利用線性分組碼的深度分布特性識別G。由定義1知，只需找到k個(gè)不相關(guān)的向量組成矩陣形式，即為G。由定理知，深度值互不相同的非零碼字向量作為行向量生成的矩陣是G，根據(jù)此結(jié)論識別G。將G進(jìn)行初等行變換，得到典型生成矩陣。對于循環(huán)碼，進(jìn)而得到生成多項(xiàng)式。

該方法關(guān)鍵點(diǎn)是識別k值。(n，k)線性碼深度譜中有且僅有k個(gè)非零值，當(dāng)已知碼長和同步點(diǎn)后，求出M個(gè)碼字中每個(gè)碼字的深度值，記為j，j∈{0，1，…，n}，將深度為j的碼字個(gè)數(shù)相加，結(jié)果為Dj，則深度分布為{D0，D1，…，Dn}，深度譜為{j|1＜j＜n，Dj≠0}，由定理知選出深度譜中所有不同深度值分別對應(yīng)的任意一個(gè)碼字，擺成矩陣形式，即為G。此方法簡單，過程易于實(shí)現(xiàn)。

4 仿真驗(yàn)證及分析

4.1 已知同步點(diǎn)識別碼長

當(dāng) BSC 信道無誤碼時(shí)，采用(6，3)，(15，5)，(31，11)，(63，18)，(127，50)5 種線性分組碼進(jìn)行實(shí)驗(yàn)，用 MATLAB產(chǎn)生一段隨機(jī)序列進(jìn)行編碼。取10 000個(gè)碼元進(jìn)行仿真，結(jié)果如圖1所示。

圖1 5種低碼率線性分組碼的碼長識別

經(jīng)圖1仿真分析，當(dāng)遍歷的碼長是真實(shí)碼長或碼長整數(shù)倍時(shí)，碼組內(nèi)有完整的線性約束關(guān)系，不同碼重的碼字分布是非等概的，與隨機(jī)序列碼重分布相差最大，相似度最小，即判定系數(shù)最小，此時(shí)，相似度相對于臨近點(diǎn)其值變化較大，因此當(dāng)首次出現(xiàn)低谷時(shí)對應(yīng)的碼長為真實(shí)碼長。當(dāng)遍歷的碼長不是真實(shí)碼長或碼長整數(shù)倍時(shí)，碼組內(nèi)不具有完整的線性約束關(guān)系，不同碼重的碼字分布趨于等概率，接近隨機(jī)序列碼重分布，此時(shí)實(shí)際序列與隨機(jī)序列相似度較高。經(jīng)仿真分析該方法能正確識別碼長n。

當(dāng)BSC信道有誤碼時(shí)，以(15，5)線性分組碼為實(shí)驗(yàn)對象，碼元個(gè)數(shù)為10 000個(gè)，誤碼率分別為Pe=0.001，0.01，0.05，0.08，仿真結(jié)果如圖2 所示。

圖2 不同誤碼率對應(yīng)的仿真圖

從圖2可知，碼重相似度識別算法受誤碼率的影響。常規(guī)誤碼率為0.001～0.01，在常規(guī)誤碼率下可以正確識別碼長，之后隨著誤碼率的增加，在正確碼長或碼長整數(shù)倍處判定系數(shù)變化相對緩慢，在碼長整數(shù)倍處可能不會(huì)出現(xiàn)谷值，當(dāng)誤碼率增大到一定程度，出現(xiàn)失真，不能識別碼長。如在Pe=0.08時(shí)正確識別率很低，由給出的仿真圖勉強(qiáng)識別碼長。

4.2 已知碼長識別同步點(diǎn)

設(shè)BSC信道有誤碼，以誤碼率為Pe=0.03的(6，3)，(15，5)，(31，11)和Pe=0.01 的(63，18)4 種線性分組碼為實(shí)驗(yàn)對象，碼元個(gè)數(shù)為10 000個(gè)，在碼長n已知條件下，從任意起點(diǎn)開始，順序遍歷n個(gè)點(diǎn)，在各點(diǎn)處均以碼長n劃分序列，并統(tǒng)計(jì)判定系數(shù)，尋找判定系數(shù)為最小值時(shí)對應(yīng)的點(diǎn)，即為同步點(diǎn)。用MATLAB進(jìn)行仿真，結(jié)果如圖3所示。

圖3 碼字同步點(diǎn)識別仿真圖

計(jì)算同步點(diǎn)由m=1遍歷到m=n+1對應(yīng)的判定系數(shù)，并作分析，其中m=1表示起點(diǎn)，沒有移位，m=n+1表示從起點(diǎn)向右移n位，由于碼長為n，所以m=1與m=n+2對應(yīng)的判定系數(shù)是一樣的，因此僅比較起點(diǎn)和移位n個(gè)起點(diǎn)即可。由圖3可知，m分別為5，11，17，22處判定系數(shù)最小，即碼重相似度最低，碼字內(nèi)線性約束關(guān)系最強(qiáng)，此時(shí)對應(yīng)的m值為同步點(diǎn);而在其他位置，隨機(jī)性比較強(qiáng)，與隨機(jī)序列相似度較高。因此在誤碼率較高的條件下，運(yùn)用碼重相似度方法也能準(zhǔn)確識別碼字同步點(diǎn)。

4.3 深度分布性質(zhì)識別生成矩陣

假設(shè)截獲序列已知碼長和同步點(diǎn)，以(15，5)二進(jìn)制線性分組碼為例，取200個(gè)碼字。計(jì)算每個(gè)碼字的深度值，統(tǒng)計(jì)深度值相同的碼字個(gè)數(shù)。通過MATLAB編程，產(chǎn)生深度分布直方圖如圖4所示，圖4中橫坐標(biāo)為深度值j，縱坐標(biāo)為深度值相同的碼字個(gè)數(shù)之和Dj。

圖4對應(yīng)的深度分布為{4 10 0 0 0 0 0 0 0 0 0 0 10 22 57 97}，深度譜為{1，12，13，14，15}，根據(jù)定理知，此線性碼k=5即生成矩陣有5行，從這k個(gè)非零不同深度值對應(yīng)的碼字中，各取一個(gè)碼字，組成5×15的矩陣形式，即為生成矩陣，對其初等行變換得到典型生成矩陣。任取k=1對應(yīng)碼字為(111111111111111)，k=12對應(yīng)碼字為(101011001000111)，k=13對 應(yīng) 碼 字 為(100110111000010)，k=14對 應(yīng) 碼 字 為(111010110010001)，k=15對 應(yīng) 碼 字 為(111000010100110)，將此組成的矩陣形式如圖5所示。

圖4 (15，5)線性分組碼深度分布仿真圖

圖5 矩陣形式

從圖5可知，G3為典型生成矩陣。本節(jié)實(shí)驗(yàn)對象(15，5)也屬于循環(huán)碼，G3最后一行為生成多項(xiàng)式的系數(shù)，即循環(huán)碼的生成多項(xiàng)式為g(x)=x10+x8+x5+x4+x2+x+1。利用深度分布識別生成矩陣的方法簡單，過程易于實(shí)現(xiàn)。

5 容錯(cuò)性能比較分析

根據(jù)上述分析，碼重相似度識別碼長和同步點(diǎn)方法是有效的。下面以(7，4)，(15，5)，(31，16)，(63，16)這 4種線性分組碼為實(shí)驗(yàn)對象，分別對識別碼長和同步點(diǎn)兩種情況進(jìn)行容錯(cuò)性分析。

針對本文和文獻(xiàn)［5］兩種識別同步點(diǎn)的方法在相同環(huán)境下比較分析，對1 000個(gè)碼字在不同誤碼率下進(jìn)行1 000次蒙特卡洛仿真實(shí)驗(yàn)，各種線性碼的識別率與誤碼率曲線如圖6、圖7所示:圖6為碼重相似度識別同步點(diǎn)的仿真圖，明顯看出，當(dāng)誤碼率為0.18 時(shí)，(7，4)，(15，5)分組碼的同步點(diǎn)識別率超過了90%;誤碼率為0.06時(shí)，(31，16)分組碼的同步點(diǎn)識別率高達(dá)90%;誤碼率為0.016時(shí)，(63，16)識別率超過90%;因此本文算法能在高誤碼率下識別同步點(diǎn)。圖7為比特頻率檢測法識別同步點(diǎn)，其容錯(cuò)性較好，但本文算法相對于比特頻率檢測法容錯(cuò)性更有優(yōu)勢。

圖6 碼重相似度算法識別碼字同步點(diǎn)

圖7 比特頻率檢測方法識別碼字同步點(diǎn)

根據(jù)文獻(xiàn)［4］知碼重信息熵算法容錯(cuò)性強(qiáng)于碼重分布距離［3］算法，在此僅對文獻(xiàn)［4－5］和本文提出的識別碼長算法進(jìn)行比較。分別取1 000個(gè)4種長度的線性分組碼碼字為實(shí)驗(yàn)對象，進(jìn)行仿真，圖8為各種算法的誤碼適應(yīng)能力［13］曲線圖，圖中的誤碼適應(yīng)能力是以正確識別率90%以上為門限，不難看出，本文算法與以往算法相比，誤碼適應(yīng)能力有一定的提升，在適應(yīng)誤碼率1%以上識別碼長的正確率高達(dá)90%以上，容錯(cuò)性較好。

圖8 不同算法誤碼適應(yīng)能力

6 結(jié)論

根據(jù)線性分組碼碼重分布不平衡與隨機(jī)序列差異較大的特性，提出了一種碼重相似度算法識別碼長和同步點(diǎn)。在此基礎(chǔ)上，利用深度分布特性，識別生成矩陣，利用高斯消去法產(chǎn)生典型生成矩陣，針對循環(huán)碼，識別生成多項(xiàng)式，實(shí)現(xiàn)了線性分組碼的盲識別。最后在不同誤碼率下對低碼率線性分組碼進(jìn)行大量仿真實(shí)驗(yàn)，并與其他算法進(jìn)行對比，碼重相似度識別算法能在誤碼率為0.01情況下識別低碼率線性分組碼碼長和同步點(diǎn)，具有較好的容錯(cuò)性，此方法的誤碼適應(yīng)能力也有一定的提高。利用深度分布特性識別出生成矩陣，此方法簡單，隨著碼長增加數(shù)據(jù)量不斷擴(kuò)大，此識別生成矩陣的方法對無誤碼情況下的中短碼及低碼率的線性分組碼識別效果較好。運(yùn)用深度分布特性識別高誤碼率下、高碼率的線性分組碼參數(shù)成為下一步研究的重點(diǎn)。

:

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

［2］王偉祥，劉玉君.基于信道編碼的信息隱藏技術(shù)研究［J］.電視技術(shù)，2006，30(3):284－286.

［3］昝俊軍，李艷斌.低碼率二進(jìn)制線性分組碼的盲識別［J］.無線電工程，2009，39(1):19－24.

［4］陳金杰，楊俊安.基于碼重信息熵低碼率線性分組碼的盲識別［J］.電路與系統(tǒng)學(xué)報(bào)，2012，17(1):41－47.

［5］陳金杰，楊俊安.一種對線性分組碼編碼參數(shù)的盲識別方法［J］.電路與系統(tǒng)學(xué)報(bào)，2013，18(2):248－254.

［6］閆郁翰，湯建龍.基于漢明碼距離的二進(jìn)制線性分組碼盲識別方法［J］.通信對抗，2011(4):20－23.

［7］張永光，鄭仕鏈.BCH碼的參數(shù)識別研究［J］.西安電子科技大學(xué)學(xué)報(bào)，2013，40(5):92－98.

［8］王蘭勛，李丹芳，汪洋.二進(jìn)制本原BCH碼的參數(shù)盲識別［J］.河北大學(xué)學(xué)報(bào)，2012，32(4):416－420.

［9］于沛東，李靜，彭華.一種利用軟判決的信道編碼識別新算法［J］.電子學(xué)報(bào)，2013(2):301－306.

［10］王新梅，肖國鎮(zhèn).糾錯(cuò)碼——原理與方法［M］.修訂版.西安:西安電子科技大學(xué)出版社，2001.

［11］李超，耿晉.有限域上線性碼的深度分布［D］.長沙:國防科學(xué)技術(shù)大學(xué)，2006.

［12］王磊，胡以華，王勇，等.基于碼重分布的系統(tǒng)循環(huán)碼識別方法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48(7):150－153.

［13］解輝，王豐華，黃知濤，等.基于頻譜預(yù)處理的RS碼盲檢測識別方法［J］.宇航學(xué)報(bào)，2013，34(1):128－132.