本原BCH碼參數(shù)的盲識別方法

王蘭勛，熊政達(dá)，孫旭麗

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

本原BCH碼參數(shù)的盲識別方法

王蘭勛，熊政達(dá)，孫旭麗

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

針對本原BCH碼編碼參數(shù)的盲識別，首先，根據(jù)循環(huán)移位前后碼字的最大公約式的階數(shù)，利用實際序列與隨機序列階數(shù)概率分布差異最大的特性，提出一種基于變異系數(shù)識別碼長的方法。在此基礎(chǔ)上，根據(jù)碼字之間的線性約束關(guān)系，以階數(shù)概率最大值為下限，通過計算概率總和來識別起始點，進(jìn)而，計算鄰域半徑快速去除含錯碼字，根據(jù)階數(shù)分布最大值識別生成多項式，實現(xiàn)了BCH碼的盲識別。理論分析及仿真實驗表明，該算法簡單易行，在誤碼率為0.01的條件下識別效果較好，容錯性較強。

BCH碼；盲識別；階數(shù)概率分布；生成多項式

在數(shù)字通信系統(tǒng)中，為抗擊傳輸中噪聲的干擾，通常在信息序列中增加冗余碼元，以提高數(shù)據(jù)傳輸?shù)目煽啃?。而對于信息截獲方，為獲取更多信息，需要對截獲數(shù)據(jù)的編碼體制和參數(shù)進(jìn)行識別。因此，信道編碼技術(shù)[1]和信道編碼盲識別技術(shù)[2]在通信工程領(lǐng)域具有重要的應(yīng)用價值[3]。

目前，據(jù)現(xiàn)在公開發(fā)表的文獻(xiàn)可知，大部分主要集中在卷積碼的盲識別上，較少研究循環(huán)碼。文獻(xiàn)[4]根據(jù)比特率檢測法識別碼長和起始點，文獻(xiàn)[5]根據(jù)碼重分布概率方差識別碼長，計算碼多項式的公約式求解生成矩陣，二者均對低碼率的分組碼識別效果較好；文獻(xiàn)[6]根據(jù)矩陣秩信息熵識別碼長及碼重信息熵識別起始點，但需多次構(gòu)造矩陣，文獻(xiàn)[7]根據(jù)對偶碼字的統(tǒng)計特性，并判斷對偶空間歸一化維數(shù)的最大值識別碼長和起始點，但迭代次數(shù)較多，二者均運算時間較長且計算量較大；文獻(xiàn)[8]根據(jù)歐幾里德算法得到最大公因式，完成對碼長及生成多項式的識別，文獻(xiàn)[9]根據(jù)概率逼近的算法，利用概率門限，在不同的域間搜索并識別碼長，利用根的連續(xù)性及共軛根系的性質(zhì)，識別生成多項式，二者容錯性較好，但起始點已知；文獻(xiàn)[10]根據(jù)最大公約式指數(shù)的相關(guān)性估計碼長，并利用傅里葉變換實現(xiàn)生成多項式的識別，雖無復(fù)雜計算，但GFFT是有限域上的矩陣運算，隨碼長和數(shù)據(jù)量的增加，運算量會急劇增加。

上述的識別算法，計算量大、容錯性一般或起始點已知，針對這些不足，本文根據(jù)最大公約式階數(shù)概率分布的差異對BCH碼編碼參數(shù)進(jìn)行識別，理論分析并與其他算法進(jìn)行比較，仿真結(jié)果表明，本算法復(fù)雜度低，計算量小，在高誤碼率為0.01時能夠識別碼長和起始點，且效果明顯。

1 BCH碼的定義及分析

定義1[11]：給定任一有限域GF(q)及其擴域GF(qm)，其中q是素數(shù)或素數(shù)的冪，m為某一正整數(shù)。若碼元取自GF(q) 上的一循環(huán)碼，它的生成多項式g(x)的根集合R中含有以下δ-1個連續(xù)根時，則由g(x)生成的循環(huán)碼稱為q進(jìn)制BCH碼。

R?{am0,am0+1,…,am0+δ-2}

(1)

當(dāng)q=2且n=2m-1時，稱這類碼為二進(jìn)制本原BCH碼。

定義2[11]：若(f(x),g(x),…,k(x))是同時除盡多項式f(x),g(x),…,k(x)的次數(shù)最高的首一多項式，則稱(f(x),g(x),…,k(x))是f(x),g(x),…k(x)的最大公約式。

定義3[11]：BCH碼是糾正多個隨機錯誤的循環(huán)碼，且碼字多項式c(x)應(yīng)當(dāng)滿足如下等式

c(x)=m(x)g(x)

(2)

式中：g(x)稱為生成多項式，可表示為：g(x)=xn-k+gn-k-1·xn-k-1+…+g1x+g0，即c(x)是g(x)的倍式，因此，g(x)是BCH碼中次數(shù)最低的多項式。

輾轉(zhuǎn)相除法[12]：求二元域上兩個多項式的最大公約式，其所有計算均為模二和運算，具體步驟如下：

1)任取一接收的碼字為C，將其作為被除式寫在第一行，并將碼字C循環(huán)移動m位后得到新的碼字為C1，將其作為除式寫在第二行，兩行均左端對齊且首位若為0，可省去不寫。

2)被除式與除式進(jìn)行相加，得到余式序列。

3)余式序列作為被除式，上一步中被除式作為除式，按照上述原則，進(jìn)行相加，再次得余式序列。

4)反復(fù)進(jìn)行第3步，直到余式序列全為0，則此時的被除式序列即為所求的最大公約式。

2 BCH碼的參數(shù)估計

2.1 碼長的識別方法

由上述定義可知，BCH碼的碼字與其m次循環(huán)移位后得到的碼字必定含有一個最大公約式，當(dāng)碼長選取不正確時，碼字類似為隨機序列，則根據(jù)實際序列與隨機序列最大公約式階數(shù)概率分布間的差異，利用變異系數(shù)識別碼長。

變異系數(shù)，簡稱CV，反映了相對波動的大小，通過變異系數(shù)的差值更能準(zhǔn)確衡量出兩個向量的差異程度，當(dāng)變異系數(shù)差值越大，實際序列與隨機序列相對波動越明顯，當(dāng)最大時，此時的碼長即為真實碼長，計算過程如下

(3)

假設(shè)接收序列長度為R，碼長的識別步驟如下：

1)初始化估計的有限域指數(shù)為m，范圍為3≤m≤8，即從m=3依次進(jìn)行遍歷，則碼長為n=2m-1。

4)根據(jù)式(3)計算ΔCV的值。

5)m=m+1，轉(zhuǎn)到步驟1)，計算不同域值m對應(yīng)的變異系數(shù)的差值ΔCV。

6)計算完成后，找出ΔCV最大值，即域值m對應(yīng)的碼長估計值n即為真實碼長。

2.2 起始點的識別方法

(4)

起始點的識別步驟如下：

2)同上述碼長識別步驟3)計算方法相同，得到測試序列階數(shù)的概率分布后，找到概率最大值并以此為下限，逐次相加，直到次數(shù)為n-1時的概率，利用式(4)計算概率和的值；

3)q=q+1，轉(zhuǎn)到步驟1)繼續(xù)執(zhí)行，直到q=n+1，比較上述計算的結(jié)果，找出概率和的最大值，為準(zhǔn)確地看出q值的位置，編程時保留最大值，令其他值為0，則該值對應(yīng)的位置即為碼字起始點。

2.3 生成矩陣的識別方法

在識別出碼長和起始點的基礎(chǔ)上，為達(dá)到無誤碼字最大化，提高碼字的識別效率，應(yīng)快速剔除含錯碼字。取1 000組碼字得到(15，5)BCH碼在不同誤碼率下最大公約式階數(shù)的概率分布曲線圖，如圖1所示。

圖1 不同誤碼率下階數(shù)概率分布曲線圖

(5)

3 仿真驗證與結(jié)果分析

3.1 碼長識別驗證

為了驗證識別方法的正確性和適用性，選取誤碼率Pe=0.02的(15，5)和Pe=0.01的(63，16)兩種低碼率BCH碼以及Pe=0.02的(31，26)和Pe=0.01的(127，106)兩種高碼率BCH碼，碼組個數(shù)為103，運用MATLAB進(jìn)行試驗仿真，結(jié)果如圖2 所示。

由圖2可知，根據(jù)碼組內(nèi)具有完整的線性約束關(guān)系，碼字循環(huán)移位后，實際序列與隨機序列最大公約式階數(shù)分布的概率相差較大，所以，遍歷有限域值m對應(yīng)的值ΔCV取最大時，此時m值對應(yīng)的碼長即為真實碼長n。相反，當(dāng)不是真實值時，實際序列的最大公約式階數(shù)概率分布接近于隨機序列，所以，ΔCV變化相對平穩(wěn)。經(jīng)仿真分析可知，該方法在一定的誤碼率條件下，不僅適用于低碼率的碼字，而且對高碼率的碼字也同樣適用，且識別效果明顯，容錯性較好。

圖2 碼長識別仿真圖

3.2 起始點識別驗證

為驗證起始點識別方法的正確性，選取誤碼率在Pe=0.06下(15，11)和Pe=0.02下(31，26)兩種高碼率的BCH碼以及Pe=0.005下(127，50)低碼率的BCH碼，碼組個數(shù)為103，運用MATLAB進(jìn)行試驗仿真，結(jié)果如圖3所示。

由圖3可知，在識別出碼長的基礎(chǔ)上，根據(jù)碼字之間線性約束關(guān)系較強的特性，對3種不同碼率的碼字在一定的誤碼率下進(jìn)行起始點識別。由圖可知，依次對起始點進(jìn)行遍歷，統(tǒng)計最大公約式階數(shù)的概率和，最大值分別出現(xiàn)在6、8、12，則該點即為起始點?？梢?，該方法對不同碼長且碼率不同的碼字進(jìn)行識別，容錯性較好，識別效果較明顯。

圖3 碼字起始點識別仿真圖

4 生成矩陣求解及驗證

圖4 (15，5)BCH碼階數(shù)分布仿真圖

經(jīng)圖4可知，當(dāng)最大公約式次數(shù)為第10階時，出現(xiàn)次數(shù)最多，根據(jù)定義3可知，g(x)是BCH碼中次數(shù)最低的多項式，因此，選取該階數(shù)對應(yīng)的碼字(循環(huán)移位前的接收碼字)，全零碼進(jìn)行剔除，找出碼字中出現(xiàn)次數(shù)最低的多項式，該多項式即為生成多項式。截取部分多項式的仿真結(jié)果如圖5所示，由圖可以看出，次數(shù)最小的多項式即為生成多項式：g(x)=x10+x8+x5+x4+x2+x+1，即可完成識別。可見，該算法相對于文獻(xiàn)[8]，利用鄰域半徑δ，提高了正確碼字的利用率，使其所需的數(shù)據(jù)量大大減小，計算量減小。

圖5 (15，5)BCH碼部分多項式仿真圖(截圖)

5 性能分析

5.1 算法復(fù)雜度分析比較

文獻(xiàn)[13]基于碼根信息差熵和碼根統(tǒng)計來識別BCH碼，在識別出碼長的條件下，需遍歷本原多項式，且碼長越長，其本原多項式的個數(shù)越多，算法的復(fù)雜度也就越高，其復(fù)雜度為O(n3)；文獻(xiàn)[14]對m行n列的矩陣進(jìn)行對角化，需進(jìn)行m(m-1)/2 行和n(n-1)/2次列模二運算；文獻(xiàn)[15]相對于文獻(xiàn)[14]而言，可減少一半的計算量，只需進(jìn)行n(n-1)/2次列模二運算，該算法的復(fù)雜度為O(n2)；文獻(xiàn)[16]基于稀疏沃爾什譜并利用Walsh-Hadamard變換進(jìn)行識別，對于碼長為n，信息位為k的BCH碼，計算量主要為n(n-k)/2，則該算法的復(fù)雜度主要為O(n2)；而本文基于輾轉(zhuǎn)相除法，主要的復(fù)雜度僅為O(n)，可見，該算法的計算復(fù)雜度優(yōu)于上述文獻(xiàn)。

5.2 算法容錯性分析比較

在誤碼率取值不同的條件下，選取103組不同參數(shù)的碼字進(jìn)行500次蒙特卡洛仿真實驗，得出碼長和起始點識別率，如圖6～圖7所示。在誤碼率為0.02時，碼長n≤31的碼字識別效果高達(dá)90%；在誤碼率為0.006時，碼長31≤n≤127的碼字識別效果高達(dá)90%；而在起始點的識別上，在誤碼率為0.1時，(15，11)識別效果略高于(7，4)碼?？傻茫S著碼長與碼率的增加，碼字之間的線性約束關(guān)系降低，導(dǎo)致識別概率逐漸減?。煌瑫r，該算法在碼長和碼率不同的條件下，能有效識別碼長和起始點，容錯性較好。

圖6 碼長識別概率曲線圖

圖7 起始點識別概率曲線圖

BCH碼也是一種線性分組碼，選取數(shù)目種類相同的碼字，對文獻(xiàn)[5-6，15]和本文提出的碼長識別算法進(jìn)行比較，圖8為不同算法的90%識別碼長誤碼率上限[17]曲線圖，以碼長7為例，本文的誤碼率為12%，文獻(xiàn)[5]的誤碼率為9%，文獻(xiàn)[15]的誤碼率為5%，文獻(xiàn)[6]的誤碼率為3%，仿真結(jié)果表明，在碼長取值相同的條件下，本文識別算法抗誤碼的能力較強，容錯性較好；同樣，選取上述同樣的碼字，對文獻(xiàn)[6，15]和本文提出的起始點識別算法進(jìn)行比較，由圖9可以看出，除碼長為7的碼字外，本文算法的抗誤碼能力優(yōu)于文獻(xiàn)[6，15]。

圖8 不同算法的90%識別碼長誤碼率上限

圖9 不同算法的90%識別起始點誤碼率上限

6 結(jié)論

本文依據(jù)碼字之間的線性約束關(guān)系及實際序列與隨機序列最大公約式階數(shù)概率分布的差異性，利用變異系數(shù)的差值識別碼長并由概率和準(zhǔn)確識別出起始點，在此基礎(chǔ)上，通過設(shè)置鄰域半徑剔除含錯碼字，利用階數(shù)分布最大值完成對生成多項式的識別，進(jìn)而實現(xiàn)了BCH碼參數(shù)的盲識別。最后，在不同的誤碼率下，對不同碼率的碼字進(jìn)行了大量的仿真實驗，并與其他算法進(jìn)行比較，結(jié)果表明，該算法復(fù)雜度低，不僅針對低碼率的碼字，還可以對高碼率的碼字進(jìn)行識別，且在誤碼率為0.01時識別效果較明顯，容錯性能較好。

[1] 解輝，黃知濤，王豐華.信道編碼盲識別技術(shù)研究進(jìn)展[J].電子學(xué)報，2013，41(6)：1166-1176.

[2] 閆郁翰.信道編碼盲識別技術(shù)研究[D].西安：西安電子科技大學(xué)，2012.

[3] 張永光，樓才義.信道編碼及其識別分析[M].北京：電子工業(yè)出版社，2010.

[4] 陳金杰，楊俊安.一種對線性分組碼編碼參數(shù)的盲識別方法[J].電路與系統(tǒng)學(xué)報，2013，18(2)：248-254.

[5] 鄧瑞瑞，汪立新.基于碼重分布概率方差的循環(huán)碼識別方法[J].太赫茲科學(xué)與電子信息學(xué)報，2013，11(5)：792-796.

[6] 陳金杰，計時鐘，楊俊安.高誤碼條件下線性分組碼的盲識別[J].應(yīng)用科學(xué)學(xué)報，2013，31(5)：459-467.

[7] 楊曉煒，甘露.基于Walsh-Hadamard變換的線性分組碼參數(shù)盲估計算法[J].電子與信息學(xué)報，2012，34(7)：1643-1646.

[8] 王蘭勛，李丹芳，汪洋.二進(jìn)制本原BCH碼的參數(shù)盲識別[J].河北大學(xué)學(xué)報，2012，32(4)：416-420.

[9] 闊永紅，曾偉濤，陳健.基于概率逼近的本原BCH碼編碼參數(shù)的盲識別方法[J].電子與信息學(xué)報，2014，36(2)：332-339.

[10] 戚林，郝士琦，王磊，等.一種RS碼快速盲識別方法[J].電路與系統(tǒng)學(xué)報，2011，16(2)：71-76.

[11] 王新梅，肖國鎮(zhèn).糾錯碼——原理與方法[M].修訂版.西安：西安電子科技大學(xué)出版社，2001.

[12] 杜宇峰，裴昌幸.信道編碼分析識別技術(shù)研究[D].西安：西安電子科技大學(xué)，2012.

[13] 楊曉靜，聞年成.基于碼根信息差熵和碼根統(tǒng)計的BCH碼識別方法[J].探測與控制學(xué)報，2010，32(3)：69-73.

[14] 張永光，樓才義，王挺.一種線性分組碼編碼參數(shù)的盲識別方法：中國，201010131103.3[P].2010-10-13.

[15] 朱聯(lián)祥，李荔.改進(jìn)的二進(jìn)制循環(huán)碼盲識別方法[J].計算機應(yīng)用，2013，33(10)：2762-2764.

[16] 解輝，宋陽，王豐華，等.基于稀疏沃爾什譜的BCH碼檢測識別方法[J].中國電子科學(xué)研究院學(xué)報，2013，8(2)：156-160.

[17] 王平，曾偉濤，陳健，等.一種利用本原元的快速RS碼盲識別算法[J].西安電子科技大學(xué)學(xué)報，2013，40(1)：105-110.

王蘭勛(1956— )，教授，主要從事數(shù)字通信與信息編碼方面研究；

熊政達(dá)(1989— )，女，碩士生，主研信道編碼盲識別；

孫旭麗(1990— )，女，碩士生，主研信道編碼識別的硬件實現(xiàn)。

責(zé)任編輯：時 雯

Blind Recognition Method of Primitive BCH Codes Parameters

WANG Lanxun，XIONG Zhengda，SUN Xuli

(CollegeofElectronicandInformationalEngineering，HebeiUniversity，HebeiBaoding071002，China)

In order to solve the problem of the blind recognition of primitive BCH code parameters， the code length are identified by the recognition method based on the coefficient of variation that is proposed by the most notable differences whose order of the largest common divisor probability distribution between the actual sequence and random sequence，by computing the order between the code word and its circular shift code word.On this basis， according to the linear constraint relationship between the code word，the starting point are identified by calculating the sum of all probability with the lower limit of maximum probability.The generator matrix is solved through the method of calculating the radius of neighbourhood to remove wrong words quickly and then getting the maximum of the order distribution，the blind recognition of primitive BCH codes is finally realized.The recognition method is simple，theoretical analysis and simulation results show that the method has better error-tolerance and the recognition has better performance in 0.01BER.

primitive BCH code；blind recognition； the greatest common divisor； generator matrix

河北省自然科學(xué)基金項目(F2014201168)

TN911.22

A

10.16280/j.videoe.2015.17.010

2015-07-10

【本文獻(xiàn)信息】王蘭勛，熊政達(dá)，孫旭麗.本原BCH碼參數(shù)的盲識別方法[J].電視技術(shù),2015，39(17).