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

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

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

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

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

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

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

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

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

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

1 BCH碼的定義及分析

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

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

(1)

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

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

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

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

(2)

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

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

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

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

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

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

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

2.1 碼長的識(shí)別方法

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

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

(3)

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

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

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

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

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

2.2 起始點(diǎn)的識(shí)別方法

(4)

起始點(diǎn)的識(shí)別步驟如下：

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

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

2.3 生成矩陣的識(shí)別方法

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

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

(5)

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

3.1 碼長識(shí)別驗(yàn)證

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

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

圖2 碼長識(shí)別仿真圖

3.2 起始點(diǎn)識(shí)別驗(yàn)證

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

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

圖3 碼字起始點(diǎn)識(shí)別仿真圖

4 生成矩陣求解及驗(yàn)證

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

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

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

5 性能分析

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

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

5.2 算法容錯(cuò)性分析比較

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

圖6 碼長識(shí)別概率曲線圖

圖7 起始點(diǎn)識(shí)別概率曲線圖

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

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

圖9 不同算法的90%識(shí)別起始點(diǎn)誤碼率上限

6 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

責(zé)任編輯：時(shí) 雯

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é)基金項(xiàng)目(F2014201168)

TN911.22

A

10.16280/j.videoe.2015.17.010

2015-07-10

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