基于共軛梯度求解代價函數(shù)的卷積碼參數(shù)識別算法

陳增茂，陸 麗，孫志國，*，孫溶辰

（1.哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江 哈爾濱 150001；2.哈爾濱工程大學(xué)工業(yè)和信息化部先進船舶通信與信息技術(shù)重點實驗室，黑龍江 哈爾濱 150001）

0 引 言

糾錯編碼識別技術(shù)是在缺少編碼先驗信息的情況下，通過一些反推方法，根據(jù)接收序列恢復(fù)出原始的編碼參數(shù)，在深空通信、信息對抗等領(lǐng)域有著廣泛的應(yīng)用［1］。卷積碼作為一種非常重要的糾錯編碼方式［2］，自1955年由Elias提出以來，一直受到廣泛關(guān)注。由于卷積碼具有優(yōu)良的性能，其常用于構(gòu)造級聯(lián)碼和Turbo碼［3-4］，例如遞歸系統(tǒng)卷積（recursive systematic convolutional，RSC）碼通常作為Turbo碼的子碼，正確地識別出RSC碼的參數(shù)是識別Turbo碼參數(shù)的關(guān)鍵［5］。Turbo碼具有較好的糾錯能力，常工作于惡劣的信道環(huán)境中［6］，這就要求卷積碼參數(shù)識別算法也要具有很強的抗噪能力。但目前的研究現(xiàn)狀不足以實現(xiàn)低信噪比（signal to noise ratio，SNR）下卷積碼參數(shù)的盲識別，僅能在已知卷積碼的碼長、信息位長度、記憶長度、生成矩陣和碼字起點中的一種或多種的情況下，識別出剩余參數(shù)。于是本文重點研究根據(jù)先驗信息提高卷積碼參數(shù)識別算法的抗噪能力。

卷積碼參數(shù)識別算法根據(jù)接收序列的不同，可以分為利用解調(diào)硬判決序列的算法和利用解調(diào)軟判決序列的算法。解調(diào)硬判決序列僅利用了比特符號信息，丟棄了可靠度信息，對接收信息的利用不夠充分；而解調(diào)軟判決序列中不僅包含比特符號信息，還包括可靠度信息，充分利用這些可靠度信息可以大大提升算法的識別性能。

利用解調(diào)硬判決序列的算法有高斯直解法、快速合沖法［7］、歐幾里得法［8］、Walsh-Hadamard［9-11］變換（Walsh-Hadamard transform，WHT）法和主元消元法［12-16］等，其中WHT算法本質(zhì)上是一種窮舉算法，抗噪能力較強，但記憶長度的增加會導(dǎo)致計算量呈指數(shù)級別增大。

解調(diào)軟判決序列中包含比特符號信息和可靠度信息，充分利用可靠度信息可以提高算法的抗噪能力。文獻［17］提出對解調(diào)軟判決序列進行識別，首次將EM（expectationmaximization）算法引入到卷積碼參數(shù)識別中，但該算法的抗噪能力一般，且計算量較大。文獻［18-19］提出了一種基于對數(shù)似然比（log-likelihood ratio，LLR）的卷積碼參數(shù)識別方法，該算法將生成矩陣的識別問題轉(zhuǎn)化成求解含錯方程的問題，并且將方程成立的概率用來衡量解向量符合的程度，但對算法抗噪能力的提升有限。文獻［20-21］提出用校驗關(guān)系的平均似然差（likelihood difference，LD）代替LLR作為校驗結(jié)果正確性的度量，降低了算法的復(fù)雜度。但是，這些算法的抗噪能力都略差于利用解調(diào)硬判決序列的WHT算法。為了進一步挖掘解調(diào)軟判決序列提高算法抗噪能力的潛能，文獻［22］提出了一種基于最小二乘（least square，LS）代價函數(shù)的算法，顯著提高了算法的抗噪能力，但計算復(fù)雜度較高，在低SNR的環(huán)境下魯棒性相對較弱。為了克服這些缺點，文獻［23］改進了文獻［22］的算法，提出了一種基于最大余弦（maximum cosinoidal，MC）代價函數(shù)的方法。該方法的計算復(fù)雜度明顯降低，識別性能也有所提升，但是這些算法的抗噪能力僅與WHT方法相當(dāng)甚至略差，未充分發(fā)揮出解調(diào)軟判決序列可以提高算法抗噪能力的作用。

針對上述問題，本文繼續(xù)研究利用解調(diào)軟判決序列的卷積碼參數(shù)識別算法。首先，根據(jù)編碼序列和生成矩陣的約束關(guān)系構(gòu)造了一個基于指數(shù)函數(shù)的代價函數(shù)模型，將生成矩陣的識別問題轉(zhuǎn)換成代價函數(shù)極值的求解問題。進而，采用共軛梯度法［24］完成生成矩陣的識別。最終，通過仿真結(jié)果驗證了該算法的適用性，提升了算法在低SNR下的抗噪能力。

1 卷積碼識別數(shù)學(xué)模型

（n，k，m）卷積碼的編碼過程［25-26］用數(shù)學(xué)描述為

式中：x（D）＝［x0（D），x1（D），…，x k-1（D）］表示輸入的k路信息序列多項式向量；c（D）＝［c0（D），c1（D），…，c n-1（D）］表示輸出的n路編碼序列多項式向量；m表示記憶長度；G（D）表示卷積碼的生成矩陣。對于（n，1，m）卷積碼，G（D）＝［g0（D），g1（D），…，g n-1（D）］。其中，D表示延遲操作。

式中：τ表示編碼序列的時間長度；x i＝｛x i，0，x i，1，…，x i，τ｝表示信息序列；c i＝｛ci，0，ci，1，…，ci，τ｝表示編碼序列。

對于RSC碼，其編碼器是反饋編碼器。用g1（D），g2（D），…，g n-1（D）表示編碼器的前向生成多項式，g0（D）表示反饋多項式。編碼過程可以用系統(tǒng)反饋形式表示：

編碼序列c經(jīng)過數(shù)字調(diào)制等處理后，通過加性高斯白噪聲（additive white Gaussian noise，AWGN）信道傳輸，在接收端得到的解調(diào)軟判決序列為r＝（r0，r1，…，r n-1），其中r i＝｛ri，0，ri，1，…，ri，τ｝。以二進制相移鍵控（binary phase shift keying，BPSK）調(diào)制為例，編碼信息“0”被映射成調(diào)制符號“1”，編碼信息“1”被映射成調(diào)制符號“-1”，用數(shù)學(xué)形式表 示該映射過 程：si，t＝1-2c i，t。經(jīng)過AWGN信道傳輸，接收端得到的解調(diào)軟判決信息為r i，t，ri，t＝si，t＋w i，t＝1-2ci，t＋w i，t，其中w i，t表示AWGN，w i，t～N（0，σ2）。由于信道噪聲與傳輸信號是相對獨立的，因此ri，t服從均值為s i，t、方差為σ2的高斯分布：ri，t～N（si，t，σ2）。因此，ri，t具有如下形式的概率密度函數(shù)［27］：

一般情況下，發(fā)送的信息是隨機的，si，t的值為“1”和“-1”的概率相同，均為1／2。在給定si，t的條件下，ri，t的概率密度函數(shù)為

根據(jù)貝葉斯定理，可以得到如下形式的條件概率密度函數(shù)：

生成矩陣對應(yīng)元素為1的概率用qi，l表示，則有P（g i，l＝1）（i＝0，1，…，n-1；l＝0，1，…，m）。

用q＝（q0，q1，…，q n-1）表示生成矩陣每個元素為1的概率，其中q i＝（qi，0，qi，1，…，qi，m）。求解生成矩陣的問題可以轉(zhuǎn)換成q的計算。

2 卷積碼參數(shù)識別算法

2.1 代價函數(shù)模型

根據(jù)式（5），可以推出：

式中：i，j＝0，1，…，n-1，i≠j。

進一步可以推出

展開得

下面討論如何利用解調(diào)軟判決序列r＝（r0，r1，…，r n-1）表示式（16）。首先給出二元域中的一些結(jié)論［28］。令u1和u2是二元域中的兩個獨立隨機變量，有

將式（18）推廣，u1，u2，…，us均為二元域的獨立隨機變量，得

式（16）中的ci，t-u和c j，t-u是編碼序列中的比特元素，取值為0或1，可當(dāng)作常量；g i，u和g j，u是待識別的變量，取值也是0或1，可看作二元域中互相獨立的隨機變量。因此，不考 慮編碼序列 中比特 間 的 相 關(guān) 性，ci，t-u g j，u和c j，t-u g i，u可視為二元域中互相獨立的隨機變量。故可將式（19）應(yīng)用到式（16）中，可以推出：

該式是關(guān)于q的校驗方程，可以用來衡量q滿足該式的程度。由式（15）和式（16）可知，接收序列無誤碼時，與正確的生成矩陣相對應(yīng)的q將使得的值為1；接收序列含誤碼時，q表示的生成矩陣對應(yīng)元素的概率越接近正確值，校驗方程的符合度越高的值越接近1。

為了更高效地估計生成矩陣，引入最優(yōu)化方法的思想，利用指數(shù)函數(shù)構(gòu)造代價函數(shù)模型：

定理1當(dāng)q對應(yīng)正確的生成矩陣時，f（q）取極小值。

證明當(dāng)q表示的生成矩陣對應(yīng)元素為1的概率取值正確時，取極大值1，由于指數(shù)函數(shù)是單調(diào)遞增函數(shù)，exp（）也取極大值，多個極大值進行求和取負的運算后，f（q）取極小值。證畢

于是，將生成矩陣的識別問題轉(zhuǎn)化成求解f（q）極小值的問題，即

（1）g i和g j中元素為0的位置對應(yīng)于c i、c j中誤碼出現(xiàn)的位置；

（2）g i和g j中元素為1的位置對應(yīng)于c i、c j中含有誤碼的個數(shù)為奇數(shù)個。

在誤碼率為Pe的條件下，設(shè)其成立的概率為P0，則有：

式中：d為生成矩陣g的碼重；C表示組合數(shù)運算符。則

2.2 算法描述

對于代價函數(shù)的求解，采用共軛梯度法［29-30］。該方法的基本思想是在每一次迭代時利用當(dāng)前點處最速下降方向-y k與算法的前一個方向d k-1的線性組合作為當(dāng)前的搜索方向，即

再利用當(dāng)次迭代點q k和已經(jīng)確定的搜索方向計算下一次迭代點q k＋1，即

下面給出對代價函數(shù)求關(guān)于q的梯度f（q）的表達式：

式中：i＝0，…，n-1；0≤l≤m

利用共軛梯度法求解代價函數(shù)極小值的算法步驟如下：

步驟4令k＝k＋1，轉(zhuǎn)步驟1。

RSC碼的生成矩陣的第一個元素一般為1，其他元素未知。因此，在迭代過程中設(shè)置q集的初始值為

在計算過程中，會出現(xiàn)qi，l在［0，1］區(qū)間外的情況。當(dāng)qi，l＞1時，令qi，l＝1；當(dāng)qi，l＜0時，令qi，l＝0。迭代過程結(jié)束之后，當(dāng)qi，l≥0.5時，令g i，l＝1；當(dāng)qi，l＜0.5時，令g i，l＝0。

3 仿真實驗

3.1 代價函數(shù)仿真分析

代價函數(shù)的正確性對后續(xù)生成矩陣的識別具有重要影響，故本節(jié)研究不同SNR下代價函數(shù)f（q）的變化情況，驗證其正確性。分別對利用解調(diào)硬判決數(shù)據(jù)和解調(diào)軟判決數(shù)據(jù)的代價函數(shù)進行仿真，并對其進行歸一化處理。本次仿真中選取的卷積碼的參數(shù)如表1所示，得到仿真結(jié)果如圖1所示。

表1 選取的卷積碼的參數(shù)Table 1 Parameters of the selected convolutional codes

圖1 代價函數(shù)的變化情況Fig.1 Change of cost function

從仿真結(jié)果可以得知，隨著信噪比的增加，歸一化f（q）的值逐漸接近1，而無誤碼時歸一化的值等于1。從圖1中還可以看出：利用解調(diào)軟判決序列情況下歸一化代價函數(shù)的值與利用解調(diào)硬判決序列的值變化趨勢一致，且明顯大于利用解調(diào)硬判決序列的歸一化f（q）值。這說明本文充分利用了解調(diào)軟判決序列的可靠度信息，且構(gòu)造的代價函數(shù)是正確的。

3.2 算法的影響因素分析

3.2.1α對算法識別性能的影響

α決定了算法的收斂速度，在一定程度上會影響算法的性能。正確選取α的值能夠提升算法的性能。對不同α下算法的識別性能進行分析，待識別的卷積碼為（2，1，6）卷積碼，其生成多項式為g0（D）＝1＋D2＋D3＋D5＋D6，g1（D）＝1＋D＋D2＋D3＋D4＋D6，以下仿真中皆選用該卷積碼作為實驗對象。仿真過程中設(shè)置接收序列長度為4 000 bit，迭代次數(shù)為15次，蒙特卡羅實驗次數(shù)為1 000次。仿真結(jié)果如圖2所示。由圖2可見，低SNR下，0.004≤α≤0.007時，算法的識別性能最佳，當(dāng)α＞0.007時，識別正確率逐漸下降，原因在于α過小影響收斂速度，α過大易錯過最佳解，故可以在仿真過程中選取α＝0.005。在后續(xù)仿真中，選取α＝0.005。

圖2 α對算法識別性能的影響Fig.2 Impact ofαon performance of the proposed algorithm

3.2.2 接收序列長度對算法識別性能的影響

在某些應(yīng)用領(lǐng)域中，需要對較小的數(shù)據(jù)量進行識別，所以接下來考察不同的接收序列長度下算法的識別性能。本次仿真中待識別的對象為（2，1，6）卷積碼，設(shè)置迭代次數(shù)15次，蒙特卡羅實驗次數(shù)1 000次，仿真結(jié)果如圖3所示。

圖3 接收序列長度對算法識別性能的影響Fig.3 Impact of the length of received sequence on performance of the proposed algorithm

由圖3可見，接收序列長度對算法的識別性能有一定的影響，隨著接收序列長度的增加，算法的識別性能也隨之提升，在SNR＝5 dB且接收序列長度大于1 000 bit的條件下，算法的識別正確率能達到85%以上。這是由于接收的信息比特增加后，解調(diào)軟判決信息也隨之增加，其統(tǒng)計特性可以更清晰地反映信道情況和編碼碼元的約束關(guān)系，算法可以正確識別出卷積碼參數(shù)的概率越高。

3.2.3 迭代次數(shù)對算法識別性能的影響

本節(jié)分析不同迭代次數(shù)下算法的識別性能。仿真中待識別的是（2，1，6）卷積碼，接收的序列長度為4 000 bit，蒙特卡羅實驗次數(shù)為1 000次，仿真結(jié)果如圖4所示。

圖4 迭代次數(shù)對算法識別性能的影響Fig.4 Impact of iterations on performance of the proposed algorithm

由圖4可見，迭代次數(shù)達到10次時，生成矩陣基本收斂到了正確值。且在低SNR下，迭代次數(shù)對算法的影響比較明顯。原因在于，信道情況較為惡劣時，每迭代一次可以更加逼近極小值，迭代次數(shù)越多，越能收斂到極小值；信道環(huán)境較好時，誤碼較少，迭代5次便能收斂到極小值。

3.3 算法的適用性分析

3.3.1 記憶長度m對算法識別性能的影響

本節(jié)研究記憶長度m對算法識別性能的影響。本次仿真選取n＝2的卷積碼為研究對象，選擇的記憶長度m分別為2、3、4、5、6，不同m對應(yīng)的生成多項式如表2所示。仿真條件為：接收序列長度4 000 bit，迭代次數(shù)15次，蒙特卡羅實驗次數(shù)1 000次，得到的仿真結(jié)果如圖5所示。

表2 不同m對應(yīng)的生成多項式Table 2 Generate matrix with respect to m

圖5 m對算法識別性能的影響Fig.5 Impact of m on performance of the proposed algorithm

從仿真結(jié)果可以得知，m越大，算法的識別正確率隨之降低，尤其在低SNR的情況下。這是因為隨著卷積碼編碼記憶長度的增加，算法需要識別的參數(shù)隨之增加，識別難度也隨之增大。

3.3.2 碼率對算法識別性能的影響

當(dāng)碼率變化時，需要識別的參數(shù)也會發(fā)生變化，所以碼率對算法的影響也需要進行考察。本次仿真中分別對1／2、1／3、1／4碼率的卷積碼進行識別，不同碼率對應(yīng)的生成多項式如表3所示。仿真條件設(shè)置為：接收序列長度4 000 bit，迭代次數(shù)15次，蒙特卡羅實驗次數(shù)1 000次，得到的仿真結(jié)果如圖6所示。

表3 不同碼率對應(yīng)的生成多項式Table 3 Generate matrix with respect to rate

圖6 碼率對算法識別性能的影響Fig.6 Impact of rate on performance of the proposed algorithm

從圖6中可以看出，在低SNR下，碼率對算法的識別性能影響較大，SNR增加后，碼率對算法的性能幾乎沒有影響。這是由于信道環(huán)境比較惡劣時，需要識別的參數(shù)增加必然會導(dǎo)致識別正確率降低；而當(dāng)信道環(huán)境較好時，解調(diào)軟判決序列的可靠性較高，參數(shù)增加對算法識別性能的影響較小。

3.4 算法性能對比

3.4.1 識別性能對比

本文提出的算法是基于最優(yōu)化方法，目前基于最優(yōu)化方法的算法有：LS算法、MC算法等，接下來對比本文算法與這些算法的識別性能。

上述算法均對解調(diào)軟判決數(shù)據(jù)進行參數(shù)識別，為了全面對比算法的性能，將本文算法與利用解調(diào)硬判決數(shù)據(jù)的算法進行性能對比，其中WHT算法是識別性能最優(yōu)的，故選取該算法與本文提出的算法進行對比仿真。

本次仿真中選取（2，1，4）RSC碼為研究對象，其生成多項式為g0（D）＝1＋D3＋D4，g1（D）＝1＋D＋D2＋D4。仿真條件為：接收序列長度4 000 bit，蒙特卡羅實驗次數(shù)1 000次，仿真結(jié)果如圖7所示。仿真過程中設(shè)置本文算法的迭代次數(shù)為15次，LS算法的最大迭代次數(shù)為50次，MC算法的迭代次數(shù)為20次。

圖7 本文算法與其他算法的性能對比Fig.7 Performance comparison of four algorithms

由圖7可見，在-3～3 dB SNR內(nèi)，本文提出的算法的識別性能明顯優(yōu)于其他算法。原因在于，本文構(gòu)造的代價函數(shù)在極值的周圍變化更加陡峭，且采用了具有Q-超線性收斂速度［30］的共軛梯度法，搜索方向更準(zhǔn)確、搜索速度更快，避免了文獻［23］中最速下降法越接近極值點迭代效果越差的情況。

3.4.2 算法復(fù)雜度對比

將本文算法的復(fù)雜度與其他算法進行比較，比較結(jié)果如表4所示。

表4 算法復(fù)雜度對比Table 4 Computational complexities of four algorithms

表4中，n表示卷積碼的碼長，m表示記憶長度，τ表示接受序列長度，μ表示算法的迭代次數(shù)，N表示所需Hadamard矩陣的行數(shù)，N＝2l，l≥2（m＋1）。

由表4可見，與利用解調(diào)軟判決數(shù)據(jù)的算法相比，該算法的迭代次數(shù)減少，計算復(fù)雜度有所降低；與利用解調(diào)硬判決數(shù)據(jù)的算法進行對比，WHT算法的計算復(fù)雜度隨著記憶長度m的增加呈指數(shù)級別增加，且占用的計算機內(nèi)存較大，而本文算法呈平方級別增加，占用的計算機內(nèi)存較小。

4 結(jié) 論

本文利用RSC碼碼元間的線性約束關(guān)系構(gòu)造了一個新型的基于指數(shù)代價函數(shù)的參數(shù)識別模型，與現(xiàn)有的代價函數(shù)模型有所區(qū)別的是，本文構(gòu)造的代價函數(shù)在極值的周圍變化更加陡峭，方便搜索極值。最后，使用共軛梯度法實現(xiàn)代價函數(shù)極值的求解。仿真結(jié)果證明本文提出的算法收斂速度快，在迭代次數(shù)達到10次時便能收斂到最優(yōu)解。與現(xiàn)有算法相比，該算法在低SNR下抗噪能力更強，且保持較低的計算復(fù)雜度。但本文目前只討論了一些記憶長度較短的卷積碼，如何在記憶長度較長時確保較強的抗噪能力和低計算復(fù)雜度，將作為下一步的研究工作。