Ferkans — Interactive Telecom Tutor

Optimal Detection on ISI Channels

Both linear equalizers and the DFE make decisions symbol by symbol, without considering the entire received sequence. The optimal approach --- maximum-likelihood sequence estimation (MLSE) --- searches over all possible transmitted sequences to find the one most likely to have produced the observed output. MLSE is implemented efficiently using the Viterbi algorithm, the same dynamic programming technique used for convolutional code decoding. The price is exponential complexity in channel memory.

Definition:
Maximum-Likelihood Sequence Estimation (MLSE)

Given a received sequence $\mathbf{y} = [y_0, y_1, \ldots, y_{K-1}]$ and channel $h[n],\; n = 0, \ldots, L$ , the MLSE detector finds

$\hat{\mathbf{a}} = \arg\max_{\mathbf{a}} \; p(\mathbf{y} \mid \mathbf{a})$

For AWGN, this is equivalent to minimising the sequence metric:

$\hat{\mathbf{a}} = \arg\min_{\mathbf{a}} \sum_{k=0}^{K-1} \left| y_k - \sum_{n=0}^{L} h[n]\, a_{k-n} \right|^2$

The minimisation is over all $M^K$ possible symbol sequences, where $M$ is the alphabet size and $K$ is the sequence length. Direct enumeration is infeasible, but the ISI channel has a trellis structure that enables the Viterbi algorithm.

,

Definition:
Branch Metric

In the Viterbi algorithm for MLSE, the branch metric at time $k$ for a state transition from $\sigma_{k-1}$ to $\sigma_k$ (corresponding to input symbol $a_k$ ) is

$\lambda_k(\sigma_{k-1}, \sigma_k) = \left| y_k - \sum_{n=0}^{L} h[n]\, a_{k-n} \right|^2$

The path metric is the cumulative sum of branch metrics along a path through the trellis. The Viterbi algorithm retains only the minimum-metric survivor path entering each state.

Theorem: Optimality of MLSE

For an ISI channel with AWGN, the MLSE detector minimises the sequence error probability $P(\hat{\mathbf{a}} \neq \mathbf{a})$ among all detectors. The pairwise error probability between sequences $\mathbf{a}$ and $\mathbf{a}'$ is

$P(\mathbf{a} \to \mathbf{a}') = Q\!\left( \sqrt{\frac{\|\mathbf{H}(\mathbf{a} - \mathbf{a}')\|^2}{2 N_0}}\right)$

where $\mathbf{H}$ is the channel convolution matrix. The performance is dominated by the minimum distance between valid sequences:

$d_{\text{free}}^2 = \min_{\mathbf{a} \neq \mathbf{a}'} \|\mathbf{H}(\mathbf{a} - \mathbf{a}')\|^2$

MLSE is optimal because it considers the entire received sequence jointly, exploiting the trellis structure of ISI. The Viterbi algorithm makes this tractable by discarding suboptimal paths at each trellis stage. The free distance $d_{\text{free}}$ plays the same role as $d_{\min}$ in memoryless detection --- it determines the asymptotic BER.

Proof

Likelihood function

Since $\eta_k \sim \mathcal{N}(0, N_0)$ i.i.d., the log-likelihood is

$\ln p(\mathbf{y} \mid \mathbf{a}) = -\frac{1}{N_0} \sum_k |y_k - (\mathbf{h} * \mathbf{a})_k|^2 + \text{const.}$

Maximising this is equivalent to minimising the squared Euclidean distance $\|\mathbf{y} - \mathbf{H}\mathbf{a}\|^2$ .

Pairwise error probability

The detector chooses $\mathbf{a}'$ over $\mathbf{a}$ when $\|\mathbf{y} - \mathbf{H}\mathbf{a}'\|^2 < \|\mathbf{y} - \mathbf{H}\mathbf{a}\|^2$ . Since $\mathbf{y} = \mathbf{H}\mathbf{a} + \boldsymbol{\eta}$ , this simplifies to a Gaussian tail probability:

$P(\mathbf{a} \to \mathbf{a}') = Q\!\left( \frac{\|\mathbf{H}\mathbf{e}\|}{2\sigma}\right) = Q\!\left(\sqrt{\frac{\|\mathbf{H}\mathbf{e}\|^2}{2N_0}}\right)$

where $\mathbf{e} = \mathbf{a} - \mathbf{a}'$ is the error sequence. $\blacksquare$

Viterbi Algorithm for ISI Channels

Complexity: Time:

O(K \cdot M^L \cdot M)

per sequence, where

M^L

is the number of trellis states and

M

transitions leave each state. Space:

O(K \cdot M^L)

for storing survivor paths. For binary signalling (

M = 2

) and channel memory

L

:

2^L

states,

2^{L+1}

branch metric computations per time step.

Input: Received sequence

\{y_0, \ldots, y_{K-1}\}

, channel taps

h[0], \ldots, h[L]

, alphabet

\mathcal{A}

Output: ML sequence estimate

\hat{\mathbf{a}}

1. Initialise: Set path metric

\Gamma_0(\sigma) = 0

for the all-zero state,

\infty

otherwise.

2. For

k = 0, 1, \ldots, K-1

:

a. For each state

\sigma_k

(representing

(a_{k-1}, \ldots, a_{k-L})

):

- For each predecessor state

\sigma_{k-1}

with transition symbol

a_k

:

\lambda_k = \left| y_k - \sum_{n=0}^{L} h[n]\, a_{k-n} \right|^2

\Gamma_k^{\text{cand}}(\sigma_k) = \Gamma_{k-1}(\sigma_{k-1}) + \lambda_k

- Select survivor:

\Gamma_k(\sigma_k) = \min_{\sigma_{k-1}} \Gamma_k^{\text{cand}}(\sigma_k)

- Store the predecessor that achieved the minimum (survivor path).

3. Traceback: Starting from the state with minimum

\Gamma_{K-1}(\sigma)

, trace back through the stored predecessors to recover

\hat{\mathbf{a}}

.

The complexity grows exponentially with channel memory $L$ . For $L > 5$ -- $6$ , the Viterbi algorithm becomes impractical and reduced-state approaches (RSSE, delayed decision-feedback sequence estimation) are needed.

,

BER Comparison: Linear EQ vs. DFE vs. MLSE

Compare the BER performance of four receivers on a multipath channel: no equalization, linear MMSE, MMSE-DFE, and MLSE. The matched-filter bound is shown as a reference.

Parameters

Channel tap

h_1

0.6

Channel tap

h_2

0

Modulation

Equalizer taps11

Viterbi Algorithm Step by Step

Watch the Viterbi algorithm process received samples on a 2-state ISI trellis. Survivor paths (green) are retained; suboptimal paths (red) are discarded at each stage.

The Viterbi algorithm retains one survivor per state, pruning the exponential search space to linear complexity per time step.

Example: MLSE via Viterbi on a Two-Tap Channel

Apply the Viterbi algorithm to detect the BPSK sequence transmitted over the channel $h = [1,\; 0.7]$ , given the received samples $\mathbf{y} = [0.8,\; 1.5,\; -0.4,\; -1.6]$ . Assume zero initial state and no noise.

Solution

Trellis structure

With $L = 1$ and BPSK ( $M = 2$ ), the trellis has $M^L = 2$ states: $S_0$ (previous symbol $= +1$ ) and $S_1$ (previous symbol $= -1$ ). Each state has 2 outgoing transitions.

Time $k = 0$

Starting from a known initial state (assume $a_{-1} = +1$ , so we start in $S_0$ ).

Transition to $S_0$ ( $a_0 = +1$ ): $y_0^{\text{pred}} = 1(+1) + 0.7(+1) = 1.7$ , $\lambda = |0.8 - 1.7|^2 = 0.81$
Transition to $S_1$ ( $a_0 = -1$ ): $y_0^{\text{pred}} = 1(-1) + 0.7(+1) = -0.3$ , $\lambda = |0.8 - (-0.3)|^2 = 1.21$

$\Gamma_0(S_0) = 0.81$ , $\Gamma_0(S_1) = 1.21$

Time $k = 1$

From $S_0$ ( $a_0 = +1$ ):

To $S_0$ ( $a_1 = +1$ ): $\lambda = |1.5 - 1.7|^2 = 0.04$ , $\Gamma = 0.81 + 0.04 = 0.85$
To $S_1$ ( $a_1 = -1$ ): $\lambda = |1.5 - (-0.3)|^2 = 3.24$ , $\Gamma = 0.81 + 3.24 = 4.05$

From $S_1$ ( $a_0 = -1$ ):

To $S_0$ ( $a_1 = +1$ ): $\lambda = |1.5 - 0.3|^2 = 1.44$ , $\Gamma = 1.21 + 1.44 = 2.65$
To $S_1$ ( $a_1 = -1$ ): $\lambda = |1.5 - (-1.7)|^2 = 10.24$ , $\Gamma = 1.21 + 10.24 = 11.45$

Survivors: $\Gamma_1(S_0) = 0.85$ (via $S_0$ ), $\Gamma_1(S_1) = 4.05$ (via $S_0$ )

Traceback and decision

Continuing similarly for $k = 2, 3$ and tracing back from the minimum final metric, the detected sequence is $\hat{\mathbf{a}} = [+1, +1, -1, -1]$ .

The Viterbi algorithm efficiently finds this without checking all $2^4 = 16$ possible sequences. $\blacksquare$

Quick Check

For a channel with memory $L = 4$ and 4-QAM modulation ( $M = 4$ ), how many trellis states does the Viterbi MLSE detector have?

$4^4 = 256$ states

$2^4 = 16$ states

$4 \times 4 = 16$ states

$4 + 4 = 8$ states

Correction:

4^4 = 256

states

Correct. The trellis state is defined by the previous $L = 4$ symbols, each from an alphabet of size $M = 4$ , giving $M^L = 4^4 = 256$ states.

Why This Matters: MLSE in GSM

The GSM cellular standard specifies a channel equalizer based on the Viterbi algorithm. The GSM channel is modelled with a typical memory of $L = 4$ -- $5$ symbol periods. With GMSK modulation (approximately binary), the trellis has $2^5 = 32$ states --- computationally feasible for a mobile handset. Each GSM burst includes a 26-bit training sequence (midamble) used to estimate the channel taps before running the Viterbi equalizer. This combination of training-based channel estimation and MLSE equalization was a key innovation that enabled reliable communication over the highly dispersive urban radio channel.

See full treatment in Chapter 14

Historical Note: Viterbi Algorithm

1967--1974

Andrew Viterbi published his algorithm in 1967 for decoding convolutional codes, but it was soon recognised as a general solution for maximum-likelihood detection on any system with a finite-state trellis representation. Forney (1972) showed that the ISI channel has a natural trellis structure and that the Viterbi algorithm provides MLSE. Ungerboeck (1974) combined this with adaptive channel estimation, creating the first practical MLSE receiver for data modems. The Viterbi algorithm remains one of the most widely used algorithms in communications, with applications in equalization, decoding, speech recognition, and bioinformatics.

⚠️Engineering Note

MLSE in Wireless Standards — Where It Works and Where It Fails

MLSE via the Viterbi algorithm has been deployed in real systems, but only when the state count is manageable:

GSM (2G): GMSK modulation ( $M \approx 2$ ), $L = 5$ gives $2^5 = 32$ states. Feasible on 1990s hardware. Every GSM phone contains a Viterbi equalizer.
EDGE (2.5G): 8-PSK ( $M = 8$ ), $L = 4$ gives $8^4 = 4096$ states. Reduced-state approaches (M-BCJR, DDFSE) are used to bring complexity to $\sim 128$ effective states.
3G WCDMA: Replaced equalization with RAKE receivers and later chip-level equalizers (linear/DFE), avoiding MLSE entirely.
4G LTE / 5G NR: OFDM eliminates the need for time-domain equalization. The only "equalization" is per-subcarrier MMSE.
Practical limit: $M^L \lesssim 256$ states is the rough boundary for real-time MLSE on current hardware. Beyond this, reduced-state or turbo equalization is required.

Practical Constraints

•
Real-time MLSE feasible for $M^L \lesssim 256$ trellis states
•
GSM: 32 states (GMSK, $L=5$ ); EDGE: reduced from 4096 to ~128 effective states
•
OFDM in 4G/5G eliminates the need for MLSE entirely

📋 Ref: GSM 05.05 (equalization), 3GPP TS 45.004 (EDGE)

Key Takeaway

MLSE is the optimal receiver for ISI channels but its complexity grows as $O(M^L)$ — exponential in channel memory. This makes it practical only for low-order modulation on short channels (e.g., GSM). For modern wideband systems, OFDM avoids the problem entirely by converting the frequency-selective channel into flat subchannels.

Maximum-Likelihood Sequence Estimation (MLSE)

An optimal detection strategy that finds the transmitted symbol sequence maximising the likelihood of the entire received sequence, implemented via the Viterbi algorithm on the channel trellis.

Viterbi Algorithm

A dynamic programming algorithm that finds the minimum-cost path through a trellis by retaining only one survivor path per state at each time step.

Branch Metric

The cost assigned to a single state transition in the Viterbi trellis, typically the squared Euclidean distance between the received sample and the predicted output for that transition.

Maximum-Likelihood Sequence Estimation