Appendix D
Network Coding
D.1 Nonbinary NC based on UE Cooperation
proof (Theorem 8.3.1)
One possibility to measure the performance in the range of medium-to-high Signal to Noise Ratio (SNR), outage probabilities are considered, represented by the diversity order d. Recall from Chapter 5, d can be expressed as:
(D.1)
where P is the relevant error probability under consideration (e.g. frame error probability or outage probability). Clearly, a received codeword is obtained as 
, where 
and 
are transmitted and received channel codewords, respectively; 
is additive white Gaussian noise with zero-mean and unit variance; 
denotes the fading channel gain. The index 
denotes the transmitting user U1 or U2, 
denotes the receiving Base Station (BS), U1 and U2, respectively, and k denotes the time slot. The factors 
are i.i.d. random variables for different i, j or k with a Rayleigh distribution and unit variance. For reciprocal inter-user channels, 
. With i.i.d. Gaussian codewords (
s), the Mutual Information (MI) between 
and 
is 
Let R denote the rate of all channel codes. 
cannot be decoded correctly if 
where 
. For Rayleigh fading, the corresponding outage probability of the link corresponding to 
is obtained as (Tse and Viswanath 2005):
(D.2)
The approximation holds for high SNRs. Without loss of generality, let us analyze the overall outage probability for U1. If there is no outage in the inter-user channel, there are 4 different network coding blocks. An outage occurs only when the direct systematic codeword s1 cannot be decoded, and two (or three) out of other three codewords (for s2, 
or 
) cannot be decoded at the BS. Since the 
s are i.i.d, the overall outage probability is hence obtained as
(D.3)
With probability Pe, the Relay Node (RN) cannot decode the partner's codeword. In this case, the BS performs Maximum Ratio Combining (MRC) and decodes. Thus, overall outage occurs when
(D.4)
Then, the outage probability is 
. Combining above results, the total outage probability is
(D.5)
Consequently, the diversity order is 
. If the inter-user channels are not reciprocal, we only need to separately consider the outage probability of two inter-user channels. By a similar analysis, the outage probability for U1 is 
Hence, the diversity order is still 3.
D.2 Multiuser and Multirelay Scenario
proof (Theorem 8.2)
For quasi-static fading channels a received codeword (base-band) is given as
(D.6)
where 
and 
are the transmitted and received channel codewords, respectively. Let us assume that 
has power Ps, where 
is an additive white Gaussian noise sample with double-sided power spectral density 
, and 
denotes the channel gain due to path-loss, shadowing and frequency nonselective fading. Here, the indices 
denote the transmitting nodes: U1, U2, RN1, and RN2, respectively, and 
denote the receiving nodes: the BS, RN1 and RN2, respectively. The factors 
s have zero-mean and are i.i.d. complex random variables. Without loss of generality, the factor 
is considered to have Rayleigh distribution and unit variance.
The outage probability for U1 is given as follows. Identical considerations hold for U2 due to symmetry. For U1, an outage event occurs if the direct codeword s1 cannot be decoded and, in addition, one or two blocks from s2 and 
(with an MRC receiver) cannot be decoded either. Hence, for perfect Source Relay (SR) channels (denoted as the event B) the outage probability for U1 is given as
(D.7)
In a similar way all SR channel outage patterns can be evaluated and the outage probabilities are obtained. Here, an outage pattern denotes the collection of states of all SR channels that are either in outage or not. In summary, the outage probability for U1 can be calculated as
(D.8)
where 
is the probability that i SR channels are in outage. It is easy to see that the diversity order is d = 2. This is not an optimal result since the information of each user is transmitted through three paths.
proof (Theorem 8.3.3)
Let us assume 
and 
. In addition, assuming perfect source to RN channels, there are four different network codewords: 
and 
. For U1, an outage event occurs only when the codeword on the direct channel and two out of three codewords corresponding to s2, 
or 
cannot be decoded at the BS. Since all channels are assumed to be independent the outage probability for perfect SR channels (denoted by the event B) is given as 
Similarly, all possible SR channel patterns can be analyzed and then the corresponding outage probability is obtained. In summary, the overall outage probability for U1 can be obtained as
(D.9)
As the information of each user is transmitted through three independent paths, a maximum diversity order of d = 3 is obtained. Clearly, it is higher than the two-user, two-relay scheme using binary-Network Coding (NC).