李 影,王曉君,劉 健

(1.石家莊郵電職業(yè)技術(shù)學(xué)院電信工程系,河北石家莊 050031;2.河北科技大學(xué)信息科學(xué)與工程學(xué)院,河北石家莊 050018;3.西安電子科技大學(xué)ISN國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071)

擴(kuò)展 Golay碼的盲識(shí)別方法

李 影1,王曉君2,劉 健3

(1.石家莊郵電職業(yè)技術(shù)學(xué)院電信工程系,河北石家莊 050031;2.河北科技大學(xué)信息科學(xué)與工程學(xué)院,河北石家莊 050018;3.西安電子科技大學(xué)ISN國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071)

針對(duì)信道編碼的盲識(shí)別問題,首次提出了擴(kuò)展 Golay碼的盲識(shí)別方法。與前有的盲識(shí)別算法比較,該算法的識(shí)別概率有明顯的提高,這是一個(gè)全新的研究課題,在智能通信、信息截獲、密碼分析等領(lǐng)域有重要的應(yīng)用。仿真實(shí)驗(yàn)表明文中提出的方法在誤碼率為8×10-2的情況下,對(duì)于擴(kuò)展 Golay碼的識(shí)別概率高于99%,比原有算法提高了44%。

誤碼率;盲識(shí)別;信道編碼;碼重分布;擴(kuò)展 Golay碼

信道編碼的盲識(shí)別在信息截獲、信息對(duì)抗以及智能通信等領(lǐng)域有重要的應(yīng)用,但該方面的研究鮮見報(bào)道。信道編碼主要包括卷積碼和分組碼2大類。目前,信道編碼的盲識(shí)別技術(shù)研究主要涉及卷積碼的盲識(shí)別方面,如文獻(xiàn)[1]和文獻(xiàn)[2]提出了刪除卷積碼的盲識(shí)別方法;文獻(xiàn)[3]提出了基于快速合沖算法的(2,1,m)類卷積碼盲識(shí)別算法;文獻(xiàn)[4]提出了基于歐幾里德算法的(2,1,m)類卷積碼盲識(shí)別算法等。

分組碼是另一類重要的信道編碼,現(xiàn)已廣泛應(yīng)用于通信系統(tǒng)。由于其每個(gè)分組之間相互獨(dú)立,并不存在卷積碼的“相關(guān)性”,因此,盲識(shí)別的難度更大,文獻(xiàn)[5]提出了基于校驗(yàn)矩陣與所對(duì)應(yīng)編碼的正交特性的分組碼的盲識(shí)別算法。擴(kuò)展Golay碼是分組碼中較為重要的一類,是唯一已知的能糾多個(gè)錯(cuò)誤的二元完備碼。由于其良好的糾錯(cuò)能力,因而在短波、超短波通信中應(yīng)用非常廣泛。筆者提出了一種基于擴(kuò)展 Golay碼的分布特性的盲識(shí)別算法。從仿真實(shí)驗(yàn)可以看出,筆者提出的算法的正確識(shí)別率明顯優(yōu)于文獻(xiàn)[5]中的算法。

1 問題描述

設(shè)Cp是一碼序列,擴(kuò)展 Golay碼的盲識(shí)別問題是判定Cp是否為擴(kuò)展 Golay編碼。

首先給出需要引用的一些概念。

定義1 對(duì)于某個(gè)奇素?cái)?shù)p,稱i是模p的平方剩余,如果存在一個(gè)整數(shù)x,使

生成的(23,12)循環(huán)碼為平方剩余碼,這就是著名的 Golay碼。

2 Golay碼的擴(kuò)展

3 擴(kuò)展Golay碼的特性

通過Monte-Carlo仿真實(shí)驗(yàn),隨機(jī)選取了100 000組擴(kuò)展 Golay碼的數(shù)據(jù),畫出了其碼重分布柱狀圖,如圖1所示。

仿真圖1中的碼重分布也驗(yàn)證了表1的正確性。從圖1中可以看出碼重為8,12和16的擴(kuò)展Golay碼占所有擴(kuò)展Golay碼的99%以上。這是擴(kuò)展Golay碼的一條重要特性,為了方便敘述擴(kuò)展Golay碼的盲識(shí)別方法,給出一條引理。

表1 擴(kuò)展 Golay碼的質(zhì)量分布Tab.1 Weight distribution of extended Golay code

引理5 對(duì)于一個(gè)數(shù)字通信系統(tǒng),在一個(gè)碼組中同時(shí)發(fā)生t個(gè)錯(cuò)誤的概率為P(t),則

圖1 擴(kuò)展Golay碼的碼重分布柱狀圖Fig.1 Histogram of extended Golay code’s codeweight distribution

4 擴(kuò)展Golay碼的盲識(shí)別

對(duì)于擴(kuò)展 Golay碼來說,在無誤碼的情況下,任意的2個(gè)碼字的碼重如果不同,則它們的碼重之差的絕對(duì)值會(huì)在3以上。除非存在偶數(shù)個(gè)誤碼,否則一個(gè)碼組的碼重會(huì)發(fā)生改變,而根據(jù)引理5,可以得知在一個(gè)碼組中發(fā)生1個(gè)錯(cuò)誤的概率遠(yuǎn)遠(yuǎn)大于發(fā)生2個(gè)錯(cuò)誤的概率,即誤碼更為可能對(duì)碼重的改變僅為 ±1。又因?yàn)榇a重為8,12和16的擴(kuò)展 Golay碼占所有擴(kuò)展 Golay碼的99%以上,因而盲識(shí)別算法可以歸納為如下步驟。

1)計(jì)算截獲碼序列的碼重。

2)選取其中的碼重為8,12和16的N個(gè)碼分組。

3)計(jì)算其中碼分組與校驗(yàn)矩陣的內(nèi)積,并記錄其中1的個(gè)數(shù)。

4)將其中1的個(gè)數(shù)與給出門限r(nóng)進(jìn)行判定,如果其小于給定門限,則認(rèn)為該截獲碼序列為擴(kuò)展Golay碼,如果大于給定門限則判定其不為擴(kuò)展Golay碼。

5 仿真實(shí)驗(yàn)及性能分析

無誤碼時(shí),任意分組與校驗(yàn)矩陣中的任一個(gè)校驗(yàn)向量的內(nèi)積應(yīng)該為0,由于誤碼的存在會(huì)造成其內(nèi)積為1。下面從概率的角度給出識(shí)別的門限r(nóng)。

當(dāng)且僅當(dāng)擴(kuò)展Golay碼的校驗(yàn)矩陣中的每一組校驗(yàn)向量均和待測(cè)碼組正交時(shí),才可以認(rèn)為待識(shí)別碼組為擴(kuò)展 Golay碼。

其中F(t)是t的概率分布函數(shù)。由式(27)可以給出一個(gè)標(biāo)準(zhǔn)t。

如果碼組與一個(gè)隨機(jī)向量做內(nèi)積,則內(nèi)積為0的概率為P0=0.5,內(nèi)積為1的概率為P1=0.5。為了有別于隨機(jī)現(xiàn)象(即校驗(yàn)向量與碼組正交不是由隨機(jī)波動(dòng)而引起的),此時(shí)取p=q=0.5,則

可以根據(jù)式(28)來判別解向量的置信度。當(dāng)t≥3時(shí),錯(cuò)誤概率為0.001 35,此時(shí)保證虛警概率為β=0.001 35。此時(shí)將門限值t設(shè)為3。

此時(shí)選定碼分組N=1 000,此時(shí)的門限r(nóng)=452,即要保證擴(kuò)展Golay碼校驗(yàn)矩陣中的12組校驗(yàn)向量與碼組內(nèi)積后的1的個(gè)數(shù)均小于r。

根據(jù)上述的參數(shù)進(jìn)行Monte-Carlo仿真實(shí)驗(yàn),在每個(gè)誤碼率下仿真實(shí)驗(yàn)次數(shù)均為1 000次,在實(shí)驗(yàn)過程中隨機(jī)加入了不同的誤碼,分別按照所提出的算法和文獻(xiàn)[5]給出的算法進(jìn)行仿真,仿真實(shí)驗(yàn)的結(jié)果如圖2所示。

從仿真圖中可以看出,所提出的算法的正確識(shí)別率明顯優(yōu)越于原有算法的正確識(shí)別率。這是因?yàn)樵诿ぷR(shí)別的第2步過程中已經(jīng)剔去了誤碼數(shù)量為奇數(shù)的可能,因此具有更高的識(shí)別率。

圖2 擴(kuò)展Golay碼的識(shí)別成功次數(shù)的曲線圖Fig.2 Curve chart of successfull recognization of extended Golay code

6 結(jié) 語

給出了擴(kuò)展 Golay碼的盲識(shí)別方法,實(shí)驗(yàn)表明該算法能夠有效解決擴(kuò)展 Golay碼盲識(shí)別問題,本識(shí)別算法已經(jīng)成功地應(yīng)用在信息截獲領(lǐng)域。

[1]LU Pei-zhong,SHEN Li,LUO Xiang-yang,et al.Blind recognition of punctured convolutional codes[A].IEEE International Symposium on Info rmation Theo ry[C].Shanghai:IEEE Press,2004.

[2]SHEN Li,LU Pei-zhong,LUO Xiang-yang,et al.Equivalence of punctured convolutional codes from shift equivalent puncturing patterns[A].IEEE International Conference on Information Technology:Coding and Computing[C].Las Vegas:IEEE Press,2004.

[3]鄒 艷,陸佩忠.關(guān)鍵方程的新推廣[J].計(jì)算機(jī)學(xué)報(bào)(Chinese Journal of Computers),2006,29(5):712-718.

[4]WANG Feng-hua,HUANG Zhi-tao,ZHOU Yi-yu.A method for blind recognition of convolution code based euclidean algorithm[A].IEEE International Conference on Wireless Communications[C].Shanghai:IEEE Press,2007.

[5]CHRISTOPHE C.Recogniton of a code in a noisy environment[A].IEEE International Symposium on Information Theory[C].Nice:IEEE Press,2007.

[6]劉玉君.信道編碼[M].鄭州:河南科學(xué)技術(shù)出版社,2007.

Methods fo r blind recognition of extended Golay code

L I Ying1,WANG Xiao-jun2,L IU Jian3
(1.Telecommunications Engineering Department,Shijiazhuang Posts and Telecommunications Technology Vocational College,Shijiazhuang Hebei 050031,China;2.College of Info rmation Science and Engineering,Hebei University of Science and Technology,Shijiazhuang Hebei 050018,China;3.National Key Lab of Integrated Services Networks,Xidian University,Xi’an Shaanxi 710071,China)

In o rder to solve the p roblem of blind recognition of channel coding,themethod of blind recognition of extended Golay code is p roposed.Compared w ith the fo rmer blind recognition,the recognition p robability has been obviously imp roved.This is a brand-new subject for research and has important app lication in such fieldsas adap tive communication,info rmation intercep tion and cryp tanalysis.The simulation experiments show that the recognition p robability for extended Golay code of the p roposed method in the thesis is above 99%,enhanced by 44%compared w ith the o riginalmethod at a bit error rate(BER)of 8×10-2.

bit erro r rate;blind recognition;channel coding;weight distribution;extended Golay code

TN911.2

A

1008-1542(2010)06-0553-05

2010-05-07;責(zé)任編輯:陳書欣

李 影(1977-),女,河北保定人,講師,碩士研究生,主要從事移動(dòng)通信方面的研究。