Low-Complexity Decoding Algorithms for Distributed Space-Time Coded Regenerative Relay Systems

Abstract

We examine decoding structure for distributed space-time coded regenerative relay networks. Given the possible demodulation error at the regenerative relays, we provide a general framework of error aware decoder, where the receiver exploits the demodulation error probability of relays to improve the system performance. Considering the high computational complexity of optimal Maximum Likelihood (ML) decoder, we also propose two low-complexity decoders, Max-Log decoder and Max-Log-Sphere decoder. Computational complexities of these three decoders are also analyzed. Simulation results show that error aware decoders can improve system performance greatly without high system overload and Max-Log decoder and Max-Log-Sphere decoder can drastically reduce the decoding complexity with negligible performance degradation.

1. Introduction

Relay-assisted communication is a promising strategy that exploits spatial diversity available among a collection of distributed single antenna terminals for both centralized and decentralized wireless networks. In most relay networks, a two-stage relaying strategy is used. In the first stage, a source transmits and all relays listen; in the second stage, the relays cooperate to forward the source symbols to the destination. Generally speaking, the relay functions can be separated into two types, regenerative and nonregenerative. If the relay processes the received signal, we call it regenerative relay, such as Decode-and-Forward (DCF) [1] and Demodulation-and-Forward (DMF) [2]. Otherwise, we call nonregenerative relay, such as Amplify-and-Forward (AF) [1].

It is well known that the channel between source and relay is unreliable because of fading and noise. The relay receives an attenuated version of the source signal. AF relaying scheme amplifies noise. DCF scheme always using cyclic redundancy check (CRC) will cause interruptions when the relay detects errors from the received message. DMF scheme is a tradeoff between AF and DCF in relay processing. Relay can always keep a transmit link from the source and detects and possibly decodes the source signal [3]. Moreover, the DCF scheme can also be considered as a special case of DMF if we consider the null signal as one choice of the modulation constellation. Therefore, in this paper, we treat DMF as the object to be studied for regenerative relay networks. However, DMF relay has an important disadvantage, which is the error produced in relay's Maximum Likelihood demodulation degrades the effective SNR at the destination significantly, which is called error propagation [4]. For distributed space-time coding system in regenerative relay networks, the degradation is more drastic [5, 6]. In [3], we proposed a threshold-based scheme to minimize the error propagation, which is an active mechanism equipped in relays but subject to the large computation complexity.

In this paper, we intend to investigate the ML decoding structure where the destination is able to be aware of the error probability at the relays. Since the error probability at relay is a monotonic decreasing function of received SNR at relay, the destination can estimate the error probability through training sequences which is transmitted by source and amplified by relay. Meanwhile, each relay also transmits its training sequence to estimate the relay-destination channel [5, 7]. Therefore, error aware distributed space-time decoding is reasonable. After analyzing the conditional likelihood function, we give a general framework of error aware decoder for regenerative relay networks. Because the proposed ML decoder is composed of multiple likelihood function generators, the computational complexity is too large to be affordable in some cases. Due to max-log approximation, we provide a Max-Log decoder based on Csiszár-Tusnady algorithm [8]. Moreover, to reduce the complexity further, we also propose a Max-Log-Sphere decoder which combines max-log approximation and sphere decoding. In addition, we analyze complexities of these decoders in terms of elementary operation number. Finally, simulations verify the low complexity and improved performance of our proposed decoders.

2. System Model

We consider a wireless network with N randomly placed relay nodes, relay $i = 1, \dots, N$ , one source node S, and a destination node D. Each node is equipped with only a single antenna and uses the Half-duplex mode. Denote the channel from the source to the ith relay as $f_{i}$ and the channel from the ith relay to the destination as $h_{i}$ . Assume that ${f_{i}}$ and ${h_{i}}$ are independent complex Gaussian random variables with zero-mean and variance $δ_{s i}^{2}$ and $δ_{i d}^{2}$ , respectively. Receiver noise is assumed as complex Gaussian random variable with zero-mean and unit-variance. We assume a block fading channel model, where channel gain stays constant during a time block and changes from block to block [1]. We also assume that the instantaneous channel is unknown to the transmitting node but perfectly known at receiving node. Assume that the source wishes to send the signal $s = [s_{1}, s_{2}, \dots, s_{T}]^{T}$ to the destination, where $s_{i} \in 𝒜$ and 𝒜 is a finite constellation with average power $1 / T$ . Here T is the signal block length. Hence, $E {s^{H} s} = 1$ . Assume $s$ is in the codebook $𝒮 = {s_{1}, \dots, s_{L}}$ , where $L \geq 2$ is the cardinality of the codebook. For the convenience of expression, we consider all transmit power is unit.

During the first stage, the source node transmits $s_{l}, l \in [0, L - 1]$ to all relays, then each relay tries to demodulate the received signal. Denote the demodulated symbol vector at the ith relay is ${\hat{s}}_{i}$ , and ${\hat{s}}_{i} \in 𝒮$ . By (6.5) of [9], the demodulation probability can be written as

\begin{array}{l} P ({\hat{s}}_{i} ∣ f_{i}, s_{l}) \\ = {\begin{cases} 𝒬 (\sqrt{\frac{1}{2} {| f_{i} |}^{2} {| s_{l} - {\hat{s}}_{i} |}^{2}}), if {\hat{s}}_{i} \neq s_{l} \\ 1 - \sum_{1 \leq j \leq L - 1, j \neq l}^{} 𝒬 (\sqrt{\frac{1}{2} {| f_{i} |}^{2} {| s_{l} - s_{i} |}^{2}}), if {\hat{s}}_{i} = s_{l}, \end{cases} \end{array}

(1)

where

𝒬 (x) = (1 / \sqrt{2 π}) \int_{x}^{\infty} ‍ e^{- t^{2} / 2} d t

. If the source node transmits

s_{l}

, the ith relay decode its received signal as

s_{i} \neq s_{l}

with probability

𝒬 (\sqrt{(1 / 2) | f_{i} |^{2} | s_{l} - {\hat{s}}_{i} |^{2}})

. Obviously, the probability of decoding successfully at the ith relay is

1 - \sum_{1 \leq j \leq L - 1, j \neq l} ‍ 𝒬 (\sqrt{(1 / 2) | f_{i} |^{2} | s_{l} - s_{j} |^{2}})

At the ith relay, the received signal ${\hat{s}}_{i}$ is mapped onto a $T \times 1$ vector (not necessary), $ℱ_{i} ({\hat{s}}_{i})$ , as processed at one antenna of colocated space-time coding transmitter. We assume the map function $ℱ_{i}$ is invertible. Therefore, there are L possible transmitted vectors to the destination for the ith relay, because ${\hat{s}}_{i}$ could be any vector in 𝒮. Herein, we assume all mapping functions $ℱ_{i}, i = 1, \dots, N$ , are different with each other. Then, all relays transmit the mapped vectors to the destination. At the destination, the received signal is

\begin{matrix} Y = [ℱ_{1} ({\hat{s}}_{1}), \dots, ℱ_{N} ({\hat{s}}_{N})] H + N, \end{matrix}

(2)

where

Y = [y_{1}, \dots, y_{T}]^{T}

is the received signal,

H = [h_{1}, \dots, h_{N}]^{T}

is the relay to destination channel vector, and

N

is Gaussian white noise. Define a codebook

𝒞 = {[ℱ_{1} ({\hat{s}}_{1}), \dots, ℱ_{N} ({\hat{s}}_{N})]}

. Clearly, 𝒞 includes

L^{N}

elements. We define the kth element of 𝒞 is

C_{k} = [c_{1 k}, \dots, c_{N k}]

, where

c_{i k} \in {ℱ_{i} ({\hat{s}}_{i})}

. Thus, if

C_{k}

is transmitted, we can express (2) as

\begin{matrix} Y = C_{k} H + N . \end{matrix}

(3)

Denote the inverse function of ℱ as

ℱ^{- 1}

. Then, we have

\begin{matrix} P (C_{k} ∣ F, s_{l}) = \prod_{i = 1}^{N} P (ℱ_{i}^{- 1} (c_{i k}) ∣ f_{i}, s_{l}), \end{matrix}

(4)

where

F = [f_{1}, \dots, f_{N}]^{T}

. So, by (1), we can derive the exact value of (4). Given a

C_{k}

, the conditional probability density function of Y is

\begin{matrix} P (Y ∣ H, C_{k}) = \frac{1}{π^{N}} \exp (- {(Y - C_{k} H)}^{ℋ} (Y - C_{k} H)) . \end{matrix}

(5)

3. Error Aware Maximum Likelihood Decoder

In this section, we provide a general Maximum Likelihood decoder for distributed space-time coded regenerative relay networks. First of all, destination should know the channel information in this relay networks. The channels from relays to the destination $h_{i}, i = 1, \dots, N$ , can be estimated through pilot symbols which are transmitted by each relay before data transmission [10]. Herein, we assume all the estimators are ideally accurate without error. The effect of estimation error will be checked in simulations. To let the destination know the demodulation error probability of each relay, we propose the following extra channel estimation scheme.

Step 1.

The source transmits its pilot symbol to all relays through channels $f_{1}, \dots, f_{N}$ . Without demodulating, each relay maps the noise version signal to a vector like the scheme proposed in [11].

Step 2.

Each relay transmits the vector to the destination like the Amplify-and-Forward based distributed space-time coding [12].

Step 3.

The cascaded channel between source and destination carried by amplified pilots, that is, $f_{i} h_{i}, i = 1, \dots, N$ , can be estimated at the destination like [11].

Therefore, $f_{i}$ also can be estimated by the above channel estimation scheme. It is difficult to analyze the effect of channel estimation error in error aware decoders, but we simulate that in Section 6. In following context, we just assume there is no channel estimation error to allow us to focus only on structures of error aware decoders. Because the signal vector set 𝒮 and all mapping functions ${ℱ_{i}}$ are known at the destination as a prior knowledge, (4) can be derived at the destination.

If the transmitted signal is $s_{l}$ , the likelihood function is

\begin{matrix} P (Y ∣ F, H, s_{l}) = \sum_{k = 1}^{L^{N}} P (Y ∣ H, C_{k}) P (C_{k} ∣ F, s_{l}) . \end{matrix}

(6)

Therefore, the error aware ML decoder is

\begin{matrix} \arg \max_{1 \leq l \leq L} {P (Y ∣ F, H, s_{l})} . \end{matrix}

(7)

Utilize (4)–(6), then (7) is derived. By (5),

P (Y ∣ H, C_{k})

is independent of

s_{l}

, so that according to the estimated channel

H

P (Y ∣ H, C_{k})

can be calculated first. Then, using the amplified pilot,

P (C_{k} ∣ F, s_{l})

is also derived. Therefore, the ML decoder can be built in Figure 1, where we show the structure of error aware ML decoder for regenerative distributed space-time coding. Note that there are L adders and

L^{N}

likelihood function generators.

Figure 1

Error aware ML decoder.

The complexity of the error aware ML decoder equals to that of $L^{N}$ colocated space-time decoders it is too large to be affordable if the signal block length, modulation order, and the number of relay are considerablely large. Reference [2] considered a piecewise-linear approximation to solve a similar problem, but in this case it is also too complicated to design an approximation function.

3.1. Optimality of Error Aware Decoder

To prove the optimality of our proposed error aware receiver, we need to analyze the error performance difference between the error aware decoder and nonerror aware decoder (traditional receiver). Unfortunately, it is difficult to derive the exact error performances of error aware decoder and nonerror aware decoder. To illustrate the optimality, we try to give following two points (in Figure 2).

Figure 2

Illustration of the signal space.

$(1)$ Receiver Rule

Since the error aware decoder is based on ML rule, it should be the optimal receiver [10].

$(2)$ Signal Space Description

To express clearly, we set the source transmit a symbol $s \in 𝒜$ and $𝒜 = {1,2, 3}$ . We assume $1$ is transmitted by the source. Consider there are 2 relays in the relay networks. Then, it is obvious that there could be $3^{2}$ possible decoding combinations at the relay network, that is, ${1,1}$ , ${1,2}$ , ${2,1}, . . ., {3,2}$ , ${3,3}$ . In the nonerror aware decoder, combinations ${1,1}, {2,2}$ , and ${3,3}$ are considered. In following, we consider two cases.

Case 1 (No error happens at relays).

In this case, relays decode the received message as $1$ , which means decode set is ${1,1}$ (red ball). According to (6), error aware decoder is equivalent to the nonerror aware decoder. Therefore, both have the same error performances.

Case 2 (Error happens at relays).

In our interested situation, the impact of noise is very slight therefore, the system SNR is very high and we could only consider the closest symbols as errors. As a result, our candidates are also limited between ${1,2}$ and ${2,1}$ in error aware decoder. As we know, the error performance is a Q-function of the distance between the transmitted symbol and the received symbols on the signal space [10]. Therefore, the error performance of nonerror aware receiver could be expressed as $Q (\sqrt{d_{3}^{2} SNR})$ . By (6), the error performance of error aware decoder is $Q (\sqrt{d_{1}^{2} SNR}) Q (\sqrt{d_{2}^{2} SNR})$ . As we consider high SNR regime, then there is $Q (x) \approx \exp (- x^{2} / 2)$ . Then the error performance of error aware decoder can be approximated as $\exp (- (d_{1}^{2} + d_{2}^{2}) SNR / 2)$ . Denote the angle between $d_{1}$ and $d_{3}$ as θ. Because the received signal is so close to ${1,2}$ , then $\cos θ > 0$ . By the law of cosines, we have $\exp (- (d_{1}^{2} + d_{2}^{2}) SNR / 2) < \exp (- d_{3}^{2} SNR / 2)$ . For ${2,1}$ , we can obtain the same result. So we can prove that error aware decoder outperforms nonerror aware decoder.

4. Low-Complexity Error Aware Decoders

In this section, we will introduce two low-complexity error aware decoders through analyzing and simplifying the structure of ML decoder. The simplifying process we used herein can be extended for more general cases to obtain low-complexity decoders. First, we use Max-Log approximation to derive a Max-Log error aware decoder which can work with Csiszár-Tusnady algorithm. Second, to reduce the complexity further, sphere decoding also is combined into the Max-Log decoder, which is called Max-Log-Sphere decoder.

4.1. Error Aware Max-Log Decoder

Substitute (6) into (7), there is

\begin{matrix} \arg \max_{1 \leq l \leq L} {\sum_{k = 1}^{L^{N}} P (Y ∣ H, C_{k}) P (C_{k} ∣ F, s_{l})} . \end{matrix}

(8)

Because

\log (x)

is an increasing monotonic function, the ML decoder can be rewritten as

\begin{matrix} \arg \max_{1 \leq l \leq L} {\log (\sum_{k = 1}^{L^{N}} \exp {- \frac{1}{2} {∥ Y - C_{k} H ∥}^{2} + λ_{k, l}})} . \end{matrix}

(9)

According to (5) and max-log approximation in [13], we derive

\begin{matrix} \arg \max_{1 \leq l \leq L} {\max_{1 \leq l \leq L^{N}} {- {∥ Y - C_{k} H ∥}^{2} + λ_{k, l}}}, \end{matrix}

(10)

where

λ_{k, l} = \log (P (C_{k} | F, s_{l}))

We can see that decoding distributed space-time code becomes searching a two-dimension array, which is indexed by $(k, l)$ . Intuitively, this decoder also needs $L^{N}$ ML detector like ML decoder. The only difference is that calculating the likelihood function of each symbol vector does not need cross-computation. However, double maximization problem can take advantage of Csiszár-Tusnady algorithm to reduce computing [8]. Because the set ${{∥ Y - C_{k} H ∥}^{2}}$ is a set of distance measure which is one-one mapped to a probability distribution set and ${λ_{k, l}}$ is the set of probability distribution, moreover, ${λ_{k, l}} \leq 0$ , then (10) can be seemed to seek the vector which has the minimum sum distance which equals to the distance from $s_{l}$ to $C_{k}$ plus the distance from $C_{k}$ to $Y$ . Thus, Csiszár-Tusnady algorithm does converge to the maximum element [8]. We summarize the iterative Max-Log decoder as follows (Figure 3).

Figure 3

Max-Log decoder.

4.2. Error Aware Max-Log-Sphere Decoder

If the length of vector $s$ and the constellation size are sufficiently large, Max-Log decoder is also subject to the implementation. The largest computation is required for searching code set 𝒞 with cardinality $L^{N}$ . Reducing the decoder complexity depends on searching 𝒞.

To state the Max-Log-Sphere decoder, we first find the real-valued equivalent of (3), Define

\begin{matrix} \tilde{Y} = {[ℛ {Y}^{T}, {ℐ {Y}}^{T}]}_{2 T \times 1}^{T}, \\ \tilde{H} = {[ℛ {H}^{T}, ℐ {H}^{T}]}_{2 N \times 1}^{T}, \\ \tilde{N} = {[ℛ {N}^{T}, ℐ {N}^{T}]}_{2 T \times 1}^{T}, \\ {\tilde{C}}_{k} = {[\begin{bmatrix} ℛ {C_{k}} & ℐ {C_{k}} \\ - ℐ {C_{k}} & ℛ {C_{k}} \end{bmatrix}]}_{2 T \times 2 N}, \end{matrix}

(11)

where

ℛ {\cdot}

and

ℐ {\cdot}

denote real part and imaginary part. By (10), we yield

\begin{matrix} \arg \min_{1 \leq l \leq L} {\min_{1 \leq k \leq L^{N}} {{∥ \tilde{Y} - {\tilde{C}}_{k} \tilde{H} ∥}^{2} - λ_{k, l}}} . \end{matrix}

(12)

For a specific

s_{l}

, the decoding object is

\begin{array}{l} \arg \min_{1 \leq l \leq L^{N}} {{∥ \tilde{Y} - {\tilde{C}}_{k} \tilde{H} ∥}^{2} - λ_{k, l}} \\ = \arg \min_{1 \leq l \leq L^{N}} {{∥ \tilde{Y} - ({\tilde{H}}^{T} \otimes I) Vec {{\tilde{C}}_{k}} ∥}^{2} - λ_{k, l}}, \end{array}

(13)

where

\otimes

is the Kronecker product operation. Obviously, we can use sphere decoding method [14, 15] to searching

C_{k}

, which minimizes (13). Note that

{∥ \tilde{N} ∥}^{2} = {∥ \tilde{Y} - \tilde{C} \tilde{H} ∥}^{2}

is an

χ^{2}

random variable with

2 N

degrees of freedom. We choose the radius r to be a linear function of the variance of

{∥ \tilde{N} ∥}^{2}

\begin{matrix} r^{2} = 2 α N, \end{matrix}

(14)

where the coefficient α is chosen in such a way that with a high probability

P_{f p}

we can find a lattice inside a sphere

\begin{matrix} \int_{0}^{2 α N} ‍ \frac{x^{N - 1}}{Γ (N)} e^{- x} d x, \end{matrix}

(15)

where

Γ (N) = \int_{0}^{\infty} ‍ t^{N} e^{- t} d t

. Note that the radius is chosen based on the noise not on channel efficiency. As stated in [14], this point has a beneficial effect on the computational complexity.

For expression convenience, we define ${\tilde{H}}^{T} \otimes I = B$ and $Vec {{\tilde{C}}_{k}} = X$ with size $4 N T \times 1$ . Therefore, searching $X$ is equal to searching $C_{k}$ . Applying the idea of the Fincke Pohst algorithm (See Algorithm 1), we search for the point $X$ that belongs to the geometric body described by

\begin{matrix} {r'}_{k, l}^{2} \geq {(X - \hat{X})}^{H} U^{H} U (X - \hat{X}) - \sum_{i = 1}^{N} \log (P (c_{i k} ∣ f_{i}, s_{l})), \end{matrix}

(16)

where

\hat{X} = B^{†} Y = (B^{T} B)^{- 1} A^{T} Y

and

U

is the low triangular matrix obtained from QR factorization of

B

. The search radius

{r'}_{k, l}

is chosen according to the statistical properties of noise and the decoding error at relays. Denote

4 N T = M

, then, a necessary condition for

x_{M}

, the Mth element of

X_{k}

, is

\begin{matrix} b_{M, M}^{2} {(x_{M} - {\hat{x}}_{M})}^{2} - δ_{k, l, M} \leq {r^{'}}_{k, l}^{2}, \end{matrix}

(17)

where

δ_{k, l, M}

is defined as

\begin{matrix} δ_{k, l, M} = \frac{1}{2 N} \log P (C_{j, k} f_{j}, s_{l}), \\ j = \frac{1}{2} mod (M, 2 T) . \end{matrix}

(18)

Herein we allocate the additional weight

δ_{k, l, m}

averagely over N relays. Moreover, we define

\begin{matrix} {r'}_{k, l, M - 1}^{2} = {r'}_{k, l}^{2} - b_{M, M}^{2} {(x_{M} - {\hat{x}}_{M})}^{2} + δ_{k, l, M}, \end{matrix}

(19)

and a new necessary condition can be written as

\begin{array}{l} b_{M - 1, M - 1}^{2} {(x_{M - 1} - {\hat{x}}_{M - 1} + \frac{b_{M - 1, M}}{b_{M - 1, M - 1}} (x_{M} - {\hat{x}}_{M}))}^{2} \\ - δ_{k, l, M - 1} \leq {r^{'}}_{k, l, M - 1}^{2} . \end{array}

(20)

In a similar fashion, one proceeds for

x_{M - 2}

, and so on, and until all components of vector

X

are found. Note that the dominant difference between Max-Log-Sphere decoder and sphere decoder proposed in [14] is that radius varies according to all possible code words. In this Max-Log-Sphere decoder, for each k, we just check

X_{k}

whether to meet its radius. If there exists more than one

X_{k}

can meet the constraint (17) for

x_{m}

, keep these survival code word and go to next code word. If some of these code words cannot meet the new constraint, then drop them. That is to say for each lattice we must try all possible radiuses. For a specific

s_{l}

, Max-Log-Sphere decoder can be summarized as Figure 4.

Algorithm 1

(1) Initialization: Set error probability set 𝒫. Take any element of $C_{k} \in 𝒞$ and compute $D_{k} = - {∥ Y - C_{k} H ∥}^{2}$ .

(2) Step 1: Find the l that makes $D_{k} + λ_{k, l}$ is maximum for the chosen k, where $λ_{k, l} \in 𝒫$ and is calculated by (4).

(3) Step 2: Fix l and find a $D_{n} \in 𝒞$ which makes $D_{n} + λ_{n, l}$ is maximum.

(4) Decision: If $n = k$ , goto End, otherwise, goto Step 1.

(5) End: $s_{l}$ is the decoded vector.

Figure 4

Max-Log-Sphere decoder.

After terminating the decoder algorithm for $s_{l}$ (See Algorithm 2), select the $C_{k}$ which achieves the minimum distance to $\tilde{Y}$ . Then through L Max-Log-Sphere decoder with $l = 1, \dots, L$ , choose the $s_{l}$ which minimizes the distance to $Y$ .

Algorithm 2

Input $B, Y, \hat{X}, r, λ_{k, l}, d$ , Set $k = 1$ .

(1) Set $m = M$ , $r_{k, l, M}^{' 2} = r^{2} - {∥ \tilde{Y} ∥}^{2} + ∥ B \hat{X} ∥$ , ${\hat{x}}_{M ∣ M + 1} = {\hat{x}}_{M}$ .

(2) (Set bounds for $x_{m}$ ) Set $z_{k} = r_{k, l, m}^{'} / b_{m, m}$ ,

$U B (x_{m}) = ⌊ z_{k} + {\hat{x}}_{m ∣ m + 1} ⌋$ , $x_{m} = ⌈ - z_{k} + {\hat{x}}_{m ∣ m + 1} ⌉ - d$ .

(3) (Check $x_{m}$ ) Set $x_{m} = X_{k} (m)$ ,

if $b_{m, m}^{2} {(x_{m} - {\hat{x}}_{m ∣ m + 1})}^{2} > r_{k, l, m}^{' 2} + δ_{k, l, m}^{}$ and $x_{m} \leq U B (x_{m})$ , go to (5), else to (4).

(4) (Increase k) $k = k + 1$ , If $k = L^{N} + 1$ , terminate algorithm, else go to (1).

(5) (Decrease m) If $m = 1$ go to (6). Else $m = m - 1$ , ${\hat{x}}_{m, m - 1} = {\hat{x}}_{m} + \sum_{j = m + 1}^{M} (b_{k \cdot j} {/ b}_{m, m}) (x_{j} - {\hat{x}}_{j})$ ,

$r_{k, l, m}^{' 2} = r_{k, l, m + 1}^{' 2} - r_{m + 1, m + 1}^{2} {(x_{m + 1} - {\hat{x}}_{m + 1 ∣ m + 2})}^{2} + δ_{k, l, m + 1}^{}$ , and go to (2)

(6) Solution found for k. Save k, $X_{k}$ and exact distance $d_{k, l}$ . and set $k = k + 1$ , if $k = L^{N} + 1$ , terminate algorithm, else go to (1).

Note that Max-Log-Sphere decoder needs estimating the noise variance of the receiver. However, Max-Log decoder using Eulerian distance and error probability is more realizable. Hence, there is a tradeoff between computational complexity and implementation to choose which one is suitable.

5. Computational Complexity Analysis

In this section, we analyze and compare the computational complexity of above three decoders. We use the average numbers of real elementary operation, $C_{p}$ (including addition, subtraction, multiplication, and division), as a measure for computational complexity.

5.1. Complexity of ML Decoder

By (5), it easy to know that compute $P (Y ∣ H, C_{k})$ needs $T N + 5 T + 3 N + 1$ times additions and $4 N T + 4 T$ multiplications. Similarly, observe (4), we also can figure out that compute $P (c_{k} ∣ F, s)$ needs $N - 1$ multiplications. Therefore, there are $(L^{N} - 1) + L^{N} (T N + 5 T + 3 N - 1)$ additions and $L^{N} (4 N T + 4 T + N - 1)$ multiplications to obtain $P (Y ∣ F, H, s_{l})$ . As a result, it needs

\begin{matrix} C_{p}^{ML} = L^{N + 1} (5 N T + 9 T + 4 N - 1) - L . \end{matrix}

(21)

operations (additions and multiplications) to perform ML decoder.

5.2. Complexity of Max-Log Decoder

Recall (10), ${∥ Y - C_{k} H ∥}^{2}$ needs $T N + 5 T + 3 N - 1$ additions and $4 N T + 4 T$ multiplications and $λ_{k, l}$ needs $N - 1$ multiplications. Therefore, Max-Log decoder needs

\begin{matrix} C_{p}^{Max - \log} = L^{N} (5 N T + 9 T + 3 N - 1) + L^{N + 1} (N - 1) + L . \end{matrix}

(22)

real operations. To compare the complexities of ML decoder and Max-Log decoder, we have

\begin{array}{l} C_{p}^{ML} - C_{p}^{Max - \log} \\ = L^{N + 1} [(5 N + 9 T + 3 N - 1) (1 - \frac{1}{L}) + 1 - \frac{2}{L^{N}}] . \end{array}

(23)

As stated in system model,

L \geq 2

and

N \geq 1

, so there is

C_{p}^{ML} > C_{p}^{Max - \log}

. That is to say ML decoder has higher complexity than Max-Log decoder.

5.3. Complexity of Max-Log-Sphere Decoder

Max-Log-Sphere decoder for a $s_{l}$ has $L^{N}$ radiuses but each radius is only assigned for searching one possible $C_{k}$ . According to [14, 15], an arbitrary lattice point $X_{k}$ that belongs to an m dimensional sphere of radius $r_{k, l}$ around the transmitted point $X_{t}$ is given by the following incomplete Gamma function:

\begin{array}{l} γ (\frac{2 α N + λ_{k, l}}{2 (1 + Pr {∥ X_{t}^{m} - X_{k}^{m} ∥}^{2})}, \frac{2 N - 2 T + m}{2}) \\ = \int_{0}^{2 (1 + Pr {∥ X_{t}^{m} - X_{k}^{m} ∥}^{2})} ‍ \frac{x^{((2 N - 2 T + m) / 2) - 1}}{Γ ((2 N - 2 T + m) / 2)} e^{- x} d x, \end{array}

(24)

where

X^{m} = [x_{M - m}, x_{M - m + 1}, \dots, x_{M}]^{T}

, and

Pr

is the relay transmit power, which is assumed as unit in above context. The number of elementary operations that the Max-Log-Sphere decoder performs per each visited point in dimension m is

\begin{matrix} C_{p} (k, l, m) = 2 m + 12 . \end{matrix}

(25)

Denote (24) as

P_{k, l}

; therefore,

C_{p}

of Max-Log-Sphere decoder is yielded as

\begin{matrix} C_{p} = \sum_{l = 1}^{L} \sum_{k = 1}^{L^{N}} \sum_{m = 1}^{M} C_{p} (k, l, m) P_{k, l} . \end{matrix}

(26)

It is difficult to compare Max-Log-Sphere decoder with other decoders, but in next section we will show simulation results to illustrate the differences.

6. Simulation Results

In this section, we provide the simulation results to show the proposed error aware decoders. We denote the total power noise ratio as the system signal-noise ratio (SNR) indicator. And half of total power is assigned for source transmit power, and another half is equally divided by all relays. In this simulation, we adopt distributed linear dispersion code proposed in [12] as the coding scheme for its simplicity, where $ℱ_{i} (s) = A_{i} s$ and $A_{i}$ is a random unitary matrix. For Max-Log-Sphere decoder, herein we set $P_{f p} = 0.99$ . All other parameters are the same with system model. We also should claim the nonerror aware decoder is

\begin{matrix} \arg \min_{s} {∥ Y - C (s) H ∥}^{2}, \end{matrix}

(27)

where

C (s) = [A_{1} s, A_{2} s, . . ., A_{N} s]

6.1. Performance Comparison with Ideal Receivers

Figure 5 demonstrates bit error rate (BER) performances of different decoders where two relays are employed and the signal modulation is BPSK. That is to say $T = N = 2$ . We can see that at high SNR regime error aware decoders achieve almost 6 dB gain than nonerror aware decoder and outperform AF scheme-based ML decoder about 3 dB. Thus it is worthy to bring slight system overhead for delivering channel estimation to improve the system performance. Over all SNR range, Max-Log decoder and Max-Log-Sphere decoder have nearly the same performance with ML decoder. Therefore, the degradation of Max-Log approximation is negligible. Carefully observing, we found that the slope of BER curve decreases. The reason is that the hard-decision error at relay limits the systems performance even though SNR is enough high.

Figure 5

BER performance of error aware decoders (2 relays, ideal receiver).

In Figure 6, we also simulate a 4-relay network to show the BER performance of that decoders. Herein, $T = N = 4$ and modulation is QPSK. Similarly, error aware decoders can bring about 7 dB power gain than nonerror aware decoder at 22 dB SNR. We can see that it is different from Figure 5 that error aware decoders only achieve about 1.5 dB gain than AF-based ML decoder. The reason is that high-order modulation incurs more error after decoding at relays and enlarges errorpropagation so that deceases the possible gain of error aware decoder. And in this case, the differences of three error aware decoders are more slight. It is interesting that the slope of BER curve does not decrease here. That is because more relays bring more error conditions and consume more power. Therefore, the slope decreasing threshold is larger than 2 relay with BPSK system. From both two figures, we can assert that error aware decoders can improve the system performance efficiently with little system cost.

Figure 6

BER performance of error aware decoders (4 relays, ideal receiver).

For distributed space-time coded (DSTC) relay networks, [12] had proved that the maximum achievable diversity order is $\min {N, T}$ . Reference [16] addressed that demodulate-and-forward scheme in a relay network where direct link is available can only achieve half of maximum diversity. In our simulations, relay network with nonerror aware decoder has an even less diversity, that is, the diversity of nonerror aware decoder in Figure 5 is 1 and in Figure 6 is only 1.2. That is because there is no direct link in our model and direct link which does not produce demodulation error. Adding a direct link can increase the system diversity by one but adding on one relay could not gain advantages, but even get worse. Essentially speaking, demodulation error limits the diversity growing. On the other hand, error aware decoder has a larger diversity than nonerror aware decoder. That is to say error aware decoder gains advantages from the available error probabilities. Since there are also demodulation errors at relays, error aware decoder cannot achieve the full diversity at finite SNR.

6.2. Performance Comparison with Practical Receiver

In order to validate the practical performance of our proposed error aware decoders, we also consider a practical receiver at the destination, where channel state information is generated by channel estimator. It means that channel state information is not perfect and has estimation error. We set the transmit power of pilot symbols used to estimate channel equal to the transmit power of data symbols. The procedure of channel estimation follows that 3-step scheme described in Section 3. Channel estimators are built on minimum mean square error (MMSE) rule [11]. In addition, the performance degradation of low-complexity decoders is incurred by less searching in codebook. Moreover, both Figures 5 and 6 prove that low-complexity decoders achieve similarly performance compared with the error aware ML decoder. Therefore, in following simulation, we do not draw the performance of all three error aware decoders but error aware ML to compare with other schemes.

Figures 7 and 8 give the BER performances of different decoders with practical receivers where channel state information is not perfect. Clearly, the channel estimation error does not change performance relationship among nonerror aware decoder, AF-based ML decoder, and error aware ML decoder. Comparing Figures 5 and 7, we can see that the performance gain obtained by error aware decoder as compared to AF-based ML decoder decreases from 3 dB to 2.5 dB. We also can find that the gain of error aware decoder over nonerror aware decoder decreases from 6 dB to 5 dB through comparing Figures 6 and 8. That is to say that the uncertainty of channel state information does degrade the performance of our proposed error aware decoder but the degradation is limited. Error aware decoder still outperforms nonerror aware decoder. In summary, our proposed error aware decoder works well in practical receivers.

Figure 7

BER performance of error aware decoders (2 relays, practical receiver).

Figure 8

BER performance of error aware decoders (4 relays, ideal receiver).

6.3. Complexity Comparison

We will show the computational complexity of three error aware decoders by elementary operation number. Note that the operation number of Max-Log-Sphere decoder varies with unitary matrices $A_{i}$ and the channel realization because of (13). We average the elementary operation number over 1000 channel realizations.

In Figure 9, we show the average operation number of these three decoders when 2 relays are employed. Obviously, $C_{p}$ s of ML decoder and Max-Log decoder are independent of SNR. Max-Log decoder has a lower complexity than ML decoder. Max-Log-Sphere decoder needs far smaller operation number than that of ML decoder and Max-Log decoder. Of course, for 2-relay network, the operation number of ML decoder is trivial compared with current hardware computing rate. However, for 4 relays with QPSK modulation scheme, it is too large to be affordable. Figure 10 gives the elementary operation number in this case. We can see that ML decoder has $1.4404 e + 014$ operations! The operation number of Max-Log decoder is nearly $1 %$ of that of ML decoder. It is notable that Max-Log-Sphere decoder needs only $0.1 %$ operation number of Max-Log decoder. Therefore, Max-Log-Sphere decoder achieves the same BER performance with optimal ML decoder but costs drastically low computation. Although Max-Log-Sphere has an attractive performance, the noise variance should be estimated first to calculate searching radius [14]. Max-Log decoder just utilizes Eulerian distance and error probabilities; therefore, it is a good tradeoff for decoding structure between implementation and computational complexity. We can choose one of them due to different receivers.

Figure 9

Average operation number of three decoders with 2 relay, BPSK.

Figure 10

Average operation number of three decoders with 4 relay, QPSK.

7. Conclusion

In this paper, we provide a general framework of error aware distributed space-time decoder for regenerative relay networks. Through two-stage pilot symbols, the destination can estimate not only the relay-destination channel but also the error probability happening at relays. Using these estimated error, Maximum Likelihood decoder is provided. To reduce computational complexity, Max-Log decoder and Max-Log-Sphere decoder are also proposed by max-log approximation. Simulations show that error aware decoders can improve the performance drastically. Max-Log-Sphere decoder can achieve the same performance with ML decoder and needs far lower computational complexity. Without noise estimating, Max-Log decoder can make a good tradeoff between implementation and computational complexity.

Footnotes

Acknowledgments

This work is supported by National Nature and Science Funding of China (no. 61102082), National High-tech R&D Program (863 Program, no. 2011AA01A105), National Science and Technology Major Project of China (no. 2012ZX03001032-002), the Fundamental Research Funds for the Central Universities, the Specialized Research Fund for the Doctoral Program of Higher Education (no. 20110201120011), and the Open Research Fund of National Mobile Communications Research Laboratory, Southeast University (no. 2011D14).

References

Laneman

J. N.

Tse

D. N. C.

Wornell

G. W.

Cooperative diversity in wireless networks: efficient protocols and outage behavior

IEEE Transactions on Information Theory 2004 50 12 3062 3080

2-s2.0-5044252003

10.1109/TIT.2004.838089

Zhao

Distributed modulation for cooperative wireless communications

IEEE Signal Processing Magazine 2006 23 5 30 36

2-s2.0-33750060726

10.1109/MSP.2006.1708410

Zhang

Yin

Wei

Selective relaying schemes for distributed space-time coded regenerative relay networks

IET Communications 2010 4 6 967 979

2-s2.0-77953490999

10.1049/iet-com.2009.0438

Onat

F. A.

Adinoyi

Fan

Yanikomeroglu

Thompson

J. S.

Optimum threshold for SNR-based selective digital relaying schemes in cooperative wireless networks

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '07)

March 2007

970 975

2-s2.0-36348990635

10.1109/WCNC.2007.184

Scutari

Barbarossa

Distributed space-time coding for regenerative relay networks

IEEE Transactions on Wireless Communications 2005 4 5 2387 2399

2-s2.0-28444435951

10.1109/TWC.2005.853883

Hoshyar

Tafazolli

A pre-BSC model for distributed turbo codes

Proceedings of the 69th Vehicular Technology Conference (VTC '09)

April 2009

2-s2.0-70349683034

10.1109/VETECS.2009.5073332

Khormuji

M. N.

Larsson

E. G.

Receiver design for wireless relay channels with regenerative relays

Proceedings of the IEEE International Conference on Communications (ICC '07)

June 2007

4034 4039

2-s2.0-38549132527

10.1109/ICC.2007.664

Cover

T. M.

Thomas

J. A.

Elements of Information Theory 1991

John Wiley & Sons

Paulraj

Nabar

Gore

Introduction to Space-Time Wireless Communications 2003

Cambridge University Press

10.

Goldsmith

Wireless Communications 2005

Cambridge University Press

11.

Gao

Cui

Nallanathan

On channel estimation and optimal training design for amplify and forward relay networks

IEEE Transactions on Wireless Communications 2008 7 5 1907 1916

2-s2.0-47149084050

10.1109/TWC.2008.070118

12.

Jing

Hassibi

Distributed space-time coding in wireless relay networks

IEEE Transactions on Wireless Communications 2006 5 12 3524 3536

2-s2.0-33845674517

10.1109/TWC.2006.256975

13.

Lin D

Costello

Jr.

Error Control Coding 2004 2nd

Pearson Education

14.

Hassibi

Vikalo

On the sphere-decoding algorithm I. Expected complexity

IEEE Transactions on Sginal Processing 2005 53 8 2806 2818

15.

Vikalo

Hassibi

Kailath

Iterative decoding for MIMO channels via modified sphere decoding

IEEE Transactions on Wireless Communications 2004 3 6 2299 2311

2-s2.0-11844253863

10.1109/TWC.2004.837271

16.

Chen

Laneman

J. N.

Modulation and demodulation for cooperative diversity in wireless systems

IEEE Transactions on Wireless Communications 2006 5 7 1785 1794

2-s2.0-33748100064

10.1109/TWC.2006.1673090

Low-Complexity Decoding Algorithms for Distributed Space-Time Coded Regenerative Relay Systems

Abstract

1. Introduction

2. System Model

3. Error Aware Maximum Likelihood Decoder

Step 1.

Step 2.

Step 3.

3.1. Optimality of Error Aware Decoder

( 1 ) Receiver Rule

( 2 ) Signal Space Description

Case 1 (No error happens at relays).

Case 2 (Error happens at relays).

4. Low-Complexity Error Aware Decoders

4.1. Error Aware Max-Log Decoder

4.2. Error Aware Max-Log-Sphere Decoder

Algorithm 1

Algorithm 2

5. Computational Complexity Analysis

5.1. Complexity of ML Decoder

5.2. Complexity of Max-Log Decoder

5.3. Complexity of Max-Log-Sphere Decoder

6. Simulation Results

6.1. Performance Comparison with Ideal Receivers

6.2. Performance Comparison with Practical Receiver

6.3. Complexity Comparison

7. Conclusion

Footnotes

Acknowledgments

References

$(1)$ Receiver Rule

$(2)$ Signal Space Description