Improved Length Term Calculation And Mmse Extention

Improved Length Term Calculation and MMSE Extension for LISS MIMO Detection Ernesto Zimmermann and Gerhard Fettweis Vodafone Chair at TU Dresden, D-01062 Dresden, Germany, [email protected] Abstract— List sequential (LISS) detection is an effective means of achieving near-capacity performance in iterative detection-decoding for MIMO systems. Using a length bias term calculated via an auxiliary stack has been shown to substantially narrow the tree search and thus reduce detection complexity. We present a novel approach to determine an approximation of the bias term, based on information available during the tree search in the main stack of the LISS detector. We also extend the LISS MIMO detector from ZF to MMSE based detection and show that by following this approach, a far better performance-complexity trade-off can be achieved.

The remainder of this paper is organized as follows. In Section II, we introduce the system model and basic notions of iterative detection-decoding of MIMO signals. Section III discusses the basics of list sequential MIMO detection and presents the novel method for calculating the length bias term. In Section IV we present simulation results before we finally draw conclusions in Section V.

I. I NTRODUCTION

We consider a MIMO system with MT transmit and NR receive antennas, as depicted in Figure 1. Let u be a vector of i.i.d. information bits which are encoded using the outer channel code, and interleaved. The resulting code bit stream is partitioned into blocks c of MT · L bits, where L denotes the number of bits per symbol (allowing to distinguish between Q = 2L different constellation points). Each block c = (c1 , · · · , cMT )T consists of MT binary vectors cm , m = 1, · · · , MT of L bits and is mapped onto a vector symbol x = (x1 , · · · , xMT )T whose components are taken from some complex constellation C (e.g. 16-QAM) using the mapping function xm = map(cm ) (e.g., Gray mapping).

The main challenge for multiple antenna (MIMO) systems lies in the non-orthogonality of the transmission channel, which renders the correct separation of the data streams at the receiver a challenging task. “Turbo-MIMO” solves this problem very efficiently by exchanging (extrinsic) information between inner MIMO detector and outer channel decoder. In this context, tree search techniques such as list sphere detection [1] (LSD) and list sequential detection [2] (LISS) have been shown to achieve performance close to the capacity limit of the MIMO channel while avoiding the prohibitive complexity of a full a posteriori probability (APP) detector. The LISS detector is a derivation of the stack algorithm. A sorted list is filled with paths of different lengths resulting from a tree search over possibly transmitted vector signals. Adjusting the stack size allows to trade-off detector performance against implementation simplicity. One main drawback of LISS detection is that shorter paths are privileged in the node extension process. The search tree thus grows very fast in width, resulting in high detection complexity. A so-called length bias term can be used to tackle this problem. One possible solution is to use an additional auxiliary stack for the calculation of the length bias [3]. Although this approach leads to an almost perfect estimation of the bias term, the required effort in terms of computational complexity and additional memory is very high. In this paper, we propose to approximate the bias term by considering the metric accumulated by the first path extended to a certain depth during the tree search. This “Babai bias” term requires practically no implementation effort and achieves a complexity reduction comparable to that of the bias term based on an auxiliary stack. We furthermore extend the LISS detector from ZF based to MMSE based MIMO detection and show that combined with the Babai length term, this approach enables to achieve an excellent performance-complexity trade-off.

II. S YSTEM M ODEL A. MIMO Model

Binary Source

u

Outer Encoder

e

Rate R

x ... H ...

Interleaver

AWGN Hard Decision Binary Sink

Constellation Mapper

c

n y

SISO Decoder

LA,Dec

-1

LE,Dec

LE,Det

MIMO Detector

LA,Det

Fig. 1. Transmission model with outer channel encoder, MIMO channel and iterative receiver (soft-input soft-output detector and decoder).

We consider transmission over a frequency flat fading MIMO channel. In the equivalent base-band model, the received signal yt at time index t is thus given by yt = Ht xt + nt

(1)

where Ht ∈ CNR ×MT is the channel transfer matrix which we assume to be perfectly known at the receiver. The entries of Ht are realizations of zero mean i.i.d. complex Gaussian random processes of variance 1 (i.e., each subchannel is passive). We normalize the average transmit energy such that NR ×1 E{xt xH represents t } = Es /MT I. The vector nt ∈ C

the receiver noise and its components are zero mean i.i.d. complex Gaussian random variables with variance N0 /2 per real dimension: E{nt nH t } = N0 I. The signal-to-noise ratio (SNR) at each receive antenna is hence given by SNR = Es /N0 and we define σ 2 = MT N0 /Es . B. Iterative Detection and Decoding We consider the serial concatenation of an inner MIMO detector and an outer channel decoder. Both entities are able to accept and generate soft information. The detector uses the received signal, the channel state information and the a-priori information provided by the decoder to generate extrinsic information on the received bits. The channel decoder uses the correlation between different code bits (i.e., the code’s structure) to generate extrinsic information about the information bits and the code bits. The latter information is interleaved and fed back to the detector. Extrinsic information is exchanged using the so called log-likelihood ratios (LLRs) for the code bits ci (dropping time index t for ease of notation): P [cm,l = +1|y] L(cm,l |y) := ln P [c = −1|y] P m,l +1 p (y|x(c)) · P [c]/p(y) x(c)∈Xm,l = ln P . (2) x(c)∈X −1 p (y|x(c)) · P [c]/p(y) m,l

where the second line follows from Bayes’ theorem and the ±1 assumption of statistically independent bits. Xm,l denotes the set of 2MT ·L−1 symbols x ∈ X for which cm,l = ±1. The second term in (2) represents the a-priori knowledge from the outer channel decoder. The conditioned probability densities in (2) are given by the complex Gaussian distribution:   1 1 2 exp − ky − Hxk . (3) p(y|x) = (πN0 )NR N0 For the LLR computation, the constant scaling factor cancels out and can thus be omitted. To evaluate the numerator and denominator of (2) at low complexity, it is useful to apply the so called “maxLog” approximation:

) MT ·L X − ky − Hxk2 L(cm,l |y) ≈ max + ln P [ci ] − ln p(y) +1 N0 x∈Xm,l i=1   − max ... . (4) (

−1 x∈Xm,l

Evaluating the two max-operations in equation (4) by a brute-force approach (max-APP/MAP detection) requires an effort growing exponentially in the number of transmitted bits per vector symbol, that is, the achieved (raw) spectral efficiency. This is clearly impractical for many applications of interest. However, this task can be solved far more efficiently, as will be detailed in the following section. For channel coding, we consider the parallel concatenation of two recursive systematic convolutional codes – a classical “Turbo code”. The decoder employs two instances of the BCJR [4] algorithm that exchange extrinsic information in a number of (internal) decoder iterations and afterwards feed back extrinsic information to the MIMO detector.

III. L IST S EQUENTIAL D ETECTION ±1 Based on the recognition that only a few hypotheses in Xm,l actually maximize each of the respective terms in (4), the LISS detector constructs a subset list L ⊂ X to determine the LLRs. This subset should on the one hand include only a fraction of the elements from X , but on the other hand be large enough to allow approaching the true detector L-values as closely as possible. Using a QR-decomposition of H, the MAP detection problem can be reformulated using the perantenna metric increments Λm : ( 1 ) X  1 X L(cm,l |y) ≈ max+1 Λm − max−1 Λm , x∈L∩Xm,l

x∈L∩Xm,l

MT

MT

(5) with Λm given by

2

X

MT L X

1

+

ln Pr[cm,l ]−ln p(ym ) r x y ˜ − Λm = − m,j j m

N0

l=1

j=m (6) where the term ln p(ym ) represents the so-called length bias term at antenna index m. The information lying in the incomplete entries of the stack can be used to further improve the L-values by extending the shortened paths to full length as proposed in [2], [3]. We use such a path augmentation, as well as soft weighting of the augmented stack entries in the final calculation of the LLRs (for details refer to [3]). A. Existing Length Bias Term Options During the tree search, the stack of the LISS detector contains paths of different lengths. Longer paths have a higher accumulated Euclidean distances and therefore tend to be sorted to the bottom of the stack – the width of the search tree grows very fast, resulting in high detection complexity. The so-called length bias term ln p(y) allows to tackle this problem by appropriate adjustment of the path metrics. For a path spanning antennas 1 through m, it is defined as: X ln p(y1m ) = ln p(y|xi ) · P [xi ] xi ∈Im

=

ln

X

eln p(y|xi )+ln P [xi ]

(7)

xi ∈Im

where Im indicates the set of all possible signal combinations for the considered path depth m. The calculation of the correct bias term is thus as complex as the whole soft output detection problem itself. In [3], [5] it is therefore suggested to approximate the length bias term by using the M-algorithm in an additional auxiliary stack. The quality of the length term can be tuned by choosing the size of this stack. The a priori knowledge is taken into account, but the effort required for calculation of the bias term is still substantial. In [6] is was therefore suggested to approximate the bias term by the average accumulated noise energy over the receive antennas. Due to the normalization of the Euclidean path increment with N0 , this noise bias term requires only an increment of 1 per detected antenna. However, it neglects the influence of a priori knowledge.

B. The Babai Length Bias Term

IV. S IMULATION R ESULTS

We propose another very efficient way of calculating the length bias term, based on the information available in the main stack. Since asymptotically (for high SNR), the path which is first extended to a certain depth has a high probability of having the best metric at this depth, we approximate the length bias for depth m by the metric of the path which is first extended to depth m. This approach evidently takes a priori knowledge into account, but will in general underestimate the real length bias and thus lead to (slightly) higher detection complexity, compared to the true length bias.

Fig. 2. Illustration of the proposed length bias term. The first leaf node found is always the Babai solution.

As becomes evident from Figure 2, using the proposed approximation for the bias term results in a “normalization” of the best extended path to a zero metric while all other paths have by definition a worse metric, independent of their depth. This in effect forces the LISS detector to conduct a depthfirst search at the beginning of the tree construction. The first leaf node (or full length candidate) found will hence be the one commonly known as the decision-feedback-equalization (DFE) solution, or Babai point [7]. We will therefore refer to the proposed length bias as “Babai bias” in the following.

To ensure comparability of results, we study the performance of the proposed scheme in a setup equivalent to the one in [1]. We consider rate 1/2 PCCC coded transmission (memory 2 (7R , 5) constituent convolutional codes) over a 4x4 MIMO channel with Gray mapped QAM modulation, an information block size (including tail bits) of 9216 bits, and spatially and temporally i.i.d. fading (each transmitted vector symbol sees a different channel). We used 8 internal decoder iterations and 4 detector-decoder iterations. In the following, we will distinguish between two different operation modes of the LISS detector. In the first mode, we require the LISS to run until the specified number of full length paths is found. During the node extension process, nodes that have a worse metric than the node at the bottom of the stack are dropped. The detection complexity is hence not bounded by the stack size and can (in the absolute worst case) grow to the full MAP complexity. This operation mode is equivalent to the one used in [2]. Alternatively, one may stop the tree search once the stack is full or the required number of full length paths is found. The detection complexity is hence upper bounded by the chosen size of the stack. This setup is similar to the one used in [3], [5] (where the number of required full length candidates was set to be equal to the stack size). A. 4-QAM Results, No Upper Bound on LISS Complexity We first investigate the performance and complexity reduction of the LISS using the proposed Babai length term with 4-QAM transmission and the first operation mode. A minimum of C = 8 full length paths is required to be found. Note that the minimum number of node extensions in this case is emin = MT + C/Q − 1 = 5 (MT = Q = 4). 10

0

LISS, 8 full length cands., stack size 256, w/ PA

C. MMSE Extension

10

2

2

= ky − Hxk + σ 2 kxk .

(8)

2

2

While for PSK (and 4-QAM) modulation, the bias σ kxk cancels out in the LLR-calculation, it has to be removed for the case of multi-level modulation (16-QAM and beyond) to avoid a deterioration of the detector’s performance. Similar to the length term, using the MMSE solution leads to a much narrower search tree of the LISS detector. Especially in the first detector iteration, where soft (ZF) augmentation of the paths yields rather poor quality of the soft output, it also enables strong performance improvements.

10

−2

BER

The channel matrix can be extended by a scaled identity matrix to obtain a convenient expression for the MMSE solution [8]. The (sorted) QR decomposition [9] of this extended channel matrix can be straightforwardly applied [10]. However, this approach leads to a bias on the calculated metrics:

  2  



y − Hx 2 = y − H x

0

σI

−1

10

10

−3

−4

2

No Bias

MAP

2.5

Noise Bias

Aux. Stack

3.5

4

3

Babai Bias

4.5

E /N [dB] b

0

Fig. 3. Performance of the ZF based LISS detector using different length bias options. Narrowing the search tree too much clearly degrades performance.

Performance results for the ZF case are presented in Figure 3. Clearly, the best performance is achieved by using no length bias at all – but this comes at the expense of substantially higher complexity (cf. results in Figure 4). The LISS shows quite poor performance when used with the Babai

length term or the length term based on the auxiliary stack. Both schemes “suffer” from the efficiency of their tree search (cf. Figure 4) – for many bits, appropriate counter-hypotheses are missing and path augmentation can alleviate this problem only to a limited extend (especially in the first iteration when no a priori knowledge is available). The number of node extensions in the main stack is roughly the same for both schemes. However, for the length bias based on the auxiliary stack, the complexity of the additional stack must be taken into account – even for a stack size of 1 (which would produce a performance equivalent to that of the LISS with Babai bias), 4 additional node extensions are required – the total average complexity would be even higher than for the case without any bias. For the ZF case, the noise bias provides the best performance-complexity trade-off.

Average number of extended nodes

9

LISS, Stack size 256, w/ PA, 8 full length candidates No Bias

8

7

Noise Bias

ZF−LISS

Babai Bias

Aux. Stack

6 MMSE−LISS

5 2

2.5

3

Eb/N0 [dB]

3.5

4

4.5

The observed improvement stems from the fact that the MMSE Babai point is typically far closer to the ML/MAP solution than the ZF Babai point and the quality of the soft output will thus be substantially higher. This is consistent with the observations from [11]. In the case of the noise bias, the impact of MMSE preprocessing is mostly on complexity, as it enables to significantly narrow the tree search. This result has been previously reported in the context of Sphere decoding in [7], [12]. The complexity results in Figure 4 show that for the MMSE-based LISS only a single additional node extension is required on average (remember that emin = 5), illustrating the very high efficiency of the tree search for both the noise bias and the Babai bias. We will therefore concentrate on those two schemes in the following. B. 16-QAM Results, LISS with Bounded Complexity In this section, we study the performance of the LISS detector using the Babai and the noise bias term, a stack size S = 512 and C ∈ {128, 256} full length candidates, for 16-QAM transmission and the second operation mode: the tree search stops once the stack is full. The effect of choosing different bias options will hence be less on the size of the search tree, but on the enumerated leaf nodes – and thus on the achieved quality of the soft output. The maximum number of node extensions emax is evidently upper bounded by emax = 1 + (S − Q)/(Q − 1) ≈ 34. The minimum number of node extensions is emin = 11 for C = 128 and emin = 19 for C = 256. The performance of an MAlgorithm/ITS based detector [13] with the same maximum number of node extensions is plotted as reference (stack size M = 11, eIT S = 1 + (MT − 1) · M = 34).

Fig. 4. Average number of node extensions in the LISS (a minimum of 5 is necessary). The lowest complexity is achieved with the MMSE based LISS.

10

Results for the MMSE case are presented in Figure 5. For the LISS using the Babai bias (where the search tree is already very narrow) the impact is mainly on performance. 0

LISS, Stack size 256, w/ PA, 8 / 16 full length candidates ... Babai Bias ... Noise Bias

8 cands.

10

−1

10

10

10 10

LISS, Stack size 512, w/ PA, 128 / 256 full length candidates ... Babai Bias ... Noise Bias

M−Algorithm, M=11, MMSE −1

128 cands.

−2

BER

10

10

0

128 cands.

−3

−4

256 cands.

ZF−LISS

MMSE−LISS Noise Bias

−2

Babai Bias

BER

256 cands.

6 10

10

−4

7

E /N [dB]

7.5

8

0

MMSE−LISS

2.5

Fig. 6. Performance results for ZF vs. MMSE based LISS MIMO detection (bounded complexity, Babai or noise bias, stack size 512). Results for the M-Algorithm/ITS [13] with the same maximum complexity are plotted as reference. The MMSE-LISS significantly outperforms the ZF-LISS.

Babai Bias

Noise Bias

MAP

ZF−LISS

16 cands.

2

6.5

b

−3

3

Eb/N0 [dB]

3.5

4

4.5

Fig. 5. Performance results for ZF vs. MMSE based LISS. There is a substantial improvement for the LISS using the Babai length term. For the LISS using the noise bias, the impact is mainly on complexity (cf. Figure 4).

For the ZF-based LISS, the best performance is achieved when using the noise bias as length term. For the MMSE case, the LISS using a Babai bias again outperforms the LISS employing the noise bias. The complexity results in Figure 7 show that for the chosen setup, the number of node

extensions is mainly dictated by the required number of full length candidates C, and largely independent of the used bias term and whether ZF or MMSE preprocessing is used (note that 1/4 < C/S < 1/2, the variance is the size of the search tree is hence very low). Again, the noise bias provides the best performance-complexity trade-off in the ZF case while in the MMSE case the Babai bias should be used.

Average number of node extensions

35

LISS, Stack size 512, w/ PA, 128 / 256 full length candidates 256 cands.

ZF−LISS

30

25

... Babai Bias ... Noise Bias

MMSE−LISS

128 cands. ZF−LISS

20

stack [3], [5]. However, the new length bias can be determined at negligible effort, avoiding the (potentially high) complexity of the additional stack. Furthermore, we extended the ZF-based LISS which has so far been studied [5], [6] to the MMSE case and showed that this approach enables a far better performance-complexity trade-off. Particularly, using MMSE preprocessing enables the LISS with bounded complexity to achieve better performance than M-Algorithm based MIMO detection having the same maximum allowed complexity. This is another clear indicator that MMSE-DFE preprocessing is a key ingredient to solving the MIMO MAP problem efficiently, as noted in [11]. The increase in preprocessing complexity when using MMSE has of course to be taken into account (the overhead decreases as the channel coherence time increases), but may be an acceptable price in light of the achieved performance gains. R EFERENCES

15

10 6

MMSE−LISS

6.5

7

E /N [dB] b

7.5

8

0

Fig. 7. Performance of the LISS detector using different length bias options.

The lower performance of the ZF-based LISS using the Babai bias is due to the fact that the search tree is centered on the ZF-Babai solution in this case, while when using the noise bias it is still centered on the ML solution (only an estimate for the metric accumulated by the ML path is subtracted from the metrics). The relevance of centering the tree search on the ML solution has been stressed in [14] in the context of sphere decoding, and we observe the same behavior here in the context of list sequential detection. Similar to the setup studied in Section IV-A, the MMSE Babai solution (on which the search is centered when using the Babai bias with the MMSE-based LISS) is significantly closer to the ML solution and the quality of the produced soft output is correspondingly higher, resulting in the observed performance improvement. Comparing the results of the MMSE-based LISS and ITS MIMO detector shows that one can either achieve the same performance with both schemes, but with the LISS requiring less than half the average detection complexity than the ITS detector; or one may achieve a gain in performance of roughly 0.5dB at similar average complexity (note that both algorithms require the same maximum number of node extensions). V. C ONCLUSIONS In this paper, we studied the performance of a list sequential (LISS) MIMO detector using different approaches for the calculation of the length bias term. We proposed a new way to calculate the bias term, relying on information which is readily available in the main stack of the LISS-MIMO detector. The achieved a performance and the complexity involved in the tree search (in the main stack) is comparable to that of earlier proposals based on running an M-Algorithm in an auxiliary

[1] B. M. Hochwald and S. ten Brink, “Achieving Near-Capacity on a Multiple-Antenna Channel,” IEEE Transactions on Communications, vol. 51, no. 3, pp. 389–399, Mar. 2003. [2] S. Baero, J. Hagenauer, and M. Witzke, “Iterative Detection of MIMO Transmission using a List-Sequential (LISS) Detector,” in Proc. IEEE International Conference on Communications (ICC’03), Anchorage, USA, May 2003. [3] J. Hagenauer and C. Kuhn, “Turbo Equalization for Channels with High Memory using a List-Sequential (LISS) Equalizer,” in Proc. International Symposium on Turbo Codes and Related Topics (ISTC’03), Brest, France, 2003. [4] L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate,” IEEE Transactions on Information Theory, vol. 20, pp. 248–287, 1974. [5] J. Hagenauer and C. Kuhn, “The List Sequential (LISS) Algorithm and Its Application,” IEEE Transactions on Communications, 2006, accepted for publication. [6] S. Bittner, E. Zimmermann, W. Rave, and G. Fettweis, “List Sequential MIMO Detection: Noise Bias Term and Partial Path Augmentation,” in Proc. IEEE International Conference on Communications (ICC’06), Istanbul, Turkey, 2006. [7] O. M. Damen, H. E. Gamal, and G. Caire, “On the Complexity of ML Detection and the Search for the Closest Lattice Point,” IEEE Transactions on Information Theory, vol. 59, no. 10, pp. 2400–2414, Oct. 2003. [8] B. Hassibi, “An Efficient Square Root Algorithm for BLAST,” in Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP’00), Istanbul, Turkey, June 2000. [9] D. Wuebben, J. Rinas, R. Boehnke, V. Kuehn, and K. Kammeyer, “Efficient Algorithm for Detecting Layered Space-Time Codes,” in Proc. 4th International ITG Conference on Source and Channel Coding (ITG SCC’02), Berlin, Germany, Jan. 2002. [10] D. Wuebben, R. Boehnke, V. Kuehn, and K. Kammeyer, “MMSE Extension of V-BLAST based on Sorted QR Decomposition,” in Proc. IEEE Semiannual Vehicular Technology Conference (VTC2003-Fall), Orlando, USA, Oct. 2003. [11] A. Murugan, H. E. Gamal, O. M. Damen, and G. Caire, “A unified framework for tree search decoding: rediscovering the sequential decoder,” IEEE Transactions on Information Theory, vol. 52, no. 3, pp. 933–953, Mar. 2006. [12] E. Zimmermann, W. Rave, and G. Fettweis, “On the Complexity of Sphere Decoding,” in Proc. International Conference on Wireless Personal and Multimedia Communications (WPMC’04), Abano Terme, Italy, Sept. 2004. [13] S. Haykin, M. Sellathurai, Y. de Jong, and T. Willink, “Turbo-MIMO for wireless communications,” IEEE Communications Magazine, vol. 42, no. 10, Oct. 2004. [14] J. Boutros, N. Gresset, L. Brunel, and M. Fossorier, “Soft-input softoutput lattice sphere decoder for linear channels,” in Proc. IEEE Global Telecommunications Conference (Globecom’03), San Francisco, USA, Dec. 2003.