基于粒子群算法的(n,1,m)卷積碼盲識別

占 超，何顯鵬

(中國人民解放軍92515部隊，遼寧 葫蘆島 125001)

0 引言

現代數字通信系統中一般采用信道編碼技術，以避免噪聲和干擾的影響，實現信息的可靠傳輸。(n,1,m)卷積碼是一種常見的編碼方式，它具有編碼易于實現以及糾錯性能強等優點，在深空探測、數字通信等領域應用廣泛。因此，對(n,1,m)卷積碼的盲識別進行研究，具有十分重要的意義[1-6]。

目前，卷積碼盲識別方法主要有高斯解方程法[7-8]、歐幾里德法[9-12]和矩陣分析法[13-16]。其中，高斯解方程法無法容錯，且必須預先知道碼字起點等先驗信息；歐幾里德法相比高斯解方程法大大降低了計算量，但只適于無記憶的卷積碼識別；矩陣分析法利用接收序列建立分析矩陣，然后初等變換并從中提取碼長及檢驗序列等信息，但誤碼適應性較差。因此，針對以上不足，本文提出了一種新的基于粒子群算法的(n,1,m)卷積碼盲識別方法。

1 問題描述

卷積碼常記為(n,k,m)，其中n稱為碼長，k稱為信息分組長度，m稱為編碼記憶長度。對于本文的(n,1,m)卷積碼，它表示編碼器每輸入1路信息序列u(x)，則輸出n路編碼序列V(x)，其中：

u(x)=u0+u1x+…+uixi+…，

(1)

C(x)=[c1(x)c2(x) …cn(x)]，

(2)

cj(x)=cj,0+cj,1x+…+cj,lxl+…,j=1,2,…,n。

(3)

設生成多項式矩陣為G(x)，則編碼過程可表示為：

C(x)=u(x)G(x)，

(4)

其中，

G(x)=[g1(x)g2(x) …gn(x)] ，

(5)

gi(x)=gi,0+gi,1x+…+gi,mxm,i=1,2,…,n。

(6)

令H(x)表示校驗矩陣，則

(7)

(8)

根據文獻[17]，有：

G(x)HT(x)=0。

(9)

由式(4)和式(9)，得：

C(x)HT(x)=u(x)·G(x)·HT(x)=0。

(10)

因此，(n,1,m)卷積碼盲識別就是利用已接收的編碼序列識別碼長n和信息分組長度k，然后恢復校驗多項式矩陣H(x)，并利用式(9)得到生成多項式矩陣G(x)。

2 識別方法介紹

2.1 模型建立

將式(10)展開，得：

(11)

(12)

為了便于直接利用編碼序列構建方程，將上式轉換為：

(13)

2.2 基于粒子群算法的校驗矩陣識別

粒子群算法通過模擬鳥群飛行覓食的行為方式，基于鳥個體之間的集體協作使群體達到最優[18]。該算法具有概念簡明、實現方便、收斂速度快以及參數設置少等特點，是一種高效的群智能算法。在粒子群算法中，每個個體被稱為一個“粒子”，而每個粒子的所在位置代表著一個潛在的解。每個粒子按一定規則運動，并估計自身位置的適應值，同時記住自己目前找到的最佳位置，此外還要記錄所有粒子達到的最佳位置。所有粒子都逐漸向最佳位置靠近，最終達到收斂狀態。

令D=n(M+1)，粒子群群體規模為q，zi=(zi1,zi2,…,zid,…,ziD)為第i個粒子(1≤i≤q)當前所在位置。每次迭代中，根據所設定的適應值函數計算zi當前的適應值，即可衡量粒子位置的優劣。設vi=(vi1,vi2,…,vid,…,viD)為粒子i的飛行速度，pi=(pi1,pi2,…,pid,…,piD)為粒子i迄今為止所搜索到的最佳位置，pg=(pg1,pg2,…,pgd,…,pgD)為整個粒子群迄今為止搜索到的最佳位置。

在每次迭代中，每個粒子按下式更新速度：

(14)

式中，a1和a2為學習因子，也稱加速因子，它使粒子具有自我總結和向群體中其他優秀個體學習的能力；r1和r2用來保持群體的多樣性；w稱為慣性權重。a1,a2在[0, 4]上，一般選取a1=a2=2。r1,r2是[0, 1]上的隨機數。慣性權重w起著權衡局部最優能力和全局最優能力的作用，實際問題中，往往希望先采用全局搜索，使搜索空間快速收斂于某一區域，然后采用局部精細搜索已獲得高精度的解。因此，將其設定為一個隨時間線性減少的函數，并表示為：

(15)

在不同速度下，粒子的位置得到如下更新，

(16)

式中，ρ為[0, 1]之間的隨機數，且

(17)

由于粒子群算法中，沒有實際的機制來控制粒子速度，因此有必要對速度的最大值進行限制，當速度超過這個閾值時，將其設定為vmax。通常選取vmax=6，此時Sigmoid(·)的取值范圍為[0.002 5, 0.997 5]。

下面對適應值函數的選取進行說明。當zi是方程組(13)的根時，該線性方程組中方程成立的個數達到最多。反之，方程成立與否的概率各為0.5。令cl=[c1,l…cn,lc1,l+1…cn,l+1…c1,M+l…cn,M+l]，并計：

(18)

2.3 生成多項式求解

在得到校驗多項式矩陣H(x)，將根據式(9)展開，有：

(19)

式中，包含n(m+1)個未知數，而通過待定系數法可以列出(n-1)(m+M+1)個方程，要保證有解，則必須滿足(n-1)(m+M+1)≤n(m+1)，即m≥n(M-1)-1。以此可以計算得到生成多項式矩陣G(x)。

綜上，(n,1,m)卷積碼識別步驟可總結如下：

輸入：接收序列c；

輸出：碼長n，編碼記憶長度m，生成多項式矩陣G(x)；

識別步驟：

步驟1：設定碼長取值范圍2≤n≤8，校驗多項式最高次數取值范圍2≤M≤6，取n和M的初值為2；

步驟2：設定粒子群算法的種群規模q=50，算法最大迭代次數kmax=?22m+1/q」，其中?·」表示向下取整；

步驟3：按式(13)建立方程組，并采用粒子群算法計算bi值；

步驟4：判斷bi值是否大于門限T。如果是，則記錄對應的M值和向量zi，并將其轉為校驗多項式矩陣H(x)。反之，判斷M是否大于6，如果是，則n自加1，并重復步驟3、4；如果否，則M自加1，并重復步驟3、4；

步驟5:設定m初值為n(M-1)-1，根據式(19)計算生成多項式矩陣G(x)。

3 仿真分析

選取(4,1,5)卷積碼進行仿真，其生成多項式用8進制可表示為G(53,67,71,75)，即G(x)=[1+x2+x4+x51+x+x3+x4+x51+x+x2+x51+x+x2+x3+x5]。首先生成2 000 bit卷積碼編碼數據，然后隨機加入誤碼率為0.01的誤比特，按2.3節步驟進行識別，通過對參數進行遍歷，當n=4,M=2時，結果如圖1所示。此時，方程共有15個解，分別為(000011000110),(001101010011),(001110010101),(010100011100),(010111011010),(011001001111),(011010001001),(100101111100),(100110111010),(101000101111),(101011101001),(110001100000),(110010100110),(111100110011)和(111111110101)。

圖1 (4,1,5)卷積碼識別結果

選取第1、第2和第4個解，可得：

(20)

令m=5，帶入式(19)，可以建立如下方程組：

(21)

解方程，最終得到解向量為(101011110111111001111101)，因此G(x)=[1+x2+x4+x51+x+x3+x4+x51+x+x2+x51+x+x2+x3+x5]，與前面設置的參數相同，識別正確。

將本文方法、文獻[13]中基于矩陣分析的方法和文獻[16]中基于歐幾里得的識別方法進行抗誤碼性能對比。選取(3,1,5)卷積碼作為研究對象，生成1 000組碼字，加入錯誤比特后按不同方法進行識別。在每組誤比特率和識別方法組合下分別進行500次蒙特卡洛仿真，結果如圖2所示。可以看出，本文識別方法性能明顯優于其他2種方法。

圖2 不同識別方法抗誤碼性能對比圖

4 結束語

針對傳統(n,1,m)卷積碼盲識別方法對誤碼適應性較差的問題，基于粒子群算法提出了一種新的識別方法。該方法能有效完成各參數的識別，并具有較好的容錯性能。仿真結果表明，該方法在誤碼率低于10-2時能有效實現對常用卷積碼生成多項式的估計，且性能明顯優于傳統方法，能有效滿足通信偵察和自適應調制編碼等不同應用領域的要求。后續將針對其他碼率的卷積碼進行進一步的研究。