基于碼根信息差熵和碼根統(tǒng)計(jì)的BCH碼識(shí)別方法

楊曉靜,聞年成

(電子工程學(xué)院,安徽合肥 230037)

0 引言

BCH碼是能夠糾正多個(gè)隨機(jī)錯(cuò)誤的循環(huán)碼,具有較強(qiáng)的糾錯(cuò)能力和嚴(yán)格的代數(shù)結(jié)構(gòu),同時(shí)具有構(gòu)造方便、編碼簡(jiǎn)單的優(yōu)點(diǎn)。因此,BCH碼在現(xiàn)階段有著較為廣泛的應(yīng)用。在截獲BCH碼序列后,為偵獲信息,需對(duì)編碼方式和編碼參數(shù)進(jìn)行盲識(shí)別。

目前,此領(lǐng)域的研究主要集中于卷積碼的盲識(shí)別和提高各種信道編碼方式的編譯碼性能,而在編碼方式識(shí)別及參數(shù)識(shí)別方面的相關(guān)研究很少。在目前編碼方式識(shí)別的算法中,快速雙合沖算法[1]實(shí)現(xiàn)了對(duì)1/2碼率的卷積碼的識(shí)別,但其模型不能應(yīng)用于其他高碼率的卷積碼的盲識(shí)別;歐幾里德算法[2]在低碼率方面實(shí)現(xiàn)了對(duì)卷積碼的盲識(shí)別,但沒有考慮誤碼條件下的識(shí)別處理方法。文獻(xiàn)[3]提出了一種新型數(shù)據(jù)矩陣模型,實(shí)現(xiàn)了對(duì)線性分組碼的盲識(shí)別,并且該方法可推廣到對(duì)系統(tǒng)卷積碼的盲識(shí)別,但其也沒有考慮誤碼條件下的識(shí)別處理方法。文獻(xiàn)[4]提出了一種對(duì)低碼率二進(jìn)制線性分組碼的識(shí)別方法,由碼重分布函數(shù)提取碼長(zhǎng)參數(shù) n的方法在4.71×10-3誤碼率條件下仍有效,并在此基礎(chǔ)上通過(guò)矩陣變換獲得生成矩陣,實(shí)現(xiàn)對(duì)二進(jìn)制線性分組碼的盲識(shí)別,但該方法不能解決高碼率分組碼的識(shí)別問題。與此同時(shí),這些編碼識(shí)別方法都采用了大量的矩陣運(yùn)算,且對(duì)誤碼率的要求比較高,有的方法甚至要求無(wú)誤碼情況下,才能獲得良好的性能。因此,在實(shí)際較高誤碼率條件下,如何正確識(shí)別BCH碼成為一個(gè)難點(diǎn)問題。

本文針對(duì)本原BCH碼的盲識(shí)別問題,提出了一種基于碼根信息差熵和碼根統(tǒng)計(jì)的識(shí)別方法。

1 BCH碼識(shí)別基礎(chǔ)

對(duì)于BCH碼的盲識(shí)別問題,就是在不知道編碼先驗(yàn)信息的情況下,通過(guò)對(duì)碼字序列的分析處理,從而估計(jì)出其生成多項(xiàng)式,其數(shù)學(xué)模型為:

式中,m(x)表示信息輸入多項(xiàng)式,c(x)表示信息編碼輸出多項(xiàng)式,g(x)表示編碼生成多項(xiàng)式。實(shí)際中,c(x)是通過(guò)對(duì)接收或偵察信號(hào)解調(diào)處理得到。因此,BCH碼的盲識(shí)別問題就是在僅知道c(x)的前提下如何獲得生成多項(xiàng)式 g(x),進(jìn)而完成對(duì)信息的還原。

定義1:給定有限域GF(q)及其擴(kuò)域GF(qm),其中q=2,m為某一正整數(shù)。若碼元取自GF(q)上的循環(huán)碼,其生成多項(xiàng)式g(x)的根集合R中含有δ-1個(gè)連續(xù)根:

時(shí),則由g(x)生成的循環(huán)碼稱為二進(jìn)制本原BCH碼,碼長(zhǎng)為n=2m-1,其生成多項(xiàng)式根的性質(zhì)如下:

1)該生成多項(xiàng)式的根在GF(qm)中,且包含一組m個(gè)共軛根{a,a2,a4,…,a2m-1}[5],a是本原根。

2)該生成多項(xiàng)式的偶數(shù)個(gè)根是其本原根a的連續(xù)冪。

本文在BCH碼盲識(shí)別中,提出的碼根信息差熵的概念如下:

定義2:實(shí)際測(cè)得的碼根分布信息熵與均勻分布的碼根分布信息熵的差值,即為碼根信息差熵函數(shù),其計(jì)算公式如下:

這里需要對(duì)p作一下擴(kuò)展,將p中的零元素改為元素“1”,剔除元素“0”對(duì)碼根信息差熵函數(shù)的影響,因?yàn)閷?duì)于對(duì)數(shù)函數(shù)log(x)要求其自變量x＞0,而log(1)=0可以剔除“0”元素的影響。

2 碼根信息差熵和碼根統(tǒng)計(jì)的識(shí)別原理

當(dāng)截獲 BCH碼序列后,通過(guò)遍歷m對(duì)本原BCH碼進(jìn)行分組,得到分組數(shù)N。對(duì)每個(gè)碼字求取整數(shù)碼根并進(jìn)行統(tǒng)計(jì),得到不同碼根出現(xiàn)的次數(shù)N 0{1,2,…,n},進(jìn)而得到所有碼根出現(xiàn)的總次數(shù)S=sum(N0)。

2.1 基于碼根信息差熵的碼長(zhǎng)識(shí)別

由有限域多項(xiàng)式根的性質(zhì)[5],對(duì)于碼長(zhǎng)為n的循環(huán)碼碼字,其碼根個(gè)數(shù)為n-1,范圍為0～n-1,并且其分布具有一定的規(guī)律,即生成多項(xiàng)式的根在每個(gè)碼字中均會(huì)出現(xiàn),而每個(gè)碼字中其他的碼根是隨機(jī)出現(xiàn)的。若估計(jì)的碼長(zhǎng)不是真實(shí)循環(huán)碼的碼長(zhǎng),那么碼字之間的相關(guān)性和碼根分布的特征便不存在,則統(tǒng)計(jì)得到的碼根是隨機(jī)出現(xiàn)的。假設(shè)其碼根分布為均勻分布,不同碼根的出現(xiàn)概率均為:

對(duì)于碼根在域GF(2m)上、碼長(zhǎng)為n的BCH碼而言,信道的誤比特率Pe與碼塊正確率Ps具有如下的關(guān)系

由此可以看出,碼塊出現(xiàn)錯(cuò)誤時(shí),碼塊的根不會(huì)出現(xiàn)BCH碼的根特征。在隨機(jī)錯(cuò)誤或突發(fā)錯(cuò)誤的條件下,每個(gè)碼塊中出現(xiàn)錯(cuò)誤的位置是隨機(jī)的,因此碼塊的碼根也將是隨機(jī)出現(xiàn)的。在數(shù)據(jù)量足夠大的條件下,碼塊數(shù)足夠多,其正確碼塊的數(shù)目就多,那么正確碼塊的碼根中滿足的性質(zhì)1和性質(zhì)2的根將會(huì)在每次正確碼塊的碼根統(tǒng)計(jì)中出現(xiàn)。下節(jié)將對(duì)在足夠多的數(shù)據(jù)量條件下實(shí)現(xiàn)BCH碼的正確識(shí)別進(jìn)行可行性證明。

若實(shí)際測(cè)得的碼根分布為 p=p{p 1,p2,…,p n}=N0{1,2,…,n}/S,利用定義2的碼根信息差熵的函數(shù)可以實(shí)現(xiàn)對(duì)BCH碼的碼長(zhǎng)識(shí)別。

2.2 基于碼根統(tǒng)計(jì)的生成多項(xiàng)式識(shí)別

在碼字整數(shù)根中,生成多項(xiàng)式根的分布是最大的且隨本原多項(xiàng)式的變化而變化,僅在整數(shù)分布中發(fā)生位置的變化,而大小不變。這給利用碼根信息差熵函數(shù)識(shí)別碼長(zhǎng)提供了的條件,簡(jiǎn)化了識(shí)別過(guò)程。在識(shí)別碼長(zhǎng)的基礎(chǔ)上,利用統(tǒng)計(jì)得到的碼根分布p=p{p 1,p 2,…,p n}=N0{1,2,…,n}/N,尋找概率接近1的碼根即為生成多項(xiàng)式的整數(shù)根Z 。

接下來(lái),遍歷本原多項(xiàng)式,然后將這些整數(shù)根Zroot轉(zhuǎn)換為符號(hào)碼根Sroot。若Sroot滿足 BCH碼碼根的性質(zhì),則可同時(shí)完成對(duì)本原多項(xiàng)式和生成多項(xiàng)式根a=(a1,a2,…,al)的識(shí)別。利用有限域乘法,可以知道該生成多項(xiàng)式為:g(x)=(x-a1)(xa2)…(x-al)。

最后經(jīng)過(guò)化簡(jiǎn)處理后,得到系數(shù)為0和1的表達(dá)式,實(shí)現(xiàn)對(duì)生成多項(xiàng)式的識(shí)別。

對(duì)BCH碼的識(shí)別流程如圖1所示。

圖1 BCH碼的識(shí)別流程圖Fig.1 Recognition flow of BCH codes

3 可行性證明

上節(jié)指出了在足夠的數(shù)據(jù)量條件下可以實(shí)現(xiàn)BCH碼的正確識(shí)別,下面對(duì)其可行性進(jìn)行證明。

證明:鑒于編碼信息的隨機(jī)性,在碼長(zhǎng)為n的條件下,正確碼塊出現(xiàn)的碼根中包含生成多項(xiàng)式確定的n0個(gè)根,其余的根是隨機(jī)出現(xiàn)的;同時(shí)由于信道比特錯(cuò)誤位置的隨機(jī)性,錯(cuò)誤碼塊的所有根也是隨機(jī)出現(xiàn)的。

令H0表示碼塊正確事件,H 1表示碼塊錯(cuò)誤事件,D 0表示出現(xiàn)包含生成多項(xiàng)式n0個(gè)根的事件,D1表示出現(xiàn)其他根的事件。由概率論每個(gè)碼塊中出現(xiàn)生成多項(xiàng)式n0個(gè)根的概率為:

其余根的出現(xiàn)概率為:

因此,在一定的碼塊正確率條件下,生成多項(xiàng)式每個(gè)根的出現(xiàn)概率由公式(1)可知

其余每個(gè)根的出現(xiàn)概率由公式(2)可知

由式(3)和式(4)可以得到:

所以,通過(guò)統(tǒng)計(jì)可實(shí)現(xiàn)對(duì)BCH碼的正確識(shí)別,而且若得到BCH碼長(zhǎng)不正確,則每個(gè)碼塊都會(huì)產(chǎn)生隨機(jī)的錯(cuò)誤,導(dǎo)致根的統(tǒng)計(jì)分布接近等概率的分布。

4 仿真驗(yàn)證

在上述的識(shí)別方法基礎(chǔ)上,誤碼率設(shè)定為pe=1×10-3和p e=1×10-2,利用Matlab軟件對(duì)不同編碼參數(shù)的BCH碼進(jìn)行了盲識(shí)別仿真。大量的仿真實(shí)驗(yàn)表明識(shí)別效果較好。

下面以(63,51)BCH碼為例進(jìn)行盲識(shí)別的仿真實(shí)驗(yàn)。

該仿真模擬的信道是二進(jìn)制對(duì)稱信道(BSC),其特點(diǎn)是通過(guò)保留二進(jìn)制符號(hào)每一比特出現(xiàn)的概率來(lái)破壞信息傳輸,且與二進(jìn)制符號(hào)序列傳輸過(guò)程中前后出現(xiàn)的錯(cuò)誤無(wú)關(guān)。

4.1 碼長(zhǎng)識(shí)別驗(yàn)證

圖2和圖3是BSC分別為p e=1×10-3和pe=1×10-2情況下BCH碼碼根信息差熵的仿真驗(yàn)證圖。當(dāng)遍歷的碼長(zhǎng)不是真實(shí)碼長(zhǎng)時(shí),碼組的線性關(guān)系被破壞,故進(jìn)行分組后的得到的碼根也是隨機(jī)產(chǎn)生,其碼根信息差熵相對(duì)于以真實(shí)的碼長(zhǎng)進(jìn)行分組時(shí)較小。圖2中在m=6位置碼根信息差熵的值大于2,其余的位置碼根信息差熵均小于1。圖3中在m=6的位置碼根信息差熵的值大于1,其余位置碼根信息差熵均小于1。所以從圖2和圖3可以明顯地看出,在m=6的位置出現(xiàn)峰值。故可以識(shí)別該BCH碼的碼長(zhǎng)為n=2m-1=63。

圖2 p e=1×10-3的某BCH碼碼長(zhǎng)識(shí)別Fig.2 Code length recognition of BCH codes when p e=1×10-3

圖3 p e=1×10-2的某BCH碼碼長(zhǎng)識(shí)別Fig.3 Code length recognition of BCH codes when p e=1×10-2

從圖2和圖3看出在一定的數(shù)據(jù)量條件下,通過(guò)遍歷碼長(zhǎng),利用碼根信息差熵函數(shù)完成對(duì)BCH碼的碼長(zhǎng)識(shí)別時(shí),誤碼率對(duì)該碼根信息差熵函數(shù)存在著影響。若假設(shè)碼長(zhǎng)不是真實(shí)的碼長(zhǎng),那么誤碼率對(duì)該函數(shù)的值幾乎無(wú)影響,且該值較小,不超過(guò)1;若假設(shè)的碼長(zhǎng)是真實(shí)的碼長(zhǎng),那么隨著誤碼率的增加,該函數(shù)的值變小,而且這些函數(shù)值大小是超過(guò)1的。

4.2 生成多項(xiàng)式識(shí)別驗(yàn)證

在識(shí)別出碼長(zhǎng)的基礎(chǔ)上,利用統(tǒng)計(jì)碼根分布p=p{p 1,p2,…,p n}=N0{1,2,…,n}/N,尋找概率接近1的碼根即為生成多項(xiàng)式的整數(shù)根Z root,轉(zhuǎn)化為符號(hào)碼根Sroot。遍歷本原多項(xiàng)式,若Sroot滿足BCH碼碼根的性質(zhì),則可以同時(shí)完成對(duì)本原多項(xiàng)式和生成多項(xiàng)式根a=(a,a,…,a)的識(shí)別。利用有限域乘法,可以知道該生成多項(xiàng)式為:g(x)=(xa1)(x-a2)…(x-al)?；?jiǎn)處理后最終將是系數(shù)為0和1的表達(dá)式,完成對(duì)生成多項(xiàng)式的識(shí)別。

圖4和圖5分別是在不同誤碼率條件下對(duì)識(shí)別碼長(zhǎng)為n=63的BCH碼的整數(shù)碼根分布圖?？梢钥闯鲭S著誤碼率的增加,碼根統(tǒng)計(jì)概率均降低,且生成多項(xiàng)式的根仍保持著概率相等。

圖4 p e=1×10-3,n=63的BCH碼的整數(shù)碼根分布Fig.4 Integral code root statistic of BCH codes of n=63 when p e=1×10-3

圖5 p e=1×10-2,n=63的BCH碼的整數(shù)碼根分布Fig.5 Integral code root statistic of BCH codes of n=63 when p e=1×10-2

從圖4和圖5可以看出,概率較近且分布概率較高的碼根為:2,3,4,5,8,9,12,13,16,17,18,19。遍歷該碼長(zhǎng)對(duì)應(yīng)的本原多項(xiàng)式,并結(jié)合BCH碼生成多項(xiàng)式的碼根t特征,進(jìn)一步識(shí)別可以得到該序列本原多項(xiàng)式為:p(x)=x6+x+1;上述的整數(shù)碼根對(duì)應(yīng)的符號(hào)碼根為:a1,a6,a2,a12,a3,a32,a8,a48,a4,a24,a33,a16,其中a為p(x)對(duì)應(yīng)的本原根。利用有限域的乘法原理可以知道,該碼序列的生成多項(xiàng)式為:g(x)=(x-a1)(x-a6)…(x-a33)(x-a16)=x12+x10+x8+x5+x4+x3+1。

在獲取碼長(zhǎng)后,通過(guò)遍歷本原多項(xiàng)式對(duì)生成多項(xiàng)式的整數(shù)根Z root轉(zhuǎn)換為符號(hào)根S root,完成對(duì)本原多項(xiàng)式的識(shí)別,同時(shí)獲得對(duì)應(yīng)的符號(hào)碼根,利用有限域乘法恢復(fù)生成多項(xiàng)式,完成BCH碼的識(shí)別。

5 結(jié)論

本文提出的基于碼根信息差熵和碼根統(tǒng)計(jì)的BCH碼的識(shí)別方法,首次定義了碼根信息差熵函數(shù),利用該函數(shù)實(shí)現(xiàn)了BCH碼的碼長(zhǎng)識(shí)別;采用碼根統(tǒng)計(jì)的方法完成了BCH碼的生成多項(xiàng)式識(shí)別,進(jìn)而實(shí)現(xiàn)了對(duì)BCH碼的盲識(shí)別。仿真驗(yàn)證分析表明:該方法能夠在較高的誤碼率條件下對(duì)二進(jìn)制本原BCH碼進(jìn)行有效的盲識(shí)別,且具有較好的容錯(cuò)性能。

[1]鄒艷,陸佩忠.關(guān)鍵方程的新推廣[J].計(jì)算機(jī)學(xué)報(bào),2006,29(5):711-718.ZOU Yan,LU Peizhong.A new generalization of key equation[J].Chinese Journal of Computers,2006,29(5):711-718.

[2]WANG Fenghua,HUANG Zhitao.A method of blind recognition of convolution code based on euclidean algorithm[C]//IEEE Inter Conference on Wireless Com Networking and Mobile Computing.Shanghai,China:IEEE,2007:1 414-1 417.

[3]薛國(guó)慶.系統(tǒng)卷積碼的盲識(shí)別[J].信息安全與保密通信,2009(2):57-60.XUE Guoqing.Blind identification of system convolutional codes[J].Information Security and Communications Privacy,2009(2):57-60.

[4]昝俊軍.低碼率線性分組碼的盲識(shí)別[J].無(wú)線電技術(shù),2009,39(1):19-22.ZAN Junjun,LI Yanbin.Blind recognition of low coderate binary linear block code[J].Radio Engineering,2009,39(1):19-22.

[5]王新梅.糾錯(cuò)碼-原理與方法[M].西安:西安電子科技大學(xué)出版社,2002.