Figure 2.7: Factor graph for Markov model.
effective number of independent users/streams included in the discrete Markov model andQis the number of bits per symbol. Although this algorithm exploits the Markov structure of the system, the complexity of this detector often makes its implementation unfeasible and approximations must be used instead as will be discussed in chapter 3. For decoding of binary convolutional codes, the complexity per information bit scales as O r−12Nc
where ris the rate of the code and Nc is the constraint length. Typical real-life values for r and Nc
lead to a complexity which is usually implementable and no approximations are therefore required. If the target is not to minimize the information BER but FER, the Viterbi algorithm [Vit67] should be used instead, which again can be seen as a special case of the FBA. Some cellular systems of interest to this thesis use Turbo codes [BGT93] instead of convolutional codes, but these codes are constructed from convolutional codes and the FBA is therefore also used as a component in its decoding. Systems may also employ block codes like LDPC, Reed-Solomon or CRC codes or combinations of all these mentioned coding schemes. Such component codes may also employ the BP algorithm for decoding [MN97,EKM06], but this is outside the scope of this thesis.
Although only described here for iterative exchange of information in a disjoint detector and decoder setup commonly known as Turbo equalization, the Turbo principle is a general way of separating various components from each other such that inference in each component becomes manageable. For example, if the information bits originated from a source encoder, e.g. a voice codec, the Turbo principle could be extended to iterate not only between the detector and the decoder, but also include the source decoder in the iterations.
2.5 Summary
This chapter has introduced the signal model that is used throughout this the-sis. The model is quite general in the sense that it supports most of the features of interest in today’s coded multiuser MIMO systems operating in a multipath environment. For simplicity, the channel model is assumed to be block-fading,
but all methods presented throughout this thesis naturally generalize to a time-varying Gaussian state-space channel model, if desired. Furthermore, the fun-damental channel capacity along with the associated rate-diversity tradeoff has been introduced including a IQ-split system model capable of capturing any non-circular properties of the signals.
Next, the concept of representing the system by a factor graph is introduced along with the sum-product algorithm for computing marginals on such graphs.
As a generalization of this idea, the region graph is introduced along with a GBP algorithm for computing region marginals and methods for constructing various region graph approximations, namely the Bethe and Kikuchi approximations.
In addition, a heuristic method for helping GBP converge in otherwise non-convergent loopy region graphs is presented, but the drawback of this method is slower convergence.
To see how this can be used for disjoint detection and decoding, the now well-known Turbo principle is outlined. The exchange of marginals, called extrinsic information in the Turbo framework, is a direct result of the underlying Bethe approximation leading to a manageable complexity. Having established these methods for detection and decoding, the stage is now set for improving both the individual components of the Turbo scheme, but also going beyond the Turbo framework using more advanced graph approximations.
Chapter 3
Approximate Detection and Decoding
As optimal detection and decoding is most often infeasible due to the exponen-tially scaling complexity, this chapter describes various methods of approximate detection and decoding that has been investigated during the research study.
3.1 MMSE Detection and Subtractive Exten-sions
The MMSE detector is, as the name implies, designed to minimize the mean-squared error of the detected signal. The underlying idea of this is, that had the transmitted symbols been Gaussian instead of discrete, the MMSE detector would be optimal. This is a result of the optimality of processing first- and second-order statistics in linear Gaussian models with Gaussian noise, see e.g.
[Poo88].
Considering the model in (2.1)1, the starting point is to assume that the
trans-1Noise whitening will be automatically included in the result
mitted symbols are Gaussian and thus specify a prior on the symbols as
x∼ CN(µx,Σx) (3.1)
Using the traditional assumption that the transmitted symbols are i.i.d. with equal probability and unit power, the resulting prior hasµx=0N×1 andΣx= IN. However, if priors are in fact available as in the case of Turbo equalization, the MMSE detector will be able to exploit this extra information [TSK02].
Due to the fact that the Gaussian prior is conjugate2, the symbol posteriorxˆis also Gaussian, i.e.
ˆ
x∼ CN(µxˆ,Σxˆ) (3.2)
with covariance and mean easily found to be given by Σxˆ= HHΣ−1H+Σ−x1−1
µxˆ=Σxˆ HHΣ−1y+Σ−x1µx
=ΣxHH HΣxHH+Σ−1
(y−Hµx) +µx
(3.3)
As a result of the Gaussian assumption, the posterior mean µˆx is both the MAP and MMSE symbol estimate andΣxˆ describe the covariance around this estimate. As in [TSK02], marginals can be generated from this, but (3.3) pro-vides the sufficient statistics of the full posterior distribution and not only the marginals. In fact, the posterior for all detectors should posess a Markov3 struc-ture as the multipath channel results inHHHbeing a banded matrix. For this detector, the posterior will not only be Markov, but Gauss-Markov due to (3.2) andΣ−ˆx1 is therefore a banded matrix.
When used as a component in Turbo equalization, only posterior marginals are required as discussed in section 2.4 and it could therefore be argued that there is no need for the full posterior. However, when incorporating parameter estimation with detection and decoding, the full posterior may in fact be of use as discussed in section4.1.3.
If desired, other linear and non-linear detectors can be formulated based on this. For example, using Σ = σ2IM and letting σ2 → 0, the Zero-Forcing (ZF) solution is recovered. Another interesting option is to extend the above framework so as to provide subtractive interference cancelation schemes such as the MMSE-DFE with input priors and probabilistic output. Such schemes typically formulate the linear filtering of (3.3) as a forward and a backward filter and then subtract interference terms after some temporal delay, but may also operate across other dimensions, e.g. users in a multiuser scenario. Methods
2A conjugate prior results in a posterior of the same form as the prior
3Assuming the channel structure is not violated by the noise or prior