易 丹

（武漢交通職業(yè)學(xué)院，湖北 武漢 430065）

0 引言

低密度奇偶校驗（LDPC）碼最先被Gallager發(fā)明，由于當(dāng)時計算機條件的限制，沒有引起人們的關(guān)注。后來在上個世紀(jì)九十年代初被MacKey等重新發(fā)現(xiàn)，他們通過系統(tǒng)仿真發(fā)現(xiàn)LDPC碼的性能超過以前發(fā)現(xiàn)的各種編碼，比Turbo碼更接近香農(nóng)限，因此引起了通信研究者的極大關(guān)注，現(xiàn)在已經(jīng)成為編碼領(lǐng)域一項熱門的研究方向。Thmos J．Richardson等提出了采用密度進化算法優(yōu)化非規(guī)則LDPC的度分布對［1］，HuXiaoYu等提出了采用PEG算法增大校驗矩陣的圍長［2］，Tao Tian等提出了采用ACE算法增大校驗矩陣中環(huán)之間的連通性［3］，雖然這些算法可以提高非規(guī)則LDPC的性能，降低它的誤碼平臺，但是由它們設(shè)計出來的非規(guī)則LDPC不易硬件實現(xiàn)。隨后，2005年，Seho Myung等提出了一種易于硬件實現(xiàn)的高性能的QC－LDPC，使得LDPC的硬件應(yīng)用成為可能［4］，現(xiàn)在這種結(jié)構(gòu)化QC－LDPC已經(jīng)被IEEE802．16e和IEEE802．11n推薦采用。但是，Seho Myung等沒有提出任意碼率QC－LDPC的設(shè)計方法。本文提出了一種任意碼率QCLDPC的設(shè)計方法，編碼復(fù)雜度和IEEE802．16e相同，但是誤碼平臺更低。

1 易于硬件實現(xiàn)的QC－LDPC碼的結(jié)構(gòu)

Seho Myung，Kyeongcheol提出了一種結(jié)構(gòu)化的QC－LDPC碼［5］，這種LDPC碼編碼復(fù)雜度和編碼碼長呈線性關(guān)系，并且在譯碼過程中可以并行執(zhí)行并節(jié)省存儲空間，所以非常適合于硬件實現(xiàn)。另外，仿真結(jié)果顯示這種LDPC碼的性能優(yōu)良。它的校驗矩陣H的結(jié)構(gòu)如下式（1）所示。

校驗矩陣包含兩部分：結(jié)構(gòu)自由的H1和結(jié)構(gòu)相對固定的HP。假設(shè)H有M行N列，QC－LDPC碼的碼率R＝M／N，則要求HP有M行和M列，其中度為2的列數(shù)為M－1，度為3的列數(shù)為1。HP所占的列數(shù)決定了QC－LDPC碼得碼率大小，這種結(jié)構(gòu)化的設(shè)計可以使這種QC－LDPC碼的編碼復(fù)雜度和編碼長度呈線性關(guān)系。HP中的I表示一個大小為［L，L］的單位矩陣；0表示大小為［L，L］的零矩陣；Px表示一個單位置換序列，這個序列是通過將I循環(huán)右移x次得到。

2 碼率自由且低誤碼平臺的QC－LDPC碼的設(shè)計

設(shè)計結(jié)構(gòu)化QC－LDPC碼的一般步驟是：首先通過密度進化算法得到一個好的度分布對，然后根據(jù)這個度分布對搜索到圍長盡量大的校驗?zāi)妇仃?，最后使用大小為［L，L］的單位矩陣、0矩陣或者Px填充校驗?zāi)妇仃?。在這個過程中H的度分布由碼率的大小決定，同時，度分布對的好壞，校驗矩陣的最小圍長（girth）以及環(huán)之間的連通性決定最后得到的QC－LDPC碼的性能。所以本文通過優(yōu)化度分布對、最小圍長以及環(huán)之間的連通性來得到碼率自由且低誤碼平臺的QC－LDPC碼。

2．1 改進的密度進化算法

原始的密度進化算法復(fù)雜度非常高，并且只給出了非規(guī)則LDPC的度分布對的求法［6］。但是我們需要高效率的優(yōu)化結(jié)構(gòu)化QC－LDPC的度分布對，所以我們需要改進原有的密度進化算法，使得它的計算復(fù)雜度降低，并且更重要的是能夠優(yōu)化結(jié)構(gòu)化QC－LDPC的度分布對。首先，我們采用高斯近似（Gaussian Approximation）來求給定度分布對的門限值。高斯近似是文獻［1］提出的門限值求法的一種近似，可以大大的節(jié)省計算時間，但是精度的損失卻很小。然后使用差分進化（Differential Evolution）完成全局搜索，得到門限值最大的那個度分布對［7］。這里我們需要改進差分進化的全局約束條件，使優(yōu)化的度分布對滿足結(jié)構(gòu)化QC－LDPC校驗矩陣的要求。Seho Myung，Kyeongcheol等提出的全局約束條件［8］僅包含下面的式（2）－（4）。

dv（dc）表示變量（校驗）節(jié)點的最大的度。λi（ρj）代表從變量（校驗）節(jié)點i（j）發(fā)出的邊占Tanner圖中所有的邊的比例。除此了上面三個約束條件外，本文通過分析HP的結(jié)構(gòu)，還提出了其它的兩條約束條件，如下面的式（5）、（6）所示。

Pv2表示度為2的變量節(jié)點在所有變量節(jié)點中所占的比例，Pv3表示度為3的變量節(jié)點在所有變量節(jié)點中所占的比例。添加這兩個全局搜索的約束條件后，可以使優(yōu)化后的度分布對滿足H的要求。在第四部分的仿真結(jié)果中，我們列出了改進的密度進化算法得到的四組不同碼率的度分布對。

2．2 改進后的PEG算法

在校驗?zāi)妇仃囋O(shè)計過程中，要求母矩陣包含的短環(huán)盡量少，最小圍長盡量大，這樣可以使最后的校驗矩陣的圍長較大［9］。Hu XiaoYu提出了一種應(yīng)用于非規(guī)則LDPC碼的PEG算法，這個算法主要的思想是按照度分布對，通過依次在校驗節(jié)點和變量節(jié)點之間添加邊連接，每次新邊的位置要求使Tanner圖的圍長達到最大［10］，最后得到大圍長的校驗矩陣。我們可以使用PEG算法簡單快速的得到校驗?zāi)妇仃?，但是PEG算法不能直接應(yīng)用于結(jié)構(gòu)化QC－LDPC，這里需要將PEG算法做出改進。由于校驗矩陣中只有HP部分的結(jié)構(gòu)固定，所以改進后的PEG算法首先按照度分布對要求生成HP，然后使用原來的PEG算法生成H1即可。改進后的PEG算法如下所示。

改進后的PEG算法：

2．3 實施增大圍長和ACE約束

TaoTian等學(xué)者發(fā)現(xiàn)，LDPC碼的性能不僅受環(huán)長的影響，而且也受到環(huán)之間的連通性的影響［11］。有可能一個LDPC碼的Tanner圖中包含比較多的短環(huán)，但是這些短環(huán)之間的連通性良好，從而導(dǎo)致這個LDPC碼的糾錯性能沒有預(yù)期的那么差。環(huán)之間的連通性使用ACE值來表示，一個長為2l的環(huán)的ACE值為，其中di表示此環(huán)中第i個變量節(jié)點的度。度為d的單個變量節(jié)點的ACE值為d－2，單個校驗節(jié)點的ACE值為0。當(dāng)使用置換序列填充校驗?zāi)妇仃嚂r，我們在使校驗矩陣的圍長盡量大的同時，也要使環(huán)之間的ACE盡量大，特別是那些度為2和3組成的環(huán)。所以在置換序列填充校驗?zāi)妇仃嚨臅r候，不僅要考慮使用文獻［4］中的方法盡量增大H的圍長，并且也要使用文獻［3］的方法消除那些ACE值非常小的關(guān)鍵環(huán)。我們使用圖1和2來說明這些關(guān)鍵環(huán)在H中的分布。兩圖取自H的一個片段，包含部分的H1和全部的Hp。圖1中使用實線勾畫出了兩個環(huán)，環(huán)長分別為8和4，它們是由度為2、3的變量節(jié)點形成的環(huán)，ACE值都為2。圖2也使用實線勾畫出兩個環(huán)，環(huán)長分別為10和6。它們是由度為2、3的變量節(jié)點形成的環(huán)，ACE值也為2。

圖1 環(huán)長為8和4的關(guān)鍵環(huán)

圖2 長為10和6的關(guān)鍵環(huán)

由于這些環(huán)的ACE值特別小，只有2，所以它們與其它環(huán)的連通性很差，在譯碼過程中這些環(huán)容易產(chǎn)生錯誤不可糾的情況，所以我們在隨機產(chǎn)生Px填充校驗?zāi)妇仃嚂r應(yīng)該消除這些關(guān)鍵環(huán)。根據(jù)文獻［2］，如果圖1和2中長為的環(huán)被置換序列填充后形成的鏈條，當(dāng)10modL時則可以消除這些關(guān)鍵環(huán)。

3 仿真結(jié)果

3．1 好的度分布對

表1 四種不同碼率的好的度分布對

表1是通過改進后的密度進化算法，搜索到1／2、2／3、3／4、5／6四種不同碼率的好的度分布對，并計算它們對應(yīng)的門限值。從下表我們可以看到這些門限值非常接近香農(nóng)限。在搜索過程中，我們設(shè)定［M，N］分別為［12，24］、［8，24］、［6，24］和［4，24］。

3．2 性能對比

為了比較使用本文方法設(shè)計的QC－LDPC碼和IEEE802，16e中QC－LDPC碼的性能，我們分別設(shè)計碼率為1／2、2／3、3／4、5／6，碼長為2304的四種QC－LDPC碼。仿真的信道為二進制輸入加性高斯白噪聲（Binary－InputAdditiveWhite－GaussianNoise，BIAWGN）信道，譯碼方法為BP譯碼算法，迭代次數(shù)為50次，曲線上的每個點的仿真幀數(shù)為30000幀。從圖3我們可以看到，采用本文提出的方法設(shè)計的QC－LDPC碼的誤碼平臺更低，并且當(dāng)碼率越小時，這種優(yōu)勢越明顯。

圖3 提出的QC－LDPC碼與IEEE802．16e中的QC－LDPC碼的性能對比

4 結(jié)束語

本文改進了密度進化算法和PEG算法，使它們能夠應(yīng)用于結(jié)構(gòu)化QC－LDPC中，可以生成高性能、碼率自由的可硬件實現(xiàn)LDPC碼。并且在填充校驗?zāi)妇仃囘^程中實施增大圍長和ACE的約束，使得QC－LDPC碼的誤碼平臺降低，性能優(yōu)于IEEE802．16e中的QC－LDPC碼。本文提出的設(shè)計方法可以應(yīng)用在無線通信系統(tǒng)中，提高通信系統(tǒng)的抗干擾性。

［1］［6］Thmos J．Richardson，M．Amin Shokrollahi，Rüdiger L．Urbanke．Density of Capacity－Appro aching Irregular Low－Density Parity－Check Co des［J］．IEEE Transaction on Information Theory，2001，（2）：619－637．

［2］［10］Hu XiaoYu，E．ELEFTHERIOU，D．－M．Arn old．Irregular Progressive Edge－Growth（PEG）Tanner Graphs［C］／／Proceeding of ISIT．Lausanne，Switzerland：IEEE，2002：480－480．

［3］［11］Tao Tian，Christopher R．Jones，John D．Vill asenor，et al．Selective Avoidance of Cycles in Irregu lar LDPC Code Construction［J］．IEEE Transaction on Communication，2004，（8）：1242－1247．

［4］［5］［9］Seho Myung，Kyeongcheol Yang．Quasi－Cyclic LDPC Codes for Fast Encoding［J］．IEEE Transaction on Information Theory，2005，（8）：2894－2901．

［7］Vitaliy Feoktistov，Stefan Janaqi．Generalization of the Strategies in Differential Evolution［C］／／Proceeding of the 18th Internation Parallel and Distributed Processing Symposium．France：IEEE，2004：153－156．

［8］賈向東，海陽，歐陽玉花．基于差分進化的非規(guī)則LDPC碼分布對優(yōu)化［J］．無線電工程，2009，（3）：24－25．