Sequence Estimation and Per Survivor Processing

In this Section we summarize the development of the MLSE algorithm for a fast fading Gauss-Markov channel model. Given prior information on the sequence distribution, the corresponding MAP estimator is a straightforward extension (e.g. [14]).

For the Gauss Markov model under consideration here, $f({\bf h}_k\vert{\bf h}_{k-1})$ is Gaussian with mean ${\bf d} + \alpha {\bf h}_{k-1}$ and covariance $\bf C$. $f( {\bf H} )$ can be written as

$$f({\bf H}) = \prod_{k=1}^n f({\bf h}_k\vert{\bf h}_{k-1}) .$$ (6)

To simplify expressions, we assume below that $\bf d$ is zero. We also assume that the initial channel coefficient vector ${\bf h}_0$ is known (e.g. estimated from a previous data block). Substituting (2) and (6) into (4), we obtain

 

$$f({\bf r}\vert{\bf A}) E[f({\bf r}\vert{\bf H},{\bf A})]$$ =

$$\int_{{\bf H}} f({\bf r}\vert{\bf H},{\bf A}) f({\bf H }) d{\bf H }$$ =

$$\doteq \int_{{\bf H}}\left( \prod_{k=1}^{n} e^{ - \frac {{\vert r_k-{\bf... ...igma}^{2} } } \right) \prod_{k=1}^n f({\bf h}_{k}\vert{\bf h}_{k-1}) d {\bf H}.$$ (7)

We can marginalize over the channel coefficient distribution, integrating step by step as shown in [8]. After the integration over all of the channel coefficients, we have the likelihood function

$$f({\bf r}\vert{\bf A}) \doteq \prod_{k=1}^n e^{{{\bf q}_k}^{H} {\bf G}_k {\bf q}_k} \vert{\bf G}_k\vert ,$$ (8)

where the ${\bf q}_k$ and ${\bf G}_k$; $k=1,2, \cdots , n$ are given as

 

$${\bf {G}}_1 \left[ \frac {{\bf a}_1^* {\bf a}_1^T} {\sigma^2} + (1 + {\vert\alpha\vert}^2){\bf C}^{-1} \right]^{-1}$$ =

$${\bf {q}}_1 \frac {r_1 {\bf a}_1^* } {\sigma^2}+ \alpha {\bf C}^{-1} {\bf h}_0$$ = (9)

 

$${\bf {G}}_k \left[ \frac {{\bf a}_k^* {\bf a}_k^T} {\sigma^2} + {\bf C}^{-1} ... ...( {\bf C}^{-1} - {\bf C}^{-1} {\bf {G}}_{k-1} {\bf C}^{-1} \right) \right]^{-1}$$ =

$${\bf {q}}_k \frac {r_k {\bf a}_k^* } {\sigma^2} + \alpha {\bf C}^{-1} {\bf {G}}_{k-1} {\bf {q}}_{k-1} ~ ~ ~ ~ ~ k=2,...,n-1 ,$$ = (10)

and

 

$${\bf G}_n \left[ \frac {{\bf a}_n^*{\bf a}_n^T} {\sigma^2} + {\bf C}^{-1} -\vert\alpha\vert^2 {\bf C}^{-1} {\bf {G}}_{n-1} {\bf C}^{-1} \right]^{-1}$$ =

$${\bf q}_n \frac {r_n{\bf a}_n^*} {\sigma^2} + \alpha {\bf C}^{-1} {\bf {G}}_{n-1} {\bf {q}}_{n-1} .$$ = (11)

If we take the negative natural logarithm of (8), we will obtain the time-recursive form of the cost function:

$$- \log f({\bf r}\vert{\bf A}) \doteq - \sum_{k=1}^n \left[{{... ..._k}^{H} {\bf G}_k {\bf q}_k}+\log \vert{\bf G}_k\vert \right].$$ (12)

From the expressions for ${\bf G}_k$ and ${\bf q}_k$, we see that the transition costs of the Viterbi algorithm depend on all of the previous states. So the standard Viterbi algorithm can not be optimally applied here. Optimum results can be obtained by exhaustive search. Alternatively, computationally feasible suboptimum algorithms can be considered. Here we describe a suboptimum algorithm which employs the generalized Viterbi algorithm (GVA) [10] to prune possible data sequences. Considering a trellis formulation, at each state of each stage we keep $L \geq 1$ survivor paths (i.e. surviving hypothesized sequences). For each survivor, the ${\bf q}_k$ and ${\bf G}_k$required for the incremental cost are computed. (Since for each survivor path the ${\bf G}_k$ and ${\bf q}_k$ are computed from the sequence associated with that path, we can interpret this as data-aided estimation of the incremental cost corresponding to the particular path, so this algorithm is effectively a form of PSP [9].) At time n the sequence estimate corresponds to the best surviving path. As L increases, the PSP algorithm results will approach the optimum. Simulations in [8] show that this approach results in effective algorithms for ML (or MAP) sequence estimation over unknown, fast time-varying channels for reasonably small values of L. We have found that $L \leq 3$is typically adequate.