List Sequential Mimo Detection

List Sequential MIMO Detection: Noise Bias Term and Partial Path Augmentation Steffen Bittner, Ernesto Zimmermann, Wolfgang Rave and Gerhard Fettweis Vodafone Chair Mobile Communications Systems Technische Universit¨at Dresden, D-01062 Dresden, Germany Email: [email protected]

Abstract— Near-capacity performance can be achieved in multiple-antenna systems by using a list sequential (LISS) detector for iterative equalization. Path augmentation is known to increase the performance of this detector, while a so-called bias term has been used to reduce its computational complexity, in applications other than MIMO detection. In this work, we extend the LISS MIMO detector [1] to incorporate different implementations of the bias term. We show that following the traditional approach of using an auxiliary stack for this purpose leads to a strong narrowing of the search tree, but also to a significant performance degradation, due to a reduced quality of the detector soft output. We therefore propose to use a so-called noise bias term instead, which can be implemented with negligible effort, significantly reduces the size of the search tree, but allows for almost retaining detector performance. Finally, we demonstrate that the extension of only a small fraction of the incomplete stack entries is sufficient to leverage the full gains of path augmentation, thus enabling further substantial savings in computational complexity.

I. I NTRODUCTION Radio frequency spectrum is a scarce resource and thus has to be used as efficiently as possible to satisfy the demands of modern data services. To achieve this high spectral efficiency, multiple antennas can be used at transmitter and receiver to spatially multiplex several parallel data streams into the same time-frequency bin. A big challenge in this context is the correct separation of the transmitted signals at the receiver. Recently, the field of iterative MIMO equalization based on the serial concatenation of an inner MIMO detector and an outer channel decoder has received a lot of attention. Two representatives of this approach are list sphere [4] and list sequential (LISS) [1] detection. Both schemes are able to approach the capacity limit of the MIMO channel while avoiding the prohibitive complexity of a full APP detector. The LISS detector is a derivation of the basic stack algorithm. A sorted list is filled with paths of different lengths resulting from a tree search over possibly transmitted vector signals. The detection procedure is stopped as soon as a predefined number of full length paths (candidates) is found. Adjusting the stack size allows to trade-off detector performance against implementation simplicity. There are two main drawbacks of (conventional) LISS detection: firstly, the stack usually contains a large number of incomplete paths which are not considered in the calculation of soft outputs and thus constitute a waste of resources. Secondly, shorter paths are

privileged in the extension process. The search tree thus grows very fast in width, resulting in high detection complexity. The problem of shortened paths can be resolved by using soft bits to extend all incomplete stack entries to full length [1]. Very good performance can then be achieved even when the stack contains only a low number of full length paths after the tree search. However, the complexity of this path augmentation can still be significant. In this paper we therefore propose to extend only a small fraction of the shortened paths – the ones with the best path metrics – and show that similar performance gains can be achieved. The issue of different path lengths during the tree search has not been considered in previous work on LISS MIMO detection. A so-called bias term can be used to tackle this problem. By penalizing short paths, it prevents the tree from growing too fast in width, thus speeding up the search. One possible solution is to use an additional auxiliary stack for this purpose [3]. Although this variant leads to an almost perfect estimation of the bias term, the required effort in terms of computational complexity and additional memory is prohibitively high. In this paper, we propose to approximate the bias term by the average accumulated noise energy over the receive antennas. This easily implementable noise term requires practically no implementation effort and provides an even better performance-complexity trade-off than the original bias term. The remainder of this paper is organised as follows. In Section II we describe the system model and the principles of iterative equalization. Section III introduces the basics of list sequential (LISS) detection investigated in detail in this paper. We also present different possibilities for bias term calculation and path augmentation. In Section IV we show results on the performance and complexity of the different LISS detector implementations investigated in this paper. We conclude the paper with a summary of our findings in Section V. II. S YSTEM M ODEL A. MIMO-Model We consider a MIMO (multiple-input, multiple-output) system with T x transmit and Rx receive antennas as depicted in Figure 1. Let u be a vector of information bits which are encoded by the outer encoder and interleaved. The resulting code bit stream is separated into blocks x containing T x·N independent binary digits. Here, N represents the number of bits per symbol and therefore allows to separate between M = 2N

different constellation points. Each block x = (x1 , · · · , xT x )T consists of T x binary vectors xt = (xt1 , · · · , xtN ) of N bits. As part of the transmission process, every single block is mapped onto a T x × 1 complex vector of symbols s = (s1 , · · · , sT x )T whose components are taken from some complex constellation C (e.g. 16-quadrature amplitude modulation (QAM)). These components are obtained using the mapping function st = map(xt ), t = 1, · · · , T x (e.g., Gray mapping). Binary Source

u

Outer Encoder

c

Rate R

Constellation Mapper

x

s ... H ...

Interleaver

AWGN

n

Hard Decision Binary Sink

y SISO Decoder

LA,Dec

LE,Dec

-1

LE,Det

MIMO Detector

LA,Det

Fig. 1. Transmission model with outer PCC encoder, MIMO channel and iterative receiver (soft SIC MIMO detector and SISO decoder).

The average transmission energy is equal to E[ksk2 ] = Es , with each component obeying the energy constraint of Es /T x. Let y be a vector of received symbols according to y = Hs + n

(1)

where H is a dimension Rx × T x MIMO channel matrix perfectly known at the receiver. Each entry of the channel matrix is an independent realisation of a complex Gaussian random process with zero mean and variance 1/2 per real dimension. The noise vector n consists of mutually independent zero-mean circularly symmetric complex Gaussian random variables, each with variance N0 /2 per real dimension. B. Iterative MIMO Equalization As receiver architecture we consider the serial concatenation of an inner MIMO detector and an outer channel decoder. Both detector and decoder are able to accept and generate soft information, which can be exchanged in an iterative fashion. The detector uses the received signal, the channel state information and the a-priori information provided by the decoder to generate new (extrinsic) information. The decoder exploits the correlation among different bits of the codeword (code bits), which are introduced by the channel code, to generate extrinsic information about the information bits as well as about the code bits. The latter information is interleaved and fed back to the detector. The MIMO detector can hence employ the provided a-priori information to further improve its soft output. For the soft information representation we use the convention of the so called log-likelihood values (L-values), see [2] for details. The L-value of a certain bit xtn conditioned on the received signal y is defined as: L(xtn |y) := ln

P [xtn = +1|y] . P [xtn = −1|y]

(2)

Using Bayes’ theorem under the assumption of mutually independent bits xtn (which is justified by the use of an interleaver

of appropriate size and structure), the joint probabilities can be split into products. The L-value computation can now be rewritten as: P x∈Xtn,+1 p(y|x) · P [x]/p(y) L(xtn |y) = ln P (3) x∈Xtn,−1 p(y|x) · P [x]/p(y) where Xtn,±1 is the set of 2T x·N −1 bit blocks x with xtn = ±1. The MIMO channel introduces interference among the transmitted signals at the receiver. The conditioned probability density in (3) is therefore given by the complex Gaussian distribution   1 1 2 exp − ky − Hsk . (4) p(y|x) = (πN0 )Rx N0 For the L-value computation only the exponential term is relevant – the constant scaling factor 1/(πN0 )Rx cancels out and can be omitted. The second term in (3) represents the apriori knowledge fed into the detector from the outer decoder, whereas the third (bias) term p(y) takes the influence of the different path lengths during the tree search into account. Note that this bias term effectively cancels itself out in the L-value computation, as only full length paths are considered there. Its only purpose is to speed up the tree search as will be explained later in Section III. To evaluate the numerator and denominator in (3) it is often convenient to apply the so called ”max-Log” approximation in order to speed up computation at the expense of some performance degradation [6]. The computation of the detector L-value can hence be approximated as a difference of two max-operations:  L(xtn |y) ≈

max

x∈Xtn ,+1

 −

max

x∈Xtn ,−1

1

y−Hs 2 +ln Y Y P [x ]−ln p(y)

tn N0 t=1 n=1 Tx

−





1

y −Hs 2 +ln Y Y P [x ]−ln p(y) .

tn N0 t=1 n=1 (5) Tx

−

N

N

As outlined in the introduction, equation (5) can be implemented by a number of different MIMO detection strategies. In our work, we concentrated on the list sequential approach, whose specifics are discussed in the following section. III. S EQUENTIAL D ETECTION A. Tree Search Evaluating the two max-operations in equation (5) by a brute-force approach is an intractable task which grows exponentially with the number of transmit antennas and the modulation size. However, only a few hypotheses x ∈ Xtn , ±1 actually maximise each of the respective terms. We call these hypotheses candidates and restrict our search to a subset list L ⊂ X. This list should on the one hand include only a fraction of elements from X but on the other hand be large enough to allow approaching the true detector L-value as closely as possible, such that any performance degradation of the receiver can be avoided. One effective scheme enabling

the construction of such a subset list is the stack algorithm, of which the List-Sequential (LISS) Detector introduced in [1] is a derivative. The LISS detector performs a tree search, maintaining a list of paths of different lengths which are sorted according to their metrics. For systems with an equal number of transmit and receive antennas, the computation of the squared Euclidian distance in (5) can be written as: ky − Hsk2 = kH(s − ˆ sZF )k2

(6)

where ˆ sZF = (HH H)−1 HH y is the unconstrained ML estimate of s (also known as the Zero-Forcing solution), which acts as the starting point of our search. During the tree search we always extend the path with the best metric which has not yet reached full length, by its M successors. The search ends after we obtained a predefined number of fully extended paths. (cf. Figure 2 for an illustration of such a BPSK search tree, where ”×” indicates the received symbol per antenna and ”•” represents the BPSK constellation points as well as the soft modulated constellation points in case of augmented paths.) LA (x11 ) = −5 x11 = +1

LA (x31 ) = −1.1

LA (x21 ) = +2.2 x ¯21 = +0.8

x ¯31 = −0.5

PSfrag replacements x31 = +1 x21 = +1 x31 = −1 x11 = −1 x21 = −1

x ¯31 = −0.5

As a prerequisite for evaluating (5) by a tree search algorithm, we have to decompose the channel matrix H to obtain a matrix of upper triangular structure. Since it is obviously also advantageous to detect reliably received signals first, we use the sorted QR decomposition (ZF-SQRD) introduced in [7] for this purpose. The upper triangular structure of R allows for defining a set of per-antenna metric increments, where each increment depends only on the current and previously detected symbols:

Tx

2 N X X

1

Λt = − rt,j (sj − sˆZFj ) + ln P [xtn ] − ln p(yt )

N0 j=t n=1 (7) where the term ln p(yt ) represents the bias increment at antenna t. Using these metric increments, the overall path metric can now be calculated as:  X   X  1 1 L(xtn |y) ≈ max Λt − max Λt . t=T x

x∈Xtn ,−1

t=T x

xi ∈It

=

ln

X

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

(9)

xi ∈It

where It indicates the set of all possible signal combinations for the considered path depth t. The calculation of the correct bias term is thus as complex as the whole soft output detection problem itself. In [3] it is therefore suggested to calculate an approximate bias term by using an additional auxiliary stack which contains only an appropriate subset of I. However, the increase in complexity and the additional memory requirements eat up a substantial part of the savings obtained by introducing this version of the bias term. We therefore take a different approach that directly addresses the main problem: the larger accumulated Euclidean distance in the metric of long paths. We propose to approximate the bias term by the average accumulated noise energy over the receive antennas. Assuming perfect detection of the transmitted signal, ˆ s = s, the squared Euclidian distance d2M L is equal to the squared norm of the noise vector n: d2M L

Fig. 2. Search tree for a 3 × 3 MIMO system using BPSK transmission. Dashed lines indicate augmented paths.

x∈Xtn ,+1

B. Bias Term Calculation During the tree search, the stack of the LISS detector contains paths of different lengths. Longer paths usually have worse metrics, due to the higher accumulated Euclidean distances, and hence tend to be sorted to the bottom of the stack. As a result, the width of the search tree grows very fast, resulting in high detection complexity. The so-called bias term ln p(y) in (7) enables to efficiently tackle this problem by appropriate adjustment of the path metrics. For a path of length t (i.e., spanning antennas 1 through t), it is defined as: X p(y|xi ) · P [xi ] ln p(y1t ) = ln

(8)

= ky − Hˆ sk2 = kH(s − ˆ s) + nk2 = knk2 N0 ∼ · χ22Rx . (10) 2 which is proportional to a weighted N20 chi-square random variable with 2Rx degrees of freedom. Thus, E{d2M L } = Rx · N0 and in view of the definition of the path metric increment (7) it becomes evident that, even in the case of perfect detection, the path metric is decremented by 1 per detected antenna, on average. We therefore propose to compensate this effect by incrementing the path metric by 1 per detected antenna. The introduction of this noise term can be expected to yield a narrower search tree and hence a complexity reduction at practically zero implementation effort. C. Path Augmentation 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, each list vector (horizontal stack entry) can be written as: x ˜l

= (˜ x1 , x ˜2 , · · · , x ˜N ·Hl , x ˜N ·Hl +1 , · · · , x ˜N ·T x )T := (x1 , x2 , · · · , xN ·Hl , x ¯N ·Hl +1 , · · · , x ¯N ·T x )T .(11)

where Hl indicates the number of perfectly known (in terms of distance computations) and hard decided bit values of the

lth list vector. Early proposals for such a path augmentation [5] suggested the use of a random tail. However, better performance can be achieved by extending the shortened paths using soft bits generated from available a-priori knowledge [1], that is:   LA (xtn ) x ¯tn = tanh . (12) 2 An example for such a path augmentation is given in ¯ t for t = H + Figure 2. The expected metric increment Λ 1, · · · , T x can be derived as the average over all possible ¯ t = E[Λt ] = ln PM exp(Λtm ). Again, metric increments Λ m=1 the max-log approximation is employed to simplify the calculation:  ¯ t ≈ max Λ ∀ m

1

r (s − sˆ ) + X r (˜s − sˆ ) 2

t,t tm t,j j ZFt ZFj N0 j=t+1 Tx

−

··· +

N X

IV. S IMULATION R ESULTS The performance of the LISS detector using different approaches for noise term calculation and path augmentation was tested by simulating a 4 × 4 MIMO system, with parameters selected equivalent to the setup in [4]. We assumed the receiver to know the channel perfectly and the channel gains to remain constant over the transmission of one vector but change statistically independent from one vector to another. As channel code we used a rate R = 1/2 parallel concatenated G = [7R , 5] turbo code, where 7 indicates the memory two feedback polynomial G(D) = 1 + D + D2 and 5 the memory two feedforward polynomial G(D) = 1 + D2 . The decoder performed 8 internal turbo decoding iterations. The interleaver size was set to 9216 bits. Moreover, we performed 4 detector-decoder iterations.



ln P [xnm ]

0

10

− ln p(yt )

8 candidates

n=1

(13)

−1

10

j=H

After the augmentation we have a complete working stack and compute the L-value by soft weighting of the stack entries Λ(l) as proposed in [3]:









1−x ˜tn 1+x ˜tn L(xtn |y) ≈ max Λ(l)+ln −max Λ(l)+ln . ∀l ∀l 2 2

This approach makes it possible to evaluate each maxoperation over all entries in the working stack, since the ln(·) part suppresses all contributions from negative bits in the first and all contribution from positive bits in the second term, by adding −∞. From the outline of the path augmentation procedure it becomes evident that the expected increase in performance may come at a substantial cost in terms of implementation effort, since a very high number of additional metric increments have to be calculated and far more stack entries have to be considered in the L-value computation (remember that the stack size is usually far larger than the number of full length candidates). One key question is hence whether it is really necessary to augment all incomplete paths in the stack. Motivated by the typical max-Log approximation, an alternative way is to sort the shortened paths according to their metric and use only a small fraction for path augmentation. The remaining incomplete paths are deleted from the stack.

No path augm. No bias

−2

10

BER →

where the (hard/soft) symbols ˜sl are obtained by (hard/soft) ˜ l . The bit probabilities are equal to mapping of x 1 + xtn · x ˜tn . (14) P [xtn = ±1] = 2 For the first iteration, however, no a-priori information is available. We therefore base the path augmentation on the ZF solution ˆsZF [1]. The corresponding metric increment can be written as:

Tx

2

1 X

Λt = − (15) r (s − s ˆ ) t,j j ZFj − ln p(yt )

N0

No path augm. Noise bias

Path augm. Aux. stack bias

−3

10

Full search

Path augm. No bias

1/3 path augm. Noise bias

−4

10

2

2.5

3

3.5

Eb/N0 [dB] →

4

4.5

5

Fig. 3. Performance results of a QPSK LISS receiver after 4 DetectorDecoder-Iterations with and without path augmentation and different types of bias approximations.

Figure 3 shows the result for QPSK transmission. As reference and upper performance bound, we plotted results for full APP detection (running the LISS with 28 = 256 candidates). The waterfall region for this brute-force approach is around 2.5dB. For all further investigations with QPSK transmission, we stopped the LISS algorithm after finding 8 full length candidates, to assess the performance of a detector having acceptable complexity. If we base our L-value computation solely on these 8 full length candidates, we cannot guarantee the stack to contain a hypothesis (bit is +1) and counterhypothesis (bit is −1) for each possible bit position. To avoid infinite L-values, it is therefore necessary to clip the corresponding soft outputs (we chose a clipping level of ±4). A performance degradation of roughly 2dB is incurred in this setup of the LISS detector. Applying path augmentation of the incomplete stack entries improves performance by almost 1.5dB – the waterfall region is now around 3.2dB. As stated before, the main problem of this strategy is that we have a rather high number of paths that need to be extended and therefore a high computational complexity.

0

8 Cand./path−augm. 8 Cand./Aux+path−augm. 8 Cand./Noise+path−augm.

11

No. of Nodes →

1/3 augmented 1/10 augmented 1/20 augmented 1 Path augmented

−1

10

−2

10

−3

10

−4

10

6

6.2

6.4

6.6

6.8

7

E /N [dB] → b

7.2

7.4

7.6

7.8

0

Fig. 5. Bit error rate for a 16-QAM system with 96 full length candidates and different numbers of path augmentations.

setup is presented in Figure 6. The single path augmentation curve is also plotted for reference. This curve approaches T x − 1 = 3 augmentations with increasing SNR. However, using the 1/20 partial path augmentation we could reduce the augmentation complexity from 300 augmented nodes to 15 – a dramatic reduction in complexity without any significant loss in performance. We thus consider a combination of the noise term and partial path augmentation as the most promising approach in LISS MIMO detection, in terms of the performance-complexity trade-off.

13 12

10

BER →

To reduce the stack size we therefore have to include the bias term during the tree search. For the bias term based on the auxiliary stack, we used a stack size of 256 and always extended all nodes as proposed in [3]. The simulation results in Figure 3 show that this very accurate estimation of ln p(y) leads to a significant performance degradation. The explanation for this result is that the search tree is narrowed “too much” (cf. the results in Figure 4). Even extending all incomplete paths does not yield sufficient information to calculate accurate soft outputs for certain bit values. The second option for bias term calculation is the proposed noise term. Combined with a partial path augmentation of only 1/3 of all incomplete paths, this approach leads only to a slight performance degradation of around 0.2 dB. It is obviously a far more attractive approach. Without path augmentation, using the bias term even results in a small performance improvement which appears to be a beneficial side-effect of the more directed search.

10 9 8 7 6

140 1/3 augmented 1/10 augmented 1/20 augmented 1 Path augmented

5

2.5

3

3.5

Eb/N0 [dB] →

4

4.5

5

Fig. 4. Number of extended nodes during the tree search, corresponding to Figure 3.

The influence of the different bias terms on the tree search, in terms of the number of extended nodes, is depicted in Figure 4. Interestingly, for the auxiliary stack version this figure is almost independent of the SNR, which would be advantageous for a real-time implementation of the LISS algorithm. However, the observed performance degradation is not justifiable. Using the noise term, we could achieve a complexity reduction of more than 12%. To assess the potential complexity reduction by using only partial path augmentation, we chose a scenario of 16-QAM transmission using 96 full length candidates. Figure 5 shows the performance of the LISS detector using path augmentation of different fractions of the incomplete stack entries. It is easily seen that it is sufficient to extend only 1/20 of all incomplete paths to retain the original performance. Extending only a single path results in a performance loss of roughly 0.5 dB. Again, we cannot completely forbear from doing the path augmentation, since we need the soft entries in the stack to always ensure a reliable counter hypothesis. The total number of path augmentations for the 16-QAM

No. of Path augmentations →

120

4 2

100

80

60

40

20

0 4

Fig. 6.

5

6

7

Eb/N0 [dB] →

8

9

10

Number of augmented paths, corresponding to Figure 5

A parameter not considered yet is the number of full length candidates. A performance comparison for a 16-QAM system is shown in Figure 7. Here one can see the slight performance loss between a full complexity setup, where we did not use any bias approximation and augmented all incomplete paths, and a reduced complexity setup including the noise term and a partial augmentation of 1/3. With the help of the noise term we succeeded in speeding up the tree search by more than 20% (compared to 12% for the QPSK case). But we still have a quite large number of path augmentations, which can be reduced as show in Figure 5.

0

10

ACKNOWLEDGMENT This work was supported by the German ministry of research and education within the project Wireless Gigabit with advanced multimedia support (WIGWAM) under grant 01 BU 370.

−1

10

−2

BER →

10

R EFERENCES −3

10

−4

10

96 Cand. full Complexity 96 Cand. reduced Complexity 160 Cand. full Complexity 160 Cand. reduced Complexity 5

5.5

6

6.5

Eb/N0 [dB] →

7

7.5

8

Fig. 7. Simulation results of a 16-QAM LISS receiver depending on the number of full length candidates and different complexity stages.

V. C ONCLUSIONS In this paper, we presented an iterative equalization system for multiple antenna systems. For the detection we used a ListSequential-Detector (LISS) employing path augmentation to improve the accuracy of its soft output. In order to reduce the computational complexity, we extended the LISS by a bias term based either on an auxiliary stack or on the consideration of the receiver noise. Our performance evaluations showed that the second option, the noise term, is a far more attractive option, speeding up the tree search by more than 20% (for 16-QAM transmission in a 4 × 4 MIMO system) at a negligible performance loss and implementation complexity. Furthermore, we showed that extending only a few incomplete paths with the best metric to full length and removing all other shortened paths from the stack reduces the complexity of path augmentation drastically without any significant loss in performance. A combination of the proposed noise term and partial path augmentation hence offers a very attractive tradeoff between performance and implementation complexity for list sequential iterative MIMO detection.

[1] S. B¨aro, J. Hagenauer and M. Witzke, Iterative Detection of MIMO Transmission Using a List-Sequential (LISS) Detector, Proceedings of the IEEE International Conference on Communications (ICC’03), vol. 4, pp. 2653-2657, May 2003. [2] J. Hagenauer, E. Offer and L. Papke, Iterative Decoding of Binary Block and Convolutional Codes, IEEE Transactions on Information Theory, vol. 42, pp. 429-445, Mar. 1996. [3] J. Hagenauer and C. Kuhn, Turbo Equalization for Channels with High Memory using a List-Sequential (LISS) Equalizer, Proceedings of the International Symposium on Turbo Codes, ENST de Bretagne, 2003. [4] 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. [5] J. L. Massey, Variable-Length Codes and the Fano Metric, IEEE Transactions on Information Theory, vol. 18, pp. 196-198, Jan. 1972. [6] P. Robertson, E. Villebrun and P. Hoeher, A comparison of optimal and suboptimal MAP decoding algorithms operating in the log domain, Proceedings of the IEEE International Conference on Communications (ICC’95), pp. 1009-1013, Jun. 1995. [7] D. W¨ubben, J. Rinas and R. B¨ohnke and V. K¨uhn and K. D. Kammeyer, Efficient Algorithm for Detecting Layered Space-Time Codes, 4th International ITG Conference on Source and Channel Coding, Jan. 2002.