Abstract
Joint networkchannel 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 errorcorrecting code. JNCC is increasingly proposed as an alternative to a standard layered construction, such as the OSImodel. 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 pointtopoint links, where all sources also act as relay and additional nonsource 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 networkchannel coding; Slow Rayleigh fading; Diversity; Lowdensity paritycheck codes1 Introduction
Pointtopoint 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 crosslayer design [1,2], thereby leaving the classical layered architectures, such as the sevenlayer 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 pointtopoint transmissions have been decoded at the physical layer. Channel coding refers to the case where nodes perform coding over one pointtopoint 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., [46] for cooperative channel coding and [711] for network coding).
Standard linear network coding consists of taking linear combinations of several source packets. In general, nonbinary coefficients are used in the linear combinations. In JNCC, cooperative channel coding (e.g., decode and forward [12]) and crosslayer 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 paritycheck matrix of a binary code, referred to as joint networkchannel 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,P_{e}), where R is the information rate and P_{e }is the error rate. Here, we consider a fixed information rate R, so that the aim is to minimize P_{e} for a given pointtopoint channel quality, expressed by γ, the signaltonoise ratio (SNR) per symbol. Expressing the asymptotic (for large
γ) error rate as
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 twoway 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. [1416] 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 errorcorrecting 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
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 errorcorrecting 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 nonperfect sourcerelay 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 diversityoptimal, by providing a tighter lower bound on the word error rate, and by providing more numerical results.
2 Joint networkchannel coding
We first illustrate joint networkchannel coding by means of a simple example. Consider two sources orthogonally broadcasting a vector of symbols, mapped from the binary vectors s_{1} and s_{2}, 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 r_{1}, which is mapped to symbols and transmitted to the destination. The relation between all bits is expressed by the JNCC, whose paritycheck matrix has the following general form,
The matrix H_{p }represents the paritycheck matrix for the pointtopoint channel code. Each of the
binary vectors s_{1}, s_{2}, and r_{1}, can be separately decoded using this code. The bottom part of H represents the GLNC, which we denote as
Note that GLNC includes standard network codes used in an OSI communication model
as a special case. In the latter case, the matrices
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 H_{GLNC}; in this case the information bits of the code are s_{1 }and s_{2}, and r_{1 }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 H_{p} do not affect the diversity order in the case of the MARC.
3 System model
We consider wireless networks with m_{s }sources directly communicating to a common destination (e.g., cellphones communicating to a base station). Two timeorthogonal 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 m_{r} relays, where m_{r }≥ m_{s}. 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 subnetworks 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 halfduplex and transmit orthogonally using BPSK
modulation. The K information bits of each source are encoded via pointtopoint channel codes into a systematic codeword, denoted as source codeword, of length L, expressed by the column vector
The destination declares a word error if it can not perfectly retrieve all m_{s }K information bits, and the overall word error rate is denoted by P_{ew}.
All relevant channels between different^{a} 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
where
Hence, at the destination, each of the m_{s }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 m_{r }− m_{s }fading gains between the nonsource relays and the destination affects L bits, assuming that all m_{r }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 m_{r} blocks, each affected by its own fading gain, where m_{s}blocks have length 2L and m_{r }− m_{s }blocks have length L. This notion will be essential in the subsequent diversity analysis (Section ‘Diversity analysis of JNCC’).
In the source phase, relay u_{r }attempts to decode the received symbols from sources belonging to the decoding set
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,
Using the transmission set for each relay, the GLNC in Equation (2) generalizes to
where the matrices
where H_{c} is block diagonal with H_{p }on its diagonal, representing the channel code, and
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 wellknown formal definition of the diversity order ([23], Chap. 3).
Definition 1
The diversity order attained by a code
where γ is the signaltonoise ratio.
In other words, P_{ew }∝ γ^{−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 pointtopoint channel is either erased or perfect. Denoting the erasure
probability
In this section, we present the relation between the diversity order d and the parameters
We first prove that the diversity order is a function of only the network coding rate
R_{n }(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
4.1 Diversity as a function of the network coding rate
We denote the maximum achievable diversity order by d_{max}. We will determine d_{max }in this section and show that it only depends on the network coding rate
Proposition 1
Under ML decoding, the maximum diversity order d_{max }that can be achieved by any linear JNCC is
Proof
See Appendix 1. □
Note that the maximal diversity order does not depend on L. It can actually be reformulated in the following way:
which for m_{r }= m_{s }= m reduces to the maximum diversity order for a standard BF channel^{e} with m blocks and coding rate R_{n}[2729].
Hence, the maximum diversity order does not change when the pointtopoint channel coding rate R_{c,p }changes. This corresponds with our intuition as the parity bits of the pointtopoint codes only provide redundancy within one block forming a pointtopoint codeword, hence these parity bits cannot combat erasures which affect the complete pointtopoint 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 = d_{max}, from (8).
4.2 Space diversity by cooperation
We denote the word error rate for each source u_{s }by
Denote
Proposition 2
For any linear JNCC, applied in our system model, the diversity order d is upper bounded as
Proof
We use the diversity equivalence between a BF channel and block BEC [24,25]. Assume that the channel between source u_{s }and the destination is erased. Source u_{s }is included in at most
Note that the proof of Proposition 2 is based on the assumption that relay u_{r }only considers packets transmitted in the source phase for inclusion in
In Corollary 1, we propose the conditions on t_{min }so that the space diversity order d_{R }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 t_{min }≥ q, where
Proof
The proof follows directly from Propositions 1 and 2. □
Given a GLNC, and thus a choice of
Corollary 2
For any linear JNCC, applied in our system model, with constant
Proof
It always holds that t_{min }≤ ⌊t_{av }⌋ and if
Table 2 illustrates Corollary 2, showing the set of networks in which a certain parameter
n is diversityoptimal, which means that the choice of n does not prevent the code to achieve full diversity. In Section ‘Practical JNCC for
Table 2. Minimal value n for a JNCC with constant
4.3 A lower bound based on
{
T
(
u
r
)
}
for
n
u
r
=
2
A certain relay does not help one source only, but a combination of sources, expressed
by the transmission set
Based on
The matrix M expresses the presence of a sourcecodeword in each transmission, i.e.,
Consider a block BEC channel where e of the m_{r }blocks have been erased. The indices of the fading gains corresponding to the erased
blocks are collected in the set
Consider an example for m_{s }= m_{r }= 3. Assume that
Next, assume that
and
We can now define a metric that depends on
Definition 2
We define d_{M }= e^{∗} + 1, where e^{∗ }is the maximal cardinality of
A simple computer program can compute d_{M}, given
Lemma 1
In a JNCC following the form of Equation (6) with m_{s }= m_{r }and constant
Proof
If m_{s }= m_{r }and n = 2, then the minimum column weight of M is smaller than or equal to three. Erasing the three rows where
In the next proposition, we provide a lower bound on the diversity order under ML decoding or Belief Propagation (BP) decoding [31]. We denote
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
if the matrices
Using BPdecoding, the diversity order of a JNCC following the form of Equation (6)
with constant
if, for each u_{r}, the set of L equations
can be solved with BP in the case of only one unknown sourcecodeword 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 pointtopoint codes do not have a support in H_{GLNC}, or said differently, when the L − K right most columns of the matrices
In Section ‘Practical JNCC for
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
Lemma 2
In the case of nonreciprocal 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
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 pointtopoint transmissions. If it can not successfully retrieve the
transmitted pointtopoint codeword for a particular nodetodestination channel,
then it declares a block erasure, where a block refers to one pointtopoint codeword.
Denoting this block erasure probability by ε, we have that
Standard linear network coding consists of taking linear combinations of several source packets. In general, nonbinary coefficients are used in the linear
combinations. Hence, packets are treated symbolwise, which is shown to be capacity
achieving for the layered construction [8]. A consequence of this symbolwise treatment is that the effective block length of
the network code reduces to m_{s} + m_{r} and the set of equations, that are available at the destination for decoding, is
expressed by the coding matrix
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
n
u
r
=
2
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
We consider networks with m_{s }= m_{r }= m ≥ 4 and a JNCC following the form of Equation (6) with
From Table 2, it is clear that restricting n to two is not diversityoptimal 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 lowcomplexity 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
5.1 First step: design of
T
(
u
r
)
The transmission sets
We present an algorithm to determine
Algorithm 1
Choose transmission set
The transmission set
If a node is added as a source node, it adopts the largest source index, m_{s} + 1, and relayonly nodes, with indices larger than or equal to m_{s} + 1, increment their index by one. The function
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 m_{s }= m_{r }and with transmission set constructed via Algorithm 1, achieves a diversity order d = 3 using BPdecoding, if, for each u_{r}, Equation (17) can be solved with BP in the case of only one unknown sourcecodeword vector.
Proof
Because the links between sources and relays are perfect, the relays will never stay
silent. In the case that m_{r }= m_{s }and
Next, we show that d_{M }= 3 (and thus, according to Lemma 1, d_{M }is maximized if n = 2). Consider
Hence, source 1 is included in
As d_{R }= d_{M }= 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 nonreciprocal 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 m_{s }> 4 or when m_{s }= m_{r }= m ≤ 4.
Proof
See Appendix 4. □
For conciseness, we do not consider the other cases, m_{r }> m_{s }≤ 4.
5.2 Second step: JNCC of LDPCtype
In the first step, we specified
A simple solution is to replace the K left most columns in all K × L sub matrices
In the literature, a fulldiversity closetooutage 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
can be decoded via BP if only one coding vector s_{1}, s_{2} or r_{1} is erased and the other coding vectors are perfectly known. We denote this JNCC by MARCJNCC. The matrix H_{GLNC, MARC} of the MARCJNCC is given by Equation (A.7) in [21]^{f}:
where s_{j }= [1i_{j}2i_{j}p_{j}] is the codeword from source j, with [1i_{j}2i_{j}] and p_{j} denoting the information bits and the parity bits, respectively (j = 1,2); 1i_{j} and 2i_{j} each contain
and H_{3 }= R_{3}, so that
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 SMARCJNCC, where S stands for scalable.
Proposition 4
In a network following the system model proposed in Section ‘System model’ and using BP, the SMARCJNCC achieves a diversity order d = 3.
Proof
Consider the set of K equations
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
By Corollary 3 and Lemma 3, the SMARCJNCC 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 R_{1 }and R_{2} in Equation 19, so that all information bits have a random matrix in their corresponding block column in the paritycheck matrix. Now, the LDPC code can conform any degree distribution.
6 Lower bound for the WER
To assess the performance of the SMARCJNCC 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 multiuser environment, two types of mutual information are considered. First,
it is verified whether the sumrate, R_{c} 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,
The outage probability is
where
where
The terms I(S_{i};D), I(R_{i};D), and I(S_{i};R_{j}) are the instantaneous mutual informations of the corresponding pointtopoint channels
with input x ∈ {−1,1}, received signal y = α_{i}x + w with
where
We now consider the outage probability of a layered construction, such as the standard
OSI model, where the destination first decodes the pointtopoint transmissions, declaring
a block erasure if decoding is not successful. For the network code, we assume a maximum
distance separable (MDS) code, which is outageachieving over the (noiseless) blockerasure
channel [26]. That is, any m_{s} correctly received packets suffice for decoding. Accordingly, an outage event for
the layered construction, denoted as
where
and
The outage probability for JNCC and a layered construction are compared in Figure
1 for m_{s }= m_{r }= 5, coding matrix^{g} M given in Equation (18) and R_{c,p }= 6/7. The overall spectral efficiency is R = 3/7 bpcu, so that
Figure 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 pointtopoint codes are forced in a block diagonal structure in H_{c }(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 R_{c} but on R_{n}, 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 m_{s }= m_{r }= 3. The adopted pointtopoint codes have coding rate R_{c,p }= 0.5, so that R_{c }= 0.25. We take n_{u }= 2 and adopt the coding matrix M, given in Equation (13). Because of the small coding rate R_{c}, the outage probability achieves a diversity order of three (Figure 2). However, it follows from Proposition 1 that d_{max }= 2. We therefore propose a new lower bound, which takes into account the pointtopoint codes.
Figure 2. The conventional and tighter outage probability of JNCC are compared.
A bit node is essentially protected by two codes: a pointtopoint code (H_{c}) and a network code (H_{GLNC}), which is illustrated on the factor graph [38] representation (a Tanner notation [39] is adopted)^{h} of the decoder (Figure 3).
Figure 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 H_{c }and H_{GLNC}, respectively. A set of check nodes is denoted as CND for check node decoder. The LLRvalue coming from the CND corresponding with H_{c }is denoted as L_{c}. The LLRvalue corresponding with the channel observation is denoted as L_{obs,i}.
Usually, both codes are characterized by separate degree distributions, denoted as (λ_{c}(x),ρ_{c}(x)) and (λ_{GLNC}(x),ρ_{GLNC}(x)) for H_{c} and H_{GLNC}, respectively.
The new lower bound assumes a concatenated decoding scheme. At the destination, first
the pointtopoint 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 loglikelihood ratio (LLR)
The LLR
The terms
The density of the random variable
Similarly to the conventional case, an outage event, denoted as
Note that the network coding rate is used instead of the overall rate R_{c}, which corresponds to Proposition 1.
The tight lower bound presented here is a valid lower bound if the pointtopoint codes are first decoded, followed by the network code, without iterating back to the pointtopoint codes.
Let us now go back to the small network example with m_{s }= m_{r }= 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 pointtopoint code, the WER of the SMARCJNCC 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 SMARCJNCC. We will clarify the proposed techniques on an illustrating network example, where m_{s }= m_{r }= 5 (Figure 5). We use the same network example as in [17,18] so that a comparison is possible.
Figure 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 nonreciprocal interuser channel in the simulation results.
Note that in the case that m_{s }> 4 and Algorithm 1 is used to construct
We compare the error rate performance of the SMARCJNCC 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 H_{GLNC}) and a layered network construction (also using identity matrices in H_{GLNC}, and where, at the destination, the network code is only decoded after decoding all pointtopoint codewords separately and taking a hard decision).
The pointtopoint code used in the simulations is an irregular LDPC code [41] characterized by the standard polynomials λ(x) and ρ(x) [41]:
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 pointtopoint code is fetched from [42], has coding rate R_{c,p }= 6/7 and conforms the following degree distributions:
7.1 Perfect sourcerelay links
We start by assessing the performance of H_{GLNC}, 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, m_{s }= m_{r }= 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 E_{b}/N_{0 }= 2γ.
Figure 6 shows that a diversity order of 3 is achieved for SMARCJNCC, which corroborates
Corollary 3. It performs at 2.5 dB from the outage probability (because no pointtopoint
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
Figure 6. The word error rate of the SMARCJNCC is compared to that of the IJNCC, assuming perfect sourcerelay channels.
It is clear that, even without optimizing the SMARCJNCC, there is a benefit in terms of coding gain compared to the IJNCC.
7.2 Rayleigh faded sourcerelay links
Now, we assess the performance of the complete paritycheck matrix H of the SMARCJNCC. 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, R_{c,p }= 6/7, L = 707, m_{s }= m_{r }= 5 (so that N = 10L = 7070). The overall spectral efficiency is R = 3/7 bpcu, so that E_{b}/N_{0 }= 7γ/3. Because the simulation time would be very large if every pointtopoint sourcerelay link had to be decoded separately, we made an approximation. The word error rate of the pointtopoint code when transmitted on a channel with fading gain α is smaller than 10^{−4}when α^{2}γ = 5.5 dB. Therefore, we assumed that a relay had correctly decoded the sourcecodeword if α^{2}γ > 5.5 dB and not otherwise. We also add the performance of the SMARCJNCC from Section ‘Perfect sourcerelay links’, corresponding to perfect sourcerelay links and R = 0.5 bpcu, as a reference curve (note that the reference curve corresponds to a larger spectral efficiency—the coding rate R_{c }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 SMARCJNCC compared to the IJNCC is considerably decreased, compared to Section ‘Perfect sourcerelay links’, which corresponds to the small horizontal SNRgap 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 R_{c,p}). Finally, the WER performance of a layered construction is shown, which coincides with that of the IJNCC.
Figure 7. The word error rate of the SMARCJNCC is compared to that of the IJNCC and a layered construction, assuming Rayleigh faded sourcerelay channels. The reference curve is the performance of the SMARCJNCC assuming perfect sourcerelay channels (Section ‘Perfect sourcerelay links’).
7.3 Gaussian sourcerelay links
We test again the complete paritycheck matrix H of the SMARCJNCC, now assuming that the sourcerelay links are Gaussian, having additive white Gaussian noise only, without fading; fading occurs on the sourcedestination and relaydestination 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 sourcerelay 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 IJNCC has improved a lot in comparison with Section ‘Perfect sourcerelay links’, where H_{GLNC }only was used. The degree distributions causing the poor coding gain of the IJNCC in Section ‘Perfect sourcerelay links’, have changed considerably through the pointtopoint codes, significantly improving the coding gain.
Figure 8. The word error rate of the SMARCJNCC is compared to that of the IJNCC, assuming Gaussian sourcerelay channels. The reference curve is the performance of the SMARCJNCC assuming perfect sourcerelay channels (Section ‘Perfect sourcerelay links’).
8 Conclusion
We put forward a general form of joint networkchannel 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
Denoting by e = e_{1} + e_{2} the total number of erased blocks, the largest value e_{max }of e for which e_{1 }and e_{2} satisfy (23) for all e_{1 }≤ m_{s }and e_{2 }≤ m_{r }− m_{s} is given by
Hence, d_{max }= e_{max} + 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
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
where ε_{i }= 0 when the channel is erased and ε_{i }= 1 otherwise. Hence, ε_{i }= 0 if
Sourcecodewords s_{i} can be retrieved from the transmissions in the source phase if ε_{i }= 0. Decoding the other sourcecodewords at the destination is performed through the paritycheck matrix H (Equation (6)). We split H in two parts:
where H_{left} and H_{right} have m_{s}L and m_{r}L columns, respectively. We also define
As we consider a block BEC, some transmissions are perfect. As in Appendix 1, consider
the case that e_{1} blocks of length 2L and e_{2} blocks of length L have been erased, where
or, using the notation from (15),
where
It is now easy to see that
If
or of the type
Under ML decoding, we obtain what was claimed if the matrices
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 m^{2}−m interuser channels, which all have a probability of failure. Hence, there exist
Using Bayes’ law, the error rate can be split:
Defining the diversity order corresponding to each case as
The probability of f failures on independent interuser channels is proportional to
The diversity order in the case of perfect interuser channels (f = 0) is d_{c,1}. That is, the errorcorrecting code can bear d_{c,1}−1 erasures on nodedestination links. Hence, d_{c,i }≥ d_{c,1 }only if
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 nodedestination erasures adding to the assumed d_{c,1}−f−1 already erased nodedestination channels, yielding a total of at most d_{c,1}−1 erased nodedestination channels, which can be supported by the code, by the definition of d_{c,1}.
Appendix 4
Proof of Lemma 3
In the case that m_{s }> 4 and Algorithm 1 is used to construct
Now consider the case that d_{c,1 }= 2, which corresponds to m_{s }= m_{r }= m < 4 (see Proposition 1). In the case of f = 1 interuser channel, d_{c,i} is always larger than one, because
Finally, consider the case that m_{s }= m_{r }= m = 4 and thus d_{c,1 }= 3. Hence, in the case of no interuser failures, the code can support two nodedestination
failures, corresponding to four erased transmissions from two nodes, in the source
phase and in the relay phase. Reciprocity is relevant as
Endnotes
^{a}Unless mentioned otherwise, we assume that channels are reciprocal, i.e., the channel from u_{1} to u_{2} is the same as the channel from u_{2 }to u_{1}.
^{b}In practice, increasing the SNR value can be achieved by increasing the transmission power of a node, so that both the SNR of the nodetodestination channels and channels between nondestination nodes increase.
^{c}For conciseness, we do not formulate the equation for channels between nondestination nodes.
^{d}Note that relays u are not allowed to consider relay codewords
^{e}A 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−R_{c})⌋, where R_{c} is the coding rate [2729].
^{f}The 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 pointtopoint codes are available, which is not the case here.
^{g}The coding matrix expresses the transmission sets for each relay, which is required to determine the outage probability.
^{h}For a specific instance, the paritycheck 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

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

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

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

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

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)

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

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

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

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

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

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

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

Z Guo, J Huang, B Wang, JH Cui, S Zhou, P Willett, A practical joint networkchannel 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

C Hausl, P Dupraz, Joint networkchannel coding for the multipleaccess relay channel. Proc. IEEE Commun. Soc. Sensor Ad Hoc Commun. Netw 3, 817–822 (2006)

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

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

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)

D Duyck, D Capirone, M Heindlmaier, M Moeneclaey, Towards fulldiversity joint networkchannel coding for large networks. in Proc, ed. by . of Europ. Wirel. Conf (Vienna, Austria, 2011), pp. 1–8

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

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

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

D Duyck, D Capirone, JJ Boutros, M Moeneclaey, A fulldiversity joint networkchannel 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

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

JJ Boutros, presentedat Controlled doping via highorder 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

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)

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

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

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

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

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

RJ McEliece, DJC MacKay, JF 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

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)

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

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

C Hausl, Joint networkchannel coding for the multipleaccess relay channel based on turbo codes. Eur. Trans. Telecommun 20(2), 175–181 (2009). Publisher Full Text

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

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

F Kschischang, B Frey, HA Loeliger, Factor graphs and the sumproduct algorithm. IEEE Trans. Inf. Theory 47(2), 498–519 (2001). Publisher Full Text

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

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

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

D Hamdani, E Safrianti, Construction of shortlength highrates LDPC codes using difference families. Makara, Teknologi 11(1), 25–29 (2007)