摘 要： 針對一般LDPC碼優化方法無法有效實現IRA碼度分布優化的問題，提出了特定約束下IRA碼度分布的優化方法。結合密度進化的高斯近似算法優化IRA碼度分布序列，提取了IRA碼檢驗矩陣構造的特定約束以改進差分進化算法。仿真結果表明，所設計的度分布序列的噪聲門限高且搜索時間比改進前減少30%。
關鍵詞： 低密度奇偶校驗碼； 度分布； 非規則重復累積碼； 差分進化
?
1962年，Gallager在其論文中首先提出了LDPC碼(Low-Density Parity-Check Codes)[1]，但當時并未受到重視，直到上世紀末被Mackay重新發現后，才掀起了一股研究與應用的熱潮。LDPC碼是一類由非常稀疏的奇偶校驗矩陣及Tanner圖定義的線性分組前向糾錯碼，它具有簡單的結構描述與硬件復雜度，可實現完全并行操作，有利于高速、大吞吐能力譯碼，譯碼復雜度亦比Turbo碼低，且具有更優良的基底（Floor）殘余誤碼性能，因此，LDPC在現代通信系統中得到了越來越多的應用。常用的非規則LDPC碼校驗矩陣的非系統比特部分為雙對角線結構，即IRA碼(Irregular Repeat-Accumulate codes)，這種結構的特點給度分布優化設計增加了更多約束。本文研究的重點是分析IRA碼構造方法，從中提取碼構造的特定約束，并轉化為度分布序列中各分量的相關性描述，以便消除相關性，利用差分進化DE(Differential Evolution)搜索最優化的度分布序列，同時提出了改進方法，在一定程度上加快了搜索速度和性能。
1 IRA碼的構造
1.1 度分布序列的定義
設LDPC碼的碼長為n，信息比特長度為k，校驗比特長度為m，則n=k+m，碼率R=k/n。λ(x):=Σλi xi-1代表非規則LDPC碼Tanner圖中變量節點(v-node)的度分布，ρ(x):=Σλi xi-1代表校驗節點(c-node)的度分布。這里，λi是度為i的變量節點連接的邊占Tanner圖中所有邊的比例，λi是度為i的校驗節點連接的邊占Tanner圖中所有邊的比例，最大的變量節點度為dv，最大的校驗節點度為dc。非規則LDPC碼度分布序列可表示為λ2λ3…λdv, ρ2 ρ3…ρdv)，容易驗證下列等式:
定義Nv(i)為度等于i的變量節點個數，Nc(i)為度等于i的校驗節點個數，推導得出:
1.2 IRA碼構造法
下面分析參數文獻[3]中IRA碼的構造方法。構造一個(n-1,k)非規則LDPC碼，其校驗矩陣為：
其中，H1是受度分布約束、隨機產生的稀疏矩陣，且不含重量為2的列；T包含了H中所有重量為2的列(即度為2的變量節點)。
在矩陣T最后添加度為1的列構成H2，產生一個新矩陣H，作為IRA碼的校驗矩陣，如式(6)、(7)所示[3]:
在校驗矩陣中添加度為1的列后，IRA碼度分布只有略微變化，且該列位于校驗比特位置，對BP(Belief-Propagation)迭代解碼后的誤碼率影響很小。從構造方法可知，IRA碼度分布受如下特殊約束：
約束：所有度為2的變量節點都分配給奇偶校驗比特，且度為2的變量節點個數剛好為m(包括度為1的列)。m為IRA碼的校驗比特長度。
通過推導，由(6)式得系統碼生成矩陣：
式中H2T為上三角矩陣，可用傳遞函數為1/1+D的差分編碼器實現，因此，IRA碼很容易在硬件上實現快速編碼。
對于已知碼率為R的IRA碼設計，設計約束實際上規定了度為2的變量節點個數和位置，結合(4)式，有:
又根據(1)式，有:
從一個dv+dc-6維各分量不相關的分布矢量(λ4…λdv-1, ρ2…ρdc-1)，可依據(9)～(12)式依次計算ρdv、λ2、λ3和λdv,從而唯一確定度分布序列。
2 密度進化的高斯近似和度分布優化
??? 密度進化理論是分析度分布序列噪聲門限值的強有力工具，然而該理論涉及很多卷積運算，運算量大。為了簡化計算，Sac-Young Chung等針對加性高斯白噪聲信道AWGN(Additive White Gaussian Noise channel)提出了密度進化的高斯近似分析方法。在消息獨立和消息密度高斯分布條件下，該方法僅分析消息密度高斯分布均值，極大地減少了計算量。這里列出高斯近似分析法的消息密度均值遞推公式:
使用(13)式計算消息概率密度函數，從而得到迭代后解碼誤比特率，若誤比特率小于預設值ε(如10e-6)，則適當增大σn2，直到誤比特率大于ε。經嘗試，求得度分布(λ,ρ)在誤比特率小于ε時的最大σn2，確定為該度分布的噪聲門限。
3 DE方法及改進
DE是一種并行搜索方法，能夠搜索連續空間非線性代價方程的全局極值。該方法有能力使搜索跳出局部極值點，避免錯誤的收斂。DE的特點在于產生測試參數矢量的方案。以DE實現IRA碼度分布序列優化的步驟如下，流程如圖 1所示。
?
?
(1) 初始化：確定度分布序列中參與DE的變量個數L，隨機產生Np個L維隨機矢量xi,g(0≤i≤Np-1，g為迭代次數)；
(2) 計算門限f(xi,g)，找出最大值，設門限最大的矢量為基本矢量xb,g(如圖中xb,g=xl,g)；
(3) 對于每一個矢量xi,g，在其他矢量中隨機選擇兩個矢量xr1,g和xr2,g，定義F為權重因子，以下式計算新矢量vi,g，vi=xb,g+F(xr1,g-xr2,g);
(4) 新矢量ui,g的每個分量以概率CR取vi,g的對應分量值，以概率(1-CR)取xi,g的對應分量值；
(5) 選擇：如果 f(ui,g)> f(xi,g)則xi,g+1=ui,g否則xi,g+1= xi,g；
(6) 停止準則：如果超過了最大迭代次數或所有矢量已經充分接近，則迭代結束；否則跳轉到第(2)步。
權重因子F對DE的影響很大，增大F會加快收斂速度，但容易收斂于局部極值點；減小F則效果相反。這里，F取0.8；測試矢量數Np取10L～30L；交疊參數CR對DE的影響比F小，它更像一種微調，取較大的CR會加快收斂速度，一般在[0.5,1]中取值。
使用DE搜索IRA碼的最優度分布序列，首先要消除度分布序列各分量的相關性，否則搜索到的結果無法滿足IRA碼設計的特定要求。1.2節最后指出dv+dc-6維的分布矢量(λ4…λdv-1, ρ2…ρdv-1)中各分量消除了相關性，并唯一確定度分布序列，因此，筆者在優化中使用該矢量。
DE搜索IRA碼的最優度分布序列相當耗時，特別是當dv和dc較大，即測試矢量維數較大時，差分進化的速度很難讓人滿意，根據一些先驗知識和測試結果，在不影響最終結果的前提下，改進了DE方法，加快了優化速度。
測試表明，DE的大部分時間消耗于第二步的門限計算上，因而，改進的主要目標是減少門限計算的時間，為此首先要減少DE測試矢量維數。
先假定在IRA碼的度分布序列中只有(λ2λ3λ4λdv, ρdv-1 ρdv)大于零，其他都為零，根據(9)～(12)式，去相關性之后的矢量為(λ4,ρdv-1)，矢量維數從dv+dc-6維銳減為2維。實驗結果表明，矢量每減少一維，DE的收斂時間大約減少一半，改進后DE可迅速收斂。我們稱這種維數削減的DE過程為“DE_FIRST”。一般來說，在dv不大時(如dv<10)結果已經很接近最優的度分布了，但當dv較大時結果距最優的度分布仍有一定差距，這時還要搜索更優的度分布。適當調整當前的最優矢量(λ2λ3λ4λdv, ρdv-1 ρdv)，在該矢量的一定范圍內隨機產生L=dv-2個矢量，并在此約束下隨機產生若干取值較小的矢量(λ5λ6…λdv,ρdv-2)組成dv-2維隨機矢量(λ4…λdv-1, ρdc-2， ρdc-1)，然后從DE的第二步開始繼續搜索。這里并沒有擴展(ρ2…ρdc-3)是因為將這些分量設為零幾乎不會影響優化度分布的結果。擴展后的隨機矢量唯一確定的度分布已經十分接近最優化的度分布了，所以DE的收斂速度比一開始就隨機產生dv-2維隨機矢量的DE快很多。我們稱維數擴展以后的差分進化過程為“DE_SECOND”。
通過分析大量優化結果和其他文獻給出的優化序列可以發現，λ4數值較小，大多取值在[0,0.2]內，ρdc-1也比ρdc小，一般取值在[0,0.4]。這樣，“DE_FIRST”的初始隨機矢量選擇范圍可以減小，在第一步中，矢量(λ4,ρdc-1)的兩個分量分別在上述兩個區間隨機產生。實驗證明，這樣做能夠加快搜索速度。
4 仿真結果
仿真參數設置如下：碼率為1/2；差分進化的Np=20L，F=0.8，CR=0.8。表1列出了用本文介紹的基于密度進化高斯近似的DE搜索方法得到的最優化度分布，同時還列出了參考文獻[4]優化得到的非規則LDPC碼度分布和參考文獻[5]同樣用密度進化高斯近似優化得到的非規則LDPC碼度分布。最后一行是度分布對應的噪聲門限。比較dv=20的噪聲門限可知，本文方法得到的最優化度分布優于參考文獻[5]中的最優化度分布，如圖2所示。由于優化后的非規則LDPC碼的Nv(2)一般略大于(11)式規定的值，因此在約束下搜索的IRA碼度分布中λ2比優化的非規則LDPC碼度分布中λ2小，如表1所示。若沒有IRA碼的設計約束，本文介紹的方法可以搜索到更好的度分布序列。表2是DE改進前后收斂時間及噪聲門限?滓的對比(仿真程序運行于1.5GHz PC機)，可知，改進前后優化的度分布噪聲門限很接近，而改進方法能夠節省大約30%的搜索時間。
?
本文通過分析IRA碼構造方法的特定約束，消除了度分布序列各分量之間的相關性，從而利用DE方法搜索具有更高噪聲門限的度分布序列，并利用先驗知識改進了DE方法，加快了搜索速度。這種方法也可以用來搜索其他構造方式下優化的度分布序列，對更廣泛的非規則LDPC碼優化設計具有一定的借鑒意義。
參考文獻
[1] ?GALLAGER R G. Low-density parity-check codes[J].IEEE Trans. Inform. Theory, August, 1962：21-28.
[2] ?JIN H, KHANDEKAR A, MCELIECE R. Irregular repeataccumulate codes[J]. in Proc. 2nd. Int. Symp. Turbo?Codes and Related Topics, Brest,France, Sept. 2000:1-8.
[3] ?YANG M, RYAN W E, LI Y. Design of efficiently?encodable moderate-length high-rate irregular LDPC
?codes[J]. IEEE Trans. Commun, 2004,52:564-571.
[4] ?RICHARDSON T, SHOKROLLAHI A, URBANKE R. Design of capacity-approaching irregular low-density paritycheck codes[J]. IEEE Trans. Inform.Theory, 2001,47(2):619-637.
[5] ?肖娟,王琳,鄧禮釗. 不規則LDPC碼的密度進化方法及門限值確定[J]. 電子與信息學報, 2005,27(4):617-620.