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

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

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

0 引 言

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

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

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

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

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

1 卷積碼識別數學模型

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

式中：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）表示反饋多項式。編碼過程可以用系統反饋形式表示：

編碼序列c經過數字調制等處理后，通過加性高斯白噪聲（additive white Gaussian noise，AWGN）信道傳輸，在接收端得到的解調軟判決序列為r＝（r0，r1，…，r n-1），其中r i＝｛ri，0，ri，1，…，ri，τ｝。以二進制相移鍵控（binary phase shift keying，BPSK）調制為例，編碼信息“0”被映射成調制符號“1”，編碼信息“1”被映射成調制符號“-1”，用數學形式表 示該映射過 程：si，t＝1-2c i，t。經過AWGN信道傳輸，接收端得到的解調軟判決信息為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具有如下形式的概率密度函數［27］：

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

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

生成矩陣對應元素為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）。求解生成矩陣的問題可以轉換成q的計算。

2 卷積碼參數識別算法

2.1 代價函數模型

根據式（5），可以推出：

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

進一步可以推出

展開得

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

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

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

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

為了更高效地估計生成矩陣，引入最優化方法的思想，利用指數函數構造代價函數模型：

定理1當q對應正確的生成矩陣時，f（q）取極小值。

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

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

（1）g i和g j中元素為0的位置對應于c i、c j中誤碼出現的位置；

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

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

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

2.2 算法描述

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

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

下面給出對代價函數求關于q的梯度f（q）的表達式：

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

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

步驟4令k＝k＋1，轉步驟1。

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

在計算過程中，會出現qi，l在［0，1］區間外的情況。當qi，l＞1時，令qi，l＝1；當qi，l＜0時，令qi，l＝0。迭代過程結束之后，當qi，l≥0.5時，令g i，l＝1；當qi，l＜0.5時，令g i，l＝0。

3 仿真實驗

3.1 代價函數仿真分析

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

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

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

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

3.2 算法的影響因素分析

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

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

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

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

在某些應用領域中，需要對較小的數據量進行識別，所以接下來考察不同的接收序列長度下算法的識別性能。本次仿真中待識別的對象為（2，1，6）卷積碼，設置迭代次數15次，蒙特卡羅實驗次數1 000次，仿真結果如圖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%以上。這是由于接收的信息比特增加后，解調軟判決信息也隨之增加，其統計特性可以更清晰地反映信道情況和編碼碼元的約束關系，算法可以正確識別出卷積碼參數的概率越高。

3.2.3 迭代次數對算法識別性能的影響

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

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

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

3.3 算法的適用性分析

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

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

表2 不同m對應的生成多項式Table 2 Generate matrix with respect to m

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

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

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

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

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

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

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

3.4 算法性能對比

3.4.1 識別性能對比

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

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

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

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

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

3.4.2 算法復雜度對比

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

表4 算法復雜度對比Table 4 Computational complexities of four algorithms

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

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

4 結 論

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