二進(jìn)制本原BCH碼的參數(shù)盲識(shí)別

王蘭勛，李丹芳，汪洋

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

二進(jìn)制本原BCH碼的參數(shù)盲識(shí)別

王蘭勛，李丹芳，汪洋

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

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

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

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

本文針對(duì)本原BCH碼的特殊性質(zhì)，結(jié)合歐幾里德算法，提出一種新的識(shí)別方法．該方法識(shí)別原理簡(jiǎn)單，并具有較好的容錯(cuò)性，經(jīng)實(shí)驗(yàn)驗(yàn)證在無(wú)誤碼較少的數(shù)據(jù)量時(shí)可達(dá)到識(shí)別的目的，有誤碼數(shù)據(jù)量足夠時(shí)，仍有較好的識(shí)別效果．

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

定義1［8］給定任一有限域GF（q）及其擴(kuò)域GF（qm），其中q是素?cái)?shù)或素?cái)?shù)的冪，m為某一正整數(shù)．若碼元取自GF（q）上的一個(gè)循環(huán)碼，它的生成多項(xiàng)式g（x）的根集合R中含有以下δ－1個(gè)連續(xù)根：

時(shí)，即則由g（x）生成的循環(huán)碼稱為q進(jìn)制BCH碼．通常取m0＝1，如果生成多項(xiàng)式g（x）的根中，有一個(gè)GF（2m）中的本原域元素，則n＝qm－1，當(dāng)q＝2時(shí)，稱這種碼長(zhǎng)n＝2m－1的BCH碼為二進(jìn)制本原BCH碼．

二進(jìn)制本原BCH碼具有的性質(zhì)：

1）循環(huán)性．循環(huán)性是指任一碼組循環(huán)移位以后，仍為該碼中的一個(gè)碼組．

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

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

如何找到d（x）是本文研究的重點(diǎn)．

定理1 設(shè)c（x）和c′（x）是二元域上的2個(gè)多項(xiàng)式，則有唯一的一對(duì)二元域上的多項(xiàng)式q（x）和r（x），具有下面的性質(zhì)：

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

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

該算法說(shuō)明了找出（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．因?yàn)橐陨隙囗?xiàng)式均是二元域上的多項(xiàng)式，所以式中的運(yùn)算均為模二運(yùn)算．BCH碼多項(xiàng)式的歐幾里德算法可以用輾轉(zhuǎn)相除的方法來(lái)實(shí)現(xiàn)［9］．

當(dāng)截獲碼流后，根據(jù)幀同步的信息很容易確定BCH碼的起始點(diǎn)，所以本文的識(shí)別研究是在起始點(diǎn)已知的條件下進(jìn)行的，這也是符合實(shí)際情況的．

2 識(shí)別方法

本文提出的識(shí)別方法是利用歐幾里德算法計(jì)算循環(huán)移位前后2個(gè)碼字多項(xiàng)式的最大公因式d（x）．因?yàn)檠h(huán)碼的每個(gè)碼字均是生成多項(xiàng)式的倍式，所以它們的最大公因式是生成多項(xiàng)式或生成多項(xiàng)式的倍式，由仿真實(shí)驗(yàn)分析得出碼長(zhǎng)n和生成多項(xiàng)式g（x）．下面對(duì)該方法進(jìn)行詳細(xì)描述．

2．1 數(shù)學(xué)公式描述

BCH碼的編碼數(shù)學(xué)模型為

其中c（x）為碼字多項(xiàng)式，m（x）為信息多項(xiàng)式，g（x）為生成多項(xiàng)式．實(shí)際應(yīng)用中，c（x）為接收或截獲的碼流，在不知道任何編碼參數(shù)的情況下通過(guò)識(shí)別方法獲得g（x），進(jìn)而得到該碼流攜帶的信息m（x）．

2．2 基于歐幾里德算法的識(shí)別原理

因任一BCH碼多項(xiàng)式c（x）都是g（x）的倍式，所以同一碼組中2個(gè)BCH碼多項(xiàng)式的最大公因式不是g（x）就是g（x）的倍式．而若假設(shè)c（x）是BCH碼的一個(gè)碼組，所以c（x）循環(huán)移位m次的結(jié)果c′（x）也必為該碼中的一個(gè)碼組．根據(jù)這一性質(zhì)結(jié)合歐幾里德算法計(jì)算出最大公因式d（x），進(jìn)而通過(guò)數(shù)據(jù)分析得到g（x）．

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

綜上所述，二進(jìn)制本原BCH碼的識(shí)別流程如圖1所示．

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

3 仿真驗(yàn)證及分析

采用上述識(shí)別方法，分別在無(wú)誤碼和有誤碼的情況下進(jìn)行實(shí)驗(yàn)仿真．本文以（15，5）的二進(jìn)制本原BCH碼為例．

3．1 無(wú)誤碼識(shí)別

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

圖2d（x）計(jì)算Fig．2d（x）algorithm

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

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

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

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

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

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

3．2 有誤碼識(shí)別

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

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

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

對(duì)比無(wú)誤碼和有誤碼的識(shí)別仿真圖，根據(jù)理論分析可知，在無(wú)誤碼的條件下，當(dāng)m選取正確時(shí)，移位前后所求最大公因式的次數(shù)均大于等于生成多項(xiàng)式的次數(shù)；當(dāng)選取的m對(duì)應(yīng)最大公因式次數(shù)為零時(shí)說(shuō)明移位前后碼字互素，不滿足BCH碼的性質(zhì)，與碼長(zhǎng)n直接相關(guān)的參數(shù)m選取的不正確，舍棄該m值．這一結(jié)論簡(jiǎn)化了無(wú)誤碼條件下的BCH碼的盲識(shí)別；在有誤碼時(shí)，則需根據(jù)最大公因式的次數(shù)分布規(guī)律，分析是否存在次數(shù)閾值來(lái)判斷該m值選取的正確性，若存在次數(shù)閾值，m選取正確，反之，不正確．

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

4 結(jié)論

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

［1］ 薛國(guó)慶．卷積碼的盲識(shí)別研究［D］．合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2009．

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

［2］ 陳金杰，楊俊安．無(wú)線數(shù)傳信號(hào)編碼盲識(shí)別與解碼技術(shù)研究［J］．電子測(cè)量與儀器學(xué)報(bào)，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ìn)制線性分組碼的盲識(shí)別［J］．無(wú)線電工程，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］ 閆郁翰．循環(huán)碼的盲識(shí)別［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］ 劉菁．卷積碼和循環(huán)碼識(shí)別技術(shù)研究［D］．西安：西安電子科技大學(xué)，2010．

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

［6］ 聞年成，楊曉靜．采用秩統(tǒng)計(jì)和碼根特征的二進(jìn)制循環(huán)碼盲識(shí)別方法［J］．電子信息對(duì)抗技術(shù)，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］ 楊曉靜，聞年成．基于碼根信息差熵和碼根統(tǒng)計(jì)BCH碼識(shí)別方法［J］．探測(cè)與控制學(xué)報(bào)，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］ 王新梅．糾錯(cuò)碼－原理與方法［M］．西安：西安電子科技大學(xué)出版社，2002．

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

［9］ 戚林，郝士琦，王磊，等．一種RS碼快速盲識(shí)別方法［J］．電路與系統(tǒng)學(xué)報(bào)，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．

（責(zé)任編輯：孟素蘭）

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

河北省自然科學(xué)基金資助項(xiàng)目（F2009000224）

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