一種短碼長下最優LDPC碼的啟發性搜索算法

摘要：圍長分布是影響低密度校驗碼譯碼性能的重要因素。基于Tanner圖的樹結構展開，對啟發式搜索最優LDPC碼的算法進行了仿真。通過仿真實驗結果分析了圍長分布的變化對LDPC碼譯碼性能的影響，同時分析了平均圍長與譯碼性能的關系。該算法有助于對復雜性要求較嚴的短碼的設計及應用。

關鍵詞：LDPC碼 Tannr圖 圍長分布 啟發式搜索

0 引言

低密度校驗(LDPC)碼[1]由Gallager于1962年提出，并于上世紀90年代中期被重新發現并推廣。LDPC碼由于具有逼近Shonnon限的優越性能和低的譯碼復雜度而受到人們的普遍關注，成為目前最具前景的糾錯編碼技術之一。LDPC碼在結構上可用二部圖來表示，稱為Tanner圖[2]。Tanner圖由變量結點和校驗結點構成(如圖1所示)。特別是短環會影響LDPC碼譯碼迭代次數，降低迭代譯碼收斂速度，Tanner圖中最短環的長度稱為該Tanner圖的圍長。對于等碼長LDPC碼來說，由于圍長不同其譯碼性能差異也會很大。根據該理論，用Mackay2A[3]方法構造隨機矩陣，然后以樹結構形式展開求其平均圍長，在隨機生成的碼中求出平均圍長最大的碼，最后與其它隨機碼比較譯碼性能差異。分析平均圍長對LDPC碼譯碼性能的影響。

1 圍長及圍長分布

按照Mackay2A方法構造隨機矩陣，然后轉化為相應的Tanner圖，按樹結構形式展開，計算其圍長及圍長分布。構造稀疏隨機校驗矩陣m×n規則如下[3](如圖1所示)：

①把矩陣m×n分成左右兩個子矩陣m×（m/2）和m×（n-m/2）；

②子矩陣m×（m/2）每列‘1’的個數是2，由上下兩個對角子矩陣組成；

③子矩陣m×（n-m/2）每列‘1’的個數是3；

④矩陣m×n中任意兩列之間在同一行的位置1的個數不大于1，即保證不存在4環；

⑤矩陣m×n中每行‘1’的數目盡可能一致；

一般地，圍長指圖中最短環的長度，這里意思擴大為節點的圍長[4]，節點v的圍長指通過v的最短環的長度，計算變量節點圍長的基本思想為：將Tanner圖中以某一變量結點為根節點按樹結構形式展開，樹的偶數層由校驗結點組成，樹的奇數層由變量結點組成，當展到樹中某層（k層）出現相同結點且為根結點的不同孩子時就會構成最短環即該變量結點的圍長，大小為2k，如圖1（右邊）所示，變量節點v1的圍長為6。圍長分布則是指圍長為l的變量節點占所有變量節點N的比率。

圍長分布是影響迭代譯碼性能的一個重要因素。對于一個無環TG圖[5]，采用基于置信傳播BP的迭代譯碼算法具有良好性能。然而對于有環TG圖來說，從一個變量結點傳播消息然后回到該結點，結點的圍長就是所傳播最短路徑的長度，即最小迭代譯碼次數。由于圍長的存在使得信息不能傳播到圖的所有結點，降低了迭代譯碼傳遞消息的可靠性及收斂速度或使其無法收斂，嚴重影響譯碼性能。為了提高譯碼性能，需要使變量節點的圍長盡可能地大，即使較多變量節點有較大圍長。

2 基于啟發式的最優碼搜索算法

要在很多等長碼中搜索最優碼，即搜索最大平均圍長碼，必須先計算出碼中每個變量節點的圍長，然后求出每個碼的圍長分布和平均圍長，計算出隨機生成的q個碼的圍長分布的平均值及標準差，最后從q個碼中選出圍長平均值最大的碼，以便分析其碼的性能。具體算法描述如下所示：

①初始化i=1，j=1；

②構造碼長為N的隨機矩陣，相應的Tanner圖為G，G有n個變量節點為v1，v2，…，vn；

③將G以變量節點vj為根節點按樹結構展開，當展到樹中某層（k層）出現相同結點且為根節點的不同孩子時就會構成該變量結點的圍長，圍長為2k；把圍長依次存放在一個大小為n的數組中；j++，若j≤n，轉向②繼續；

④計算該碼的圍長分布gi（l），l=4，6，…，lmax，lmax是Tanner圖中最大圍長，平均圍長 ；并記錄到大小為n的數組中。 i++，若i

⑤求出k個碼中最大圍長平均值gmax，并把該碼記錄下來；

⑥計算k個碼圍長分布的平均值：

及圍長分布的標準差： ；

這個算法的復雜度較低而且特別適合分組長度較低的碼。容易計算出分組長度為n的碼的圍長分布的復雜度是O（n2）

3 仿真實驗結果及分析

3.1 碼長與圍長分布的關系

利用2.1節構造隨機矩陣的方法構造四類碼，碼率都是1/3，碼長分別為：960，1920，5100和11100位。每類隨機生成2000個碼，具有相同的TG度序列。利用上節算法可以計算出每類碼的圍長分布的平均值（即每類2000個碼圍長分布的平均值），圍長分布的標準差STD（即標準偏移量）和平均圍長的柱狀分布圖（如圖2所示）從左到右依次是碼長為：960，1920，5100和11100位。

可以看出，對于給定的度序列，碼長越長，最大平均圍長就越大，同時Tanner圖中出現較大的圍長的節點就越多，圍長分布的變化幅度(標準偏移量)也越小。基于圍長分布與LDPC碼的置信傳播譯碼性能的關系，可以尋找最大平均圍長的碼，它要比隨機選擇的碼性能好得多。

3.2 圍長分布對碼性能的影響

對于相同碼長和相同度序列的碼，它們的性能差異也很大，僅僅通過反復試驗來尋找最優碼的代價也相當大的，解決這個問題，可以選擇最優圍長分布的碼，即最高平均圍長的碼。

把這種方法運用在MPEG-2和ATM包中傳輸的兩類LDPC碼，碼長分別為3480和1268位，信息位長度分別為1504和456位，每類碼包含2000個碼字，具有相同的TG度序列，圖3（上）給出了兩類碼平均圍長的柱狀圖，從中選擇最大平均圍長（分別為9.455和9.351）的碼和隨機選擇（圍長分別為9.198和8.779）的碼。分別模擬仿真出最大平均圍長碼和隨機選擇碼的誤比特率（BERs）和誤信息率（MERs），如圖3（下）所示，左邊為碼長為3480比特位的最大平均圍長碼和隨機選擇碼的BERs和MERs的模擬仿真圖，右邊為碼長為1268比特位的最大平均圍長碼和隨機選擇碼的BERs和MERs模擬仿真圖，實線表示選擇碼的BERs和MERs，虛線表示隨機碼的BERs和MERs。

從圖中可以看出，兩類碼的隨機碼在錯誤率曲線上出現了平層效應，降低了圖的連通性，嚴重影響了高信噪比（SNRs）下碼的性能。而選擇碼避免了平層效應，很大程度上提高了高信噪比（SNRs）下碼的性能。再隨機選取幾組碼進行測試，它們的性能都要比平均圍長最大的碼的性能差，最大平均圍長碼具有較好的譯碼性能，卻沒有以增加其復雜度為代價，迭代譯碼的平均次數幾乎和隨機選擇的碼是一樣的。

4 結束語

本文應用啟發式搜索的思想，利用圍長分布來搜索最優LDPC碼，實驗證明具有較大平均圍長的碼可以避免錯誤平層，具有較好的譯碼性能。圍長分布是碼的Tanner圖的一個重要聯系實體，它把置信傳播算法的性能和圖的結構聯系起來，很大程度上可以提高碼的性能，雖然這里僅僅用平均圍長作為選擇標準，但圍長分布的其它相關標準也可能會被利用到，比如Tanner圖中最小圍長碼所占的比率對研究碼的性能也是非常有用的。

參考文獻：

[1]Gallager R G. Low-density Parity-check Codes[J].IRE Trans Information Theory，1962，8(1):21-28..

[2]Tanner R M.A Recursive Approach to Low Complexity Codes[J].IEEE Trans on Information Theory，1981.

[3]D.J.C.lacKay and R.M.Neal，“Near Shannon limit performance of low density parity check codes，”Electron.Lett.，vol.33，no.6，pp. 457-458，Mar.1997.

[4]Mao，Y.，and Banihashemi，AH.:‘A heuristic search for good low-density parity-check codes at short block lengths'.Proc.IEEE Int.Conf.Communications，Helsinki，Finland，2001，Vol.1，pp.11-14.

[5]T.Richarson and R.Urbanke， “The capacity of low density parity check codes under message-passing decoding，”submitted to IEEE Trans.Inform.Theory，1998.