多 濱，王振永，顧學(xué)邁

(哈爾濱工業(yè)大學(xué) 通信技術(shù)研究所，150080 哈爾濱)

近年來，隨著信息理論應(yīng)用的快速發(fā)展，Turbo碼和 LDPC(Low Density Parity Check，LDPC)碼都被看作是信道編碼領(lǐng)域中兩類具有逼近 Shannon理論限的信道編碼方案［1－2］.但是這兩種編碼的編碼或譯碼復(fù)雜度較高，在實(shí)現(xiàn)過程中還需進(jìn)一步優(yōu)化.在實(shí)際應(yīng)用中，編譯碼方案復(fù)雜度的問題是需要考慮的一個(gè)關(guān)鍵問題，因此尋找一個(gè)編碼復(fù)雜度和譯碼復(fù)雜度同時(shí)較低，并且具有應(yīng)用性能優(yōu)異的碼字是信道編碼領(lǐng)域研究的一個(gè)重點(diǎn).

作為一類特殊的 LDPC碼，LDGM(Low Density Generator Matrix，LDGM)碼有編碼復(fù)雜度和譯碼復(fù)雜度都低，并且實(shí)現(xiàn)更為簡單的優(yōu)點(diǎn)［3］，因此，研究具有低編譯碼復(fù)雜度的 LDGM碼的信道編碼技術(shù)方案具有重要的理論和實(shí)用價(jià)值.LDGM碼是線性系統(tǒng)碼，其校驗(yàn)矩陣可以通過一個(gè)隨機(jī)構(gòu)造的稀疏矩陣與單位矩陣簡單的組合得到，因此可以看出LDGM碼的構(gòu)造主要與該稀疏矩陣的如何創(chuàng)建有關(guān).雖然稀疏矩陣的產(chǎn)生與LDPC碼校驗(yàn)矩陣的生成類似，但是目前還沒有一個(gè)統(tǒng)一確定的產(chǎn)生方法，因此，自從MacKay［4］等重新發(fā)現(xiàn)LDPC碼的優(yōu)異性能以來，在校驗(yàn)矩陣的構(gòu)造方面始終是一個(gè)研究熱點(diǎn).由于LDGM碼校驗(yàn)矩陣的稀疏性，它同樣可以采用適用于LDPC碼的置信傳播(Belief Propagation，BP)算法，而不改變其譯碼復(fù)雜度.盡管LDGM碼有如此多的優(yōu)點(diǎn)，但由于存在度為1的變量節(jié)點(diǎn)，LDGM碼譯碼性能存在較高的錯(cuò)誤平層.文獻(xiàn)［3］提出了串行級(jí)聯(lián)低密度生成矩陣(Serially-Concatenated LDGM，SCLDGM)碼，其不僅可以明顯地改善LDGM碼譯碼中所存在的錯(cuò)誤平層現(xiàn)象，還能獲得逼近Shannon理論限的優(yōu)異性能.目前，針對(duì)SCLDGM碼的研究主要集中在如何進(jìn)一步降低或消除LDGM碼的高錯(cuò)誤平層的問題［5－7］.然而，對(duì)于如何具體產(chǎn)生適合 SCLDGM碼的編碼構(gòu)造并沒有被提及.

為此，本文從實(shí)際應(yīng)用的角度出發(fā)，首先在保證性能的前提下，提出了一種具有低復(fù)雜度的LDGM碼編碼構(gòu)造算法.此外，為了進(jìn)一步提高譯碼性能，結(jié)合SCLDGM碼的逼近Shannon理論限的特點(diǎn)以及擁有著很好的錯(cuò)誤平層性能的優(yōu)點(diǎn)，給出了一種改進(jìn)的級(jí)聯(lián)譯碼算法.該算法是將外編碼器的輸出和內(nèi)譯碼器的輸出看作二進(jìn)制刪除信道(Binary Erasure Channel，BEC)，因此將該信道的先驗(yàn)信息輸入外譯碼器，可以進(jìn)一步降低錯(cuò)誤信息.通過計(jì)算機(jī)仿真，驗(yàn)證了不同仿真參數(shù)下的性能差異，找到了提出方案近優(yōu)的內(nèi)外碼速率組合和近優(yōu)的內(nèi)外碼碼重.仿真結(jié)果表明，本文提出的算法不僅具有較低的復(fù)雜度，同時(shí)有效的降低了LDGM碼錯(cuò)誤平層.

1 LDGM碼編碼構(gòu)造

在本節(jié)中，分析了LDGM碼基本原理，提出了具有低復(fù)雜度的稀疏矩陣構(gòu)造算法，該算法對(duì)于本文第2節(jié)提出的SCLDGM編譯碼方案起著至關(guān)重要的作用.

1.1 LDGM碼校驗(yàn)矩陣構(gòu)造

LDGM碼是一類特殊的LDPC碼，正如式(1)所示，一個(gè)系統(tǒng) LDGM碼的校驗(yàn)矩陣包括左右兩個(gè)部分:左側(cè)是一個(gè)隨機(jī)構(gòu)造的稀疏矩陣P，右側(cè)是一個(gè)對(duì)角單位矩陣I.如果P中所有的行(和列)都有同樣數(shù)量“1”，那么該LDGM碼就被稱為規(guī)則LDGM碼;如果P中所有的行(和列)中“1”的數(shù)量不一樣，則把其稱為非規(guī)則LDGM碼.

式中，校驗(yàn)矩陣H有N列和M行，那么N個(gè)比特的碼字序列c必須滿足校驗(yàn)關(guān)系HcT=0.信息比特的數(shù)量為K=N－M，編碼速率為R=K/N.本文用(N，K，w)分別表示非規(guī)則LDGM碼的編碼長度、信息比特長度和碼重.

當(dāng)系統(tǒng)信息比特、校驗(yàn)比特和碼字序列分別表示為 u= ［uk］T、p= ［pm］T和 c= ［cn］T=［u1… ukp1… pm］T時(shí)，LDGM 碼的編碼可以由下式表示:

式中 hm，n表示矩陣中第 m列、第 n行元素在校驗(yàn)矩陣中相應(yīng)的位置.需要注意的是，LDGM碼是一類特殊的LDPC碼，因此其譯碼方式同樣可以采用適用于LDPC碼的BP算法，只需對(duì)其譯碼算法進(jìn)行適當(dāng)?shù)母淖?，而不增加其譯碼復(fù)雜度.

與LDPC碼相比，LDGM碼唯一不同之處就是存在N－K個(gè)度為1的校驗(yàn)比特節(jié)點(diǎn)和K個(gè)比特節(jié)點(diǎn)對(duì)應(yīng)著系統(tǒng)信息比特.因此，LDGM碼無法更新來自度為1的比特節(jié)點(diǎn)到相應(yīng)校驗(yàn)節(jié)點(diǎn)的對(duì)數(shù)似然比(Log Likelihood Ratio，LLR)軟信息，所以LDGM碼的缺點(diǎn)就是存在較高的錯(cuò)誤平層問題.雖然可以在LDGM碼的性能收斂性和性能錯(cuò)誤平層性之間采取一個(gè)折中的方案，但是單獨(dú)利用LDGM碼作為信道編碼方案在實(shí)際無線信道應(yīng)用中還有一定的局限性.

1.2 低復(fù)雜度稀疏矩陣構(gòu)造算法

由上述可知，LDGM碼的構(gòu)造是由稀疏矩陣的構(gòu)造決定的.而LDPC碼的性能好壞完全由它的校驗(yàn)矩陣來確定，也就是說校驗(yàn)矩陣的構(gòu)造對(duì)于LDPC碼的性能起著決定性的作用.現(xiàn)有的LDPC碼校驗(yàn)矩陣的隨機(jī)構(gòu)造方法主要有Gallager構(gòu)造法［8］和 Mackay 構(gòu)造法［4］.其中，為了避免Tanner圖中長度為4的短環(huán)，Mackay的1A構(gòu)造法保證每列有t個(gè)“1”，并隨機(jī)設(shè)定它們的位置，使每一行中的“1”盡可能相等均勻分布，同時(shí)任意每兩列之間的重疊“1”的個(gè)數(shù)不大于1.Mackay的1A構(gòu)造方法不僅保證了矩陣的隨機(jī)性，同時(shí)通過相關(guān)算法(由于篇幅限制，該算法請(qǐng)參考文獻(xiàn)［4］)進(jìn)一步消除了長度為4的短環(huán).

雖然采用Mackay方法構(gòu)造的稀疏矩陣具有很好的碼距離特性，同時(shí)避免了長度為4的短環(huán)，但缺點(diǎn)是稀疏矩陣的構(gòu)造復(fù)雜度較高，而且所構(gòu)造的稀疏矩陣有50%的概率存在線性相關(guān)的行，使得實(shí)際的碼率略有增加［4］.本文定義采用Mackay方法構(gòu)造的LDGM碼為LDGM1碼.

為了解決LDGM1碼復(fù)雜度較高的問題，本文提出一種具有低復(fù)雜度的不規(guī)則稀疏矩陣構(gòu)造方法，具體算法步驟如下:

1)稀疏矩陣初始化:生成維度為(N－K，K)的全0矩陣作為初始稀疏矩陣.隨機(jī)分配給定列重?cái)?shù)量的每一個(gè)“1”到初始化的稀疏矩陣的每一列當(dāng)中，完成稀疏矩陣的初始化;

2)檢驗(yàn)與更新稀疏矩陣:經(jīng)過初始化生成的矩陣中任意同一列中可能會(huì)存在相同行位置的“1”的分配，所以，還需要對(duì)初始化的稀疏矩陣進(jìn)行逐列檢測(cè)，如果發(fā)現(xiàn)同一列中有相同的行位置分配，則對(duì)該列“1”的位置進(jìn)行重新隨機(jī)分配，直到該列沒有相同的行位置分配，最后更新稀疏矩陣;

3)生成LDGM校驗(yàn)矩陣和生成矩陣:將得到的稀疏矩陣與單位矩陣組合即可以生成相應(yīng)的生成矩陣與校驗(yàn)矩陣，分別用于LDGM碼的編碼與譯碼.定義用此構(gòu)造法構(gòu)造的LDGM碼為LDGM2碼.

與LDGM1碼的稀疏矩陣相比，LDGM2碼并沒有消除長度為4的短環(huán)，故不需像LDGM1碼那樣反復(fù)驗(yàn)證構(gòu)成稀疏矩陣是否存在長度為4的短環(huán)，所以LDGM2碼的生成具有較小的計(jì)算量，即復(fù)雜度相對(duì)較低.圖1給出了 LDGM1碼和LDGM2碼的BER性能比較.為了公平比較均選取編碼長度為1 000，列重為6和碼速率為0.5的LDGM碼.從圖中可以看出，盡管LDGM1碼的P矩陣消除了長度為4的短環(huán)，但是不能保證H矩陣也不存在長度為4的短環(huán)，因此與LDGM2碼相比，LDGM1碼的性能并沒有大幅度的增益，其性能僅僅略高于LDGM2碼的性能.同時(shí)隨著碼長的不斷增加，構(gòu)建LDGM1碼中P矩陣的計(jì)算時(shí)間將越來越長，所以其對(duì)于長碼字的應(yīng)用存在一定的局限性.而本文提出的算法盡管性能上有很小的損失，但是隨著編碼長度的不斷增加，其性能也會(huì)不斷提高，并且其較低的編碼復(fù)雜度使其在實(shí)際應(yīng)用當(dāng)中具有很好的應(yīng)用前景.

圖1 (1 000，500，6)的LDGM1碼和LDGM2碼性能比較

2 SCLDGM碼編譯碼設(shè)計(jì)方案

2.1 SCLDGM碼編譯碼構(gòu)造

圖2給出了SCLDGM碼編譯碼系統(tǒng)框圖，可以看出，該系統(tǒng)是將二進(jìn)制LDGM碼分別作為系統(tǒng)的內(nèi)碼和外碼進(jìn)行串行級(jí)聯(lián)的.具體來說，首先用高碼率為K/N1的外LDGM碼編碼器對(duì)待發(fā)送信息進(jìn)行編碼，然后對(duì)外編碼器的輸出碼字用碼率為N1/N的內(nèi)LDGM碼編碼器再次編碼，最后生成總碼率為K/N的碼字.碼字經(jīng)過BPSK調(diào)制后，通過高斯隨機(jī)變量方差為 σ2=N0/2的AWGN信道.在信宿端，內(nèi)譯碼器首先利用校驗(yàn)矩陣對(duì)接收到的信號(hào)進(jìn)行譯碼.直到內(nèi)譯碼器譯碼完成后，外譯碼器才利用內(nèi)譯碼器輸出的LLR軟信息作為先驗(yàn)信息對(duì)外譯碼器的輸入進(jìn)行初始化.待外譯碼器譯碼完成后，即可得到信源發(fā)送信息的估計(jì)值.

圖2 SCLDGM碼編譯碼系統(tǒng)框圖

2.2 SCLDGM碼譯碼算法

1)級(jí)聯(lián)譯碼算法1.對(duì)于SCLDGM碼譯碼，傳統(tǒng)的方法采用內(nèi)外碼LLR軟信息單獨(dú)迭代傳遞方案.首先，從AWGN信道接收到的信號(hào)經(jīng)過BPSK解調(diào)后送入到內(nèi)LDGM碼譯碼器，采用BP迭代譯碼算法在內(nèi)譯碼器中的變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間進(jìn)行若干次LLR軟信息迭代更新后，從變量節(jié)點(diǎn)得到最后的LLR軟信息，即對(duì)應(yīng)內(nèi)譯碼器的譯碼輸出信息.將內(nèi)譯碼器的輸出LLR軟信息作為外譯碼器的先驗(yàn)概率軟信息進(jìn)行初始化輸入.然后外譯碼器進(jìn)行若干次BP迭代譯碼得到最后的LLR軟信息，即外譯碼器的輸出軟信息，最后通過判決得到譯碼結(jié)果.

2)級(jí)聯(lián)譯碼算法2.本文在級(jí)聯(lián)譯碼算法1的基礎(chǔ)上提出一種改進(jìn)的級(jí)聯(lián)譯碼算法，稱之為級(jí)聯(lián)譯碼算法2.從級(jí)聯(lián)譯碼算法1可知，LDGM外譯碼器可以利用內(nèi)譯碼器的輸出作為先驗(yàn)信息進(jìn)一步降低內(nèi)譯碼器的譯碼錯(cuò)誤比特，所以，內(nèi)譯碼器的輸出實(shí)際上已經(jīng)含有輸出錯(cuò)誤比特位置信息.因?yàn)橥ㄟ^仿真發(fā)現(xiàn)，內(nèi)譯碼器輸出的正確譯碼比特0或者1的概率接近于1，即內(nèi)譯碼器對(duì)該比特正確譯碼的確定性為100%;而相比之下，內(nèi)譯碼器輸出的錯(cuò)誤比特0或者1的概率接近于0.5，即內(nèi)譯碼器對(duì)該信息比特的判定是0或者1的確定性為50%.這就意味著可以把圖2當(dāng)中從外編碼器的輸出到內(nèi)譯碼器的輸出部分看成是BEC信道，而內(nèi)譯碼器輸出的錯(cuò)誤系統(tǒng)信息比特就相當(dāng)于BEC當(dāng)中已經(jīng)被“刪除”的比特.需要注意的是，這個(gè)BEC信道并不是一個(gè)標(biāo)準(zhǔn)的BEC信道，因?yàn)椴⒉恢厘e(cuò)誤信息比特確切的位置，但是內(nèi)譯碼器的輸出信息卻含有錯(cuò)誤信息比特的先驗(yàn)概率信息.外譯碼器可以將內(nèi)譯碼器的輸出看作是來自BEC信道的輸出信號(hào)，然后利用內(nèi)譯碼器輸出信息比特的先驗(yàn)概率信息得到被“刪除”比特位置的先驗(yàn)信息，這些比特的初始化LLR軟信息為0.最后完成所有比特先驗(yàn)概率初始化，輸入到外譯碼器當(dāng)中，使得外譯碼器可以進(jìn)一步準(zhǔn)確的完成對(duì)來自內(nèi)譯碼器的先驗(yàn)概率信息的譯碼.

3 仿真分析與結(jié)果

本小節(jié)，通過計(jì)算機(jī)對(duì)無線通信信道中的環(huán)境進(jìn)行模擬仿真構(gòu)造近優(yōu)的SCLDGM碼方案.因此數(shù)據(jù)傳輸速率選擇不能太高，為了便于仿真驗(yàn)證本文提出的構(gòu)造SCLDGM碼方案的可行性，首先考慮近優(yōu)的內(nèi)外碼速率組合，并假設(shè)整個(gè)SCLDGM碼碼率R為0.5，那么內(nèi)外碼速率的乘積為0.5;其次，分析內(nèi)外碼碼重對(duì)級(jí)聯(lián)方案性能的影響.

1)確定近優(yōu)內(nèi)外碼速率組合.定義內(nèi)外碼碼率分別為Rin和Rout，那么R=Rin×Rout=0.5.首先要找到一種近優(yōu)的內(nèi)外碼速率組合以達(dá)到最好的BER性能.需要注意，Rin和Rout都大于碼速率0.5.由于高碼率的LDGM碼擁有優(yōu)異的BER性能(不僅距離Shannon理論限僅有0.36 dB，同時(shí)還保持著非常低的錯(cuò)誤平層［9］)，所以圖2中的外譯碼器可以利用內(nèi)譯碼器的輸出作為先驗(yàn)概率信息來進(jìn)行初始化操作，然后通過高速率的外譯碼器進(jìn)一步降低內(nèi)碼譯碼沒有消除的錯(cuò)誤.因此為了使得外碼速率的損失最小，選擇Rin接近于R，那么Rout則接近于1.作為所有內(nèi)外碼速率組合采樣的代表，圖3給出了3種不同內(nèi)外碼速率組合的 BER性能曲線.內(nèi)外碼速率組合(Rin，Rout)分別為(0.990 1，0.505)、(0.980 4，0.51)和(0.970 9，0.515).從圖中可以看出，最優(yōu)的速率組合是(0.980 4，0.51).

圖3 具有不同內(nèi)外碼速率組合的SCLDGM碼的BER性能

2)確定近優(yōu)內(nèi)外碼碼重.為了便于仿真分析內(nèi)外碼碼列重的選取是否也會(huì)對(duì)SCLDGM碼方案的性能產(chǎn)生一定的影響.作為所有內(nèi)外碼碼列重組合采樣的代表，假設(shè)其內(nèi)外碼碼重具有相同的數(shù)值 D.圖 4給出了 (600，500，wout)外LDGM碼和(1 176，600，win)內(nèi)LDGM碼3種不同內(nèi)外碼碼列重組合級(jí)聯(lián)方案的BER性能曲線，其中wout和win分別為外碼和內(nèi)碼的列重.從圖中可以看出，SCLDGM碼存在近優(yōu)的內(nèi)外碼碼重，且近優(yōu)的內(nèi)外碼碼重D為6.

圖4 級(jí)聯(lián)(600，500，wout)外 LDGM 碼和(1000，600，win)內(nèi)LDGM碼的BER性能

3)性能比較與分析.圖5分別比較了碼長為1 176、碼率為 0.5的傳統(tǒng) LDGM碼、具有Mackay構(gòu)造法的SCLDGM碼和具有本文提出構(gòu)造法的SCLDGM碼的BER性能，并且對(duì)級(jí)聯(lián)譯碼算法1和級(jí)聯(lián)譯碼算法2做出了性能比較.從圖中可以看出，近優(yōu)SCLDGM碼方案可以極大的改善LDGM碼錯(cuò)誤平層問題，這是因?yàn)榻?jīng)過內(nèi)譯碼器后剩余的錯(cuò)誤比特可以被外譯碼器進(jìn)一步糾正.同時(shí)，級(jí)聯(lián)譯碼算法2在級(jí)聯(lián)譯碼算法1的基礎(chǔ)上，其性能得了到進(jìn)一步的改善.

圖5 LDGM碼和SCLDGM碼的不同譯碼算法BER性能比較

如圖5所示，對(duì)于采用Mackay的1A構(gòu)造法的SCLDGM碼雖然在性能上略優(yōu)于本文提出的SCLDGM碼，但是隨著編碼長度的不斷增加，與第2.2小節(jié)分析結(jié)果類似，通過仿真得到，Mackay構(gòu)造法的復(fù)雜度也將會(huì)越來越高，優(yōu)勢(shì)也相應(yīng)的越來越小，所以對(duì)于長碼字的應(yīng)用存在一定的局限性.而本文提出的算法盡管在性能上略低于Mackay構(gòu)造法，但是其較低的編碼復(fù)雜度，以及編碼的快速性，使其在實(shí)際應(yīng)用當(dāng)中具有很好的應(yīng)用前景.

4 結(jié)論

本文針對(duì)SCLDGM碼稀疏矩陣構(gòu)造復(fù)雜度較高的問題，提出了一種具有低復(fù)雜度的SCLDGM碼編碼設(shè)計(jì)方案.首先，給出了低構(gòu)造復(fù)雜度的LDGM2碼生成算法，仿真表明，與LDGM1碼相比，LDGM2碼僅有很小的性能損失.此外，通過計(jì)算機(jī)仿真確定了仿真參數(shù)，分別為近優(yōu)的內(nèi)外碼碼率組合以及內(nèi)外碼碼重.仿真結(jié)果表明，本文提出的SCLDGM碼編譯碼算法可以有效克服LDGM碼所存在的錯(cuò)誤平層問題，在保持其實(shí)現(xiàn)低復(fù)雜度和編碼快速性的同時(shí)可以大幅改善傳統(tǒng)LDGM碼性能.

綜上，本文提出的低復(fù)雜度SCLDGM碼構(gòu)造方法在無線通信信道當(dāng)中具有相當(dāng)好的BER性能，隨著編碼長度的不斷增加，其性能將會(huì)接近于隨機(jī)構(gòu)造的非規(guī)則LDPC碼，因此，在無線通信中具有良好的應(yīng)用前景.由于本文提出的方案是近優(yōu)的，下一步工作將利用EXIT圖［10］進(jìn)行理論分析，設(shè)計(jì)最優(yōu)的SCLDMG碼方案，以期進(jìn)一步提高系統(tǒng)的性能.

［1］ ZHANG Zheng，DUMAN T M.Capacity approaching turbo coding forhalfduplexrelaying［C］//IEEE International Symposium on Information Theory.Piscatway:IEEE Press，2005:1888 －1892.

［2］CHAKRABARTI A，SABHARWAL A，AAZHANG B.Low density parity check codes for the relay channel［J］. IEEE Journal on Selected Areas in Communications，2007，25(2):280 －291.

［3］GARCIA-FRIAS J，ZHONG Wei.Approaching shannon performance by iterative decoding of linear codes with low-density generator matrix［J］.IEEE Communications Letters，2003，7(6):266－268.

［4］ MACKAY D C.Good error-correcting codes based on very sparse matrices［J］. IEEE Transactionson Information Theory，1999，45(2):399 －431.

［5］GONZALEZ-LOPEZ M，VAZQUEZ-ARAUJO F J，CASTEDO L，et al.Serially-concatenated low-density generator matrix(SCLDGM)codes for transmission over AWGN and Rayleigh fading channels［J］.IEEE Transactions on Wireless Communications，2007，6(8):2753 －2758.

［6］ ZHONG Wei，GARCIA-FRIAS J.LDGM codes for channel coding and joint source-channel coding of correlated sources［J］.EURASIP Journal Applied Signal Process，2005，6:942 －953.

［7］VAZQUEZ-ARAUJO F J，GONZALEZ-LOPEZ M，CASTEDO L，et al.Serially-concatenated LDGM codes for MIMO channels［J］. IEEE Transactions on Wireless Communications，2007，6(8):2860－2871.

［8］GALLAGER R G.Low density parity check codes［J］.IEEE Transactions on Information Theory，1962，8:21－28.

［9］VAZQUEZ-ARAUJO F，GONZALEZ-LOPEZ M，CASTEDO L，et al.Layered LDGM codes:a capacity-approaching structure for arbitrary rates［C］//4th International Symposium on Wireless Communications Systems.Piscatway:IEEE Press，2007:16 －20.

［10］TEN BRINK S，KRAMER G，ASHIKHMIN A.Design of low-density parity-check codes for modulation and detection［J］.IEEE Transactions on Communications，2004，52(4):670－678.