基于遺傳算法的（n，n-1，m）卷積碼盲識(shí)別*

張 岱，張 玉，楊曉靜，樊斌斌

（電子工程學(xué)院，合肥 230037）

基于遺傳算法的（n，n-1，m）卷積碼盲識(shí)別*

張 岱，張 玉，楊曉靜，樊斌斌

（電子工程學(xué)院，合肥 230037）

針對(duì)信息截獲領(lǐng)域中（n，n-1，m）卷積碼盲識(shí)別問(wèn)題，提出基于遺傳算法的盲識(shí)別方法。該方法在矩陣分析得到編碼參數(shù)之后，利用遺傳算法的全局搜索能力實(shí)現(xiàn)對(duì)基本校驗(yàn)多項(xiàng)式矩陣的精確識(shí)別，進(jìn)而實(shí)現(xiàn)對(duì)基本生成多項(xiàng)式矩陣的識(shí)別。仿真表明：該方法能夠在高誤碼條件下實(shí)現(xiàn)對(duì)（n，n-1，m）卷積碼的盲識(shí)別，且運(yùn)算量相對(duì)于以往的高容錯(cuò)識(shí)別方法得到降低。

信息截獲，卷積碼，盲識(shí)別，遺傳算法

0 引言

在現(xiàn)代數(shù)字通信系統(tǒng)中普遍采用信道編碼技術(shù)以提高信息傳輸?shù)陌踩煽啃?，其中，卷積碼作為信道編碼中一種典型的糾錯(cuò)編碼方式，廣泛應(yīng)用于衛(wèi)星通信、深空通信等領(lǐng)域中。因此，卷積碼盲識(shí)別研究在非合作環(huán)境下的信息截獲等領(lǐng)域具有重要意義［1］。（n，n-1，m）卷積碼具有較高的編碼效率，故本文將針對(duì)（n，n-1，m）卷積碼的盲識(shí)別展開(kāi)研究。

卷積碼盲識(shí)別技術(shù)的重要性受到了國(guó)內(nèi)外越來(lái)越多研究人員的關(guān)注［2-8］，目前的識(shí)別方法主要有基于歐幾里德算法的識(shí)別方法［3］、Walsh-Hadamard分析法［4］、基于校驗(yàn)統(tǒng)計(jì)的識(shí)別方法［5-6］、基于BM的快速合沖法［7］和基于矩陣分析的識(shí)別方法［8］等。其中基于歐幾里德算法的識(shí)別方法適用于1/n碼率卷積碼，運(yùn)算量小但容錯(cuò)性能差；Walsh-Hadamard分析法和基于校驗(yàn)統(tǒng)計(jì)的識(shí)別方法同樣只適用于1/n碼率卷積碼，具有較好的容錯(cuò)性，但運(yùn)算量巨大；基于BM的快速合沖法運(yùn)算量小且具備一定容錯(cuò)性，但該方法只適用于1/2碼率卷積碼的識(shí)別；基于矩陣分析的識(shí)別方法可對(duì)不同碼率卷積碼進(jìn)行全盲識(shí)別，其中在對(duì)卷積碼編碼參數(shù)識(shí)別時(shí)具有較高容錯(cuò)性，但對(duì)基本校驗(yàn)矩陣進(jìn)行識(shí)別時(shí)容錯(cuò)性差。

綜上所述，現(xiàn)有的卷積碼識(shí)別方法主要針對(duì)1/n碼率卷積碼進(jìn)行識(shí)別，對(duì)（n-1）/n碼率卷積碼識(shí)別研究少，且容錯(cuò)性能差。為此，本文提出一種基于遺傳算法的卷積碼盲識(shí)別方法，可實(shí)現(xiàn)對(duì)高誤碼（n，n-1，m）卷積碼的盲識(shí)別。

1（n，n-1，m）卷積碼盲識(shí)別問(wèn)題描述

記u和c分別為（n，n-1，m）卷積碼的信息序列和碼字序列，在F2（x）上，二者滿足如下關(guān)系：

式（1）中，G（x）為（n，n-1，m）卷積碼的生成多項(xiàng)式矩陣。同時(shí)，存在校驗(yàn)多項(xiàng)式矩陣H（x），并滿足以下關(guān)系［9］：

對(duì)于（n-1）/n碼率卷積碼，其基本校驗(yàn)多項(xiàng)式矩陣可表示如下：

通過(guò)矩陣分析法對(duì)卷積碼編碼數(shù)據(jù)進(jìn)行處理可得到如下結(jié)果［7］：

通常情況下，當(dāng)接收數(shù)據(jù)中存在誤碼時(shí)僅會(huì)使校驗(yàn)序列P1i發(fā)生錯(cuò)誤，而不影響對(duì)卷積碼編碼參數(shù)的識(shí)別結(jié)果，由式（6）可直接識(shí)別得到原卷積碼碼長(zhǎng)n。記P1i所在列數(shù)為p，則碼字約束度K+1估計(jì)如下：

利用式（6）、式（7）識(shí)別得到的卷積碼參數(shù)n、K，對(duì)截獲的含錯(cuò)碼字序列r={r1，0，r2，0，…，rn，0，…，r1，NK+N-1，r2，NK+N-1，…，rn，NK+N-1}構(gòu)建編碼矩陣如下：

結(jié)合式（1）、式（2）可得編碼矩陣R與基本校驗(yàn)序列之間有如下校驗(yàn)關(guān)系：

由此，對(duì)（n，n-1，m）卷積碼基本校驗(yàn)多項(xiàng)式矩陣的識(shí)別問(wèn)題轉(zhuǎn)化為求F2上含錯(cuò)線性方程組式（9）最優(yōu)解的問(wèn)題。

2 基于遺傳算法的（n，n-1，m）卷積碼盲識(shí)別

遺傳算法由美國(guó)密歇根（Michigan）大學(xué)教授John H.Holland于20世紀(jì)70年代初提出，該算法運(yùn)行原理基于模仿生物進(jìn)化的過(guò)程，是一種概率性的自適應(yīng)迭代尋優(yōu)算法。它從某一隨機(jī)產(chǎn)生的或是特定的初始群體（父體）出發(fā)，按照一定的操作規(guī)則，如選擇、交叉、變異等，不斷地迭代計(jì)算，并根據(jù)每一個(gè)個(gè)體的適應(yīng)度，保留優(yōu)良品種，淘汰次品，引導(dǎo)搜索過(guò)程向最優(yōu)解逼近。因此，遺傳算法是一種能在復(fù)雜空間中進(jìn)行魯棒搜索的方法，能夠解決許多傳統(tǒng)的優(yōu)化方法難以解決的優(yōu)化問(wèn)題［10］。

2.1 算法適應(yīng)度函數(shù)及判決門限分析

由第1節(jié)可知，對(duì)（n，n-1，m）卷積碼基本校驗(yàn)多項(xiàng)式矩陣的識(shí)別問(wèn)題即為求式（9）的最優(yōu)解問(wèn)題。任取F2上非零n（K+1）×1向量hk，則有：

上式bk中0的數(shù)目表示R的行向量中與hk滿足校驗(yàn)關(guān)系的數(shù)目，線性含錯(cuò)方程組式（9）的最優(yōu)解即為使得bk中0數(shù)目最多的行向量hk。對(duì)于（n，n-1，m）卷積碼，其基本校驗(yàn)序列h唯一，因此，可求解如下：

綜合以上分析，將適應(yīng)度函數(shù)確定如下：

對(duì)于F2上n（K+1）×1向量空間中任意元素hk，若hk≠h，則對(duì)bk中的每個(gè)元素bkj，j=1，2，…，N，有：

即bkj～b（1，1/2），有E（bkj）=1/2，D（bkj）=1/4。當(dāng)編碼矩陣行數(shù)N取足夠大時(shí)，有：

φ（x）為標(biāo)準(zhǔn)正態(tài)分布函數(shù)。設(shè)定識(shí)別虛警概率為pfa=1×10-5，令：

可查表求得f（k）的取值范圍為：

因此，設(shè)定適應(yīng)度判決門限為：

2.2 基于遺傳算法的（n，n-1，m）卷積碼識(shí)別

利用第1節(jié)原理識(shí)別積碼參數(shù)n、K，進(jìn)而采用遺傳算法對(duì)（n，n-1，m）卷積碼的基本校驗(yàn)矩陣進(jìn)行識(shí)別。算法實(shí)現(xiàn)的具體步驟如下：

1）利用識(shí)別得到的參數(shù)n、K，選取一較大數(shù)N，將接收序列按式（8）形式構(gòu)建編碼矩陣RN×n（K+1）；

2）設(shè)定染色體長(zhǎng)度L=n（K+1），群體規(guī)模M（每代處理的染色體數(shù)目）；設(shè)定進(jìn)化代數(shù)上限Gen、選擇概率Ps、交叉概率Pc和變異概率Pm，使得Ps+Pc+ Pm=1，以確保每代染色體的完備；根據(jù)式（12）、式（20），確定適應(yīng)度函數(shù)f（k）和適應(yīng)度判決門限λ；

3）隨機(jī)從F2上n（K+1）×1向量空間中選擇初始染色體hk（1≤k≤M），并構(gòu)造初始群體集H0= {h1，h2，…，hM}；

4）遍歷選取H0中元素hk（k=1，2，…，m），計(jì)算RN×n（K+1）·hkT=bk，得到群體中M個(gè)個(gè)體的適應(yīng)度值：{f（k）|k=1，2，…，M}，此時(shí)進(jìn)化代數(shù)gen設(shè)置為0；

5）判斷max{f（k）|k=1，2，…，M}是否大于適應(yīng)度判決門限λ，若條件滿足則結(jié)束進(jìn)化，輸出最優(yōu)解h={hi|f（i）=max（f（k）），i，k=1，2，…，M}，結(jié)束算法運(yùn)行；若不滿足判決條件則進(jìn)行遺傳進(jìn)化：選取Hgen中適應(yīng)度最高的M·Ps個(gè)個(gè)體直接復(fù)制；選取適應(yīng)度最高的M·Pc個(gè)個(gè)體，將其兩兩配對(duì)在隨機(jī)位置上進(jìn)行交叉；選取適應(yīng)度適中的M·Pm個(gè)個(gè)體，對(duì)每個(gè)個(gè)體選擇隨機(jī)位置進(jìn)行突變，處理后傳遞給下一代；

6）令gen=gen+1，計(jì)算新一代群體中M個(gè)個(gè)體的適應(yīng)度值：{f（k）|k=1，2，…，M}，返回步驟5）；若gen=Gen，則識(shí)別失敗，結(jié)束算法運(yùn)行。

利用遺傳算法識(shí)別得到的基本校驗(yàn)序列h可根據(jù)式（3）、式（4）還原出原卷積碼的基本校驗(yàn)多項(xiàng)式矩陣h（x）。對(duì)于（n，n-1，m）系統(tǒng)卷積碼其基本生成多項(xiàng)式矩陣g（x）與基本校驗(yàn)矩陣之間存在嚴(yán)格的相似轉(zhuǎn)換關(guān)系，因此，可由h（x）直接變換得到。對(duì)于（n，n-1，m）非系統(tǒng)卷積碼基本生成多項(xiàng)式矩陣的識(shí)別原理如下：

解多項(xiàng)式方程組式（20）時(shí)將得到多解，這些解均是基本多項(xiàng)式矩陣行向量的線性組合，因此，可通過(guò)對(duì)解向量進(jìn)行初等變換使其化到最簡(jiǎn)，最終完成原卷積碼基本生成多項(xiàng)式矩陣g（x）的識(shí)別［11］。

3 仿真分析

以（2，1，6）和（3，2，4）非系統(tǒng)卷積碼識(shí)別為例驗(yàn)證本文算法的可行性。其基本生成多項(xiàng)式矩陣分別表示如下：

仿真生成誤碼率為0.05的（2，1，6）和（3，2，3）兩種卷積碼序列，利用第1節(jié)原理對(duì)其進(jìn)行識(shí)別，可得到如下結(jié)果：對(duì)（2，1，6）卷積碼含錯(cuò)序列，碼長(zhǎng)n1=2，碼字約束度為7，即K1=6；對(duì)（3，2，3）卷積碼含錯(cuò)序列，碼長(zhǎng)n2=3，碼字約束度為7，即K2=6。

隨后基于遺傳算法對(duì)（n，n-1，m）卷積碼的基本校驗(yàn)序列進(jìn)行識(shí)別，設(shè)置仿真條件：編碼矩陣R行數(shù)N=400，對(duì)兩種卷積碼識(shí)別的染色體長(zhǎng)度分別設(shè)定為：L1=14、L2=21；群體規(guī)模M=60，進(jìn)化代數(shù)上限Gen=2 000，選擇概率Ps=0.2，交叉概率Pc=0.4，變異概率Pm=0.4；適應(yīng)度函數(shù)f（k）=400-weight（bk），適應(yīng)度判決門限λ=242。分別對(duì)兩種卷積碼含錯(cuò)編碼序列進(jìn)行識(shí)別仿真，其識(shí)別情況如圖1所示。

由圖1知，利用遺傳算法進(jìn)行識(shí)別時(shí)，對(duì)（2，1，6）卷積碼，當(dāng)進(jìn)化到350代時(shí)，群體最高適應(yīng)度值達(dá)到245，對(duì)（3，2，3）卷積碼，當(dāng)進(jìn)化到1 526代時(shí)，群體最高適應(yīng)度值達(dá)到249，均搜索到滿足條件的染色體，即所要識(shí)別的基本校驗(yàn)序列。由仿真還可得到，識(shí)別進(jìn)化代數(shù)隨基本校驗(yàn)序列長(zhǎng)度的增加而逐漸增多，這是由搜索空間的擴(kuò)張所致。利用遺傳算法識(shí)別得到兩種卷積碼的基本校驗(yàn)序列分別為h1=11100011110111和h2=111000110111000111101。由此，h1（x）和h2（x）可分別表示如下：

對(duì)（2，1，6）卷積碼，在F2（x）上其基本校驗(yàn)多項(xiàng)式矩陣與基本生成多項(xiàng)式之間有如下關(guān)系：

又gcd（g1，1（x），g1，2（x））=0，且一般卷積碼編碼器不存在反饋逆［8］，可得：

最終識(shí)別得到（2，1，6）卷積碼含錯(cuò)編碼序列的原基本生成多項(xiàng)式矩陣為：

對(duì)（3，2，3）卷積碼含錯(cuò)編碼序列，根據(jù)式（21），設(shè)基本生成多項(xiàng)式矩陣的最高階數(shù)（編碼記憶長(zhǎng)度）為m，建立F2（x）上的多項(xiàng)式方程如下：

對(duì)多項(xiàng)式方程式（27）分析可得，其最高階次為m+6，未知項(xiàng)系數(shù)有3（m+1）個(gè)，由此，將式（27）按階次提取系數(shù)可構(gòu)建F2上方程個(gè)數(shù)為m+7、未知數(shù)個(gè)數(shù)為3（m+1）的線性方程組。又基本生成多項(xiàng)式矩陣的行數(shù)即為方程式（24）最大線性無(wú)關(guān)解的個(gè)數(shù)，即解空間維數(shù)。對(duì)線性方程組維數(shù)進(jìn)行分析可得如下關(guān)系：

解得卷積碼編碼記憶長(zhǎng)度為m=3。求解由多項(xiàng)式方程式（27）系數(shù)提取構(gòu)造的線性方程組，得到基礎(chǔ)解向量為：p1=111101101101，p2=111111011010。表示成多項(xiàng)式矩陣形式如下：

對(duì)p（x）作行初等化簡(jiǎn)，使其行最高階次最?。词咕幋a矩陣結(jié)構(gòu)最簡(jiǎn)）［11］，得到：

式（26）和式（27）識(shí)別結(jié)果均與原卷積碼基本生成多項(xiàng)式矩陣相同，驗(yàn)證了本文算法在高誤碼環(huán)境下對(duì)（n，n-1，m）卷積碼盲識(shí)別的可行性。

當(dāng)前對(duì)（n，n-1，m）卷積碼識(shí)別主要采用矩陣分析法，此外采用校驗(yàn)統(tǒng)計(jì)的方法也可對(duì)（n，n-1，m）卷積碼進(jìn)行識(shí)別，但由于需對(duì)2n（K+1）個(gè)F2上向量進(jìn)行逐個(gè)檢驗(yàn)，運(yùn)算量較大，因此，不具有實(shí)用性［5］?，F(xiàn)在卷積碼參數(shù)n和K準(zhǔn)確識(shí)別的基礎(chǔ)之上，對(duì)3 000 bit不同誤碼率的（3，2，3）卷積碼序列，分別采用矩陣分析法［8］和本文算法（為保證實(shí)時(shí)性，設(shè)置進(jìn)化代數(shù)上限Gen=2 000）識(shí)別其基本校驗(yàn)序列，通過(guò)蒙特卡羅方法統(tǒng)計(jì)識(shí)別概率如圖2所示。

由圖2可以看出，采用矩陣分析法對(duì)（n，n-1，m）卷積碼進(jìn)行識(shí)別，當(dāng)誤碼率達(dá)到0.02時(shí)，對(duì)卷積碼基本校驗(yàn)序列的識(shí)別率將降低到50%以下，而采用本文算法進(jìn)行識(shí)別時(shí)，當(dāng)誤碼率在0.07左右時(shí)，對(duì)基本校驗(yàn)序列的準(zhǔn)確識(shí)別率仍能達(dá)到50%以上，識(shí)別率取得了明顯提高。同時(shí)，由于本文算法與基于校驗(yàn)統(tǒng)計(jì)的識(shí)別算法均是通過(guò)在F2上向量空間中尋找編碼約束方程組最優(yōu)解向量實(shí)現(xiàn)對(duì)基本校驗(yàn)序列的識(shí)別，因此，本文算法與基于校驗(yàn)統(tǒng)計(jì)識(shí)別算法的識(shí)別概率接近，然而在運(yùn)算量對(duì)比上，基于校驗(yàn)統(tǒng)計(jì)識(shí)別算法識(shí)別運(yùn)算量為N（2nK+2n-1）（2n（K+1）-1），本文算法在進(jìn)化到進(jìn)化代數(shù)上限Gen時(shí)運(yùn)算量為Gen·M·N（2nK+2n-1）。當(dāng)對(duì)（3，2，3）卷積碼進(jìn)行識(shí)別時(shí)，基于校驗(yàn)統(tǒng)計(jì)識(shí)別算法運(yùn)算量在1010量級(jí)，本文算法運(yùn)算量在108量級(jí)，運(yùn)算量得到了明顯降低。

4 結(jié)束語(yǔ)

本文提出了基于遺傳算法的卷積碼盲識(shí)別方法。該方法通過(guò)矩陣分析識(shí)別卷積碼參數(shù)，利用遺傳算法的全局搜索能力實(shí)現(xiàn)對(duì)高誤碼（n，n-1，m）卷積碼基本校驗(yàn)多項(xiàng)式矩陣的準(zhǔn)確識(shí)別，進(jìn)而通過(guò)與基本生成多項(xiàng)式矩陣間的校驗(yàn)關(guān)系實(shí)現(xiàn)對(duì)基本生成多項(xiàng)式矩陣的識(shí)別。仿真結(jié)果表明，與矩陣分析法［7］相比，本文方法具有較好的容錯(cuò)性，同時(shí)，和校驗(yàn)統(tǒng)計(jì)的方法［5］相比，極大地降低了運(yùn)算量，在非合作信號(hào)處理及智能通信等領(lǐng)域具有重要應(yīng)用意義。

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

［2］Marazin M，Gautier R，Burel G.Blind Recovery of k/n Rate Convolutional Encoders in a Noisy Environment［J］.EURASIP Journal on Wireless Comunications and Networking，2011:168.

［3］劉建成，楊曉靜，張玉.基于改進(jìn)歐幾里德算法的（n，1，m）卷積碼識(shí)別［J］.探測(cè)與控制學(xué)報(bào)，2012，34（1）:64-68.［4］劉健，王曉君，周希元.基于Walsh-hadamard變換的卷積碼盲識(shí)別［J］.電子與信息學(xué)報(bào)，2010，32（4）:884-888.

［5］解輝，王豐華，黃知濤.基于最大似然檢測(cè)的（n，1，m）卷積碼盲識(shí)別［J］.電子與信息學(xué)報(bào)，2013，35（7）:1672-1676.

［6］張東，陳格順，王格芳，等.一種新的高誤碼（2，1，m）卷積碼盲識(shí)別方法［J］.火力與指揮控制，2013，38（11）:69-72.

［7］Peizhong L，Yan Z.Fast Computations of Grobner Bases and Blind Recognitions of Convolutional Codes［J］.Lecture Notes in Computer Science，2007，4547:303-317.

［8］楊曉靜，劉建成，張玉.基于求解校驗(yàn)序列的（n，k，m）卷積碼盲識(shí)別［J］.宇航學(xué)報(bào)，2013，34（4）:568-573.

［9］Marazin M，Gautier R，Burel G.Some Intresting Dual-code Properties of Convolutional Encoder for Standards Self-recognition［J］.IET Commun，2012，8（6）:931-935.

［10］王耀南.智能信息處理技術(shù)［M］.北京：高等教育出版社，2003.

［11］Cote M，Sendrier N.Reconstruction of Convolutional Codes from Noisy Observation［C］//ISIT 09，Seoul，Korea，2009: 546-550.

Blind Recognition of（n，n-1，m）Convolutional Code Based on Genetic Algorithm

ZHANG Dai，ZHANG Yu，YANG Xiao-jing，F(xiàn)AN Bin-bin
（Electronic Engineering Institute，Hefei 230037，China）

Considering blind recognition of（n，n-1，m）convolutional code in information interception，a recognition method based on genetic algorithm is proposed.After obtaining coding characters through matrix analysis，this method achieves accurate recognition of the basic check polynomial matrix by utilizing global searching ability of the genetic algorithm.Then，recognition of basic generator polynomial matrix is realized.The simulation shows that this method can blindly recognise（n，n-1，m）convolutional code in a high BER environment，while its computing efforts get lower compared with high fault-tolerant methods before.

information interception，convolutional code，blind recognition，genetic algorithm

TP309

A

1002-0640（2015）09-0031-04

2014-08-12

2014-09-18

國(guó)家自然科學(xué)基金（61201379）；安徽省自然科學(xué)基金資助項(xiàng)目（1208085QF103）

張 岱（1993- ），男，安徽太和人，碩士研究生。研究方向：信道編碼識(shí)別分析。