楊曉靜,聞年成

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

0 引言

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

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

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

1 BCH碼識別基礎(chǔ)

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

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

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

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

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

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

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

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

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

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

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

2.1 基于碼根信息差熵的碼長識別

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

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

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

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

2.2 基于碼根統(tǒng)計的生成多項式識別

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

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

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

對BCH碼的識別流程如圖1所示。

圖1 BCH碼的識別流程圖Fig.1 Recognition flow of BCH codes

3 可行性證明

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

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

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

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

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

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

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

所以,通過統(tǒng)計可實現(xiàn)對BCH碼的正確識別,而且若得到BCH碼長不正確,則每個碼塊都會產(chǎn)生隨機的錯誤,導致根的統(tǒng)計分布接近等概率的分布。

4 仿真驗證

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

下面以(63,51)BCH碼為例進行盲識別的仿真實驗。

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

4.1 碼長識別驗證

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

圖2 p e=1×10-3的某BCH碼碼長識別Fig.2 Code length recognition of BCH codes when p e=1×10-3

圖3 p e=1×10-2的某BCH碼碼長識別Fig.3 Code length recognition of BCH codes when p e=1×10-2

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

4.2 生成多項式識別驗證

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

圖4和圖5分別是在不同誤碼率條件下對識別碼長為n=63的BCH碼的整數(shù)碼根分布圖?？梢钥闯鲭S著誤碼率的增加,碼根統(tǒ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。遍歷該碼長對應的本原多項式,并結(jié)合BCH碼生成多項式的碼根t特征,進一步識別可以得到該序列本原多項式為:p(x)=x6+x+1;上述的整數(shù)碼根對應的符號碼根為:a1,a6,a2,a12,a3,a32,a8,a48,a4,a24,a33,a16,其中a為p(x)對應的本原根。利用有限域的乘法原理可以知道,該碼序列的生成多項式為:g(x)=(x-a1)(x-a6)…(x-a33)(x-a16)=x12+x10+x8+x5+x4+x3+1。

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

5 結(jié)論

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

[1]鄒艷,陸佩忠.關(guān)鍵方程的新推廣[J].計算機學報,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]薛國慶.系統(tǒng)卷積碼的盲識別[J].信息安全與保密通信,2009(2):57-60.XUE Guoqing.Blind identification of system convolutional codes[J].Information Security and Communications Privacy,2009(2):57-60.

[4]昝俊軍.低碼率線性分組碼的盲識別[J].無線電技術(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]王新梅.糾錯碼-原理與方法[M].西安:西安電子科技大學出版社,2002.