碼率自由且低誤碼平臺(tái)QC－LDPC碼的設(shè)計(jì)

易 丹

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

0 引言

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

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

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

校驗(yàn)矩陣包含兩部分：結(jié)構(gòu)自由的H1和結(jié)構(gòu)相對(duì)固定的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è)計(jì)可以使這種QC－LDPC碼的編碼復(fù)雜度和編碼長(zhǎng)度呈線性關(guān)系。HP中的I表示一個(gè)大小為［L，L］的單位矩陣；0表示大小為［L，L］的零矩陣；Px表示一個(gè)單位置換序列，這個(gè)序列是通過(guò)將I循環(huán)右移x次得到。

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

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

2．1 改進(jìn)的密度進(jìn)化算法

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

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

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

2．2 改進(jìn)后的PEG算法

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

改進(jìn)后的PEG算法：

2．3 實(shí)施增大圍長(zhǎng)和ACE約束

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

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

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

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

3 仿真結(jié)果

3．1 好的度分布對(duì)

表1 四種不同碼率的好的度分布對(duì)

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

3．2 性能對(duì)比

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

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

4 結(jié)束語(yǔ)

本文改進(jìn)了密度進(jìn)化算法和PEG算法，使它們能夠應(yīng)用于結(jié)構(gòu)化QC－LDPC中，可以生成高性能、碼率自由的可硬件實(shí)現(xiàn)LDPC碼。并且在填充校驗(yàn)?zāi)妇仃囘^(guò)程中實(shí)施增大圍長(zhǎng)和ACE的約束，使得QC－LDPC碼的誤碼平臺(tái)降低，性能優(yōu)于IEEE802．16e中的QC－LDPC碼。本文提出的設(shè)計(jì)方法可以應(yīng)用在無(wú)線通信系統(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］賈向東，海陽(yáng)，歐陽(yáng)玉花．基于差分進(jìn)化的非規(guī)則LDPC碼分布對(duì)優(yōu)化［J］．無(wú)線電工程，2009，（3）：24－25．