Open Access Research

Diversity analysis, code design, and tight error rate lower bound for binary joint network-channel coding

Dieter Duyck1*, Michael Heindlmaier2, Daniele Capirone3 and Marc Moeneclaey1

Author Affiliations

1 Department of Telecommunications and Information processing, Ghent University, St-Pietersnieuwstraat 41, B-9000 Gent, Belgium

2 Technische Universität München, München, Germany

3 Politecnico di Torino, Torino, Italy

For all author emails, please log on.

EURASIP Journal on Wireless Communications and Networking 2012, 2012:350  doi:10.1186/1687-1499-2012-350


The electronic version of this article is the complete one and can be found online at: http://jwcn.eurasipjournals.com/content/2012/1/350


Received:10 February 2012
Accepted:21 September 2012
Published:21 November 2012

© 2012 Duyck et al; licensee Springer.

This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Joint network-channel codes (JNCC) can improve the performance of communication in wireless networks, by combining, at the physical layer, the channel codes and the network code as an overall error-correcting code. JNCC is increasingly proposed as an alternative to a standard layered construction, such as the OSI-model. The main performance metrics for JNCCs are scalability to larger networks and error rate. The diversity order is one of the most important parameters determining the error rate. The literature on JNCC is growing, but a rigorous diversity analysis is lacking, mainly because of the many degrees of freedom in wireless networks, which makes it very hard to prove general statements on the diversity order. In this article, we consider a network with slowly varying fading point-to-point links, where all sources also act as relay and additional non-source relays may be present. We propose a general structure for JNCCs to be applied in such network. In the relay phase, each relay transmits a linear transform of a set of source codewords. Our main contributions are the proposition of an upper and lower bound on the diversity order, a scalable code design and a new lower bound on the word error rate to assess the performance of the network code. The lower bound on the diversity order is only valid for JNCCs where the relays transform only two source codewords. We then validate this analysis with an example which compares the JNCC performance to that of a standard layered construction. Our numerical results suggest that as networks grow, it is difficult to perform significantly better than a standard layered construction, both on a fundamental level, expressed by the outage probability, as on a practical level, expressed by the word error rate.

Keywords:
Joint network-channel coding; Slow Rayleigh fading; Diversity; Low-density parity-check codes

1 Introduction

Point-to-point communication has revealed many of its secrets. Driven by new applications, research in wireless communication is now focusing more on the optimization of communication in wireless networks. For example, the joint operation of multiple network layers can be optimized, denoted as cross-layer design [1,2], thereby leaving the classical layered architectures, such as the seven-layer open systems interconnect (OSI) model ([3], p. 20). Another example of network optimization is cooperative communication, where multiple nodes in the network cooperate to improve their error performance. Cooperation may occur in many forms at different layers, e.g., cooperative channel coding at the physical layer and network coding at the network layer. Network coding refers to the case where the intermediate nodes in the network are allowed to perform encoding operations over multiple received streams from different sources. In a standard layered construction, the decoding of the network code is performed at the network layer, after the point-to-point transmissions have been decoded at the physical layer. Channel coding refers to the case where nodes perform coding over one point-to-point wireless link only. Cooperative channel coding is achieved by letting one or more relays transmit redundant bits for one source at a time. Usually, channel coding and network coding are studied separately (e.g., [4-6] for cooperative channel coding and [7-11] for network coding).

Standard linear network coding consists of taking linear combinations of several source packets. In general, non-binary coefficients are used in the linear combinations. In JNCC, cooperative channel coding (e.g., decode and forward [12]) and cross-layer design are combined, by using the network code for decoding at the physical layer. The rationale behind JNCC is to improve the joint error rate performance (i.e., the average error rate performance over all users participating in the network) by letting the redundancy of the network code help to decode the noisy channel output [13]. In that case, a joint optimization of the network and channel code is useful. For example, one can opt to let the network and channel code be represented by one parity-check matrix of a binary code, referred to as joint network-channel coding (JNCC). Hence, the coefficients multiplying the packets in the case of standard linear network coding are replaced by matrices in the case of JNCC.

Mostly, the two most important performance metrics are (R,Pe), where R is the information rate and Pe is the error rate. Here, we consider a fixed information rate R, so that the aim is to minimize Pe for a given point-to-point channel quality, expressed by γ, the signal-to-noise ratio (SNR) per symbol. Expressing the asymptotic (for large γ) error rate as <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M1">View MathML</a>, where g and d are defined as the coding gain and the diversity order, respectively, improving the performance refers to maximizing first d and then g (because d has the larger impact). Next to minimizing the error rate, scalability of the code design (e.g., to larger networks) is also an important criterion often recurring in the literature. JNCC is increasingly proposed as an alternative to a standard layered construction, such as the OSI model. However, it must be verified that important metrics, such as the diversity order d and the scalability to large networks, are not negatively affected.

Binary JNCC received much attention in the last years. Pioneering articles [14,15] designed turbo codes and LDPC codes, respectively, for the multiple access relay channel (MARC) and for the two-way relay channel [16]. However, the code design was not immediately scalable to general large networks and did not contain the required structure to achieve full diversity. The study of Hausl et al. [14-16] was followed by the interesting study of Bao et al. [17], presenting a JNCC that is scalable to large networks. However, this JNCC was not structured to achieve full diversity and has weak points from a coding point of view [18]. A deficiency in the literature, for general networks with a number of sources and relays, is the lack of a detailed diversity analysis in the case that the sources can act as a relay (which is for example the model assumed by [17]). The effect of the parameters of the JNCC on the diversity order is in general not known, because of the many degrees of freedom in such networks. Related to this, we mention [19,20], where the authors designed a JNCC for the case where the sources cannot act as a relay, but other nodes play the role of relay to communicate to one destination. As the source nodes are excluded to act as a relay node in this model, the diversity analysis in [19,20] is different from ours.

In this article, we consider a JNCC where the network code forms an integral part of the overall error-correcting code, that is used at the destination to decode the information from the sources. The rest of the article is organized as follows. In Section ‘Diversity analysis of JNCC’, we perform a diversity analysis, leading to an upper bound on the diversity order of any linear binary JNCC following our system model, and to a lower bound on the diversity order for a particular subset of linear binary JNCCs. The upper and lower bound depend on the parameters of the JNCC and can be used to verify whether a particular JNCC has the potential to achieve full diversity on a certain network. Second, in Section ‘Practical JNCC for <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M2','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M2">View MathML</a>’, a specific JNCC of the LDPC-type is proposed that achieves full diversity for a well identified set of wireless networks. The scalability of this specific JNCC to large networks is discussed. The coding gain c is not considered in the body of the article and the parameters of our proposed code may be further optimized by applying techniques such as in [19], to maximize c. To assess the performance of the proposed JNCC, we determine the outage probability, a well known lower bound of the word error rate, in Section ‘Lower bound for the WER’. We also present a tighter word error rate lower bound in Section ‘Calculation of a tighter lower bound on WER’, that takes into account the particular structure of the JNCC. In Section ‘Numerical results’, the numerical results corroborate the established theory. We also briefly comment on the coding gain achieved by the proposed JNCC and conclusions are drawn for different classes of large networks.

The main contribution of this article is to indicate the effect of the parameters of the JNCC on the diversity order, for networks that fit our channel model. More specifically, we propose an upper and lower bound on the diversity order, a scalable code design and a new lower bound on the word error rate that is tighter than the outage probability and thus better suited to assess the performance of the overall error-correcting code. The main contributions are summarized in the lemmas, propositions and corollaries. These can be a guide for any coding theorist designing JNCCs. Further, our numerical results suggest that as networks grow, it is difficult to perform significantly better than a standard layered construction, both on a fundamental level, expressed by the outage probability, as on a practical level, expressed by the word error rate. This conjecture is important, because one will now need to clearly motivate the use of JNCC instead of a standard layered construction, given the extra efforts that are required for JNCC.

This article extends the study, published in [18], by also considering non-perfect source-relay channels, by considerably extending the diversity analysis, by providing an achievability proof for the diversity order of the proposed JNCC, by clearly indicating the set of wireless networks where the proposed JNCC is diversity-optimal, by providing a tighter lower bound on the word error rate, and by providing more numerical results.

2 Joint network-channel coding

We first illustrate joint network-channel coding by means of a simple example. Consider two sources orthogonally broadcasting a vector of symbols, mapped from the binary vectors s1 and s2, respectively, to a relay and a destination. This channel is denoted as a multiple access relay channel (MARC) in the literature. Supposing that the relay is able to decode the received symbols, the relay computes a binary vector r1, which is mapped to symbols and transmitted to the destination. The relation between all bits is expressed by the JNCC, whose parity-check matrix has the following general form,

(1)

The matrix Hp represents the parity-check matrix for the point-to-point channel code. Each of the binary vectors s1, s2, and r1, can be separately decoded using this code. The bottom part of H represents the GLNC, which we denote as <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M4">View MathML</a>. It expresses the relation between r1, s1, and s2. More specifically, we have

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M5','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M5">View MathML</a>

(2)

Note that GLNC includes standard network codes used in an OSI communication model as a special case. In the latter case, the matrices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M6','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M6">View MathML</a> and Hi (considering more than one relay in general) are identity matrices or all-zero matrices, so that the network code simplifies to the relay packet being a linear combination of source packets, also expressed as XORing of packets or symbol-wise addition of packets.

Ideally, the overall matrix H conforms optimized degree distributions that specify the LDPC code. When the channels between sources and relay are perfect, we can drop the first three sets of rows and only keep the GLNC, represented by HGLNC; in this case the information bits of the code are s1 and s2, and r1 contains the parity bits. This is still a JNCC as the redundancy in the network code is used to decode the received symbols on the physical layer at the destination. In [21,22], it is proved that the matrices Hp do not affect the diversity order in the case of the MARC.

3 System model

We consider wireless networks with ms sources directly communicating to a common destination (e.g., cellphones communicating to a base station). Two time-orthogonal phases are distinguished. In the source phase, the sources orthogonally broadcast their respective source packet. In the following relay phase, the relays orthogonally broadcast their respective packet. All considered sources overhear each other during the source phase, and act as relay in the relay phase. Other nodes, not acting as a source, might be present in the network (i.e., overhearing the sources) and also act as relay. Hence, we consider a total of mr relays, where mr ms. This general network model, which is practically relevant as it fits many applications, is adopted in, e.g., [17]. Take for example any large network and consider a volume in space (cf. picocells or femtocells) where all nodes can overhear each other. These nodes form sub-networks and can be modeled by our proposed model. Note that in the literature, sometimes other models are assumed, such as the M N − 1 model [19,20], where M sources are helped by N relays (the relays are nodes different from the sources) to communicate to one destination.

All devices have one antenna, are half-duplex and transmit orthogonally using BPSK modulation. The K information bits of each source are encoded via point-to-point channel codes into a systematic codeword, denoted as source codeword, of length L, expressed by the column vector <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M7','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M7">View MathML</a> for user us, us ∈ [1,…,ms]. The parity-check matrix of dimension (L K) × L of this point-to-point codeword is denoted by Hp, which is the same for each user us, so that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M8','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M8">View MathML</a> for all us. In the relay phase, each relay ur, ur ∈ [1,…,mr], transmits a point-to-point codeword <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M9','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M9">View MathML</a> of length L to the destination, also satisfying <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M10','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M10">View MathML</a>. Hence, all slots have equal duration, the coding rate of the point-to-point channels is <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M11','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M11">View MathML</a>, and the overall coding rate is <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M12','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M12">View MathML</a>. We define the fraction of source transmissions in the total number of transmissions as the network coding rate <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M13','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M13">View MathML</a>, so that Rc = Rc,pRn. The overall codeword of length (ms + mr)L is expressed by the column vector

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M14','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M14">View MathML</a>

(3)

The destination declares a word error if it can not perfectly retrieve all ms K information bits, and the overall word error rate is denoted by Pew.

All relevant channels between differenta pairs of network nodes are assumed independent, memoryless, with real additive white Gaussian noise and multiplicative real fading (Rayleigh distributed with expected squared value equal to one). The fading coefficient of a wireless link is only known at the receiver side of that link. We consider a slow fading environment with a finite coherence time that is longer than the duration of the source phase and the relay phase, so that the fading gain between two network nodes takes the same value during both phases. We denote the fading gain from node u to the destination as αu, with <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M15','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M15">View MathML</a>. All point-to-point channels have the same average signal-to-noise ratio (SNR), denoted by γ. Differences in average SNR between the channels would not alter the diversity analysis, on the condition that the large SNR behavior inherent to a diversity analysis refers to allb SNRs being large. Denoting the received symbol vector at the destinationc in timeslot i as yi, the channel equation is

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M16','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M16">View MathML</a>

(4)

where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M17','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M17">View MathML</a> is the noise vector in timeslot i, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M18','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M18">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M19','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M19">View MathML</a> (BPSK modulation).

Hence, at the destination, each of the ms independent fading gains between the sources and the destination affects 2L bits (L bits in the source phase and L bits in the relay phase) and each of mr ms fading gains between the non-source relays and the destination affects L bits, assuming that all mr relays could decode the messages received from the sources. Hence, from the point of view of the destination, the overall codeword is transmitted on a block fading (BF) channel with mr blocks, each affected by its own fading gain, where msblocks have length 2L and mr ms blocks have length L. This notion will be essential in the subsequent diversity analysis (Section ‘Diversity analysis of JNCC’).

In the source phase, relay ur attempts to decode the received symbols from sources belonging to the decoding set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M20','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M20">View MathML</a>. The users that are successfully decoded at relay ur are added to its retrieval set, denoted by <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M21','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M21">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M22','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M22">View MathML</a>, with cardinality <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M23','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M23">View MathML</a>. Next, in the relay phase, relay ur transmits a relay packet, which is a linear transformation of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M24','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M24">View MathML</a> source codewordsd originated by the sources from the transmission set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M25','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M25">View MathML</a> of relay ur, with <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M26','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M26">View MathML</a>. If <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M27">View MathML</a>, then relay ur does not transmit anything. In Section ‘Diversity analysis of JNCC’, we show that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M28','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M28">View MathML</a> is an important parameter that strongly affects the diversity order.

For example, user 3 attempts to decode the messages from users 1, 2, and 5, and succeeds in decoding the messages from users 1 and 5 from which a linear transformation is computed. Hence, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M29','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M29">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M30','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M30">View MathML</a>, l3 = n3 = 2. Because the channel between a node and the destination remains constant during both source and relay phases, a relay has no interest in including its own source message in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M31','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M31">View MathML</a>.

Using the transmission set for each relay, the GLNC in Equation (2) generalizes to

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M32','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M32">View MathML</a>

(5)

where the matrices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M33">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M34','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M34">View MathML</a> are of dimension K × L. Hence, each transmitted relay codeword <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M35','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M35">View MathML</a> is a linear transformation of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M36','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M36">View MathML</a> source codewords. The superscript ur in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M37','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M37">View MathML</a> indicates that the vector <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M38','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M38">View MathML</a> is in general not transformed by the same matrix for all relays ur where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M39','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M39">View MathML</a>. The overall parity-check matrix H is thus expressed as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M40','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M40">View MathML</a>

(6)

where Hc is block diagonal with Hp on its diagonal, representing the channel code, and

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M41','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M41">View MathML</a>

(7)

represents the GLNC.

Table 1 provides an overview of the notation presented in the system model.

Table 1. Overview of notation for JNCC for larger networks

4 Diversity analysis of JNCC

Before passing to the actual diversity analysis, we provide the well-known formal definition of the diversity order ([23], Chap. 3).

Definition 1

The diversity order attained by a code <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M54','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M54">View MathML</a> is defined as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M55','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M55">View MathML</a>

where γ is the signal-to-noise ratio.

In other words, Pew γd, where ∝ denotes proportional to.

In the proofs of propositions in this article, we will often use the diversity equivalence between a BF channel and a block binary erasure channel (block BEC), which was proved in [24,25]. A block BEC channel is obtained by restricting the fading gains in our model to belong to the set {0,}, so that a point-to-point channel is either erased or perfect. Denoting the erasure probability <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M56','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M56">View MathML</a> by ε, a diversity order d is achieved if Pew εd for small ε[26]. A diversity order of d is thus achievable if there exists no combination of d − 1 erased point-to-point channels leading to a word error. On the other hand, a diversity order of d is not achievable if there exists at least one combination of d − 1 erased channels leading to word error.

In this section, we present the relation between the diversity order d and the parameters <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M57','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M57">View MathML</a>, as well as between d and the choice of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M58','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M58">View MathML</a>. This guides the code design and furthermore, the potential, of a linear binary JNCC satisfying some conditions, to achieve full diversity, can be verified without performing Monte Carlo simulations.

We first prove that the diversity order is a function of only the network coding rate Rn (Section ‘Diversity as a function of the network coding rate’). We then determine in Section ‘Space diversity by cooperation’ the relation between the diversity order d and the set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M59','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M59">View MathML</a>, for any linear binary JNCC expressed as in Equations (6) and (7). The set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M60','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M60">View MathML</a> actually determines the maximal spatial diversity that can be achieved by cooperation, leading to an upper bound on the diversity order. In Section ‘A lower bound based on <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M61','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M61">View MathML</a> for <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M62','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M62">View MathML</a>’, we propose a lower bound on the diversity order in the case that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M63','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M63">View MathML</a>, which depends on all transmission sets <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M64','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M64">View MathML</a>. In Section ‘Diversity order with interuser failures’, we discuss how the diversity order is affected by interuser failures. Finally, in Section ‘Diversity order in a layered construction’, we briefly comment on the diversity order in a layered construction, such as the OSI model.

4.1 Diversity as a function of the network coding rate

We denote the maximum achievable diversity order by dmax. We will determine dmax in this section and show that it only depends on the network coding rate <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M65','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M65">View MathML</a>.

Proposition 1

Under ML decoding, the maximum diversity order dmax that can be achieved by any linear JNCC is

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M66','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M66">View MathML</a>

(8)

Proof

See Appendix 1. □

Note that the maximal diversity order does not depend on L. It can actually be reformulated in the following way:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M67','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M67">View MathML</a>

(9)

which for mr = ms = m reduces to the maximum diversity order for a standard BF channele with m blocks and coding rate Rn[27-29].

Hence, the maximum diversity order does not change when the point-to-point channel coding rate Rc,p changes. This corresponds with our intuition as the parity bits of the point-to-point codes only provide redundancy within one block forming a point-to-point codeword, hence these parity bits cannot combat erasures which affect the complete point-to-point codeword. Another consequence is that the maximal diversity order of JNCC cannot be larger than in a layered approach, with the same network coding rate.

In the remainder of the article, full diversity refers to the diversity order being equal to the maximal diversity order, d = dmax, from (8).

4.2 Space diversity by cooperation

We denote the word error rate for each source us by <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M68','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M68">View MathML</a>, which is the fraction of packets where at least 1 of the K information bits from source us is erroneously decoded at the destination. Associated to <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M69','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M69">View MathML</a>, we define <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M70','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M70">View MathML</a>, so that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M71','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M71">View MathML</a> for large γ. We have that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M72','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M72">View MathML</a>. From Definition 1, it follows that

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M73','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M73">View MathML</a>

(10)

Denote <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M74','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M74">View MathML</a>, us ∈ {1,…,ms}, as the number of times that source us is included in the transmission set of a relay: <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M75','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M75">View MathML</a><a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M76">View MathML</a>, where (.) is the indicator function, which equals one when its argument is true and zero otherwise. Some simple measures can be determined: <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M77','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M77">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M78','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M78">View MathML</a>. We will show that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M79','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M79">View MathML</a> depends on <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M80','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M80">View MathML</a> and thus, by Equation (10), d depends on tmin. We denote 1 + tmin by dR, which we call the space diversity order, as it is the minimal number of channels that convey a source message to the destination.

Proposition 2

For any linear JNCC, applied in our system model, the diversity order d is upper bounded as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M81','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M81">View MathML</a>

Proof

We use the diversity equivalence between a BF channel and block BEC [24,25]. Assume that the channel between source us and the destination is erased. Source us is included in at most <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M82','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M82">View MathML</a> transmission sets. Assume that all <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M83','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M83">View MathML</a> channels between the relays, that include source us in their transmission set, and the destination are also erased. Then the destination does not receive any information on source us so that it can never retrieve its message. The probability of occurrence of this event is <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M84','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M84">View MathML</a>, so that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M85','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M85">View MathML</a>, hence <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M86','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M86">View MathML</a>. Using Equation (10), we obtain Proposition 2. □

Note that the proof of Proposition 2 is based on the assumption that relay ur only considers packets transmitted in the source phase for inclusion in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M87','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M87">View MathML</a>. In the case that relay ur computes its relay packet also based on packets transmitted by other relays during the relay phase, the diversity order becomes more difficult to analyze.

In Corollary 1, we propose the conditions on tmin so that the space diversity order dR is not smaller than the maximum achievable diversity order.

Corollary 1

For any linear JNCC, applied in our system model, full diversity can be achieved only if tmin q, where

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M88','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M88">View MathML</a>

Proof

The proof follows directly from Propositions 1 and 2. □

Given a GLNC, and thus a choice of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M89','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M89">View MathML</a>, one can verify whether the condition in Corollary 1 holds. In the disaffirmative case, full diversity cannot be achieved. To get more insight for the code design, we consider the simplest case of a network code where the cardinality of the transmission set is constant (<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M90','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M90">View MathML</a>).

Corollary 2

For any linear JNCC, applied in our system model, with constant <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M91','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M91">View MathML</a>, full diversity can be achieved only if

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M92','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M92">View MathML</a>

(11)

Proof

It always holds that tmin ≤ ⌊tav ⌋ and if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M93','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M93">View MathML</a>, then <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M94','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M94">View MathML</a>. From Corollary 1, full diversity can be achieved only if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M95','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M95">View MathML</a>. Because <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M96','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M96">View MathML</a>, we have the necessary condition that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M97','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M97">View MathML</a>. As n is an integer, this bound can be tightened, yielding <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M98','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M98">View MathML</a>. Filling in q from Corollary 1 yields Corollary 2. □

Table 2 illustrates Corollary 2, showing the set of networks in which a certain parameter n is diversity-optimal, which means that the choice of n does not prevent the code to achieve full diversity. In Section ‘Practical JNCC for <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M99','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M99">View MathML</a>’, we propose a JNCC for n = 2, where taking n = 2 is diversity-optimal in all networks corresponding to bold elements in Table 2.

Table 2. Minimal value n for a JNCC with constant <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M100','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M100">View MathML</a> to maintain its capability to achieve full diversity

4.3 A lower bound based on <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M101','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M101">View MathML</a> for <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M102','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M102">View MathML</a>

A certain relay does not help one source only, but a combination of sources, expressed by the transmission set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M103','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M103">View MathML</a> for each relay ur. In this section, we provide a lower bound on the diversity order, based on the choice of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M104','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M104">View MathML</a>. If this lower bound and the upper bound in the previous section are tight, the exact diversity order of JNCCs can so be determined, as will be illustrated in Section ‘Practical JNCC for <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M105','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M105">View MathML</a>’.

Based on <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M106','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M106">View MathML</a> and mr, we construct the (ms + mr) × ms coding matrix M, where

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M107','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M107">View MathML</a>

(12)

The matrix M expresses the presence of a source-codeword in each transmission, i.e., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M108','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M108">View MathML</a> if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M109','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M109">View MathML</a> is considered in transmission i (i = 1,…,ms and i = ms + 1,…,ms + mr correspond to the source and relay transmission phases, respectively). Therefore, the upper part of M is an identity matrix as each source us transmits its own codeword <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M110','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M110">View MathML</a> in the source phase. The matrix M represents what is often called the “coding header” or “the global coding coefficients” in the network coding literature (see e.g., [30]).

Consider a block BEC channel where e of the mr blocks have been erased. The indices of the fading gains corresponding to the erased blocks are collected in the set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M111','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M111">View MathML</a>). Based on <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M112','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M112">View MathML</a>, we construct <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M113','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M113">View MathML</a> which corresponds to the subset of transmissions that are not erased, i.e., all rows <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M114','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M114">View MathML</a> (if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M115','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M115">View MathML</a>) and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M116','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M116">View MathML</a>, for i = 1,…,e, in M are dropped. We denote the rank of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M117','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M117">View MathML</a> as <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M118','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M118">View MathML</a>. The set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M119','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M119">View MathML</a> collects all possible matrices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M120','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M120">View MathML</a> which can be constructed from M if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M121','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M121">View MathML</a>.

Consider an example for ms = mr = 3. Assume that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M122','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M122">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M123','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M123">View MathML</a>, and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M124','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M124">View MathML</a>, so that

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M125','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M125">View MathML</a>

(13)

Next, assume that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M126','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M126">View MathML</a>. Hence, the channel between user 1 and the destination is erased, so that rows 1 and 4 from M are dropped:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M127','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M127">View MathML</a>

(14)

and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M128','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M128">View MathML</a>. It can be verified that all matrices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M129','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M129">View MathML</a> have rank <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M130','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M130">View MathML</a>. However, there exist matrices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M131','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M131">View MathML</a> having rank <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M132','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M132">View MathML</a>.

We can now define a metric that depends on <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M133','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M133">View MathML</a>.

Definition 2

We define dM = e + 1, where eis the maximal cardinality of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M134','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M134">View MathML</a> such that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M135','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M135">View MathML</a> for each <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M136','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M136">View MathML</a>.

A simple computer program can compute dM, given <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M137','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M137">View MathML</a> and mr.

Lemma 1

In a JNCC following the form of Equation (6) with ms = mr and constant <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M138','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M138">View MathML</a>, the metric dM is at most three.

Proof

If ms = mr and n = 2, then the minimum column weight of M is smaller than or equal to three. Erasing the three rows where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M139','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M139">View MathML</a>, for a certain us corresponding to the minimum column weight, leads to <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M140','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M140">View MathML</a> having at least one zero column, and thus <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M141','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M141">View MathML</a>. By Definition 2, dM < 4. □

In the next proposition, we provide a lower bound on the diversity order under ML decoding or Belief Propagation (BP) decoding [31]. We denote

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M142','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M142">View MathML</a>

(15)

which are square matrices of dimension L.

Proposition 3

Using ML decoding, the diversity order of a JNCC following the form of Equation (6) with constant <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M143','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M143">View MathML</a>, is lower bounded as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M144','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M144">View MathML</a>

if the matrices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M145','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M145">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M146','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M146">View MathML</a>, have full rank.

Using BP-decoding, the diversity order of a JNCC following the form of Equation (6) with constant <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M147','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M147">View MathML</a>, is lower bounded as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M148','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M148">View MathML</a>

if, for each ur, the set of L equations

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M149','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M149">View MathML</a>

(16)

can be solved with BP in the case of only one unknown source-codeword vector.

Proof

See Appendix 2. □

We can simplify the condition for BP decoding, stated in Proposition 3, when we assume that the parity bits of point-to-point codes do not have a support in HGLNC, or said differently, when the L K right most columns of the matrices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M150','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M150">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M151','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M151">View MathML</a> are zeroes. In that case, one iteration in the backward substitution, mentioned in Appendix 2, corresponds to solving the K unknown information bits of su via the set of K equations

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M152','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M152">View MathML</a>

(17)

In Section ‘Practical JNCC for <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M153','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M153">View MathML</a>’, we propose a JNCC where the parity bits of point-to-point codes do not have a support in HGLNC, so that we take (17) instead of (16) as condition for BP decoding in the remainder of the article.

4.4 Diversity order with interuser failures

It is often easier to prove that a particular diversity order is achieved assuming perfect interuser channels (see for example in Section ‘Practical JNCC for <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M154','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M154">View MathML</a>’). Here, we discuss how this diversity order is affected by interuser failures.

Lemma 2

In the case of non-reciprocal interuser channels, any JNCC achieves the same diversity order with or without interuser channel failures.

Proof

See Appendix 3. □

In the case of reciprocal interuser channels, the achieved diversity order with interuser failures depends on the transmission sets <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M155','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M155">View MathML</a>. We propose an algorithm to construct <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M156','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M156">View MathML</a> in Section ‘Practical JNCC for <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M157','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M157">View MathML</a>’ and we will then discuss the diversity order with reciprocal interuser channels.

4.5 Diversity order in a layered construction

In a layered construction, such as the standard OSI model, the destination first attempts to decode the point-to-point transmissions. If it can not successfully retrieve the transmitted point-to-point codeword for a particular node-to-destination channel, then it declares a block erasure, where a block refers to one point-to-point codeword. Denoting this block erasure probability by ε, we have that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M158','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M158">View MathML</a> ([23], Equation (3.157)). If for example e blocks of length L are erased, then the decoding corresponds to solving a set of equations with eL unknowns.

Standard linear network coding consists of taking linear combinations of several source packets. In general, non-binary coefficients are used in the linear combinations. Hence, packets are treated symbol-wise, which is shown to be capacity achieving for the layered construction [8]. A consequence of this symbol-wise treatment is that the effective block length of the network code reduces to ms + mr and the set of equations, that are available at the destination for decoding, is expressed by the coding matrix <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M159','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M159">View MathML</a>. At this block length, ML decoding (which is equivalent to Gaussian elimination at the network layer) has low complexity. Under ML decoding, a sufficient condition for successful decoding is <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M160','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M160">View MathML</a>. Also, for ML decoding, the maximum number of erasures e= dM − 1 (Definition 2), so that the condition <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M161','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M161">View MathML</a> is satisfied, is equal to the minimum distance of the non-binary code minus one. The minimal distance is, for a given coding rate, maximum for maximum distance separable (MDS) codes, so that dM is maximum for MDS codes as well. Also note that random linear network codes are MDS codes with high probability for a sufficiently large field size [32].

Table 3 provides an overview of the notation presented in this diversity analysis.

Table 3. Overview of notation introduced in the diversity analysis

Tables 1 and 3 indicate the complexity of the analysis of JNCC for large networks.

5 Practical JNCC for <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M173','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M173">View MathML</a>

In the literature, a detailed diversity analysis is most often lacking. Codes were proposed and corresponding numerical results suggested that a certain diversity order was achieved on a specific network. It is sometimes not clear why this diversity order is achieved, and how it would vary if the network or some parameters change. In the previous section, we made a detailed diversity analysis of a JNCC following the form of Equation (6). However, the utility of for example Proposition 3 is limited to JNCCs following the form of Equation (6) with a constant <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M174','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M174">View MathML</a>, which suggests that it is very hard to rigorously prove diversity claims in general. However, the modest analysis made in Section ‘Diversity analysis of JNCC’ can be applied in some cases and we will show its utility through an example.

We consider networks with ms = mr = m ≥ 4 and a JNCC following the form of Equation (6) with <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M175','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M175">View MathML</a> for ur = 1,…,m. We will rigorously prove that a diversity order of three is achieved, using the propositions of Section ‘Diversity analysis of JNCC’. From Table 2, it can be seen that this JNCC is diversity-optimal for m = 4 and m = 5. In Section ‘Numerical results’, we provide numerical results for m = 5.

From Table 2, it is clear that restricting n to two is not diversity-optimal in larger networks. However, it also has some advantages. If n = 2, then every relay just needs to decode 2 users, and encoding is restricted to taking a linear transformation of only two source packets. Furthermore, taking n = 2 does not impose infeasible constraints on the number of sources in the vicinity of a relay in the case that spatial neighborhoods are taken into account. Next, the theoretical analysis is simpler in the case n = 2. Finally, taking n = 2 allows to reuse strong codes designed for the multiple access relay channel, e.g., in [21,22].

Besides the diversity order, we indicated in Section ‘Introduction’ that scalability is also very important. The JNCC proposed here is scalable to any large network without requiring a redesign of the code. This means that we provide an on the fly construction method. The latter is particularly important for self regulating networks. As a node adds itself to the network, it can seamlessly integrate to the network. Together with the new symbols sent by the new node, a new JNCC code is formed which still possesses all desirable properties. Finally, note that due to the large block length of JNCC, ML decoding is too complex and low-complexity techniques, such as BP decoding, must be used.

Hence, two properties are claimed: scalability to large networks and a diversity order of three (which is full diversity in some cases) under BP decoding. The JNCC code is presented in two steps. First, we present the design of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M176','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M176">View MathML</a> and thus the coding matrix M. In a second step (Equation (20)), we specify the matrices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M177','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M177">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M178','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M178">View MathML</a> and we will prove that the scalability and the diversity order of three are achieved.

5.1 First step: design of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M179','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M179">View MathML</a>

The transmission sets <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M180','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M180">View MathML</a> have a large impact on the diversity order. For example, in [18], a random construction was studied (each relay chooses n = 2 sources at random) and it was shown that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M181','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M181">View MathML</a>, but <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M182','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M182">View MathML</a> as well, so that most probably tmin < 2 and dR < 3 (Proposition 2). So we need a more intelligent construction.

We present an algorithm to determine <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M183','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M183">View MathML</a>, given ms and mr, and we subsequently determine the corresponding metrics tmin and dM. We define the function <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M184','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M184">View MathML</a> which adapts the modulo operation to the range <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M185','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M185">View MathML</a>.

Algorithm 1

Choose transmission set<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M186','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M186">View MathML</a>.

The transmission set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M187','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M187">View MathML</a> is expressed via the bottom part of M. An example of such a matrix M is given in Equation (18) for ms = mr = 5.

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M188','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M188">View MathML</a>

(18)

If a node is added as a source node, it adopts the largest source index, ms + 1, and relay-only nodes, with indices larger than or equal to ms + 1, increment their index by one. The function <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M189','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M189">View MathML</a> is updated to the new ms. Note that the algorithm corresponds to a deterministic cooperation strategy, which avoids extra signalling to the destination regarding the code design.

We first consider the case of perfect interuser channels and prove that Algorithm 1 yields d = 3 (Corollary 3). We then consider interuser failures and prove that the diversity order is not affected (Lemma 3).

Corollary 3

Having perfect links from sources to relays, the diversity order of a JNCC, with ms = mr and with transmission set constructed via Algorithm 1, achieves a diversity order d = 3 using BP-decoding, if, for each ur, Equation (17) can be solved with BP in the case of only one unknown source-codeword vector.

Proof

Because the links between sources and relays are perfect, the relays will never stay silent. In the case that mr = ms and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M190','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M190">View MathML</a>, we have that tmin = tav = 2 and so dR = 3.

Next, we show that dM = 3 (and thus, according to Lemma 1, dM is maximized if n = 2). Consider <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M191','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M191">View MathML</a>. Without loss of generality, consider that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M192','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M192">View MathML</a>. Consider the set of equations <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M193','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M193">View MathML</a>. Variables <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M194','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M194">View MathML</a> can be recovered via the top ms − 2 rows of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M195','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M195">View MathML</a>. The two relays u1 and u2 having source us in their transmission set (<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M196','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M196">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M197','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M197">View MathML</a>, respectively) are

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M198','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M198">View MathML</a>

Hence, source 1 is included in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M199','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M199">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M200','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M200">View MathML</a>, and source 2 is included in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M201','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M201">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M202','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M202">View MathML</a>. Hence, relay transmission m − 1 can be used to retrieve source 1 and relay transmission m can be used to retrieve source 2, as long as m ≥ 4. Hence, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M203','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M203">View MathML</a> has full rank. The generalization to any set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M204','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M204">View MathML</a> satisfying <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M205','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M205">View MathML</a>, is straightforward. Therefore, we have that dM = 3.

As dR = dM = 3, the proof follows immediately from Propositions 2 and 3. □

Next, it can be proved that a JNCC applied in our system model has a diversity order of three, if it has a diversity order of three when all interuser channels are perfect. This is proved in general for non-reciprocal interuser channels in Lemma 2, and here, we consider reciprocal interuser channels.

Lemma 3

A JNCC, with transmission set constructed via Algorithm 1, achieves the same diversity order with or without interuser channel failures when ms > 4 or when ms = mr = m ≤ 4.

Proof

See Appendix 4. □

For conciseness, we do not consider the other cases, mr > ms ≤ 4.

5.2 Second step: JNCC of LDPC-type

In the first step, we specified <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M206','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M206">View MathML</a> and proved that dR = dM = 3 if mr = ms = m > 3. According to Corollary 3, a diversity order of three is achieved under BP decoding if, for each ur, Equation (17) can be solved with BP in the case of only one unknown source-codeword vector. In the second step, we specify the sub matrices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M207','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M207">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M208','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M208">View MathML</a>, ∀ur,us, to satisfy this condition, given that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M209','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M209">View MathML</a> is constructed according to Algorithm 1.

A simple solution is to replace the K left most columns in all K × L sub matrices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M210','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M210">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M211','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M211">View MathML</a>, ∀ur,us, by identity matrices. In this case, the joint network channel coding essentially reduces to a layered solution: the source-codewords are decoded at the relays and simply added according to Equation (5). If the network code is used at the physical layer, it has to deal with noise and a more advanced code might be required.

In the literature, a full-diversity close-to-outage performing JNCC for the Multiple Access Relay Channel (MARC) has been proposed [21,22], which is a code in the form of Equation (1). These codes are such that the set of equations

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M212','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M212">View MathML</a>

can be decoded via BP if only one coding vector s1, s2 or r1 is erased and the other coding vectors are perfectly known. We denote this JNCC by MARC-JNCC. The matrix HGLNC, MARC of the MARC-JNCC is given by Equation (A.7) in [21]f:

(19)

where sj = [1ij2ijpj] is the codeword from source j, with [1ij2ij] and pj denoting the information bits and the parity bits, respectively (j = 1,2); 1ij and 2ij each contain <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M214','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M214">View MathML</a> information bits. However, the parity bits pj are not involved in HGLNC, MARC. The matrices Ri, with i = 1,2,3, are random matrices, chosen according to the required degree distributions of the LDPC code. To facilitate future notation, we denote

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M215','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M215">View MathML</a>

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M216','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M216">View MathML</a>

and H3 = R3, so that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M217','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M217">View MathML</a>, where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M218','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M218">View MathML</a> (it will become clear hereunder which one has to be chosen at each relay). In <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M219','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M219">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M220','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M220">View MathML</a>, the first two block columns each consist of K/2 columns (corresponding to information bits) and the last block column consists of L Kcolumns (corresponding to parity bits from the point-to-point codes). The zero block columns indicate that parity bits from point-to-point codes have no support in these matrices. Now replace all sub matrices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M221','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M221">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M222','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M222">View MathML</a> by these matrices, for each relay ur, so that in each block column corresponding to information bits, we have a random matrix Ri; this is required to conform any preferred degree distribution of the LDPC code. For example, HGLNC can be given by

(20)

Each set of rows and each set of columns in H will have at least one random matrix, so that any LDPC code degree distribution can be conformed. We denote this JNCC by the SMARC-JNCC, where S stands for scalable.

Proposition 4

In a network following the system model proposed in Section ‘System model’ and using BP, the SMARC-JNCC achieves a diversity order d = 3.

Proof

Consider the set of K equations

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M224','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M224">View MathML</a>

(21)

In [21], it is proved that this set of K equations can be solved using the matrices proposed above. We provide another more simple proof here. Consider a block BEC. Because <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M225','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M225">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M226','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M226">View MathML</a> are upper- or lower-triangular, with ones on the diagonal, the unknown K information bits can be retrieved using backward substitution, hence it can be retrieved with BP as well.

By Corollary 3 and Lemma 3, the SMARC-JNCC achieves a diversity order d = 3. □

Note that the information bits of a source need to be split in two parts: bits of the type 1i and 2i. This allows the introduction of the matrices R1 and R2 in Equation 19, so that all information bits have a random matrix in their corresponding block column in the parity-check matrix. Now, the LDPC code can conform any degree distribution.

6 Lower bound for the WER

To assess the performance of the SMARC-JNCC we need to compare it with the outage probability limit (Section “Calculation of the outage probability”). We show that the outage probability limit is not always tight and we propose a tighter lower bound, which is presented in Section “Calculation of a tighter lower bound on WER”.

6.1 Calculation of the outage probability

The outage probability limit is the probability that the instantaneous mutual information between the sources and sinks of the network is less than the transmitted rate. The outage probability is an achievable (using a random codebook) lower bound of the average WER of coded systems in the limit of large block length [27,33,34].

For a multi-user environment, two types of mutual information are considered. First, it is verified whether the sum-rate, Rc in this case, is smaller than the instantaneous mutual information between all the sources and the sink. Then, it is verified whether each individual source rate, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M227','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M227">View MathML</a> in this case, is smaller than the instantaneous mutual information between the nodes, transmitting information for this source, and the destination. The outage probability for the MARC was determined in [21,35] using the method described above.

The outage probability is

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M228','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M228">View MathML</a>

where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M229','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M229">View MathML</a> is denoted as an outage event. Similarly as in [21,35], an outage event is given by

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M230','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M230">View MathML</a>

where

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M231','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M231">View MathML</a>

The terms I(Si;D), I(Ri;D), and I(Si;Rj) are the instantaneous mutual informations of the corresponding point-to-point channels with input x ∈ {−1,1}, received signal y = αix + w with <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M232','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M232">View MathML</a>, conditioned on the channel realization αi, which are determined by applying the formula for mutual information [36,37]:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M233','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M233">View MathML</a>

where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M234','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M234">View MathML</a> is the mathematical expectation over Y given x = 1 and αi.

We now consider the outage probability of a layered construction, such as the standard OSI model, where the destination first decodes the point-to-point transmissions, declaring a block erasure if decoding is not successful. For the network code, we assume a maximum distance separable (MDS) code, which is outage-achieving over the (noiseless) block-erasure channel [26]. That is, any ms correctly received packets suffice for decoding. Accordingly, an outage event for the layered construction, denoted as <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M235','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M235">View MathML</a> is given by

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M236','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M236">View MathML</a>

where

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M237','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M237">View MathML</a>

and

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M238','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M238">View MathML</a>

The outage probability for JNCC and a layered construction are compared in Figure 1 for ms = mr = 5, coding matrixg M given in Equation (18) and Rc,p = 6/7. The overall spectral efficiency is R = 3/7 bpcu, so that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M239','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M239">View MathML</a>.

thumbnailFigure 1. The outage probabilities of JNCC and a layered construction are compared. The spectral efficiency is R = 3/7 bpcu.

The main conclusion is that the difference between both outage probabilities is only 1 dB. Hence, on a fundamental level, the achievable coding gain by JNCC with respect to a standard layered construction is small for the adopted system model.

6.2 Calculation of a tighter lower bound on WER

According to information theory, the outage probability is achievable, where the proof relies on using random codebooks. However, the nature of the JNCC protocol largely deviates from a random code. For example, the parity bits corresponding to the point-to-point codes are forced in a block diagonal structure in Hc (see Equation 6), which is not taken into account in the outage probability limit. In fact, in Proposition 1, it was proved that the maximal diversity order does not depend on Rc but on Rn, which is not taken into account in the outage probability limit. Therefore, we argue that the outage probability limit is in general not achievable by a JNCC, which is illustrated by means of an example.

Consider a network with ms = mr = 3. The adopted point-to-point codes have coding rate Rc,p = 0.5, so that Rc = 0.25. We take nu = 2 and adopt the coding matrix M, given in Equation (13). Because of the small coding rate Rc, the outage probability achieves a diversity order of three (Figure 2). However, it follows from Proposition 1 that dmax = 2. We therefore propose a new lower bound, which takes into account the point-to-point codes.

thumbnailFigure 2. The conventional and tighter outage probability of JNCC are compared.

A bit node is essentially protected by two codes: a point-to-point code (Hc) and a network code (HGLNC), which is illustrated on the factor graph [38] representation (a Tanner notation [39] is adopted)h of the decoder (Figure 3).

thumbnailFigure 3. The depicted part of the factor graph (using a Tanner notation) illustrates that a bit node (bit i on the figure) is essentially connected to two sets of check nodes, corresponding with Hc and HGLNC, respectively. A set of check nodes is denoted as CND for check node decoder. The LLR-value coming from the CND corresponding with Hc is denoted as Lc. The LLR-value corresponding with the channel observation is denoted as Lobs,i.

Usually, both codes are characterized by separate degree distributions, denoted as (λc(x),ρc(x)) and (λGLNC(x),ρGLNC(x)) for Hc and HGLNC, respectively.

The new lower bound assumes a concatenated decoding scheme. At the destination, first the point-to-point codes are decoded and then soft information is passed to the network decoder. This is illustrated in Figure 4, where the soft information is denoted by the log-likelihood ratio (LLR) <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M240','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M240">View MathML</a>. Note that the bit node of bit i is duplicated to be able to clearly indicate <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M241','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M241">View MathML</a>. Applying the sum-product algorithm (SPA) on this factor graph or the original factor graph (without node duplication) is equivalent. This follows immediately from the sum-product rule for variable nodes (([40]see Section 4.4)) and ([38], Equation (5)).

thumbnailFigure 4. The bit node in Figure3 can be duplicated with a single edge between both nodes as shown in this figure. The LLR <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M242','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M242">View MathML</a> is the sum of all incoming LLR-values from the left, and contains the soft information which is passed to the network code decoder in a concatenated coding scheme.

The LLR <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M243','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M243">View MathML</a> can be viewed as a new channel observation as it remains fixed during the iterative decoding of the network code (HGLNC). The maximum rate that can be achieved by the network code is given by

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M244','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M244">View MathML</a>

The terms <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M245','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M245">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M246','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M246">View MathML</a> are the mutual informations between the channel input x ∈ {−1,1} and the associated random variable <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M247','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M247">View MathML</a>, conditioned on the channel realization αu, determined by applying the formula for mutual information [36,37], i.e., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M248','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M248">View MathML</a> is

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M249','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M249">View MathML</a>

The density of the random variable <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M250','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M250">View MathML</a> can be obtained by means of density evolution [41], given the degree distributions of the point-to-point code, or by means of Monte Carlo simulations, given the actual factor graph of the point-to-point code. Both approaches yield to the same results in our simulations.

Similarly to the conventional case, an outage event, denoted as <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M251','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M251">View MathML</a> is given by

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M252','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M252">View MathML</a>

Note that the network coding rate is used instead of the overall rate Rc, which corresponds to Proposition 1.

The tight lower bound presented here is a valid lower bound if the point-to-point codes are first decoded, followed by the network code, without iterating back to the point-to-point codes.

Let us now go back to the small network example with ms = mr = 3, considered in the beginning of this section. Figure 2 compares the conventional outage probability (Section ‘Calculation of the outage probability’) with the tighter lower bound proposed here. As mentioned before, the conventional outage probability has a larger diversity order than what is achievable, while the tighter lower bound only achieves a diversity order of two.

We are seeing a 3 dB difference at an outage probability of 10−4. To assess the performance of the network code only, given a certain point-to-point code, the WER of the SMARC-JNCC should be compared with the tight lower bound presented here. In the subsequent sections, we always include both lower bounds.

7 Numerical results

In this section, we provide numerical results for the SMARC-JNCC. We will clarify the proposed techniques on an illustrating network example, where ms = mr = 5 (Figure 5). We use the same network example as in [17,18] so that a comparison is possible.

thumbnailFigure 5. The network example that will be used in this document is illustrated. The solid lines represent interuser channels, the dashed line is the channel to the destination. Only the channels from the perspective of user 1 are shown for clarity, but all other users see equivalent channels.

For simplicity, we assume non-reciprocal interuser channel in the simulation results. Note that in the case that ms > 4 and Algorithm 1 is used to construct <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M253','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M253">View MathML</a>, reciprocity is irrelevant for our proposed code, as it applies that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M254','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M254">View MathML</a> if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M255','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M255">View MathML</a>.

We compare the error rate performance of the SMARC-JNCC with the outage probability limit and the tighter lower bound, which are presented in Section ‘Lower bound for the WER’, and with standard network coding techniques (using identity matrices in HGLNC) and a layered network construction (also using identity matrices in HGLNC, and where, at the destination, the network code is only decoded after decoding all point-to-point codewords separately and taking a hard decision).

The point-to-point code used in the simulations is an irregular LDPC code [41] characterized by the standard polynomials λ(x) and ρ(x) [41]:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M256','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M256">View MathML</a>

where λ(x) and ρ(x) are the left and right degree distributions from an edge perspective. The coefficients λi and ρi are the fraction of edges connected to a bit node and check node, respectively, of degree i. The adopted point-to-point code is fetched from [42], has coding rate Rc,p = 6/7 and conforms the following degree distributions:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M257','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M257">View MathML</a>

7.1 Perfect source-relay links

We start by assessing the performance of HGLNC, the bottom part of Equation (20), which determines the diversity order. Therefore, we assume perfect links between sources and relays. Hence, the channel model is the same as described in Section ‘System model’, with the exception of the interuser channels, which are assumed to be perfect (no fading and no noise). The parameters used for the simulation are K = L = 900, ms = mr = 5 (so that N = 10 K = 9000), where N is the block length of the overall codeword. The overall spectral efficiency is R = 0.5 bpcu, so that Eb/N0 = 2γ.

Figure 6 shows that a diversity order of 3 is achieved for SMARC-JNCC, which corroborates Corollary 3. It performs at 2.5 dB from the outage probability (because no point-to-point codes are considered, only the conventional outage probability is shown), which may be improved by optimizing the degree distributions. We also show a JNCC, where all submatrices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M258','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M258">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M259','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M259">View MathML</a>, ∀ur,us are replaced by identity matrices, denoted as the I-JNCC. Finally, we show an I-JNCC with irregular <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M260','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M260">View MathML</a>, with coding matrix M, given by

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M261','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M261">View MathML</a>

(22)

thumbnailFigure 6. The word error rate of the SMARC-JNCC is compared to that of the I-JNCC, assuming perfect source-relay channels.

It is clear that, even without optimizing the SMARC-JNCC, there is a benefit in terms of coding gain compared to the I-JNCC.

7.2 Rayleigh faded source-relay links

Now, we assess the performance of the complete parity-check matrix H of the SMARC-JNCC. We use the channel model as described in Section ‘System model’. Hence, all links have the same statistical model and the average SNR is the same for all channels. The parameters used for the simulation are K=606, Rc,p = 6/7, L = 707, ms = mr = 5 (so that N = 10L = 7070). The overall spectral efficiency is R = 3/7 bpcu, so that Eb/N0 = 7γ/3. Because the simulation time would be very large if every point-to-point source-relay link had to be decoded separately, we made an approximation. The word error rate of the point-to-point code when transmitted on a channel with fading gain α is smaller than 10−4when α2γ = 5.5 dB. Therefore, we assumed that a relay had correctly decoded the source-codeword if α2γ > 5.5 dB and not otherwise. We also add the performance of the SMARC-JNCC from Section ‘Perfect source-relay links’, corresponding to perfect source-relay links and R = 0.5 bpcu, as a reference curve (note that the reference curve corresponds to a larger spectral efficiency—the coding rate Rc is larger—than for the other curves, which slightly disadvantages the reference curve in terms of error performance).

Figure 7 shows that a diversity order of 3 is still achieved, which corroborates Proposition 4. In addition, two main conclusions can be made. First of all, the coding gain loss due to interuser failures is 6.5 dB, which is very large. Second, the benefit in terms of coding gain of the SMARC-JNCC compared to the I-JNCC is considerably decreased, compared to Section ‘Perfect source-relay links’, which corresponds to the small horizontal SNR-gap between the outage probabilities of a layered and joint construction. Also note that the tighter lower bound using density evolution, is close to the conventional lower bound in this case (probably due to the larger coding rate Rc,p). Finally, the WER performance of a layered construction is shown, which coincides with that of the I-JNCC.

thumbnailFigure 7. The word error rate of the SMARC-JNCC is compared to that of the I-JNCC and a layered construction, assuming Rayleigh faded source-relay channels. The reference curve is the performance of the SMARC-JNCC assuming perfect source-relay channels (Section ‘Perfect source-relay links’).

7.3 Gaussian source-relay links

We test again the complete parity-check matrix H of the SMARC-JNCC, now assuming that the source-relay links are Gaussian, having additive white Gaussian noise only, without fading; fading occurs on the source-destination and relay-destination links only. We assume that the average SNR is the same for all channels. The parameters used for the simulation are the same as in Section ‘Rayleigh faded source-relay links’.

Figure 8 shows that in the case of Gaussian interuser channels, the loss compared to perfect interuser channels is very small. Furthermore, the performance of the I-JNCC has improved a lot in comparison with Section ‘Perfect source-relay links’, where HGLNC only was used. The degree distributions causing the poor coding gain of the I-JNCC in Section ‘Perfect source-relay links’, have changed considerably through the point-to-point codes, significantly improving the coding gain.

thumbnailFigure 8. The word error rate of the SMARC-JNCC is compared to that of the I-JNCC, assuming Gaussian source-relay channels. The reference curve is the performance of the SMARC-JNCC assuming perfect source-relay channels (Section ‘Perfect source-relay links’).

8 Conclusion

We put forward a general form of joint network-channel codes (JNCCs) for a wireless communication network where sources also act as relay. The influence of important parameters of the JNCC on the diversity order is studied and an upper and lower bound on the diversity order are proposed. The lower bound is only valid for the case where the number of sources is equal to the number of relays, and where each relay only helps two sources.

We then proposed a practical JNCC that is scalable to large networks. Using the diversity analysis, we managed to rigorously prove its achieved diversity order, which is optimal in a well identified set of wireless networks. We verified the performance of a regular LDPC code via numerical simulations, which suggest that as networks grow, it is difficult to perform significantly better than a standard layered construction.

Appendix 1

Proof of Proposition 1

The maximal diversity order can be derived using the diversity equivalence between a block BEC and a BF channel [24,25]. Assume a block BEC, so that a block <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M262','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M262">View MathML</a> or <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M263','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M263">View MathML</a> is completely erased or perfectly known. Consider the case that e1blocks of length 2L and e2 blocks of length L have been erased, where e = e1 + e2 is the total number of erasures, e1 ms and e2 mr ms. Hence, the number of unknown bits is equal to e12L + e2L. Considering the structure of H from (6) containing the block-diagonal matrix Hc, it follows that the e12L + e2L erased bits appear in only (2e1 + e2)(L K) + mrK of the available (ms + mr)LmsK parity equations, i.e., (2e1 + e2)(L K) equations involving Hc and all mrK equations involving HGLNC. Hence, the unknown bits can be retrieved only if there are sufficient linearly independent useful equations. This yields the necessary condition:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M264','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M264">View MathML</a>

(23)

Denoting by e = e1 + e2 the total number of erased blocks, the largest value emax of e for which e1 and e2 satisfy (23) for all e1 ms and e2 mr ms is given by

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M265','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M265">View MathML</a>

(24)

Hence, dmax = emax + 1, yielding Proposition 1.

Appendix 2

Proof of Proposition 3

Before we present the actual proof, we first propose two lemmas.

Lemma 4

Any binary a × b matrix S, a b, where all rows have weight 2 cannot have full rank b.

Proof

If a matrix has full rank, there is no vector z 0 such that Sz = 0. However, if S has row weight 2, then S1 = 0, where 1 corresponds to a column vector with each entry equal to 1. □

Consider now a column vector of b unknown variables z and a set of constraints on these variables, which are stacked in S so that Sz = c, where c is a column vector of known constants. In general, solving S for z corresponds to performing Gaussian elimination of S. However, under some conditions, this simplifies to backward substitution.

Lemma 5

If a binary a × b matrix S, a b, has full rank b and maximal row weight of 2, Gaussian elimination simplifies to backward substitution.

Proof

Without loss of generality, we eliminate all redundant (linearly dependent) rows in S to obtain a square matrix of size b. By Lemma 4, there must be at least one row in S with unit weight to have full rank. Starting from this known variable, we can solve for a further variable in z at each step as the row weight is smaller than or equal to 2.

Assume that this backward substitution procedure cannot be continued until all variables are known. That is, after successive decoding, there are k rows consisting of a combination of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M266','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M266">View MathML</a> where neither <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M267','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M267">View MathML</a> nor <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M268','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M268">View MathML</a> are known. We split the matrix S into two parts: <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M269','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M269">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M270','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M270">View MathML</a>. The former comprises the rows involving only unknown variables (note that the weight of each row of Sunknown is 2). The latter consists of the rows involving only known variables. If the number of unknown variables is equal to k, then the rank of Sunknown must be equal to k which is impossible by Lemma 4. So, the matrix S was not full rank which contradicts our assumption. If the number of unknown variables is smaller than k, then there were redundant (linearly dependent) rows in Sknown which contradicts the assumptions again. We conclude that the procedure only fails if S does not have full rank. □

To prove Proposition 3, we use the diversity equivalence between a block BEC and the BF channel. In a block BEC, the channel Equation (4) simplifies to

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M271','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M271">View MathML</a>

(25)

where εi = 0 when the channel is erased and εi = 1 otherwise. Hence, εi = 0 if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M272','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M272">View MathML</a> and εi = 1 if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M273','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M273">View MathML</a>, where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M274','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M274">View MathML</a> is the complement of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M275','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M275">View MathML</a>.

Source-codewords si can be retrieved from the transmissions in the source phase if εi = 0. Decoding the other source-codewords at the destination is performed through the parity-check matrix H (Equation (6)). We split H in two parts:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M276','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M276">View MathML</a>

(26)

where Hleft and Hright have msL and mrL columns, respectively. We also define <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M277','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M277">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M278','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M278">View MathML</a>. As Hx = 0, we have that

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M279','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M279">View MathML</a>

(27)

As we consider a block BEC, some transmissions are perfect. As in Appendix 1, consider the case that e1 blocks of length 2L and e2 blocks of length L have been erased, where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M280','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M280">View MathML</a> is the total number of erasures, e1 ms and e2 mr ms. Considering the structure of H from (6) containing the block-diagonal matrix Hc, it follows that the e12L + e2L erased bits appear in only (2e1 + e2)(L K) + mrK of the available (ms + mr)L msK parity equations, i.e., (2e1 + e2)(L K) equations involving Hc and all mrK equations involving HGLNC. Next, (e1 + e2)K from the mrK equations involving HGLNC cannot be used to solve erased bits in s as these equations always have at least two unknowns. The overall set of equations to decode s thus becomes

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M281','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M281">View MathML</a>

(28)

or, using the notation from (15),

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M282','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M282">View MathML</a>

(29)

where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M283','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M283">View MathML</a> (BPSK modulation). We can stack the coefficients of all elements in s in a matrix Hs. For example, if ms = mr = 3, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M284','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M284">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M285','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M285">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M286','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M286">View MathML</a>, then

(30)

It is now easy to see that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M288','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M288">View MathML</a>, as defined in Section ‘A lower bound based on <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M289','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M289">View MathML</a> for <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M290','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M290">View MathML</a>’, is closely related to Hs: <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M291','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M291">View MathML</a> if [Hs](i−1)L + 1…iL,(j−1)L + 1…jL 0 and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M292','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M292">View MathML</a> if [Hs](i−1)L + 1…iL,(j−1)L + 1…jL = 0.

If <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M293','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M293">View MathML</a>, then <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M294','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M294">View MathML</a> has full rank, according to Definition 2. As established in Lemma 5, the set of equations represented by <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M295','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M295">View MathML</a> can be solved using backward substitution. This means that at each iteration, there is an equation with only one unknown. Consider a particular iteration and denote the index of the unknown by u. In Hs, this corresponds to an equation with an unknown source-codeword vector su of the type

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M296','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M296">View MathML</a>

(31)

or of the type <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M297','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M297">View MathML</a>.

Under ML decoding, we obtain what was claimed if the matrices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M298','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M298">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M299','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M299">View MathML</a> have full rank. Under BP decoding, we obtain what was claimed if, for each ur, the set of L Equation (30) can be solved with BP in the case of only one unknown source-codeword vector su.

Appendix 3

Proof of Lemma 2

A relay may not succeed in successfully decoding the message from a source, denoted as a failure. There are m2m interuser channels, which all have a probability of failure. Hence, there exist <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M300','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M300">View MathML</a>different cases, where each case corresponds to a combination of failures and successes. We denote the case where all interuser channels are successful as case 1.

Using Bayes’ law, the error rate can be split:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M301','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M301">View MathML</a>

(32)

Defining the diversity order corresponding to each case as <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M302','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M302">View MathML</a>, it follows that the overall diversity order is d = minidc,i.

The probability of f failures on independent interuser channels is proportional to <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M303','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M303">View MathML</a> ([23], Equation (3.157)) so that for this case i,

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M304','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M304">View MathML</a>

(33)

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M305','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M305">View MathML</a>

(34)

The diversity order in the case of perfect interuser channels (f = 0) is dc,1. That is, the error-correcting code can bear dc,1−1 erasures on node-destination links. Hence, dc,i dc,1 only if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M306','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M306">View MathML</a>, or, all information can still be retrieved at the destination, given that f interuser channels and dc,1f−1 node-destination channels are erased. Let us check whether this is true for all f.

A relay stays silent if it cannot decode all source codewords corresponding to its transmission set. If there are f interuser failures, there are at most f relays which stay silent in the relay phase. This corresponds to at most f additional node-destination erasures adding to the assumed dc,1f−1 already erased node-destination channels, yielding a total of at most dc,1−1 erased node-destination channels, which can be supported by the code, by the definition of dc,1.

Appendix 4

Proof of Lemma 3

In the case that ms > 4 and Algorithm 1 is used to construct <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M307','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M307">View MathML</a>, reciprocity is irrelevant for our proposed code, as it applies that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M308','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M308">View MathML</a> if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M309','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M309">View MathML</a>. Hence, if ms > 4, the proof given in Appendix 3 is always valid.

Now consider the case that dc,1 = 2, which corresponds to ms = mr = m < 4 (see Proposition 1). In the case of f = 1 interuser channel, dc,i is always larger than one, because <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M310','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M310">View MathML</a> as at least one channel, the source-destination channel, needs to fail to loose the corresponding information bits.

Finally, consider the case that ms = mr = m = 4 and thus dc,1 = 3. Hence, in the case of no interuser failures, the code can support two node-destination failures, corresponding to four erased transmissions from two nodes, in the source phase and in the relay phase. Reciprocity is relevant as <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M311','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M311">View MathML</a> if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M312','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M312">View MathML</a> for (i,j) is (1,3) and (2,4). Because <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M313','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M313">View MathML</a>, we only have to consider the case that f = 1, denoted as case i in general. Hence, in the case that the interuser channel between sources one and three or two and four have been erased, relays one and three or two and four, respectively, stay silent. Note that the transmission sets from the remaining active relays are disjoint when Algorithm 1 is used, and because n = 2, they support all sources us = 1,…,4. If one node-destination channel is consequently erased, which corresponds to at most two transmissions, the destination has to recover the information bits from the erased source-codeword. Because relay ur cannot have ur in their own transmission set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M314','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M314">View MathML</a>, the erased relay codeword does not contain any information on the erased source-codeword, which implies that the information is in the remaining relay codeword. Hence, we have that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M315','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M315">View MathML</a> or by (33), dc,i ≥ 3. In other words, interuser failures do not decrease the diversity order.

Endnotes

aUnless mentioned otherwise, we assume that channels are reciprocal, i.e., the channel from u1 to u2 is the same as the channel from u2 to u1.

bIn practice, increasing the SNR value can be achieved by increasing the transmission power of a node, so that both the SNR of the node-to-destination channels and channels between non-destination nodes increase.

cFor conciseness, we do not formulate the equation for channels between non-destination nodes.

dNote that relays u are not allowed to consider relay codewords <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M316','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M316">View MathML</a> for inclusion in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M317','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/350/mathml/M317">View MathML</a>. As a consequence, the right part of HGLNC is diagonal in Equation (7). This restriction was not always applied in the literature (e.g., [17]), but it simplifies the theoretical analysis and code design.

eA standard BF channel is a channel with B blocks of length L, where each block is affected by an independent fading gain. The maximal achievable diversity order on this channel is given by 1 + ⌊ B(1−Rc)⌋, where Rc is the coding rate [27-29].

fThe attentive reader will notice that the first two block rows in Equation (A.7) in [21] are not used here. These block rows are only necessary if a source is helped by one relay only and no point-to-point codes are available, which is not the case here.

gThe coding matrix expresses the transmission sets for each relay, which is required to determine the outage probability.

hFor a specific instance, the parity-check matrix can be graphically represented by a bipartite graph, denoted as a Tanner graph. The graphical Tanner graph representation is equivalent to the factor graph, which can be used for decoding.

Competing interests

The authors declare that they have no competing interests.

Acknowledgements

This study was supported by the European Commission in the framework of the FP7 Network of Excellence in Wireless COMmunications NEWCOM++ (contract no. 216715).

References

  1. S Shakkottai, TS Rappaport, PC Karlsson, Cross-layer design for wireless networks. IEEE Commun. Mag 41(10), 74–80 (2003). Publisher Full Text OpenURL

  2. V Srivastava, M Motani, Cross-layer design: a survey and the road ahead. IEEE Commun. Mag 43(12), 112–119 (2005)

  3. D Bertsekas, R Gallager, Data Networks (Prentice Hall, 1992)

  4. D Duyck, JJ Boutros, M Moeneclaey, Low-density graph codes for slow fading relay channels. IEEE Trans. Inf. Theory 57(7), 4202–4218 (2011)

  5. TE Hunter, in Coded cooperation: a new framework for user cooperation in wireless systems, Ph, ed. by . D. thesis (University of Texas at Dallas, 2004)

  6. JN Laneman, D Tse, GW Wornell, Cooperative diversity in wireless networks: efficient protocols and outage behavior. IEEE Trans. Inf. Theory 50(12), 3062–3080 (2004). Publisher Full Text OpenURL

  7. R Ahlswede, N Cai, S-YR Li, RW Yeung, Network Information Flow. IEEE Trans. Inf. Theory 46(4), 1204–1216 (2000). Publisher Full Text OpenURL

  8. R Koetter, M Médard, An algebraic approach to network coding. IEEE/ACM Trans. Netw 11(5), 782–795 (2003). Publisher Full Text OpenURL

  9. SYR Li, RW Yeung, N Cai, Linear network coding. IEEE Trans. Inf. Theory 49(2), 371–381 (2003)

  10. JK Rebelatto, BF Uchôa-Filho, Y Li, B Vucetic, Multi-user cooperative diversity through network coding based on classical coding theory. IEEE Trans. Sig. Process 60(2), 916–926 (2012)

  11. M Xiao, M Skoglund, M-user cooperative wireless communications based on non-binary network codes. in Proc, ed. by . Inf. Theory Workshop (ITW) (Volos, Greece, 2009), pp. 316–320

  12. G Kramer, M Gastpar, P Gupta, Cooperative strategies and capacity theorems for relay networks. IEEE Trans. Inf. Theory 51(9), 3037–3063 (2005). Publisher Full Text OpenURL

  13. Z Guo, J Huang, B Wang, JH Cui, S Zhou, P Willett, A practical joint network-channel coding scheme for reliable communication in wireless networks. in Proc, ed. by . of the ACM intern. symp. on mob. ad hoc netw. and comp. (Louisiana, New Orleans, 2009), pp. 279–288

  14. C Hausl, P Dupraz, Joint network-channel coding for the multiple-access relay channel. Proc. IEEE Commun. Soc. Sensor Ad Hoc Commun. Netw 3, 817–822 (2006)

  15. C Hausl, F Schreckenbach, I Oikonomidis, G Bauch, Iterative network and channel decoding on a tanner graph. in Proc, ed. by . Allerton Conf. on Commun. Control and Computing (Monticello, Illinois, 2005) (http://scholar, 2005), . google.com/citations?view_op=view_citation&hl=en&user=4GFQzXIAAAAJ&citation_for_view=4GFQzXIAAAAJ:d1gkVwhDpl0C webcite OpenURL

  16. C Hausl, J Hagenauer, Iterative network and channel decoding for the two-way relay channel. in Proc, ed. by . IEEE Int. Conf. on Comm (Istanbul, Turkey, 2006), pp. 1568–1573

  17. X Bao, JT Li, Generalized adaptive network coded cooperation (GANCC): a unified framework for network coding and channel coding. IEEE Trans. Commun 59(11), 2934–2938 (2011)

  18. D Duyck, D Capirone, M Heindlmaier, M Moeneclaey, Towards full-diversity joint network-channel coding for large networks. in Proc, ed. by . of Europ. Wirel. Conf (Vienna, Austria, 2011), pp. 1–8

  19. J Li, J Yuan, R Malaney, MH Azmi, M Xiao, Network coded LDPC code design for a multi-source relaying system. IEEE Trans. Wirel. Comm 10(5), 1538–1551 (2011)

  20. J Li, J Yuan, R Malaney, M Xiao, Binary field network coding design for multiple-source multiple-relay networks. in IEEE Int, ed. by . Conf. on Comm (Sydney, NSW, Australia, 2011), pp. 1–6

  21. D Duyck, D Capirone, JJ Boutros, M Moeneclaey, Analysis and construction of full-diversity joint network-LDPC codes for cooperative communications. Eur. J. Wirel. Commun. Netw 2010(Art ID 805216, 2010) (http://jwcn), . eurasipjournals.com/content/2010/1/805216 webcite OpenURL

  22. D Duyck, D Capirone, JJ Boutros, M Moeneclaey, A full-diversity joint network-channel code construction for cooperative communications. in Proc, ed. by . IEEE Intern. Symp. on Personal, Indoor and Mob. Radio Comm. (PIMRC) (Tokyo, Japan, 2009), pp. 1282–1286

  23. DNC Tse, P Viswanath, Fundamentals of Wireless Communication (Cambridge University Press, Cambridge, 2005)

  24. JJ Boutros, presentedat Controlled doping via high-order rootchecks in graph codes, IEEE Communication Theory Workshop Sitges (Catalonia, Spain, 2011) (Available online from http://www, 2011), . josephboutros.org/coding/root_LDPC_doping.pdf webcite OpenURL

  25. D Duyck, in Design of LDPC coded modulations for wireless fading channels, ed. by . Ph.D. dissertation (Ghent University, Ghent, Belgium)) in Press (to be published in 2012) OpenURL

  26. A Guillén i Fãbregas, Coding in the block-erasure channel. IEEE Trans. Inf. Theory 52(11), 5116–5121 (2006)

  27. A Guillén i Fãbregas, G Caire, Coded modulation in the block-fading channel: coding theorems and code construction. IEEE Trans. Inf. Theory 52(1), 91–114 (2006)

  28. R Knopp, PA Humblet, On coding for block fading channels. IEEE Trans. Inf. Theory 46(1), 189–205 (2000). Publisher Full Text OpenURL

  29. E Malkamaki, H Leib, Evaluating the performance of convolutional codes over block fading channels. IEEE Trans. Inf. Theory 45(5), 1643–1646 (1999). Publisher Full Text OpenURL

  30. PA Chou, Y Wu, K Jain, Practical network coding. in Proc, ed. by . Allerton Conf. on Communication, Control, and Computing ((Illinois, 2003)

  31. RJ McEliece, DJC MacKay, J-F Cheng, Turbo decoding as an instance of Pearl’s “belief propagation” algorithm. IEEE J. Sel. Area Commun 16(2), 140–152 (1998). Publisher Full Text OpenURL

  32. T Ho, M Médard, R Koetter, DR Karger, M Effros, J Shi, B Leong, A random linear network coding approach to multicast. IEEE Trans. Inf. Theory 52(10), 4413–4430 (2006)

  33. E Biglieri, J Proakis, S Shamai, Fading channels: information-theoretic and communications aspects. IEEE Trans. Inf. Theory 44(6), 2619–2692 (1998). Publisher Full Text OpenURL

  34. LH Ozarow, S Shamai, AD Wyner, Information theoretic considerations for cellular mobile radio. IEEE Trans. Veh. Technol 43(2), 359–379 (1994). Publisher Full Text OpenURL

  35. C Hausl, Joint network-channel coding for the multiple-access relay channel based on turbo codes. Eur. Trans. Telecommun 20(2), 175–181 (2009). Publisher Full Text OpenURL

  36. TM Cover, JA Thomas, Elements of Information Theory (Wiley, New York, 2006)

  37. G Ungerboeck, Channel coding with multilevel/phase signals. IEEE Trans. Inf. Theory IT-28(1), 55–67 (1982)

  38. F Kschischang, B Frey, H-A Loeliger, Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theory 47(2), 498–519 (2001). Publisher Full Text OpenURL

  39. M Tanner, A recursive approach to low complexity codes. IEEE Trans. Inf. Theory 27(5), 533–547 (1981). Publisher Full Text OpenURL

  40. H Wymeersch, Iterative Receiver Design (Cambridge University Press, Cambridge, 2007)

  41. TJ Richardson, RL Urbanke, Modern Coding Theory (Cambridge University Press, Cambridge, 2008)

  42. D Hamdani, E Safrianti, Construction of short-length high-rates LDPC codes using difference families. Makara, Teknologi 11(1), 25–29 (2007)