基于碼根信息差熵和碼根統計的BCH碼識別方法

楊曉靜,聞年成

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

0 引言

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

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

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

1 BCH碼識別基礎

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

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

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

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

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

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

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

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

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

2 碼根信息差熵和碼根統計的識別原理

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

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

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

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

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

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

2.2 基于碼根統計的生成多項式識別

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

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

最后經過化簡處理后,得到系數為0和1的表達式,實現對生成多項式的識別。

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

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

3 可行性證明

上節指出了在足夠的數據量條件下可以實現BCH碼的正確識別,下面對其可行性進行證明。

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

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

其余根的出現概率為:

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

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

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

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

4 仿真驗證

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

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

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

4.1 碼長識別驗證

圖2和圖3是BSC分別為p e=1×10-3和pe=1×10-2情況下BCH碼碼根信息差熵的仿真驗證圖。當遍歷的碼長不是真實碼長時,碼組的線性關系被破壞,故進行分組后的得到的碼根也是隨機產生,其碼根信息差熵相對于以真實的碼長進行分組時較小。圖2中在m=6位置碼根信息差熵的值大于2,其余的位置碼根信息差熵均小于1。圖3中在m=6的位置碼根信息差熵的值大于1,其余位置碼根信息差熵均小于1。所以從圖2和圖3可以明顯地看出,在m=6的位置出現峰值。故可以識別該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看出在一定的數據量條件下,通過遍歷碼長,利用碼根信息差熵函數完成對BCH碼的碼長識別時,誤碼率對該碼根信息差熵函數存在著影響。若假設碼長不是真實的碼長,那么誤碼率對該函數的值幾乎無影響,且該值較小,不超過1;若假設的碼長是真實的碼長,那么隨著誤碼率的增加,該函數的值變小,而且這些函數值大小是超過1的。

4.2 生成多項式識別驗證

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

圖4和圖5分別是在不同誤碼率條件下對識別碼長為n=63的BCH碼的整數碼根分布圖。可以看出隨著誤碼率的增加,碼根統計概率均降低,且生成多項式的根仍保持著概率相等。

圖4 p e=1×10-3,n=63的BCH碼的整數碼根分布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碼的整數碼根分布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。遍歷該碼長對應的本原多項式,并結合BCH碼生成多項式的碼根t特征,進一步識別可以得到該序列本原多項式為:p(x)=x6+x+1;上述的整數碼根對應的符號碼根為: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。

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

5 結論

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

[1]鄒艷,陸佩忠.關鍵方程的新推廣[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]薛國慶.系統卷積碼的盲識別[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].無線電技術,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.