Design of bilayer lengthened LDPC codes over expanded graph for relay channels①

Liu Yang (劉 洋), Li Ying

(State Key Laboratory of ISN, Xidian University, Xi’an 710071, P.R.China)

?

Design of bilayer lengthened LDPC codes over expanded graph for relay channels①

Liu Yang (劉 洋), Li Ying②

(State Key Laboratory of ISN, Xidian University, Xi’an 710071, P.R.China)

This paper presents a low complexity optimized algorithm for design of bilayer lengthened LDPC (BL-LDPC) code for decode-and-forward relay system. The design is performed over the expanded graph of the BL-LDPC code, which consists of the original bilayer graph and the extra added relay-generated parity check bits. To build up our proposed optimized algorithm, we present a modified Gaussian approximation algorithm for the expanded structure of the BL-LDPC code. Then using the proposed optimized algorithm, we find the optimum overall expanded graph of the BL-LDPC code. Simulation results show that the BL-LDPC codes obtained by our proposed optimized algorithm have excellent bit-error-rate performances and small gaps between the convergence thresholds and the theoretical limits when transmitted over the additive white Gaussian noise channels.

bilayer LDPC codes, relay channel, decode-and-forward, Gaussian approximation，channel capacity

0 Introduction

The three-node relay channel was introduced in Ref.[1] and the first capacity results were presented in Ref.[2]. While the capacity of the general relay channel is still unknown, recent years there have been a vast amount of researches on this topic, both in the information theory and coding communities. Among them, one main relay protocol is the decode-and-forward (DF) relay scheme, which is proved to achieve the capacity of the relay channel for certain special cases[2]. The classic DF technique is based on random binning[1], where the relay decodes the source data and provides a re-encoded copy (bin index) of the source message to the destination.

One of the important researches for practical implementation of a DF relay scheme is the design of practical codes. In this research field, authors in Ref.[3] proposed a novel bilayer LDPC code used in Gaussian relay channel, which was designed to approach the information theoretic limit of the DF scheme. Bilayer LDPC codes consist of two general types called bilayer-expurgated LDPC (BE-LDPC) codes and bilayer-lengthened LDPC (BL-LDPC) codes.

A bilayer LDPC code consists of one higher rate code optimized for the source-to-relay link as well as one lower rate code optimized for the source-to-destination link. As for BL-LDPC code, the lower rate code is designed first and then the higher rate code is designed by increasing the codeword length while keeping the parameters of the lower rate code unchanged. In other words, designing a BL-LDPC code corresponds to finding a bilayer graph so that the lower graph corresponds to a good LDPC code at rate R-optimized for SNR-, while the bilayer graph represents a good LDPC code at rate R+optimized for SNR+. More researches on the design of BL-LDPC codes were found in Refs[4-6]. In Ref.[4], the authors designed BL-LDPC codes for the Gaussian relay channel using irregular check degrees. The design of BL-LDPC code for Rayleigh fading relay channels was studied in Ref.[5]. Authors in Ref.[6] proposed a technique to design complexity-optimized BL-LDPC codes. However, these designs are all based on the bilayer graph not on the overall expanded graph of the BL-LDPC codes, which expands with an addition of extra parity check bits from the relay.

The authors in Ref.[7] first proposed a BL-LDPC code design when joint decoding was performed over the overall expanded graph. The optimization algorithm was based on density evolution, including three steps.

They first optimized the lower graph of BL-LDPC codes at R-, then fixing the lower graph, optimized the upper graph of BL-LDPC codes so that the bilayer graph of BL-LDPC codes was optimized at R+. In the last stage, they optimized the overall expanded graph at R-by fixing the optimized BL-LDPC code. This three-stage method resulted in a lack of global optimization. Meanwhile, since density evolution algorithm is an infinite-dimensional problem, this optimization algorithm is very much complex.

In this study, a low complexity algorithm is proposed for the design of the BL-LDPC codes over the overall expanded graph, denoted as expanded BL-LDPC codes. To simplify the process, only the mean of message updates will be tracked, which are supposed to be Gaussian mixtures[8]. Based on this fact, a modified Gaussian approximation for the expanded BL-LDPC codes will be presented. The proposed algorithm aims at optimizing the degree distributions of the lower variable nodes and the upper variable nodes simultaneously. the bit-error-rate (BER) performances of the expanded BL-LDPC codes obtained by the proposed optimization algorithm will be simulated and their decoding thresholds will be calculated using the modified Gaussian approximation. Simulation results show that the proposed expanded BL-LDPC codes are excellent in BER performances and small gaps between the convergence thresholds and the theoretical limits.

1 Preliminaries

1.1 DF strategy

A Gaussian degraded relay channel is shown in Fig.1, where X1and X2denote the transmitted signals from the source and relay while Y and Y1denote the received signals at the destination and relay. The transmission can be defined by

(1)

where Z1～N(0,N1) and Z2～N(0,N1+N2) denote Gaussian noises at relay and destination respectively. The power constraints at the source and relay are P1and P2. The overall DF rate at source is

(2)

where α is the optimal cooperation factor to maximize the rate. To ensure a successful decoding at the destination, the rate for relay’s codeword X2must satisfy

(3)

Please refer to Ref.[2] to review a full DF strategy.

Fig.1 Gaussian degraded relay channel model

1.2 Coding for DF

Based on the DF strategy in Ref.[1], authors in Ref.[3] formulized a general code design problem for the scheme. The code design involves the construction of two codebooks: source codebook X1and relay codebook X2. The relay codebook X2can be constructed as a conventional error-correcting code that guarantees successful decoding at the destination. In contrast, the source codebook X1must be constructed so that it can be decoded successfully at both relay and destination. The source’s codebook needs to be designed at two SNR values. The first SNR value ensures the relay can successfully decode X1at SNR+=αP1/N1while the second SNR value ensures a successful decoding of X1with the help of extra parity bits from the relay at SNR-=αP1/(N1+N2).

The code construction problem is illustrated in a schematic form shown in Fig.2, where

(4)

denote the effective source-to-relay and source-to-destination rates. These two rates are the targeted rates for the bilayer LDPC code design.

Fig.2 The achievable rates R+, R- and R2 using DF strategy

2 Expanded BL-LDPC code design

2.1 Expanded BL-LDPC code description

The Tanner graph of the BL-LDPC code structure[3]is depicted in Fig.3. It is divided into lower and upper graphs, which have n1and n2variable nodes respectively. Both sets of the variable nodes are connected to k1check nodes. Note that the bilayer graph corresponds to a lengthened version of the lower graph by adding n2variable nodes while keeping k1check nodes fixed. As mentioned above, designing a BL-LDPC code corresponds to finding the bilayer graph so that the lower graph corresponds to a good LDPC code at rate R-optimized for SNR-while the bilayer graph represents a good LDPC code at rate R+optimized for SNR+.

Fig.3 Tanner graph of a BL-LDPC code

In this work, BL-LDPC code design over the overall expanded graph is proposed which consists of the bilayer graph of the BL-LDPC code and the relay-generated parity bits. The overall expanded graph of the BL-LDPC code is depicted in Fig.4, where it adds up k2extra relay-generated parity bits. At this point onwards, the Tanner graph in Fig.4 is refered as an expanded bilayer lengthened LDPC code (EBL-LDPC) and the Tanner graph in Fig.3 as a bilayer lengthened LDPC code (BL-LDPC).

Fig.4 Tanner graph of an expanded BL-LDPC code

Note that there are three edge types in Fig.4. The first edge type connects the sets of n1variable nodes and k1check nodes while the second edge type connects n2variable nodes and k1check nodes. The third edge type corresponds to the edges between n2variable nodes and k2extra parity bits. Now define two parameters η1and η2which denote the percentages of the first edge type and the second edge type respectively. It is easy to obtain the following relations.

(5)

The conventional design of EBL-LDPC codes can be divided into three stages. In the first stage, optimize the first edge type at R-which represents a good LDPC code for the lower graph of the BL-LDPC code in Fig.3. In the second stage, fixing the first edge type, optimize the second edge type so that the bilayer graph of the BL-LDPC code is a capacity-approaching LDPC code at R+. In the last stage, fixing the optimized BL-LDPC code at R+, search the third edge type in order that the overall expanded graph of the BL-LDPC code is optimized at R-.

2.2 A modified Gaussian approximation for the EBL-LDPC codes

In this section, only the mean of message updates is tracked instead of the complete distribution, based on which a modified Gaussian approximation algorithm is presented to design the EBL-LDPC codes over the overall expanded graph.

(6)

Hence, the average means of message updates at the n1and n2variable nodes are obtained as follows.

(7)

Similarly, working with the message updating rule at the check nodes, it is easy to obtain:

(8)

(9)

Based on Eq.(6), the overall mean of message updates at the variable nodes is defined. This yields to

(10)

(11)

According to Ref.[8], a necessary condition to obtain a successful decoding is given by

(12)

Eq.(12) is approximated linearly in λ[i,0,0]and λ[0,j,k], which allows for linear optimization programming.

2.3 EBL-LDPC code optimization

The overall expanded BL-LDPC codes can be now optimized. The most powerful algorithm probably consists of optimizing simultaneously n1variable nodes with degree distribution λ[i,0,0]and n2variable nodes with degree distribution λ[0,j,k].

(13)

(14)

From Eq.(13), the following relation can be obtained:

(15)

(16)

subject to:

(17)

(18)

(19)

A parameter μkis introduced in Ref.[3]. It is slowly increased at each optimization iteration and approaches 1 eventually.

3 Simulation results

In this paper, since it is needed to compare the results with those in Ref.[7], only the case of additive white Gaussian noise (AWGN) channel is dealt with.

Recall that in Ref.[7], using density evolution, the code design starts with optimizing the bilayer graph of the BL-LDPC code at R+=0.7, which takes place in three stages. First, optimize the first edge type using an optimized irregular LDPC code at R-=0.5. Second, fix the optimized first edge type, and design the BL-LDPC code at R+=0.7 by adding n2variable nodes using the second edge type. In the next step, the optimized bilayer graph is fixed and the overall expanded graph is designed at R-=0.5 using the third edge type. They designed the optimized degree distribution (node-perspective) in the right side of Table 1. Denote this code as CODE(Ref). The gaps between the convergence thresholds of CODE(Ref) and the theoretical limits are calculated, denoted by gap+and gap-respectively.

Table 1 The degree distributions of CODE and CODE(Ref)

at target rate (R+,R-)=(0.7,0.5)

For ease of comparison, take an overall code length of 10000 bits and denote this code as CODE. Applying our proposed optimized algorithm, the EBL-LDPC code is designed for (R+,R-)=(0.7,0.5) and then the optimized degree distributions (node-perspective) are given in the left side of Table 1.

The convergence thresholds of CODE(Ref) are within 0.3266dB and 0.2312dB from the theoretical limits at R+=0.7 and R-=0.5, which are calculated using Gaussian approximation. In comparison, the convergence thresholds of CODE obtained by our proposed algorithm are within 0.3040dB and 0.205dB from the theoretical limits at R+=0.6925 and R-=0.4875. The gaps are slightly smaller than those in Ref.[7]. Although there exists minor rate loss, this is admissible as stated in Ref.[3]. Fig.5 plots the BER performances of these two codes. These curves show that the BER performance of CODE designed by our proposed algorithm is also slightly better than that of CODE(Ref) designed by density evolution. Here, it should be noted that the performance gains are more than the drop in theoretical limits due to the minor rate loss.

To summarize, compared with the optimization process in Ref.[7], the proposed algorithm has low complexity while maintaining the same optimization accuracy as density evolution. Specially, our optimization algorithm is based on a modified Gaussian approximation which can convert an infinite-dimension problem of density evolution to a one-dimensional problem. By doing this, the complexity can be significantly reduced. Besides, the optimization process in Ref.[7] is divided into three stages which lacks of global optimization. Our algorithm is performed in one step which can optimize the degree distributions λ[i,0,0]and λ[0,j,k]simultaneously and the gaps to the theoretical limits of the proposed codes are smaller.

Fig.5 Compare the BER performances of CODE with that of CODE(Ref). Solid straight lines represent theoretical limits of CODE; dashed straight lines represent the convergence thresholds of CODE

4 Conclusion

In this study, a low complexity optimized algorithm is proposed for the design of BL-LDPC codes over the expanded graph by adding up the extra relay-generated parity check bits. A modified Gaussian approximation algorithm is presented to build up the optimized algorithm and analyze the asymptotic performances. Our proposed algorithm shows that it is possible to optimize the degree distributions of the lower and the upper variable nodes simultaneously. Simulation results show that the BL-LDPC codes obtained by using the proposed low complexity algorithm have slightly better BER performances and smaller gaps to theoretical limits compared with those obtained by density evolution algorithm in Ref.[7].

Reference

[1] Thomas M C, Abbas A E G. Capacity theorems for the relay channel. IEEE Transactions on Informactions Theory, 1979, 25(5): 572-584

[2] Gerhard K, Michael G, Piyush G. Cooperative strategies and capacity theorems for relay networks. IEEE Transactions on Informactions Theory, 2005, 51(9): 3037-3063

[3] Peyman R, Wei Y. Bilayer low-density parity-check codes for decode-and-forward in relay channels. IEEE Transactions on Informactions Theory, 2007, 53(10): 3723-3739

[4] Marwan H A, Jinhong Y, Jun N, et al. Improved bilayer LDPC codes using irregular check node degree distribution. In: Proceedings of IEEE Symposium Information Theory, Toronto, Canada, 2008.141-145

[5] Osso V, Masoud S. Design of bilayer lengthened LDPC codes for Rayleigh fading relay channels. In: Proceedings of the 45th Annual Conference on Information Sciences and Systems, Baltimore, USA, 2011. 1-5

[6] Osso V, Masoud S. Design of complexity- optimized bilayer lengthened LDPC codes for relay channels. In: Proceedings of the 49th Annual Allerton Conference Allerton House, Monticello, USA, 2011. 1019-1024

[7] Azmi M H, Yuan J H. Performance of bilayer-lengthened LDPC codes under joint decoding. In: Proceedings of IEEE Information Theory Workshop, Taormina, Italy, 2009. 163-167

[8] Chung S Y, Richardson T J, et al. Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation. IEEE Transactions on Informaction Theory, 2001, 47(2): 657-670

Liu Yang, born in 1988. She is now studying for a Ph.D degree in State Key Lab of ISN, Xidian University. She received her B.S. degree from Xidian University in 2010. Her research interests include the construction of LDPC codes, spatially coupled codes and the design of LDPC codes for relay systems.

10.3772/j.issn.1006-6748.2015.04.017

①Supported by the National Basic Research Program of China (No. 2012CB316100) and the National Natural Science Foundation of China (No. 61072064, 61201140, 61301177).

②To whom correspondence should be addressed. E-mail: yli@mail.xidian.edu.cn Received on July 14， 2014, Su Yuping