Network Coding Based on Linear Block Codes for Multi-source Cooperative Relaying Networks

LI Zong-yan()，LI Shi-yin()，LI De-liang()

1 School of Information and Electrical Engineering，China University of Mining and Technology，Xuzhou 221116，China

2 Xuzhou College of Industrial Technology，Xuzhou 221140，China

Introduction

Relaying and cooperation have attracted many researchers’ attention for the improvement of the wireless network performance.Recently，there has been an increasing interest in applying the idea of network coding[1- 6]to the cooperative relay scenario.The idea of network coding was originally proposed to enhance the capacity of wired networks[7].Then，the idea was extended to wireless networks to enable efficient relay[8].Most existing network coding schemes demonstrate that network coding approach provides an efficient way to generate spatial diversity under the constraint of limited resources.Since the network coding techniques are applied in various cellular/relaying structures in which the relay serves as a cooperating source，such an approach leads to a more efficient exploitation of the relay resources.

In a cooperative scenario where multiple sources have distinct messages to transmit，the available resources must be shared to support multi-source data transmission.It is more beneficial to allow intermediate nodes to process different messages before forwarding the destination，rather than process the message from each source individually.This idea of treating different messages as mathematical entities，on which finite field algebraic operations can be performed，is known as network coding.

For instance，there are some ideas proposed to consider data aggregation for two sources.Hausletal.evaluated the performance of decode-and-forward (DF) strategy over multiple access relay channel (MARC)，in that the relay sends the network coded version of codewords from the two sources，x1⊕x2to the destination instead ofx1andx2respectively[9].Given the same spectrum efficiency，the scheme using the XOR-operation shows the performance improvement.This work was extended in Ref.[10] where the log-likelihood ratio (LLR) ofx1⊕x2was relayed to the destination.And this work was further studied to consider data aggregation for multiple sources[11-13].Although interesting results are reported in some current studies，it is recognized that a broad range of issues still need further research.

Taking the issues above into account，in this paper，we try to study the multi-source single-relay uplink cooperation networks and focus on the relay-coded matrix design for multi-source cooperation at relay node，the multi-source cooperative decoding of the pre-designed relay coding matrix，and the extrinsic information transfer (EXIT) chart analysis for iterative decoding at base station (BS).Meanwhile，at BS，it is shown that iterative decoding plays an important role in ensuring a good performance，and by enabling more scenarios that destination applies in iterative decoding，significant improvement can be achieved.

1 System Description

1.1 System model

Relay cooperative system model，withM(M≥2) sources (denoted asS1，S2，…，SM) transmitting independent information (denoted asu1，u2，…，uM) to the BS via a single relay node (RN)，is considered as shown in Fig.1.At the source nodeSm，the information blockumis encoded into its corresponding codewordcm，m=1，2，…，M.Thus，one transmission data packet consists of two phases，withMsources，and one RN taking turns to transmit.In the first phase，each source node broadcasts the coded data to RN and BS.After decoding the received data packets ofMsources，RN performs encoding processing on the data streams according to the pre-assigned relay-coding matrix and forwards the coded data streams to BS through relay (RN-BS) link in the second phase.During the process，the RN and BS received signal fromm-th source nodeSmat a time can be expressed as

ymR=hmR·xm+nmR，ymB=hmB·xm+nmB，
m=1，2，…，M．

(1)

The BS received signal from RN at a time can be written as

yRB=hRB·xR+nRB,

(2)

wherexmis the transmitted symbol bySm，xRis the forwarded symbol by RN.hmR，hmB，andhRBare channel fading coefficients.nmR，nmB，andnRBare complex zero-mean Gaussian noise with single sided power spectral densityN0.For simplicity，in this paper，we assume that all the source-relay links are error free.

Fig.1 Multi-source one-relay network

1.2 Network coding based on linear block codes

There are many ways，such as random network coding and linear block codes，which can be used for the multi-source network coding at RN.In this paper，we consider the relay network coding based on linear block codes.At BS，the multi-source one-relay network can be represented by a transfer matrix which in turn can be seen as a generator matrix of a systematic linear block code.

At timek，defineC(k)=[c1(k)，c2(k)，…，cM(k)] the coded data fromS1，S2，…，SMthat are received at RN.As described in Fig.1，the relay output isP=[P1，P2，…，PM]=G′CT，whereG′={g(i，j)} is anM×Mrelay coding matrix andgi，j∈{0，1}，i，j=1，2，…，M.For simplicity，we design one type of relay coding matricesG′ which is based on row (or column) circulant permutation.At BS，coded data fromMsources together with extra redundancy forwarded by RN form a systematic low-density-generator-matrix (LDGM) code with generator matrixG(the generator matrix may be dense)，whereG=[IG′] is anM×2Mcoding matrix which consists of two parts，an identity matrixIon the left and matrixG′ on the right.

The parity check matrix of these coded data can be expressed asH=[G′TI]，notice thatHis also sparse，and therefore LDGM codes[14]can be considered as a particular class of low-density-parity-check (LDPC) codes，which can be decoded by particularizing decoding algorithm for standard LDPC codes.

In this paper，we denote those systematic codes by (U，V) LDGM codes in which all theMcheck codes have degreeV+1，all theMsystematic bit nodes have degreeU，and each of theMcoded bit nodes has degree 1 and is associated to its corresponding check nodes.

TakeM=4 for example，considering (2，2) and (3，3) LDGM codes，the generator matrices are as follows.

(3)

The corresponding parity check matrices of these codes can be expressed as below.

(4)

2 Cooperative and Iterative Decoding Principle

2.1 Reference scheme

We set the reference scheme as a typical DF-based relay scheme that the relay decodes the data for each source node and only forwards the same data for a certain source node by repetition.In such scenario，there are two paths of information，one from direct link and another from relay link，at BS for each source.

For a transmitted binary phase shift keying (BPSK) symbolxmfrom them-th source node，the LLR is defined as

(5)

which is often termed as the priori information ofxm.

In the reference scheme，we calculate the conditional LLR

(6)

L(xm)=0，when the a priori information ofxmis not available at BS.It should be noted that whenL(um)=0，Eq.(6) is exactly the maximal ratio combining (MRC) which is the optimal diversity process with two receiving copies.

2.2 Cooperative decoding

For the proposed system shown in Fig.1 with M-source using the RN simultaneously，the data from the source nodes are coded according to the pre-assigned relay-coding matrix at RN.

At BS，we can get the check matrixHcorresponding to the generator matrixG.TakeGM=4(3，3) as an example，and the corresponding check matrixHM=4(3，3) is given in Eq.(4).

Thus，we can see thatHis anM×2Mcheck matrix.In terms of check matrixH，we can obtain the factor graph.The factor graph has both variable nodes，representing the codeword bits，and parity check nodes，representing the parity check equations of the code’s parity check matrix.According to the row and column of check matrixH，different computations are performed to utilize the extrinsic principle.Therefore，a priori information of each source decoder can be obtained through the multi-source cooperative decoding under belief propagation (BP) algorithm.

LetLpriordenote the received priori LLR of the cooperative decoder.qi→jdenotes LLR message passed from the variable-nodeito the check-nodej.ri←jdenotes the LLR message passed from the check-nodejto variable-nodei.Lextoutdenotes the extrinsic information output of the cooperative decoder.

Define function:

(7)

The main operations of multi-source cooperative BP decoding algorithm can be synthesized as below.

(1) Initialization，qi→j=0，ri←j=0，i=1，2，…，2M，j=1，2，…，M.

(2) Each column performs the following computation for its outgoing LLR messageqi→jto check nodej.

(8)

(3) Each row performs the following computation for its outgoing LLR messageri←jto variable nodei.

(9)

(4) The extrinsic information output

(10)

whererow[j]{i} denotes the set of row locations of the non-zero’s in thej-th row，excluding locationi;col[i]{j} denotes the set of column locations of the non-zero’s in thei-th column，excluding locationj.

2.3 Iterative decoding

The reference scheme carries out direct decoding to the received MRC data，while the iterative decoding algorithm is used for the proposed scheme.

At BS，for the proposed scheme，the decoder consists of two blocks，denoted as relay cooperative decoder (RCD) and a group of single-source channel decoders (CD).The iterative decoding structure is shown in Fig.2，and the process bears the decoding principle of turbo codes.

Fig.2 Iterative decoding structure between cooperative decoder and a group of channel decoders

It is important to note that，in all the computations above，only the so-called extrinsic information is exchanged between the component blocks.Due to the sub-optimal nature of the iterative decoding scheme，we prefer the term “reliability” to the term “probability” when referring to the quantities at the input and output of the soft-input soft-output (SISO) channel decoder block，usually referred to as a priori and a posteriori probabilities.

The overall decoding algorithm at BS can be described as follows.

(1) As initialization step，the priori probability of the multi-source coded information at the input of cooperative decoder corresponds to complete uncertainty (a value equal to 0 in the LL domain)，LAR=0.

(2) Decoding starts from cooperative decoder，which computes output reliabilitiesLERfrom channel observationsymBandyRB.ThenLERis passed through a bit interleaver to generate the a priori inputLAmof the channel decoder group.

(3) The group of channel decoders，thus，computes the extrinsic informationLEmwhich is passed through an inverse bit interleaver to become the a priori inputLARof the cooperative decoder.

(4) The algorithm iterates between steps (2) and (3) until no more improvement is observed or a maximum number of iteration (IT) is performed.

(5) At the end of the process，the complete (not extrinsic) reliabilities are computed by the channel decoder group and a decision output is made.

One important issue in the decoding implementation of this scheme is the processing of the extrinsic information including both systematic and parity information of each participating source node.We use the conventional BCJR maximum a posteriori probability (MAP) algorithm[15]for the calculation of LLR of the parity information.

3 EXIT Charts Analysis of the Iterative Decoder

The EXIT chart is considered as a useful engineering tool to analyze the performance of iterative decoding.The decoding process can then be represented as a recursive update of the mutual information (MI) in the EXIT charts.If MI converges to 1，it is possible to predict that the bit error ratio (BER) will converge.

At this point，we are interested in the computation of the EXIT charts of two decoding blocks.In general，the analytical computation of the EXIT curve is a difficult task，approximate computation can be accomplished by Monte Carlo simulations[16].Within the approximation of the EXIT chart-based analysis，the iterative decoding process converges to the final signal-to-noise ratio (SNR) threshold.

In the following discussion，we study the EXIT charts of the two components marked in Fig.2.For iterations between the two components，the extrinsic information is usually measured by MI.As shown in Fig.2，MI at the output of each decoder block is denoted asIERandIEm，respectively; MI at the input of each decoder block is labeledIARandIAm，respectively.ViewingIERas a function ofIARand theEb/N0value of the direct link and relay link，the EXIT characteristics are defined as

IER=T1(IAR，Eb/N0),

(11)

whereEbis the received energy per bit andN0is the one-sided power spectral density.

Similarly，given a particular SNR，the EXIT characteristics are defined as

IER=T2(IAR).

(12)

It is shown that given a particular SNR，convergence of the decoding process can be obtained if the tunnel between the two EXIT curves is open[7].In other words，if the tunnel between the two EXIT curves is at pinch-off，a small SNR increment should be sufficient to open it.

The performance of the considered scheme，first studied through an EXIT chart-based analysis，is evaluated in terms of BER versusEb/N0.In the simulation，we use the systematic rate 1/2 recursive systematic convolutional (RSC) codes with generator (013，015) as the channel codes.

In Fig.3，EXIT curves are shown for (2，2) and (3，3) LDGM codes withM=4，which are computed atEb/N0=0.0 dB over AWGN channel.Note that the SNR does not influence the EXIT curve relative to the channel decoder.It is easy to see that the tunnel is closed in Figs.3(a) and (b)，respectively.

(a) EXIT chart of relay network coding with (2，2) LDGM code (tunnel is closed)

(b) EXIT chart of relay network coding with (3，3) LDGM code (tunnel is closed)

In Fig.4，EXIT curves are shown for these two schemes，which are computed atEb/N0=1.5 dB.It is immediately recognized that the tunnel is at pinch-off: convergence at this and lower values ofEb/N0is not possible in Fig.4(b).Nevertheless，the EXIT curve as shown in Fig.4(a): the tunnel is still closed.

In Fig.5，EXIT curves are shown for two different schemes atEb/N0=2.5 dB.It can be observed that the tunnel is at pinch-off in Fig.5(a).

(a) EXIT chart of relay network coding with (2，2) LDGM code (tunnel is closed)

(b) EXIT chart of relay network coding with (3，3) LDGM code (tunnel is near pinch-off)

(a) EXIT chart of relay network coding with (2，2) LDGM code (tunnel is near pinch-off)

(b) EXIT chart of relay network coding with (3，3) LDGM code (tunnel is open)

Figures 6，7，and 8 depict the EXIT charts with transfer characteristics over a set ofEb/N0values (0.0，0.75，2.5 dB) for (2，2) and (5，5) LDGM codes withM=6.Note that in the graphical representation the iterative decoder characteristics are plotted up to their intersection，pinch-off，and opening; moreover，we can see that the convergence SNR thresholds predicted by the results in Figs.7(b) and 8(a) are respectively around 0.75 dB and 2.5 dB.

(a) EXIT chart of relay network coding with (2，2) LDGM code (tunnel is closed)

(b) EXIT chart of relay network coding with (5，5) LDGM code (tunnel is closed)

Figures 5(b) and 8(b) show trajectories of iterative decoding atEb/N0=2.5 dB; the trajectory is a simulation result taken from the “free-running” iterative decoder.In addition，it can be noted that the decoding generally convergences within 3 iterations in Figs.5(b) and 8(b).This is because the relay network coding in the vertical direction of check matrixHis for small value ofU.Hence the correction between the extrinsic information in this direction occurs quickly.

(a) EXIT chart of relay network coding with (2，2) LDGM code (tunnel is closed)

(b) EXIT chart of relay network coding with (5，5) LDGM code (tunnel is near pinch-off)

(a) EXIT chart of relay network coding with (2，2) LDGM code (tunnel is near pinch-off)

(b) EXIT chart of relay network coding with (5，5) LDGM code (tunnel is open)

4 Simulation Results

The proposed scheme has the same spectrum efficiency with the reference scheme，so we can focus on the BER performance only.

The performance of the considered system，is evaluated in terms of BER versusEb/N0of the relay link and direct link.A maximum number of 5 iterations are allowed.

Figure 9 shows the iterative decoding performance of the proposed relay network coding scheme against reference scheme over AWGN channel，in the case of rate 1/2 (2，2) and (3，3) LDGM codes forM=4.From Fig.9，we observe that the proposed scheme performs worse than the reference scheme at the low SNR regime.This is attributed to the poor channel messages of each source through soft information combining.However，the proposed scheme significantly outperforms the reference scheme at all BER values of interest with only a few iterations.More iterations do not help much.It can also be observed that good performance is obtained by (2，2) LDGM codes; moreover，the introduction of (3，3) LDGM codes shifts the BER curve to the left，with an SNR improvement of about 1.0 dB，as predicted by the EXIT charts-based analysis.

Figure 10 depicts the BER over theEb/N0under AWGN channel，in the case of rate 1/2 (2，2) and (3，3) LDGM codes forM=6.We can see similar performance as in Fig.9，which is also predicted by EXIT charts-based analysis.

Fig.9 BER performance of different schemes with M=4 over AWGN channel

Fig.10 BER performance of different schemes with M=6 over AWGN channel

5 Conclusions

A network coding matrix for the relay-based cooperative communication with flexible number of sources is presented and analyzed.The proposed scheme uses BP decoding algorithm for relay cooperative decoder.In particular，the iterative decoding between a cooperative decoder and a number of single-source decoders is implemented，which shows a fast convergence in only a few iterations with additional gains by the EXIT chart-based analysis.One type of relay network coding matrices at the relay，some implementation details，and simulation results have been provided.The proposed scheme has shown promising performance improvement over the scheme without multi-user cooperation at all BER values of interest.

[1] Hausl C，Dupraz P.Joint Network-Channel Coding for the Multiple-Access Relay Channel [C].IEEE Conference on Sensor and Ad Hoc Communication and Networks，Virginia，USA，2006: 817- 822.

[2] Xiao L，Fuja T，Kliewre J，etal.A Network Coding Approach to Cooperative Diversity [J].IEEETransactionsonInformationTheory，2007，53(10): 3714-3722.

[3] Ding Z G，Leung K，Goeckel D L，etal.On the Study of Network Coding with Diversity [J].IEEETransactionsonWirelessCommunications，2009，8(3): 1247-1259.

[4] Du J F，Xiao M，Mikael S.Cooperative Network Coding Strategies for Wireless Relay Networks with Backhaul [J].IEEETransactionsonCommunications，2011，59(9): 2502- 2514.

[5] Bui H C，Meric H，Lacan J.A Cooperative Network Coding Strategy for the Interference Relay Channel [J].IEEEWirelessCommunicationsLetters，2012，1(5): 456- 459.

[6] Kim D，Kim H M，Im G H.Improved Network-Coded Cooperative Transmission with Low-Complexity Adaptation to Wireless Channels [J].IEEETransactionsonWirelessCommunications，2012，59(10): 2916- 2926.

[7] Ahlswede R，Cai N，Li S R，etal.Netwrok Information Flow [J].IEEETransactionsonInformationTheory，2000，46(4): 1204-1216.

[8] Yeung R W，Li S R，Cai N，etal.Network Coding Theory [J].FoundationsandTrendsinCommunicationsandInformationTheory，2005，2(4): 241-329.

[9] Hausl C，Schreckenbach F，Oikonomidis I，etal.Iterative Network and Channel Decoding on a Tanner Graph [C].Processing of the 39th Allerton Conference on Communication，Control and Computing，Urbana Champaign，USA，2005: 1-10.

[10] Lin R，Martin P A，Taylor D P.Two-User Cooperative Transmission Using Superposition Modulation and Soft Information Combining [C].IEEE 72nd Vehicular Technology Conference Fall，Ottawa，Canada，2010: 1- 5.

[11] Cao L.A Relay-Coding Matrix for Multi-user Cooperation Communications [C].IEEE International Conference on Communications (ICC)，Kyoto，Japan，2011: 1-5.

[12] Zhang X H，Ghrayed A，Hasna M.On Relay Assignment in Network-Coded Cooperative Systems [J].IEEETransactionsonWirelessCommunications，2011，10(3): 868- 876.

[13] Li J，Yuan J H，Malaney R，etal.Full-Diversity Binary Frame-Wise Network Coding for Multiple-Source Multiple-Relay Networks over Slow-Fading Channels [J].IEEETransactionsonVehicularTechnology，2012，61(3): 1346-1360.

[14] Garcia-Frias J，Zhang W.Approaching Shannon Performance by Iterative Decoding of Linear Codes with Low-Density Generator Matrix [J].IEEECommunicationsLetters，2003，7(6): 266- 268.

[15] Brink S T，Kramer G，Ashikhmin A.Design of Low-Density Parity-Check Codes for Modulation and Detection [J].IEEETransactionsonCommunications，2004，52(4): 670- 678.

[16] Brink S T.Convergence of Iterative Decoding [J].IEEEElectronicsLetters，1999，35(10): 806- 808.