二進制本原BCH碼的參數盲識別

王蘭勛，李丹芳，汪洋

（河北大學 電子信息工程學院，河北 保定 071002）

二進制本原BCH碼的參數盲識別

王蘭勛，李丹芳，汪洋

（河北大學 電子信息工程學院，河北 保定 071002）

針對BCH碼的盲識別問題，提出一種基于歐幾里德算法的最大公因式的識別方法．首先，根據循環移位碼字求取最大公因式，得到最大公因式的系數矩陣．然后，分析最大公因式的次數分布規律確定碼長，由系數矩陣求出生成多項式．該識別方法簡單易行，無繁雜的矩陣運算．理論分析及仿真實驗表明，無誤碼時使用較小的數據量就可有效識別；誤碼率為10－2，數據量足夠時，識別效果仍然較好．

BCH碼；歐幾里德算法；最大公因式；盲識別

信道編碼盲識別是一個全新的領域，其主要應用在信息對抗、協作通信以及自適應調制編碼技術（AMC）等領域．據現在公開發表的文獻來看，大部分文獻集中在卷積碼的盲識別上，較少研究線性分組碼的盲識別．文獻［1］建立了一種線性分組碼的識別模型，是在無誤碼條件下的全盲識別，但其分析所需數據量會隨碼長估值的擴大急劇增大，導致其實用意義不大．文獻［2］則對該方法做了一定的改進，大大減少了樣本數據量，提高了實用性，并將其應用于工程實踐中．文獻［3］根據碼重分布估計碼長，進而通過矩陣化簡得出生成矩陣，該算法對低碼率二進制線性分組碼有較好的識別效果．文獻［4］在文獻［3］的基礎上先識別出碼長，再根據碼字與校驗矩陣的校驗關系識別出生成多項式．文獻［5］用經典的BM算法求解循環碼的盲識別模型，算法較復雜．文獻［6］采用秩統計的方法識別出碼長，再用統計的方法獲取生成多項式的根，進而得到生成多項式，識別繁瑣，計算量較大．文獻［7］根據碼根信息差熵識別碼長，并采用碼根統計的方法識別生成多項式，同樣所需數據量較大．

本文針對本原BCH碼的特殊性質，結合歐幾里德算法，提出一種新的識別方法．該方法識別原理簡單，并具有較好的容錯性，經實驗驗證在無誤碼較少的數據量時可達到識別的目的，有誤碼數據量足夠時，仍有較好的識別效果．

1 BCH碼識別基礎

定義1［8］給定任一有限域GF（q）及其擴域GF（qm），其中q是素數或素數的冪，m為某一正整數．若碼元取自GF（q）上的一個循環碼，它的生成多項式g（x）的根集合R中含有以下δ－1個連續根：

時，即則由g（x）生成的循環碼稱為q進制BCH碼．通常取m0＝1，如果生成多項式g（x）的根中，有一個GF（2m）中的本原域元素，則n＝qm－1，當q＝2時，稱這種碼長n＝2m－1的BCH碼為二進制本原BCH碼．

二進制本原BCH碼具有的性質：

1）循環性．循環性是指任一碼組循環移位以后，仍為該碼中的一個碼組．

2）所有碼多項式T（x）都是g（x）的倍式．可寫成

本文所用歐幾里德算法是用于搜尋二元域上的多項式c（x）和c′（x）的最大公因式d（x），即方程

如何找到d（x）是本文研究的重點．

定理1 設c（x）和c′（x）是二元域上的2個多項式，則有唯一的一對二元域上的多項式q（x）和r（x），具有下面的性質：

其中r（x）的次數小于c′（x）的次數，叫余式．

該定理也叫做歐幾里德除法定理．其中q（x）就是除法中的商式，r（x）是c（x）除以c′（x）所剩的余式，定義（c（x），c′（x））為c（x）和c′（x）的最大公因式．經典的歐幾里德算法即不斷利用定理1作除法可得下列：

該算法說明了找出（c（x），c′（x））的方法，即先找出c（x）除以c′（x）的余式r1（x），再找出c′（x）除以r1（x）的余式r2（x），依此類推找出rj－1（x）與rj（x）的余式rj＋1（x），直到余式為0．因為以上多項式均是二元域上的多項式，所以式中的運算均為模二運算．BCH碼多項式的歐幾里德算法可以用輾轉相除的方法來實現［9］．

當截獲碼流后，根據幀同步的信息很容易確定BCH碼的起始點，所以本文的識別研究是在起始點已知的條件下進行的，這也是符合實際情況的．

2 識別方法

本文提出的識別方法是利用歐幾里德算法計算循環移位前后2個碼字多項式的最大公因式d（x）．因為循環碼的每個碼字均是生成多項式的倍式，所以它們的最大公因式是生成多項式或生成多項式的倍式，由仿真實驗分析得出碼長n和生成多項式g（x）．下面對該方法進行詳細描述．

2．1 數學公式描述

BCH碼的編碼數學模型為

其中c（x）為碼字多項式，m（x）為信息多項式，g（x）為生成多項式．實際應用中，c（x）為接收或截獲的碼流，在不知道任何編碼參數的情況下通過識別方法獲得g（x），進而得到該碼流攜帶的信息m（x）．

2．2 基于歐幾里德算法的識別原理

因任一BCH碼多項式c（x）都是g（x）的倍式，所以同一碼組中2個BCH碼多項式的最大公因式不是g（x）就是g（x）的倍式．而若假設c（x）是BCH碼的一個碼組，所以c（x）循環移位m次的結果c′（x）也必為該碼中的一個碼組．根據這一性質結合歐幾里德算法計算出最大公因式d（x），進而通過數據分析得到g（x）．

首先，截獲一段BCH碼碼流，遍歷m，對于二進制BCH碼m通常取3到8．然后，由n＝2m－1對碼流分組，得到碼字矩陣，將碼字矩陣循環移位m次，運用文中介紹的歐幾里德算法計算循環移位前后碼字的最大公因式d（x），得到最大公因式的系數矩陣，進而求出d（x）的次數?0（d（x）），用matlab仿真?0（d（x））的分布圖．若m選取正確，即n正確，d（x）的次數大部分大于某一數值，即次數閾值．這個閾值就是生成多項式的次數，因為最大公因式不是g（x）就是g（x）的倍式，所以大部分?0（d（x））是大于或等于?0（g（x））的；若m選取錯誤，d（x）的次數分布無此規律，大小不均．在m選取正確時，獲取碼長n，得到d（x）的系數矩陣，并記錄次數閾值，以及該閾值對應的最大公因式，分解這個公因式，具有連續根的因子就是生成多項式g（x）．至此，完成識別．

綜上所述，二進制本原BCH碼的識別流程如圖1所示．

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

3 仿真驗證及分析

采用上述識別方法，分別在無誤碼和有誤碼的情況下進行實驗仿真．本文以（15，5）的二進制本原BCH碼為例．

3．1 無誤碼識別

在無誤碼的條件下，獲取一定數據量的碼流，遍歷m＝3～8，采用歐幾里德算法計算BCH碼字與循環移位m次的碼字的最大公因式，如碼字c＝［010011011100001］，向右循環移四位得c′＝［000101001101110］，通過輾轉相除的方法實現歐幾里德算法，得最大公因式d（x）＝r6（x），如圖2所示．用matlab編程實現歐幾里德算法并仿真d（x）的次數分布，得圖3和圖4分別是當m＝3和m＝4時取100組碼字進行實驗的仿真圖．由圖3和圖4比較可明顯看出當m＝3時，最大公因式的次數分布無規律性，在0，1，2，3，4，5均有分布；而m＝4時，最大公因式的次數100%在10以上，且分布在10和11的居多，有明顯的規律性，10即為次數閾值，則碼長n＝24－1＝15．截取部分最大公因式的系數矩陣如圖5所示，d（x）次數為從序列最右邊第1個1數到最左邊1所在的位置，從0開始計數．選取次數最小的最大公因式10100110111進行因式分解，取有連續根的因式，得，與題設相符，識別正確．

圖2d（x）計算Fig．2d（x）algorithm

圖3m＝3時100組最大公因式的次數分布Fig．3 Times distribution of the greatest common factors of 100 groups whenm＝3

圖4m＝4時100組最大公因式的次數分布Fig．4 Times distribution of the greatest common factors of 100 groups whenm＝4

圖5 前20組最大公因式的系數矩陣Fig．5 Top 20 coefficient matrix of the greatest common factors

圖6m＝3時10組最大公因式的次數分布Fig．6 Times distribution of the greatest common factors of 10 groups whenm＝3

圖7m＝4時10組最大公因式的次數分布Fig．7 Times distribution of the greatest common factors of 10 groups whenm＝4

取10組碼字仿真驗證，圖6和圖7分別為m＝3和m＝4時最大公因式的次數分布圖．由圖6和圖7比較，用同樣的方法分析，也可看出m＝4時最大公因式的次數分布均在10以上，取次數為10的最大公因式也可求出g（x）；而m＝3時次數在0，1，2，3，4均有分布，不滿足規律性．所以在較少的數據量時本文的識別方法也有效．

3．2 有誤碼識別

信道誤碼率分別為1×10－3和1×10－2時，取100個碼組的數據量．遍歷m＝3～8進行仿真，得m＝4時公因式的次數分布分別為圖8和圖9（m＝3，5，6，7，8略）．

由圖8可見，在誤碼率為1×10－3時最大公因式的次數98%均在10以上，且大部分分布在10和11，通過d（x）的系數矩陣取出次數為10的最大公因式，經驗證其因子有連續根，為所求生成多項式；由圖9可見，在誤碼率為1×10－2時最大公因式的次數81%均在10以上，且大部分分布在10和11，同樣的方法得到生成多項式．若取出的10次多項式不能分解出有連續根的因子，則進行多次選取，保證識別的正確率，所以在較高的誤碼率下該識別方法可達到正確識別的目的．

圖8m＝4，pe＝1×10－3時100組最大公因式的次數分布Fig．8 Times distribution of the greatest common factors of 100 groups of whenm＝4 whenpe＝1×10－3

對比無誤碼和有誤碼的識別仿真圖，根據理論分析可知，在無誤碼的條件下，當m選取正確時，移位前后所求最大公因式的次數均大于等于生成多項式的次數；當選取的m對應最大公因式次數為零時說明移位前后碼字互素，不滿足BCH碼的性質，與碼長n直接相關的參數m選取的不正確，舍棄該m值．這一結論簡化了無誤碼條件下的BCH碼的盲識別；在有誤碼時，則需根據最大公因式的次數分布規律，分析是否存在次數閾值來判斷該m值選取的正確性，若存在次數閾值，m選取正確，反之，不正確．

圖9m＝4，pe＝1×10－2時100組最大公因式的次數分布Fig．9 Times distribution of the greatest common factors of 100 groups ofmwhenpe＝1×10－2

4 結論

本文對二進制本原BCH碼參數盲識別提出了一種方法，該方法是基于歐幾里德算法，求取最大公因式系數矩陣，并分析最大公因式的次數分布規律，進而識別出本原BCH碼的碼長和生成多項式．此盲識別算法，識別原理簡單易行，避免了繁雜的矩陣運算，識別過程簡單．仿真實驗結果表明，在無誤碼時用較少的數據量就可達到識別的目的，在誤碼率為pe＝1×10－2時也具有較好的識別效果．

［1］ 薛國慶．卷積碼的盲識別研究［D］．合肥：中國科學技術大學，2009．

XUE Guoqing．Blind identification of convolutional codes［D］．Hefei：University of Science and Technology of China，2009．

［2］ 陳金杰，楊俊安．無線數傳信號編碼盲識別與解碼技術研究［J］．電子測量與儀器學報，2011，25（10）：905－910．

CHEN Jinjie，YANG Junan．Research on blind recognition for wireless digital transmission signals encoding and decoding technology［J］．Journal of Electronic Measurement and Instrument，2011，25（10）：905－910．

［3］ 昝俊軍，李艷斌．低碼率二進制線性分組碼的盲識別［J］．無線電工程，2009，39（1）：19－24．

ZAN Junjun，LI Yanbin．Blind recognition of low code rate binary linear block codes［J］．Radio Engineering，2009，39（1）：19－24．

［4］ 閆郁翰．循環碼的盲識別［J］．電子科技，2011，24（3）：112－114．

YAN Yuhan．Blind recognition method for the cyclic code［J］．Electronic Science and Technology，2011，24（3）：112－114．

［5］ 劉菁．卷積碼和循環碼識別技術研究［D］．西安：西安電子科技大學，2010．

LIU Jing．Research on recognition technology for convolutional codes and cyclic codes［D］．Xi'an：Xidian University，2010．

［6］ 聞年成，楊曉靜．采用秩統計和碼根特征的二進制循環碼盲識別方法［J］．電子信息對抗技術，2010，25（6）：26－29．

WEN Niancheng，YANG Xiaojing．Blind recognition of cyclic codes based on rank statistic and codes roots characteristic［J］．E－lectronic Information Warfare Technology，2010，25（6）：26－29．

［7］ 楊曉靜，聞年成．基于碼根信息差熵和碼根統計BCH碼識別方法［J］．探測與控制學報，2010，32（3）：69－73．

YANG Xiaojing，WEN Niancheng．Recognition method of BCH codes based on roots information dispersion entropy and roots statistic［J］．Journal of Detection，2010，32（3）：69－73．

［8］ 王新梅．糾錯碼－原理與方法［M］．西安：西安電子科技大學出版社，2002．

WANG Xinmei．Error correcting code－principles and methods［M］．Xi'an：Xidian University Press，2002．

［9］ 戚林，郝士琦，王磊，等．一種RS碼快速盲識別方法［J］．電路與系統學報，2011，16（2）：70－76．

QI Lin，HAO Shiqi，WANG Lei，et al．A fast blind recognition method of RS codes［J］．Journal of Circuits and Systems，2011，16（2）：70－76．

（責任編輯：孟素蘭）

Blind recognition of binary primitive BCH codes parameters

WANG Lan－xun，LI Dan－fang，WANG Yang
（College of Electronic and Informational Engineering，Hebei University，Baoding 071002，China）

A recognition method based on Euclidean algorithm is proposed to solve the problem of the blind recognition of BCH code．First，according to the cycle shifting code，a greatest common factor is achieved and many common factors constitute a coefficient matrix．Moreover，the times distribution of the greatest common factors were analyzed and the code length was obtained and polynomial generated by coefficient matrix．The recognition method is simple，and the fussy calculation of matrices is avoided．Both theoretical analysis and simulation results show that using fewer data can recognize effectively in no error and the recognition has better performance in BER．

BCH code；Euclidean algorithm；the greatest common factor；blind recognition

TN911．22

A

1000－1565（2012）04－0416－05

2012－01－10

河北省自然科學基金資助項目（F2009000224）

王蘭勛（1956－），男，河北安平人，河北大學副教授，主要從事數字通信與信息編碼方面研究．E－mail：wanglanxun＠yahoo．com．cn