碼率自適應原模圖LDPC碼的設計

王志娜，肖 旻，王 琳

（1.重慶郵電大學重慶市移動通信重點實驗室，重慶 400065;2.廈門理工學院電子工程系，福建廈門 361005;3.廈門大學通信工程系，福建廈門 361005）

0 引言

通信系統業(yè)務的多樣性、信道的時變性、物理層技術的靈活性需要信道編碼碼率能夠自適應地根據信道環(huán)境做出相應的調整。采用碼率自適應的編碼技術，可以在保證系統服務質量的前提下，根據信道的狀況及時調整碼率，從而提高通信系統的頻譜利用率。

低密度奇偶校驗碼［1］（low density parity check code，LDPC）具有良好的距離特性、小的誤碼率和較低的譯碼復雜度，被認為是迄今為止糾錯性能最好的碼。2003年，美國國家航空航天局的空氣動力實驗室（JPL）首次提出了原模圖 LDPC碼［2］（protograph LDPC codes），彌補了傳統LDPC碼編碼復雜度較高的不足。作為一種原模圖LDPC碼，AR4JA碼［3］（accumulate repeat－4 jagged－accumulate code）最大的優(yōu)勢就是錯誤地板極低。該碼的性能優(yōu)于絕大多數的一般LDPC碼和其他原模圖LDPC碼，2006年由太空數據系統咨詢委員會（consultative committee for space date systems，CCSDS）推薦給 NASA 作為深空通信的標準碼型。鑒于原模圖LDPC碼，尤其是AR4JA碼的各種優(yōu)勢，對原模圖LDPC碼率自適應的研究有著很廣闊的前景。

目前，實現碼率自適應的方法主要有刪余和擴展兩種。刪余可以利用同一對編譯碼器對不同碼率的碼進行編譯碼，是最常用的一種碼率自適應方法。2006年，J.Ha等［4］借鑒“恢復”的概念，定義了刪余變量節(jié)點（punctured variable node，PVN）的“恢復級別”。PVN的恢復級別是影響刪余碼型性能的重要因素，之后，對刪余算法的研究實質上都是基于PVN 的恢復級別進行的［5－8］。然而，J.Li等［9］表明，隨著刪余碼率的增加，碼的性能離香農限的距離增大，僅僅依靠刪余并不能在較大碼率范圍內得到好性能的碼。為了得到更大范圍變化的碼率，通常將刪余和擴展結合起來構造碼率自適應碼組。

現階段，對一般LDPC碼率自適應的研究已經取得了很多成果。然而，對原模圖LDPC碼率自適應的研究卻較少。目前，只有 El－khamy等［10］以一個低碼率的原模圖LDPC碼（accumulate repeat check accumulate code，ARCA 碼）為基礎，利用刪余的方法實現碼率自適應，得到的碼率自適應ARCA碼有較高的錯誤地板。與之不同的是，本文將擁有極低錯誤地板的AR4JA碼作為母碼，通過刪余和擴展相結合的方法來構造碼率自適應AR4JA碼（ratecompatible AR4JA，RC－AR4JA）。

1 原模圖LDPC碼

1.1 原模圖LDPC碼基本原理

原模圖是一種包含相對較少節(jié)點的Tanner圖。一個原模圖Gp=（V，C，E）包含變量節(jié)點集V，校驗節(jié)點集C和邊集E。每一條邊e=（V，C）∈E連接一個變量節(jié)點v∈V和一個校驗節(jié)點c∈C。原模圖中允許有平行邊的存在，因此e→（vi，cj）∈E并不是一一映射關系。與原模圖對應的校驗矩陣稱為基礎矩陣B，Bij的值代表第i個校驗節(jié)點和第j個變量節(jié)點之間連接邊的條數。與一般LDPC碼校驗矩陣不同的是，Bij的值并不僅限于0和1。對原模圖進行T次復制，然后把T條相同類型的變量節(jié)點和校驗節(jié)點之間的邊置換，可以擴展成不同大小的圖。我們稱這種圖為導出圖G，對應的LDPC碼稱為原模圖LDPC碼。

作為一個簡單的例子，我們考慮如圖1所示的原模圖，其中圓圈代表變量節(jié)點，方框代表校驗節(jié)點。圖1a的原模圖Gp有個變量節(jié)點，個校驗節(jié)點，條邊。圖1b是將圖1a的原模圖Gp復制T=2次得到的大圖，這2個相同的子圖之間是相互獨立，互不相連的。將圖1b中相同類型節(jié)點之間的邊進行置換，便得到圖1c所示的導出圖G，此時這2個子圖就連接在一起了。

圖1 原模圖到導出圖的過程Fig.1 Process from protograph to derived graph

原模圖中，允許變量節(jié)點集V包含刪余變量節(jié)點。假設有Vu個刪余變量節(jié)點，則未刪余變量節(jié)點個。那么碼率的計算將變?yōu)镽=

1.2 AR4JA碼

AR4JA碼是一種特殊的累加重復累加碼［11］（accumulate repeataccumulate codes，ARA）。碼率為1/2的AR4JA的編碼框圖，原模圖如圖2所示，其中I表示交織器，D表示累加器，空心圓圈代表刪余變量節(jié)點，實心圓圈代表未刪余變量節(jié)點，方框代表校驗節(jié)點。該碼的原模圖有個變量節(jié)點，個校驗節(jié)點，其中有1個變量節(jié)點被刪余了。（1）式為該碼的基礎矩陣。AR4JA碼是一種系統碼，即:變量節(jié)點3和4代表信息位，變量節(jié)點0，1和2代表校驗位。碼率為1/2的AR4JA的迭代譯碼門限為 0.628 dB，典型最小距離比為 δmin=0.015［3］。

圖2 碼率為1/2的AR4JA碼Fig.2 AR4JA code of rate 1/2

AR4JA碼具有傳統LDPC碼的優(yōu)點，作為一種ARA碼，還可以通過簡單的重復器和累加器進行編碼，編碼簡單快速更易于硬件實現。此外，它的最小距離以很高的概率與碼長成線性關系［12－13］，克服了一般原模圖LDPC碼錯誤地板欠佳的不足。

2 RC-AR4JA碼的設計

對于RC－AR4JA碼的設計，我們選取碼率為1/2的AR4JA碼作為母碼，并分兩部份進行。首先，提出“逐節(jié)點刪余”算法實現碼率由0.5～0.8的自適應。其次，利用矩陣擴展的方法獲得碼率從0.5～0.25的RC－AR4JA碼。結合刪余和擴展的方法，能夠實現碼率在0.25～0.8變化的 RC－AR4JA 碼。

2.1 “逐節(jié)點刪余”算法

刪余的基本思想:首先選取一個較低碼率及性能優(yōu)良的碼作為母碼，通過刪余母碼的冗余變量節(jié)點得到一系列高碼率的碼。

2.1.1 基本準則

在進行刪余時，我們提出以下準則，依據這些準則依次刪余滿足條件的變量節(jié)點，直到獲得想要的高碼率。

準則1 最大化最低恢復級別PVN個數。

準則2 最小化刪余變量節(jié)點通過校驗節(jié)點相連的所有PVN數目。

準則3 最小化每個校驗節(jié)點上連接PVN個數。

2.1.2 算法主要步驟

“逐節(jié)點刪余”算法的具體步驟表述如下（參數見表1）。

表1 “逐節(jié)點刪余”算法的參數Tab.1 Parameters of the“puncturing node by node”algorithm

步驟1 通過（2）式計算要刪余的節(jié)點數目

步驟2 找到集合U，并對于每一個c∈N（v），其中v∈U，計算出被刪余 。

步驟3 對于每一個v∈U，通過（3）式計算出G（v），H（v）和M（v）。

步驟4 找到集合T={vr:vr∈U＆G（vr）=minv∈U G（v）}，如果T中只有一個節(jié)點，刪余該節(jié)點，并跳到步驟5。

步驟4.1 找到集合W={vr:vr∈U＆H（vr）=minv∈T H（v）}，如果W中只有一個節(jié)點，刪余該節(jié)點，并跳到步驟5。

步驟4.2 找到集合D={vr:vr∈U＆M（vr）=minv∈W M（v）}，如果D中只有一個節(jié)點，刪余該節(jié)點。如果D中有多個節(jié)點，隨機選取一個進行刪余。

步驟5 判斷刪余的變量節(jié)點數目是否等于Npun，若是，則結束;否則，跳到步驟2。

2.2 矩陣擴展

擴展是選取一個較高碼率及性能優(yōu)秀的碼作為母碼，通過增加額外的冗余比特來降低碼率。擴展有兩種方法:矩陣擴展和校驗節(jié)點分裂。矩陣擴展是最早提出的一種擴展方法［9］，如圖3所示。首先選取一個較高碼率母碼的校驗矩陣，為N0列M0行。當碼率需要降低的時候，依次增加Mi行和Mi列，從而得到一系列碼率為Ri＜R0的碼，其中Ri=為了保證母碼的特性，擴展后的矩陣右上角全為0，同時左下角的“稀疏矩陣”也需要保證與原矩陣之間的非相關性。對于擴展矩陣中的Bi，不同的碼具有不同的構造方式。

圖3 矩陣擴展Fig.3 Matrix expansion

對于AR4JA碼，采用如圖4所示的擴展方法，左上角3T×5T的矩陣為母碼的校驗矩陣。在左下角的“稀疏矩陣”設計時，本文保證新增校驗節(jié)點的度為4，并且使得新增的校驗節(jié)點只與母碼中2號和3號變量節(jié)點相連。右上角的0代表全零矩陣，右下角的1代表單位矩陣，這樣便可以得到碼率為R=T/（2T+M）的AR4JA碼。

圖4 AR4JA的矩陣擴展Fig.4 Matrix expansion of AR4JA code

新增校驗節(jié)點的度為4，使得擴展后的矩陣校驗節(jié)點度更加集中，有利于碼的性能［14］。為了進一步提高性能，采用改進的PEG算法對新增校驗節(jié)點與變量節(jié)點的連接進行優(yōu)化，避免了Tanner中短環(huán)的出現。

3 仿真結果及分析

我們用上述方法構造RC－AR4JA碼，并進行了仿真。其中，母碼采用擴展次數為512的 AR4JA碼，即信息位長度為1 024，碼率為1/2，其中在擴展時采用改進型的PEG算法［15］來消除6環(huán)。仿真在AWGN信道下進行，采用 BPSK調制，Log－BP譯碼算法，最大迭代次數為100。

首先，采用“逐節(jié)點刪余”算法設計RC－AR4JA碼，實現了碼率從0.5～0.8的變化，并與隨機刪余構造的RC－AR4JA碼進行了對比。圖5給出了這兩種RC－AR4JA碼的性能仿真曲線。為了使不同碼率的仿真結果更加清晰，本文給出了Es/N0與BER的曲線，其中Es/N0=Eb/N0+10lgR。

相對于隨機刪余，采用“逐節(jié)點刪余”設計的RC－AR4JA碼具有更好的性能，隨著速率的增加優(yōu)勢進一步擴大。在BER為10－6數量級（無線數據通信業(yè)務的標準 BER），逐節(jié)點刪余設計的 RCAR4JA碼在碼率分別為0.6，0.7的情況下，比隨機刪余獲得的 RC－AR4JA 碼分別有約 0.5 dB，1.0 dB的增益。在碼率為0.8時，隨機刪余與逐節(jié)點刪余的差距更大。

圖5 不同刪余算法下的RC－AR4JA碼性能Fig.5 BER performances of RC－AR4JA codes with different algorithms

其次，采用圖4所示矩陣擴展的方法，設計了碼率從0.5～0.25的 RC－AR4JA 碼。作為對比，還利用隨機擴展構造0.5～0.25碼率變化的AR4JA碼。在隨機擴展時，保證新增校驗節(jié)點度同樣為4，兩者之間的對比將是公平的。圖6給出這兩種擴展方法得到的RC－AR4JA碼的性能仿真曲線。圖6中，選擇表示本文設計的擴展方法，隨機為隨機擴展方法。

圖6 不同擴展方法得到的AR4JA碼性能Fig.6 BER performances of RC－AR4JA codes obtained by differentmatrix expansion method.

相同的碼率下，用圖4所示矩陣擴展構造的RC－AR4JA碼較隨機擴展有更好的性能，隨著碼率的降低，這種優(yōu)勢更加明顯。在BER為10－6數量級，用本文的擴展方法構造的AR4JA碼在碼率分別為 0.4，0.35，0.3 和 0.25 的情況下，較隨機擴展得到的 AR4JA 碼分別有 0.2 dB，0.5 dB，0.7 dB 和 1 dB的增益。此外，我們設計的 RC－AR4JA碼，在BER為10－6數量級并未出現錯誤地板。

4 結束語

本文針對一類擁有極低錯誤地板的原模圖LDPC碼—AR4JA碼，提出了“逐節(jié)點刪余”算法，實現了碼率由0.5～0.8的增加，并利用矩陣擴展的方法構造了碼率從0.5～0.25變化的AR4JA碼。結合刪余和擴展的方法，實現碼率從0.25～0.8靈活變化的RC－AR4JA碼。在AWGN信道下的仿真結果表明，在 BER為10－6數量級處，本文設計的 RCAR4JA碼在整個碼率變化范圍內并未出現錯誤地板，保持了母碼錯誤地板低的優(yōu)良特性。

［1］GALLAGER R G.Low－density parity check codes［M］.Cambridge，MA:MIT Press，1963.

［2］THORPE J.Low－density parity－check（LDPC）codes constructed from protographs［C］//Tech.Rep.Progress Report.Pasadena，CA，USA:JPL IPN，2003:42－154.

［3］ DIVSALAR D，JONESC，THORPE J.Protograph based LDPC codeswithminimum distance linearly growing with block size［C］//IEEE.IEEE Communications Society subject.ST，louis:IEEE Globecom，2005:1152－1156.

［4］HA J，KIM J，KLINC D，et al.Rate－compatible punctured low－density parity－check codes with short block length［J］.IEEE Trans Inform Theroy，2006，52（2）:728－738.

［5］胡文江，衛(wèi)霞.碼率自適應 QC－LDPC碼的研究［J］.重慶郵電大學學報:自然科學版，2009，21（1）:53－56.

HUWen－jiang，WEIXia.Design of rate－compatible QCLDPC codes［J］.Journalof Chongqing University of Posts and Telecommunications:Nature Science Edition，2009，21（1）:53－56.

［6］ YOU Ying，XIAOMin，WANG Lin.The rate－compatible Multi－Edge Type LDPC codes with short block length［C］//IEEE.Proceedings of the 5th International Conference on Wireless communications（WiCOM'09）.NJ，USA:IEEE Press，2009:1－4.

［7］肖旻，黎勇，王琳.碼率自適應LDPC碼刪余算法［J］.應用科學學報，2011，24（9）:385－389.

XIAOMin，LIYong，WANG Lin.Puncturing Algorithm for design rate－compatible LDPC codes［J］.Journal of applied sciences，2011，24（9）:385－389.

［8］ 溫娜，徐永太，張平.有限長LDPC碼的打孔方案設計［J］.北京郵電大學學報，2007，29（6）:135－138.

WEN Na，XU Yong－tai，ZHANG Ping.Design of puncturing scheme for finite－length LDPC codes［J］.Jouranl of Beijing University of Posts and Telecommunications，2007，29（6）:135－138.

［9］LI J，NARAYANNA K.Rate－compatible low density parity check codes for capacity－approaching ARQ scheme in packet data communications［C］//Proc.Int Conf Comm Internet and Info.Tech（CIIT）.Virgin Islands，USA:2002:201－206.

［10］ MOSTAFA E1－Khamy，HOU Ji－lei，BHUSHAN Naga.Design of rate－compatible structured LDPC codes for Hybrid ARQ application［J］.IEEE JSele Areas Commun，2009，27（6）:965－973.

［11］ ABBASFAR A，DIVSALAR D，YAO Kung.Accumulate repeat accumulate codes［C］//IEEE International Symposium on Information Theory（ISIT）.Chicago，USA:IEEE Globecom，2004:509－513.

［12］ DIVSALAR D.Ensemble weight enumerators for protograph LDPC codes［C］//IEEE.IEEE International Symposium on Information Theory（ISIT）.Seattle，Washington，USA:IEEE Press，2006:1554－1558.

［13］ DIVSALAR D，DOLINAR S，JONSC R，et al.Capacity－approaching protograph codes［J］.IEEE J sele Areas Commun，2009，27（6）:876－888.

［14］ CHUNG SY，RICHARDSON T J，URBANKE R L.A－nalysis of sumproduct decoding of low－density paritycheck codes using a Gaussion approximation［J］.IEEE Trans Inform Theory，2001，47（2）:567－570.

［15］ BONELLO N，CHEN Sheng，HANZO L.Construction of regular Quasi－Cyclic protograph LDPC codes based on vandermondematrices［J］.IEEE Transactions Veh Technol，2008，54（4）:2583－2588.