擴展 Golay碼的盲識別方法

李 影,王曉君,劉 健

(1.石家莊郵電職業技術學院電信工程系,河北石家莊 050031;2.河北科技大學信息科學與工程學院,河北石家莊 050018;3.西安電子科技大學ISN國家重點實驗室,陜西西安 710071)

擴展 Golay碼的盲識別方法

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

(1.石家莊郵電職業技術學院電信工程系,河北石家莊 050031;2.河北科技大學信息科學與工程學院,河北石家莊 050018;3.西安電子科技大學ISN國家重點實驗室,陜西西安 710071)

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

誤碼率;盲識別;信道編碼;碼重分布;擴展 Golay碼

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

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

1 問題描述

設Cp是一碼序列,擴展 Golay碼的盲識別問題是判定Cp是否為擴展 Golay編碼。

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

定義1 對于某個奇素數p,稱i是模p的平方剩余,如果存在一個整數x,使

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

2 Golay碼的擴展

3 擴展Golay碼的特性

通過Monte-Carlo仿真實驗,隨機選取了100 000組擴展 Golay碼的數據,畫出了其碼重分布柱狀圖,如圖1所示。

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

表1 擴展 Golay碼的質量分布Tab.1 Weight distribution of extended Golay code

引理5 對于一個數字通信系統,在一個碼組中同時發生t個錯誤的概率為P(t),則

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

4 擴展Golay碼的盲識別

對于擴展 Golay碼來說,在無誤碼的情況下,任意的2個碼字的碼重如果不同,則它們的碼重之差的絕對值會在3以上。除非存在偶數個誤碼,否則一個碼組的碼重會發生改變,而根據引理5,可以得知在一個碼組中發生1個錯誤的概率遠遠大于發生2個錯誤的概率,即誤碼更為可能對碼重的改變僅為 ±1。又因為碼重為8,12和16的擴展 Golay碼占所有擴展 Golay碼的99%以上,因而盲識別算法可以歸納為如下步驟。

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

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

3)計算其中碼分組與校驗矩陣的內積,并記錄其中1的個數。

4)將其中1的個數與給出門限r進行判定,如果其小于給定門限,則認為該截獲碼序列為擴展Golay碼,如果大于給定門限則判定其不為擴展Golay碼。

5 仿真實驗及性能分析

無誤碼時,任意分組與校驗矩陣中的任一個校驗向量的內積應該為0,由于誤碼的存在會造成其內積為1。下面從概率的角度給出識別的門限r。

當且僅當擴展Golay碼的校驗矩陣中的每一組校驗向量均和待測碼組正交時,才可以認為待識別碼組為擴展 Golay碼。

其中F(t)是t的概率分布函數。由式(27)可以給出一個標準t。

如果碼組與一個隨機向量做內積,則內積為0的概率為P0=0.5,內積為1的概率為P1=0.5。為了有別于隨機現象(即校驗向量與碼組正交不是由隨機波動而引起的),此時取p=q=0.5,則

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

此時選定碼分組N=1 000,此時的門限r=452,即要保證擴展Golay碼校驗矩陣中的12組校驗向量與碼組內積后的1的個數均小于r。

根據上述的參數進行Monte-Carlo仿真實驗,在每個誤碼率下仿真實驗次數均為1 000次,在實驗過程中隨機加入了不同的誤碼,分別按照所提出的算法和文獻[5]給出的算法進行仿真,仿真實驗的結果如圖2所示。

從仿真圖中可以看出,所提出的算法的正確識別率明顯優越于原有算法的正確識別率。這是因為在盲識別的第2步過程中已經剔去了誤碼數量為奇數的可能,因此具有更高的識別率。

圖2 擴展Golay碼的識別成功次數的曲線圖Fig.2 Curve chart of successfull recognization of extended Golay code

6 結 語

給出了擴展 Golay碼的盲識別方法,實驗表明該算法能夠有效解決擴展 Golay碼盲識別問題,本識別算法已經成功地應用在信息截獲領域。

[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]鄒 艷,陸佩忠.關鍵方程的新推廣[J].計算機學報(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].鄭州:河南科學技術出版社,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;責任編輯:陳書欣

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