基于稀疏沃爾什譜的BCH碼檢測(cè)識(shí)別方法

解 輝，宋 陽(yáng)，王豐華，劉曉光

(1.國(guó)防科技大學(xué)電子科學(xué)與工程學(xué)院，湖南長(zhǎng)沙 410073;2.解放軍63893部隊(duì)，河南洛陽(yáng) 471003)

0 引言

隨著現(xiàn)代通信系統(tǒng)中越來(lái)越多的采用信道編碼技術(shù)實(shí)現(xiàn)系統(tǒng)快速穩(wěn)定通信，信道編碼的盲識(shí)別日益成為信息截獲、信息對(duì)抗及通信協(xié)議分析等領(lǐng)域的熱點(diǎn)問(wèn)題［1～12］。

BCH碼是能夠糾正多個(gè)隨機(jī)錯(cuò)誤的二進(jìn)制循環(huán)線性分組碼，具有較強(qiáng)的糾錯(cuò)能力和嚴(yán)格的代數(shù)結(jié)構(gòu)，同時(shí)具有構(gòu)造方便、編碼簡(jiǎn)單的優(yōu)點(diǎn)［13］，已經(jīng)廣泛應(yīng)用于現(xiàn)代數(shù)字通信系統(tǒng)中。對(duì)于BCH碼的盲識(shí)別，目前主要有 Valembois 算法［10，11］、迭代譯碼算法［12］、基于碼重分布［14］、基于歐幾里得算法［15］和基于碼根信息差熵和碼根統(tǒng)計(jì)［16］的識(shí)別方法。Valembois［10］利用最大似然求解碼字對(duì)偶碼的方法，實(shí)現(xiàn)二進(jìn)制線性分組碼的盲識(shí)別，但該方法的不足之處在于計(jì)算量較大［17］。Cluzeau［12］利用 Gallager迭代算法實(shí)現(xiàn)了碼字對(duì)偶碼的快速求解，但同樣要求碼字具有較低的碼重。文獻(xiàn)［14］利用碼重量分布估計(jì)碼長(zhǎng)，進(jìn)而通過(guò)改進(jìn)傳統(tǒng)的矩陣化簡(jiǎn)方法獲得生成矩陣，算法適應(yīng)范圍局限于低碼率分組碼，限制了算法的實(shí)際應(yīng)用范圍。算法［15］假定碼長(zhǎng)已知或碼長(zhǎng)未知而幀長(zhǎng)度已知，采用歐幾里得算法，雖然算法計(jì)算量小，但該方法誤碼適應(yīng)能力較弱，實(shí)用性不強(qiáng)。文獻(xiàn)［16］利用碼根信息差熵函數(shù)識(shí)別BCH碼的碼長(zhǎng)，進(jìn)而利用碼根統(tǒng)計(jì)獲取生成多項(xiàng)式的整數(shù)根，通過(guò)遍歷該域中的本原多項(xiàng)式以尋求滿足BCH碼生成多項(xiàng)式根性質(zhì)的碼根和本原多項(xiàng)式，從而實(shí)現(xiàn)BCH碼的盲識(shí)別。算法需要遍歷BCH碼本原域，且求解碼根計(jì)算量較大。

實(shí)際應(yīng)用中，偵收的數(shù)據(jù)誤碼率往往較高，因此有必要進(jìn)一步研究高誤碼率條件下的BCH碼識(shí)別方法。利用沃爾什譜可以有效實(shí)現(xiàn)高誤碼環(huán)境下的卷積碼和 Reed-Muller 碼的盲識(shí)別［18，19］，但算法對(duì)存儲(chǔ)空間和計(jì)算量都提出了很高的要求。針對(duì)BCH碼的盲識(shí)別問(wèn)題，提出了基于稀疏沃爾什譜的識(shí)別方法，通過(guò)BCH碼校驗(yàn)矩陣的分布特點(diǎn)，只計(jì)算碼字極少部分的沃爾什譜，極大減少了算法的計(jì)算量，同時(shí)利用沃爾什譜良好的誤碼適應(yīng)特性，能夠快速檢測(cè)識(shí)別數(shù)據(jù)中的BCH編碼，且保持較強(qiáng)的誤碼適應(yīng)能力。

1 BCH碼識(shí)別數(shù)學(xué)模型

(n，k)BCH碼的編碼過(guò)程可以表示為v=m·G［13］，其中m為k維二進(jìn)制信息向量，v為n維二進(jìn)制編碼向量，G為生成矩陣

G的左邊是一個(gè)k×k階單位矩陣，右邊是一個(gè)k×r階矩陣，r=n－k，因此矩陣G的秩為k。若分別用Ik和P表示G的兩個(gè)矩陣塊，則生成矩陣G可表示成G=［IkP］。

且對(duì)于任何一個(gè)碼字v都滿足H·vT=0，H為校驗(yàn)矩陣

則矩陣H可以寫成H=［PTIr］，不難看出，G與H可以互為轉(zhuǎn)化。BCH碼的盲識(shí)別就是通過(guò)編碼向量v，通過(guò)H·vT=0求解H，進(jìn)而獲取編碼矩陣G，并最終通過(guò)譯碼得到信息序列m。

2 基于沃爾什譜的BCH碼識(shí)別方法

利用沃爾什譜可以求解H·vT=0方程組［18，19］，若方程組系數(shù)矩陣為滿秩，則方程組只有1組解，但此時(shí)矩陣的秩為 k，方程組解的個(gè)數(shù)為2n－k，而校驗(yàn)矩陣為其中的n－k組解組成，其余解則為這n－k組解的線性組合。100組(15，11)碼的沃爾什譜如圖1所示。

圖1(15，11)BCH碼的沃爾什譜

其中的峰值所在位置轉(zhuǎn)化為二進(jìn)制向量即為方程組的解，除去0解，共15組解，為

對(duì)H進(jìn)行高斯約旦三角化，將其右邊化為單位矩陣可得到校驗(yàn)矩陣H，為

由此可推出生成矩陣G，從而實(shí)現(xiàn)BCH碼的盲識(shí)別。

但隨著碼長(zhǎng)的增加，所需的存儲(chǔ)空間和計(jì)算量呈指數(shù)增加，在實(shí)際中難以應(yīng)用，因此提出了基于稀疏沃爾什譜的識(shí)別方法。

3 稀疏沃爾什譜的計(jì)算方法

考慮一個(gè)使m維二進(jìn)制向量um滿足um·B=0的解時(shí)，可以將um化為十進(jìn)制數(shù)u，在2m×2m的Hadamard矩陣A中找出第u+1行，該行為1元素的位置p的二進(jìn)制表示的向量p就是方程的解。上述求解過(guò)程可以用式(5)表示。

任意大小的一個(gè)Hadamard矩陣都可等分為4個(gè)區(qū)間，其中3個(gè)區(qū)間的值一致，而1個(gè)區(qū)間的值與其他3個(gè)區(qū)間的值相反。所以Hadamard矩陣中任意位置的值都可由1不斷翻轉(zhuǎn)獲得。下面給出求解Hadamard矩陣中任意位置值的算法。

輸入:Hadamard矩陣的行列值x，y;

輸出:Hadamard矩陣x行、y列的值ω。

算法步驟:

(1)計(jì)算Hadamard矩陣維數(shù)m

(2)將x，y分別減1后轉(zhuǎn)化為m維二進(jìn)制向量xm，ym;

(3)初始 ω=1，i從1～m，如果

ω=－ω，否則，ω=ω。最后輸出 ω就是 Hadamard矩陣x行、y列的值。

如計(jì)算Hadamard矩陣中12行、13列的值，其減1后的二進(jìn)制向量分別為1 011和1 100，向量只有最高位相加為2，所以只將1翻轉(zhuǎn)1次，最終12行、13列的值為－1。

4 基于稀疏沃爾什譜的BCH碼識(shí)別方法

對(duì)于BCH碼的盲識(shí)別，其實(shí)無(wú)需計(jì)算出整個(gè)碼字的沃爾什譜，而只需要計(jì)算出峰值可能出現(xiàn)位置上的沃爾什譜，并根據(jù)計(jì)算的譜值大小來(lái)進(jìn)行判定是否存在BCH編碼。因此，BCH碼的盲識(shí)別只需要先估計(jì)出編碼長(zhǎng)度，然后遍歷該碼長(zhǎng)下的各種碼率，并求解其校驗(yàn)矩陣所在位置的沃爾什譜即可，而不同碼率BCH碼的校驗(yàn)矩陣可預(yù)先進(jìn)行存儲(chǔ)。

對(duì)于BCH碼的碼長(zhǎng)估計(jì)，首先給出文獻(xiàn)［20］中的假設(shè)條件，即編碼信息序列雖然未知，但其中0、1的概率分布存在一定的統(tǒng)計(jì)偏差，即Pr［xt=0］=1/2+ε，ε不為0。根據(jù)經(jīng)典的ASCII編碼，其典型值在0.05和0.1之間。文獻(xiàn)［17］利用碼字與對(duì)偶碼乘積的分布概率，給出了一種Canteaut-Chabaud算法。通過(guò)對(duì)接收的碼字序列進(jìn)行不同長(zhǎng)度的分組，如果分組長(zhǎng)度恰為碼字長(zhǎng)度n，則分組后的碼字矩陣與對(duì)偶碼的乘積為以(M/2)［1－(1－2τ)w］為中心的二項(xiàng)分布，否則為以(M/2)為中心的二項(xiàng)分布。其中，M表示分組數(shù)量，w為對(duì)偶碼字重量，τ為信道轉(zhuǎn)移概率。在兩種分布的峰值中間設(shè)定檢測(cè)門限T，通過(guò)檢測(cè)門限進(jìn)行碼字長(zhǎng)度的判定。文獻(xiàn)［17］利用Canteaut-Chabaud算法求解碼重為w的對(duì)偶碼，解決了碼字長(zhǎng)度的盲估計(jì)問(wèn)題。

在文獻(xiàn)［17］算法實(shí)現(xiàn)碼字長(zhǎng)度估計(jì)的基礎(chǔ)上，利用稀疏沃爾什譜實(shí)現(xiàn)BCH碼的碼率及其他參數(shù)的估計(jì)。

基于稀疏沃爾什譜的BCH碼識(shí)別方法可概括如下。

輸入:接收碼元序列;

輸出:BCH碼長(zhǎng)n、信息長(zhǎng)度k、生成矩陣G。

算法步驟:

(1)遍歷碼長(zhǎng)n，對(duì)接收碼元序列按長(zhǎng)度n進(jìn)行碼字劃分，得到碼字矩陣V;

(2)利用Canteaut-Chabaud算法求解對(duì)偶碼h，利用Vh與檢測(cè)門限T的比較實(shí)現(xiàn)碼字長(zhǎng)度的快速估計(jì);

(3)在正確碼長(zhǎng)n值內(nèi)遍歷其中的碼率k/n，讀取其碼率下的校驗(yàn)矩陣H;

(4)求解矩陣V在校驗(yàn)矩陣H所在位置的稀疏沃爾什譜，并求和;

(5)將所有求解的沃爾什譜值進(jìn)行差分后檢測(cè)峰值，如存在峰值，則根據(jù)峰值所在位置對(duì)碼長(zhǎng)和碼率進(jìn)行判定，并將其校驗(yàn)矩陣H轉(zhuǎn)化為生成矩陣G;如不存在峰值，則不存在BCH碼，退出檢測(cè)。

5 算法仿真及性能分析

取200組誤碼率為1%的(63，39)BCH碼進(jìn)行仿真試驗(yàn)。將編碼按各種碼長(zhǎng)進(jìn)行碼字劃分，利用文獻(xiàn)［17］方法估計(jì)碼字長(zhǎng)度，如圖2所示，當(dāng)分組長(zhǎng)度為63時(shí)，得到碼字與對(duì)偶碼乘積的碼重最小，由此可判定碼長(zhǎng)為63。遍歷碼長(zhǎng)為63的所有碼率，見(jiàn)表1;求解不同碼率對(duì)應(yīng)的稀疏沃爾什譜累積量，如圖3所示。從圖3中看出，在第4個(gè)譜值處出現(xiàn)了明顯峰值，根據(jù)表1可以判定此碼為(63，39)BCH碼。

表1 碼長(zhǎng)為63的BCH碼對(duì)應(yīng)碼率

針對(duì)不同碼長(zhǎng)，在不同誤碼率情況下對(duì)200組碼字進(jìn)行1 000次蒙特卡洛仿真試驗(yàn)，各種碼長(zhǎng)BCH碼的誤碼率與正確識(shí)別概率的曲線圖，如圖4所示。

圖4 不同碼長(zhǎng)BCH碼的誤碼率與正確識(shí)別率曲線

從圖4中可以看出，隨著碼長(zhǎng)的增加算法的誤碼適應(yīng)能力逐漸減弱，在相同誤碼率下，碼長(zhǎng)增加時(shí)，碼塊中出現(xiàn)誤碼的概率則越大;當(dāng)誤碼增大時(shí)，算法中長(zhǎng)碼的適應(yīng)能力則最先下降。(255，187)碼在誤碼為1%時(shí)的檢測(cè)概率可達(dá)100%，碼長(zhǎng)不超過(guò)31的短碼誤碼適應(yīng)能力都超過(guò)了10%。

分別取200組各種長(zhǎng)度的BCH碼，對(duì)文獻(xiàn)［10，12，15，16］和本文提出的算法進(jìn)行比較。各種算法的誤碼適應(yīng)能力，如圖5所示，圖中的誤碼適應(yīng)能力以正確識(shí)別率在90%以上為準(zhǔn)，可以看出，迭代譯碼算法［12］與歐幾里得算法［15］誤碼適應(yīng)能力較弱，碼根統(tǒng)計(jì)算法［16］與 Valembois算法［10］性能較好，本文提出的算法誤碼適應(yīng)性能優(yōu)于目前文獻(xiàn)已有算法。

圖5 不同算法的誤碼適應(yīng)能力曲線

在計(jì)算量方面，假設(shè)BCH碼長(zhǎng)為n，信息長(zhǎng)度為k，歐幾里得算法的計(jì)算復(fù)雜度為O(n)，迭代譯碼算法與其計(jì)算復(fù)雜度相當(dāng)。而碼根統(tǒng)計(jì)算法的計(jì)算復(fù)雜度為O(n3)，Valembois算法在查找對(duì)偶碼時(shí)計(jì)算量為O(nw/2)［17］，w為對(duì)偶碼重量。本文算法的計(jì)算量主要體現(xiàn)在獲取Hadamard矩陣的任意一點(diǎn)和譜值累加上，計(jì)算量為(1/2)n(n－k)，計(jì)算復(fù)雜度為O(n2)。因此，本文提出的算法計(jì)算量高于歐幾里得算法與迭代譯碼算法，而小于碼根統(tǒng)計(jì)算法和Valembois算法。

6 結(jié)語(yǔ)

針對(duì)較高誤碼條件下BCH碼的盲識(shí)別問(wèn)題，提出了一種基于稀疏沃爾什譜的BCH碼檢測(cè)識(shí)別算法。該算法有效利用了沃爾什譜良好的誤碼適應(yīng)性，同時(shí)對(duì)沃爾什譜進(jìn)行了稀疏求解，有效減少了算法的計(jì)算量。仿真結(jié)果表明，該算法的誤碼適應(yīng)性能優(yōu)于目前文獻(xiàn)中已有算法，能夠在較高誤碼率條件下實(shí)現(xiàn)對(duì)BCH碼的盲檢測(cè)與識(shí)別，且算法計(jì)算量小，易于工程實(shí)現(xiàn)。

［1］VINCK A J HAN，DOLEZAL PETR，KIM YOUNG-GIL.Convolutional Encoder State Estimation［J］.IEEE Transactions on Information Theory，1998，44(4):1 604-1 608.

［2］STEINBERG YOSSEF.Coding and Common Reconstruction［J］.IEEE Transactions on Information Theory，2009，55(11):4 995-5 010.

［3］COTE MAXIME，SENDRIER NICOLAS.Reconstruction of Convolutional Codes from Noisy Observation［C］//IEEE International Symposium on Information Theory，Seoul，Korea，2009:546-550.

［4］DINGEL JANIS，HAGENAUER JOACHIM.Parameter Estimation of a Convolutional Encoder from Noisy Observations［C］//IEEE International Symposium on Information Theory，F(xiàn)rance，2007:1 776-1 780.

［5］WANG FENG-HUA，HUANG ZHI-TAO，ZHOU YI-YU.A Method for Blind Recognition of Convolution Code Based on Euclidean Algorithm［C］//IEEE International Conference on Wireless Communications，Shanghai，2007:1 414-1 417.

［6］CLUZEAU MATHIEU，F(xiàn)INIASZ MATTHIEU，TILLICH JEAN-PIERRE.Methods for the Reconstruction of Parallel Turbo Codes［C］//IEEE International Conference on Information Theory，Austin，Texas，U.S.A，2010:2 008-2 012.

［7］CLUZEAU M，F(xiàn)INIASZ M.Reconstruction of Punctured Convolutional Codes［C］//Information Theory Workshop 2009:75-79.

［8］COTE MAXIME，SENDRIER NICOLAS.Reconstruction of a Turbo-Code Interleaver from Noisy Observation［C］//IEEE International Symposium on Information Theory Proceedings(ISIT)，Austin，Texas，U.S.A，2010:2 003-2 007.

［9］CHOQUEUSE VINCENT，YAO KOFFI.Blind Recognition of Linear Space Time Block Codes［C］//IEEE International Conference on Acoustics，Speech and Signal Processing(ICASSP)，2008:2 833-2 836.

［10］VALEMBOIS ANTOINE.Detection and Recognition of a Binary Linear Code［J］.Discrete Applied Mathematics，2001，111:199-218.

［11］CHABOT CHRISTOPHE.Recognition of a Code in a Noisy Environment［C］//IEEE International Conference on Information Theory，Nice，F(xiàn)rance，2007:2 211-2 215.

［12］CLUZEAU MATHIEU.Block Code Reconstruction Using Iterative Decoding Techniques［C］//IEEE International Conference on Information Theory(ISIT)，Seattle，USA，2006:2 269-2 273.

［13］LINT J H VAN.Introduction to Coding Theory［M］.Springer-Verlag Press，2003.

［14］陳金杰，楊俊安.基于碼重信息熵低碼率線性分組碼的盲識(shí)別［J］.電路與系統(tǒng)學(xué)報(bào)，2012，17(1):41-46.

［15］WANG JIAFENG，YUE YANG，YAO JUN.A Method of Blind Recognition of Cyclic Code Generator Polynomial［C］.Wireless Communications Networking and Mobile Computing(WiCOM)，2010:23-25.

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

［17］CLUZEAU MATHIEU，F(xiàn)INIASZ MATTHIEU.Recovering a Code's Length and Synchronization from a Noisy Intercepted Bitstream［C］//IEEE International Conference on Information Theory(ISIT)，Seoul，Korea，2009:2 737-2 741.

［18］劉健，王曉君，周希元.基于Walsh-Hadamard變換的卷積碼盲識(shí)別［J］.電子與信息學(xué)報(bào)，2010，32(4):884-888.

［19］KANG I S，LEE H.Reconstruction Method for Reed-Muller Codes Using Fast Hadamard Transform［C］//13th International Conference on Advanced Communication Technology(ICACT)，2011:793-796.

［20］LIU XIAO-BEI，KOH SOO NGEE，WU XIN-WEN.Reconstructing a Linear Scrambler with Improved Detection Capability and in the Presence of Noise［J］.IEEE Transactions on Information Forensics and Security，2012，7(1):208-218.