基于平均余弦符合度下的本原BCH 碼盲識別

吳昭軍，張立民，鐘兆根，龍玉峰

（1.海軍航空大學(xué)信息融合研究所，山東 煙臺 264001；2.海軍航空大學(xué)航空基礎(chǔ)學(xué)院，山東 煙臺 264001；3.海軍航空大學(xué)310 教研室，山東 煙臺 264001）

1 引言

為了提高數(shù)字通信的可靠性，信道編碼技術(shù)廣泛應(yīng)用于現(xiàn)代通信系統(tǒng)中。BCH 碼以其嚴格的代數(shù)結(jié)構(gòu)而具有很強的糾錯能力，從而成為循環(huán)碼中一個重要的子類。BCH 碼在中短碼長條件下，其性能接近于理論值，且編碼譯碼計算復(fù)雜度低，這些優(yōu)點使其廣泛應(yīng)用于衛(wèi)星通信、微波通信以及與其他編碼方式的級聯(lián)過程中。在非合作通信領(lǐng)域，如果能夠在惡劣信道環(huán)境下，利用截獲的比特流完成BCH 碼的有效識別，則對于信源獲取、密碼協(xié)議分析具有重要的意義[1]。

目前，具有較強容錯能力的編碼識別算法主要集中于卷積碼[2-3]、Turbo 碼[4]等，而針對BCH 碼的識別，大部分算法從BCH 碼的定義以及代數(shù)結(jié)構(gòu)出發(fā)，利用比特流序列進行參數(shù)識別，其容錯性能不足。文獻[5-6]從BCH 碼定義出發(fā)，利用碼字一定含有生成多項式因子這一性質(zhì)，采用歐幾里得算法，完成BCH 碼生成多項式識別，雖然這種算法具有較低的計算復(fù)雜度，但是該算法不具有容錯性。文獻[7-8]將BCH 碼等價于特殊的線性分組碼，采用改進的高斯消元法識別BCH 碼碼長以及校驗矩陣，雖然具有一定的容錯性能，但是當碼長增加時，算法計算復(fù)雜度將急劇增加。由于BCH 碼生成多項式由擴域中某些元素的最小多項式構(gòu)成，文獻[9]直接對擴域中元素最小多項式進行校驗匹配，從而完成碼長以及生成多項式識別，但是當擴域中元素較多時，其虛警或是漏警概率會不可避免地增加，同時也不能完成本原多項式的識別。文獻[10]利用碼長為n的碼字一定能夠整除多項式xn+1 的特點，對多項式xn+1 進行因式分解，然后對因子進行校驗匹配，同時完成碼長以及生成多項式識別，該算法雖然具有較高的計算效率，但是隨著碼長的增加，因子的誤判概率會急劇增加。為了提高算法的容錯性能，文獻[11]利用隨機碼字與BCH 碼碼根概率分布不同，提出了基于碼根信息差熵（RIDE,root information difference entropy）算法，該算法在短碼情況下具有較好的識別性能，但是在中長碼情況下還有待改進。文獻[12-13]在RIDE 算法的基礎(chǔ)上，深入分析了隨機碼字與BCH 碼概率分布規(guī)律，通過設(shè)定判決門限完成碼長以及具有最大連續(xù)碼根數(shù)目的本原多項式，最終完成生成多項式的識別，該算法相比于RIDE 方法容錯性能得到了一定的提高。以上算法僅僅適用于二進制硬判決序列，這種硬判決序列不可避免地造成來自信道的信息損失。為了克服這一缺陷，文獻[14]首次利用軟判決信息建立起碼字多項式的碼根可靠性系數(shù)，同樣利用碼根分布概率分布識別出碼長、本原多項式以及生成多項式，與以往算法相比，該方法識別性能得到較大的提高，但是在采用軟判決度量過程中，算法采用了簡單的近似處理，其性能在低信噪比條件下具有較大的性能損失。從現(xiàn)有的文獻來看，目前BCH碼識別的算法還需要進一步提高在惡劣信道環(huán)境下的容錯能力。

針對現(xiàn)有算法的不足，本文提出了一種新的識別算法。該算法首先遍歷BCH 碼可能的碼長以及構(gòu)成擴域的本原多項式，當擴域中的本原元滿足校驗關(guān)系時，遍歷的碼長即為本原BCH 碼碼長；然后在該碼長下，遍歷域上所有的本原多項式，具有最大連續(xù)碼根數(shù)目的本原多項式即為域生成多項式，同時連續(xù)碼根最小多項式對應(yīng)的最小公倍式即為本原BCH 碼生成多項式。為了直接利用截獲碼元的軟判決序列，在校驗匹配過程中，引入平均余弦符合度概念，利用隨機碼字與本原BCH 碼字在平均余弦符合度下的統(tǒng)計特性差異，設(shè)定判決門限，能夠在低信噪比下快速完成碼長以及碼根的判決。仿真結(jié)果表明，與以往方法相比，本文提出的算法在低信噪比環(huán)境下的適應(yīng)能力具有較大的提升。

2 本原BCH 碼原理及其性質(zhì)

本原BCH 碼是實際工程中應(yīng)用較多的一種編碼，憑借較強的糾錯能力被廣泛應(yīng)用于數(shù)字通信系統(tǒng)中，其定義如下。

定義1[15]給定任一有限域GF(q)以及擴域GF(qm)，其中q為素數(shù)，則稱GF(q)上碼長為n的循環(huán)碼設(shè)計距離是δ的BCH 碼，其生成多項式是

其中，m≥1，lcm(·)表示取多項式的最小公倍式，φk(x)(m≤k≤m+δ-2)表示GF(qm)中元素αk的最小多項式。

當定義1 中q=2，δ=2t-1時，BCH 碼變?yōu)榇a長為2m-1、能夠糾正t個錯誤的本原BCH 碼。在實際工程中，本原BCH 碼是中短碼，其碼長范圍為7～511（即3≤m≤9）。

由本原BCH 碼定義可知，其生成多項式g(x)以GF(qm)域中連續(xù)冪次α,α2,…,α2t為根，故其碼字生成多項式也一定以這些元素為根。設(shè)截獲的本原BCH 碼碼字數(shù)目為N，第k個BCH 碼碼字多項式為

其中，n為BCH 碼碼長。

將第i個碼根代入式(2)中得到

其中，1≤i≤ 2t，1≤k≤N。

將式(3)展開，進一步得到

式(4)中涉及的加法與乘法都是在GF(2m)域中的加法與乘法，后面不再單獨說明，涉及碼元之間的運算都是在其有限域中進行。在有限域中存在定理1。

定理1[15]設(shè)f(x)是GF(q)上的一個多項式，β是GF(q)的擴域GF(qm)中的一個元素。如果β是f(x)的一個根，那么對于任意非負正整數(shù)t，是f(x)的一個根。

由式(4)以及定理1 可得本原BCH 碼校驗矩陣H為

對于本原BCH 碼的識別，需要澄清的參數(shù)包括BCH 碼碼長、域本原多項式以及生成多項式三部分。需要注意的是，在實際通信系統(tǒng)中，為了便于數(shù)據(jù)幀同步，在每一數(shù)據(jù)幀頭會添加8 位或是16 位的同步碼，所以本文并未將碼字同步作為研究重點，重點解決的則是如何直接利用來源信道的軟判決信息，完成上述參數(shù)的識別。

3 本原BCH 碼識別模型建立

3.1 基于平均余弦符合度下的BCH 碼識別

由式(4)可知，本原BCH 碼碼字與GF(2m)上元素滿足校驗關(guān)系，不妨取式(4)中校驗矩陣第i列單獨進行研究，即

其中，1≤i≤ 2t。

由于式(6)中存在GF(2m)中的元素，而參與校驗的序列存在于GF(2)域中，在2 種不同的域中，元素之間的運算并不方便，此時考慮將校驗關(guān)系等價于二元域GF(2)中，由于元素αki(1≤i≤2t,0≤k≤n-1)，在GF(2m)中可以表示為m維向量的形式，即

聯(lián)立式(6)與式(7)可知

其中，1≤i≤ 2t。

這樣式(8)就將擴域中的校驗關(guān)系統(tǒng)一于二元域中的校驗關(guān)系。當遍歷的BCH 碼碼長、域本原多項式正確時，BCH 碼字與生成多項式根一定滿足式(9)的校驗約束關(guān)系。傳統(tǒng)方法主要利用硬判決序列，通過遍歷碼長、本原多項式以及碼根，在擴域中進行校驗匹配，這種算法計算復(fù)雜度高，同時在惡劣信道環(huán)境下實用性不好。本文直接利用截獲的軟判決序列，最大可能地保留來自信道環(huán)境的信息，實現(xiàn)參數(shù)的識別。

為了利用軟判決序列度量式(8)編碼約束關(guān)系成立的可能性大小，首先引入余弦符合度[16]的概念，為了方便說明，將式(8)中校驗矩陣第i列單獨列出來討論，即

其中，1≤k≤N，1≤i≤ 2t，1≤j≤m。

設(shè)截獲到的軟判決序列為xk,0,xk,1,…,xk,n-1，對應(yīng)于發(fā)送的信息碼元序列為ck,0,ck,1,…,ck,n-1。記在截獲軟判決信息為xk,l條件下，碼元ck,l取值為1 的概率為P(ck,l|xk,l)，則余弦符合度的定義為

假設(shè)信號調(diào)制方式為BPSK，信號幅度為A，噪聲環(huán)境為方差為σ2、均值為0 的高斯白噪聲，此時定義信噪比為

當發(fā)送的碼元為ck,l，對應(yīng)于截獲軟判決為xk,l，則xk,l的條件概率密度函數(shù)為

由貝葉斯公式可知

將分母用全概率公式展開，得到

在沒有先驗信息的條件下，P(ck,l=0)=P(ck,l)=0.5，聯(lián)立式(12)～式(15)得到

將式(16)代入式(10)中，得到余弦符合度的計算方法為

其中，1≤i≤ 2t。

當參數(shù)估計正確時，所有的碼字都滿足式(8)，此時平均余弦符合度一定大于0，且信噪比越大，越接近1；當參數(shù)估計不正確時，碼字為隨機序列，編碼方程成立概率為0.5，值一定在0 附近徘徊。此時利用二者的統(tǒng)計特性不同，設(shè)置最優(yōu)的判決門限，即可完成本原BCH 碼參數(shù)的可靠識別。下一步重點研究的統(tǒng)計特性，為門限計算準備條件。

3.2 最小錯誤判決準則的門限推導(dǎo)

由3.1 節(jié)可知，利用平均余弦符合度的統(tǒng)計特性，合理設(shè)定判決門限是完成本原BCH 碼參數(shù)識別的前提條件，首先針對的統(tǒng)計特性進行研究。

記 式 (8)中矩陣 第j列 為，設(shè)其中元素等于1 的個數(shù)為wi,l，元素等于1的集合為，對應(yīng)于參與校驗的碼元為

首先，討論當參數(shù)正確時，校驗關(guān)系成立，此時參與校驗的碼元等于1 的元素個數(shù)一定為偶數(shù)，所有的可能情況為

此時，利用均值與方差的定義，對于每一種情況計算均值與方差，并進行統(tǒng)計平均，得到在校驗關(guān)系成立下的均值與方差分別為

由于式(8)中校驗列碼重wi,l(1≤i≤2t,1≤l≤m)可能不一定相等，此時同樣需要將u1,i,k,l與進行平均加權(quán)，得到

下面進一步考慮參數(shù)不正確的情況，此時參與校驗的碼元等于1 的元素個數(shù)不需要滿足為偶數(shù)的約束，奇偶隨機出現(xiàn)，所有可能的情況為

同樣，計算每一種情況的均值與方差，然后進行統(tǒng)計平均加權(quán)，得到參數(shù)不正確情況下的均值與方差分別為

考慮到校驗列碼重不等的情況，將u0,i,k,l與進行平均處理，得到

由于式(20)～式(24)的積分表達式不存在解析解，此時可直接采用數(shù)值積分方式求解，不僅能夠快速完成計算，還能達到很高的數(shù)值精度。

H0：遍歷的域中元素αi不是本原BCH 碼碼根。

H1：遍歷的域中元素αi是本原BCH 碼碼根。

設(shè)截獲的碼塊數(shù)目為N，當N較大時，由大數(shù)定律可知，在假設(shè)條件H0下，服從均值為u0,i,k、方差為的高斯分布，記u0,i=u0,i,k，則有

同理，在假設(shè)條件H1下，服從均值為u1,i,k、方差為的高斯分布，記，則

設(shè)判決門限為Λ，則虛警概率Pf與漏警概率Pa分別為

利用式(27)與式(28)計算最小錯誤判決概率為

將Pe對門限iΛ求導(dǎo)數(shù)，并令其等于0，將方程化為一元二次方程形式

其中，有

求解得到最小錯誤判決門限為

當求解出判決門限后，通過遍歷本原BCH 碼碼長、域本原生成多項式，然后判斷域中元素αi是否為碼字的碼根，從而確定出本原BCH 碼碼長、域生成多項式以及BCH 碼生成多項式。

3.3 本原BCH 碼參數(shù)識別步驟

在實際工程中，BCH 碼碼長滿足2m-1（3≤m≤ 9），此時可以遍歷m值以及m級本原多項式構(gòu)成的擴域GF(2m)，判斷域中元素α是否為碼字的碼根，從而確定出本原BCH 碼碼長；然后再次遍歷m級本原多項式構(gòu)成的擴域，確定出從α開始具有最大連續(xù)碼根的本原多項式，從而確定出域生成多項式以及碼字生成多項式，算法具體步驟如下。

步驟1將截獲的軟判決序列按照式(16)轉(zhuǎn)化為碼元的條件概率序列。

步驟2設(shè)定m初值為3，構(gòu)造碼長為2m-1的BCH 碼碼字，同時存儲m級的所有本原多項式。

步驟3遍歷步驟2 中本原多項式，利用本原多項式構(gòu)建擴域GF(2m)，利用域元素α按照式(8)構(gòu)造校驗矩陣。

步驟4計算判決門限Λ1，同時利用式(17)與式(18)計算平均余弦符合度，若≥Λ1，則識別出本原BCH 碼碼長；否則跳轉(zhuǎn)至步驟3，遍歷下一個本原多項式，直到出現(xiàn)≥Λ1，否則m=m+1，跳轉(zhuǎn)至步驟2，直到m＞9 。

步驟5再次遍歷m級本原多項式，同時構(gòu)建擴域GF(2m)，賦初值t=1，利用域中元素α2t-1，按照式(8)構(gòu)造校驗矩陣，同時計算判決門限Λ2t-1。

步驟6計算元素α2t-1下的平均余弦符合度值，若≥Λ2t-1，則t=t+1，跳轉(zhuǎn)至步驟5，直到＜Λ2t-1出現(xiàn)，此時保存該本原多項式下的最大糾錯能力為t-1，同時跳轉(zhuǎn)至步驟5，遍歷下一個本原多項式，直到遍歷完成。

步驟7輸出最大糾錯能力下的本原多項式，即為生成多項式，同時計算連續(xù)碼根的最小多項式對應(yīng)的最小公倍式，完成本原BCH 碼生成多項式識別。

從以上步驟來看，本文算法的計算復(fù)雜度主要來源于平均余弦符合度的計算。設(shè)截獲的碼塊數(shù)目為N，BCH 碼最大糾錯能力為t，則在第一次遍歷本原多項式過程中，需要進行N(2m-1)次乘法，N(2m-1)次余弦運算以及N次加法運算，為方便分析，這里將一次余弦運算等價為3 次乘法運算，故一次本原多項式遍歷需要進行4N(2m-1)次乘法以及N次加法。考慮最不利的情況，遍歷到最后一個本原多項式，則碼長識別所需要的最大計算量為次乘法以及次加法（其中φ(·) 表示歐拉函數(shù)，表示m級本原多項式個數(shù)）；對于BCH 碼生成多項式以及域生成多項式而言，在確定了碼長后，需要t次乘法以及次加法。

4 仿真驗證

4.1 平均余弦符合度統(tǒng)計特性驗證

在算法識別過程中，需要設(shè)定最小錯誤判決門限，在門限的求解過程中，需要利用2 種假設(shè)條件下的平均余弦符合度的統(tǒng)計特性，所以驗證推導(dǎo)的統(tǒng)計特性是否正確至關(guān)重要。仿真設(shè)定3 種BCH碼，具體的參數(shù)如表1 所示。

表1 統(tǒng)計特性驗證參數(shù)設(shè)定

設(shè)定信噪比范圍為-2～10 dB，步長為0.5 dB。為了盡可能地反映實際統(tǒng)計特性，仿真中生成的樣本數(shù)目為10 000 個。在假設(shè)條件H0與H1下，仿真求得的平均余弦符合度均值與方差以及理論計算得到的均值與方差如圖1 所示。

圖1 2 種假設(shè)條件下理論與仿真統(tǒng)計特性對比

從圖1 的結(jié)果來看，首先，理論值與仿真值幾乎重合，這說明在2 種假設(shè)條件下推導(dǎo)的平均余弦符合度的統(tǒng)計特性能夠反映實際的情況；其次，當碼長增加時，均值與方差曲線逐漸前移，在同一信噪比下，碼長越長，統(tǒng)計特性區(qū)分越難。本文算法在低信噪比下的統(tǒng)計特性區(qū)分度較好，在6 dB 信道環(huán)境、碼長為511 的情況下，2 種假設(shè)條件的均值仍存在明顯差異。

4.2 算法容錯性驗證

仿真1碼長對BCH 碼識別性能影響

仿真設(shè)定本原BCH 碼類型為5 種，m值分別為5、6、7、8、9，每種編碼的糾錯能力都為2，具體的編碼參數(shù)如表2 所示。

表2 碼長對容錯性影響仿真參數(shù)設(shè)定

仿真中設(shè)定的信噪比范圍為-2～7 dB，步長為0.25 dB，蒙特卡洛仿真次數(shù)為1 000 次，記錄不同信噪比下本原BCH 碼碼長以及生成多項式正確識別率，如圖2 所示，其中L表示碼長。

從圖2 結(jié)果來看，碼長對于本原BCH 碼識別具有較大的影響，隨著碼長的增加，算法識別性能會變差，主要原因在于隨著碼長的增加，在2 種假設(shè)條件下平均余弦符合度統(tǒng)計特性差距會縮小，此時會造成較大的虛警概率，使算法性能惡化；從識別的效果來看，算法對于碼長的識別性能要遠遠好于生成多項式的識別。從1 000 次的蒙特卡洛統(tǒng)計結(jié)果來看，在信噪比不小于5 dB 條件下，目前常用的本原BCH 碼正確識別率能夠達到95%以上，故能滿足絕大多數(shù)實際情況下的性能需求。

仿真2碼塊數(shù)目對于算法影響

圖2 不同碼長對BCH 碼識別的影響

仿真設(shè)定本原BCH 碼為碼長為127，域GF(27)本原多項式為x7+x+1，BCH 碼生成多項式為x14+x12+x10+x6+x5+x4+x3+x2+1，其糾錯能力為2，設(shè)定截獲的碼塊數(shù)目為500、1 000、1 500、2 000、2 500，設(shè)定的信噪比范圍為-1～4 dB，步長為0.25 dB，蒙特卡洛仿真次數(shù)為1 000，統(tǒng)計在不同信噪比環(huán)境下，碼長與生成多項式正確識別率，結(jié)果如圖3所示。

從圖3 的結(jié)果來看，通過增加截獲的碼塊數(shù)目，可以顯著提高算法對于參數(shù)的正確識別率，當實際碼長較長時，可以通過增加碼塊數(shù)目來克服由于碼長造成的算法下降的缺陷。同時，從蒙特卡洛統(tǒng)計結(jié)果來看，本文算法具有較好的低信噪比適應(yīng)性，在截獲碼塊為500、信噪比為3 dB 的情況下，碼長與生成多項式的正確識別率達到90%以上，能夠滿足實際工程需要。

仿真3碼率對算法影響

仿真參數(shù)設(shè)定本原BCH 碼碼長為127，域GF(27)本原多項式為x7+x+1，碼率類型總共5 種，具體為 BCH(127,120)、BCH(127,113)、BCH(127,106)、BCH(127,99)、BCH(127,92)，對應(yīng)于糾錯能力分別為1、2、3、4、5，連續(xù)碼根起點從α開始，設(shè)定截獲碼塊數(shù)目為1 000，仿真中設(shè)定信噪比范圍-1～4 dB，步長為0.25 dB，蒙特卡洛仿真次數(shù)為1 000，得到在設(shè)定的信噪比范圍內(nèi)的碼長與生成多項式正確識別率曲線如圖4 所示。

圖3 碼塊數(shù)目對BCH 碼識別的影響

從圖4 結(jié)果來看，碼率對于碼長識別的影響幾乎可以忽略不計，因為在碼長識別過程中，主要考察的是域中元素α的校驗關(guān)系是否成立；而對于生成多項式的識別而言，算法性能隨著碼率的減小而逐漸變差，原因在于碼率越小，糾錯能力越強，此時需要遍歷的連續(xù)碼根數(shù)目必然增加，相應(yīng)的誤判概率也會增加。從識別率來看，當碼率下降后，算法的正確識別率變化緩慢，說明算法對于碼率具有較強的穩(wěn)健性。

4.3 與其他算法對比

圖4 碼率對算法性能的影響

與本文算法進行對比的是目前具有一定容錯性的4 種方法，分別是軟判決與硬判決相結(jié)合（SDBR,soft decision BCH recognition）的識別算法[14]（以下簡稱SDBR 算法）、基于BCH 碼碼根分布的RIDE 識別算法[11]（以下簡稱RIDE 算法）、改進RIDE 算法[12]以及文獻[10]基于多項式因子匹配識別算法（以下簡稱文獻[10]算法）。設(shè)定本原BCH碼為BCH(63,51)，截獲碼塊數(shù)目為300，統(tǒng)計各個算法在不同信噪比下BCH 碼生成多項式識別概率，結(jié)果如圖5 所示。

從圖5 中5 種算法的識別性能對比來看，本文算法性能要明顯好于其他4 種算法。與SDBR 算法相比，性能提升約0.5 dB；與改進RIDE 算法、RIDE 算法以及文獻[10]算法相比，性能分別提升約1 dB、2.5 dB 以及3.5 dB。本文算法能夠取得性能的提升，主要原因在于采用了平均余弦符合度來衡量校驗關(guān)系成立可靠性大小，沒有造成碼元信息的丟失；相反，其他4 種算法在進行參數(shù)識別過程中采用了硬判決序列或是在進行運算過程中進行了簡單的近似替代，不可避免地造成碼元可靠性信息損失。

圖5 5 種算法性能對比

5 結(jié)束語

本文從本原BCH 碼定義出發(fā)，將域GF(2m)中的校驗關(guān)系等價轉(zhuǎn)化為二元域中的校驗關(guān)系；然后引入了能夠很好地度量校驗約束關(guān)系的平均余弦符合度的概念，基于平均余弦符合度以及最小錯誤判決準則，實現(xiàn)在低信噪比下BCH 碼碼根的快速檢測，從而完成BCH 碼參數(shù)的識別。從仿真結(jié)果來看，在2 種假設(shè)條件下推導(dǎo)的平均余弦符合度統(tǒng)計特性與實際情況相符。與其他算法相比，本文算法識別性能提升比較明顯，其工程實用性更強。