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

（電子工程學院，合肥 230037）

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

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

（電子工程學院，合肥 230037）

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

信息截獲，卷積碼，盲識別，遺傳算法

0 引言

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

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

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

1（n，n-1，m）卷積碼盲識別問題描述

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

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

對于（n-1）/n碼率卷積碼，其基本校驗多項式矩陣可表示如下：

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

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

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

結合式（1）、式（2）可得編碼矩陣R與基本校驗序列之間有如下校驗關系：

由此，對（n，n-1，m）卷積碼基本校驗多項式矩陣的識別問題轉化為求F2上含錯線性方程組式（9）最優(yōu)解的問題。

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

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

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

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

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

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

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

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

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

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

因此，設定適應度判決門限為：

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

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

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

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

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

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

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

6）令gen=gen+1，計算新一代群體中M個個體的適應度值：{f（k）|k=1，2，…，M}，返回步驟5）；若gen=Gen，則識別失敗，結束算法運行。

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

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

3 仿真分析

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

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

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

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

對（2，1，6）卷積碼，在F2（x）上其基本校驗多項式矩陣與基本生成多項式之間有如下關系：

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

最終識別得到（2，1，6）卷積碼含錯編碼序列的原基本生成多項式矩陣為：

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

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

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

對p（x）作行初等化簡，使其行最高階次最?。词咕幋a矩陣結構最簡）［11］，得到：

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

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

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

4 結束語

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

［1］解輝，黃知濤，王豐華.信道編碼盲識別技術研究進展［J］.電子學報，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］劉建成，楊曉靜，張玉.基于改進歐幾里德算法的（n，1，m）卷積碼識別［J］.探測與控制學報，2012，34（1）:64-68.［4］劉健，王曉君，周希元.基于Walsh-hadamard變換的卷積碼盲識別［J］.電子與信息學報，2010，32（4）:884-888.

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

［6］張東，陳格順，王格芳，等.一種新的高誤碼（2，1，m）卷積碼盲識別方法［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］楊曉靜，劉建成，張玉.基于求解校驗序列的（n，k，m）卷積碼盲識別［J］.宇航學報，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］王耀南.智能信息處理技術［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

國家自然科學基金（61201379）；安徽省自然科學基金資助項目（1208085QF103）

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