Ferkans — Interactive Telecom Tutor

Learning the Channel on the Fly

All equalizers discussed so far assume the channel $h[n]$ is known. In practice, the channel must be estimated and may change over time (e.g., due to mobility). Adaptive equalization algorithms update the equalizer coefficients iteratively, either using a known training sequence or operating in decision-directed mode where past symbol decisions serve as the reference. The two dominant algorithms are the least mean squares (LMS) algorithm, prized for its simplicity, and the recursive least squares (RLS) algorithm, which converges faster at the cost of higher complexity.

Definition:
Least Mean Squares (LMS) Algorithm

The LMS algorithm is a stochastic gradient descent method that adapts the equalizer tap vector $\mathbf{w}$ to minimise $E[|e_k|^2]$ , where $e_k = d_k - \mathbf{w}^H \mathbf{y}_k$ is the error between the desired output $d_k$ and the equalizer output.

At each time step $k$ :

Compute the output: $\hat{a}_k = \mathbf{w}_k^H \mathbf{y}_k$
Compute the error: $e_k = d_k - \hat{a}_k$
Update the taps: $\mathbf{w}_{k+1} = \mathbf{w}_k + \mu\, e_k^*\, \mathbf{y}_k$

where $\mu > 0$ is the step size and $d_k$ is either the known training symbol (training mode) or the hard decision $\text{dec}(\hat{a}_k)$ (decision-directed mode).

The LMS algorithm has complexity $O(N_f)$ per symbol --- one multiply-accumulate per tap.

The LMS update is the instantaneous (sample-by-sample) approximation to the steepest descent algorithm $\mathbf{w}_{k+1} = \mathbf{w}_k + \mu (\mathbf{p} - \mathbf{R}_{yy} \mathbf{w}_k)$ . The noise in the gradient estimate is the price paid for avoiding the computation of $\mathbf{R}_{yy}$ and $\mathbf{p}$ .

Definition:
Recursive Least Squares (RLS) Algorithm

The RLS algorithm minimises the exponentially weighted least-squares cost

$J_k(\mathbf{w}) = \sum_{i=0}^{k} \lambda^{k-i}\, |d_i - \mathbf{w}^H \mathbf{y}_i|^2$

where $0 < \lambda \leq 1$ is the forgetting factor.

The RLS update is:

Gain vector: $\mathbf{k}_k = \frac{\mathbf{P}_{k-1}\, \mathbf{y}_k}{\lambda + \mathbf{y}_k^H \mathbf{P}_{k-1}\, \mathbf{y}_k}$
Error: $e_k = d_k - \mathbf{w}_{k-1}^H \mathbf{y}_k$
Tap update: $\mathbf{w}_k = \mathbf{w}_{k-1} + \mathbf{k}_k\, e_k^*$
Inverse correlation update: $\mathbf{P}_k = \frac{1}{\lambda}(\mathbf{P}_{k-1} - \mathbf{k}_k\, \mathbf{y}_k^H\, \mathbf{P}_{k-1})$

RLS converges much faster than LMS (independent of the eigenvalue spread of $\mathbf{R}_{yy}$ ) but has complexity $O(N_f^2)$ per symbol.

Definition:
Training Mode

In training mode, the receiver knows the transmitted symbols $d_k = a_k$ during a preamble or midamble period. The adaptive algorithm uses these known symbols as the desired output to converge the equalizer taps. Training mode provides reliable convergence but reduces throughput because the training symbols carry no user data.

Definition:
Decision-Directed Mode

In decision-directed (DD) mode, the desired output is set to the hard decision on the equalizer output: $d_k = \text{dec}(\hat{a}_k)$ . This allows the equalizer to track slow channel variations without interrupting data transmission.

Decision-directed mode works reliably only when the BER is already low (typically below $10^{-2}$ ), because incorrect decisions corrupt the adaptation. In practice, the equalizer first converges using a training sequence, then switches to decision-directed mode for tracking.

LMS Adaptive Equalizer

Complexity: Time:

O(N_f)

per symbol (one complex multiply-accumulate per tap). Memory:

O(N_f)

for the tap vector and input buffer.

Input: Received samples

\{y_k\}

, training symbols

\{d_k\}

, step size

\mu

, filter length

N_f

Output: Equalizer coefficients

\mathbf{w}

, symbol estimates

\{\hat{a}_k\}

1. Initialise:

\mathbf{w}_0 = [0, \ldots, 0, 1, 0, \ldots, 0]^T

(centre-spike or all-zeros)

2. For

k = 0, 1, 2, \ldots

:

a. Form input vector:

\mathbf{y}_k = [y_k, y_{k-1}, \ldots, y_{k-N_f+1}]^T

b. Compute output:

\hat{a}_k = \mathbf{w}_k^H \mathbf{y}_k

c. Determine desired signal:

- Training mode:

d_k = a_k

(known)

- Decision-directed:

d_k = \text{dec}(\hat{a}_k)

d. Compute error:

e_k = d_k - \hat{a}_k

e. Update taps:

\mathbf{w}_{k+1} = \mathbf{w}_k + \mu\, e_k^*\, \mathbf{y}_k

3. Output final

\mathbf{w}

and decisions

\{\hat{a}_k\}

.

The step size $\mu$ must satisfy $0 < \mu < 2/(\lambda_{\max} N_f)$ for convergence, where $\lambda_{\max}$ is the largest eigenvalue of $\mathbf{R}_{yy}$ . A common rule of thumb is $\mu \approx 1/(5 N_f \sigma_y^2)$ .

LMS Convergence Animation

Watch the LMS algorithm converge in real time. The animation shows the equalizer tap values and the MSE learning curve as a function of iteration number. Adjust the step size to see the trade-off between convergence speed and steady-state misadjustment.

Parameters

Step size

\mu

0.02

Channel tap

h_1

0.5

Channel tap

h_2

0

SNR (dB)20

Equalizer taps

N_f

11

Example: LMS Step Size and Convergence

An LMS equalizer with $N_f = 7$ taps operates on a channel with autocorrelation eigenvalues $\lambda_{\max} = 3.2$ and $\lambda_{\min} = 0.4$ .

(a) Determine the range of stable step sizes.

(b) Compute the convergence time constant for $\mu = 0.05$ .

(c) Compute the steady-state excess MSE (misadjustment).

Solution

Stability bound

For convergence, the step size must satisfy

$0 < \mu < \frac{2}{\text{tr}(\mathbf{R}_{yy})}$

A sufficient condition is $\mu < 2 / (N_f \lambda_{\max}) = 2 / (7 \times 3.2) = 0.0893$ .

So $\mu \in (0, 0.0893)$ for guaranteed stability.

Convergence time constant

The LMS convergence time constant for the slowest mode is

$\tau_{\max} = \frac{1}{2\mu\, \lambda_{\min}} = \frac{1}{2 \times 0.05 \times 0.4} = 25 \text{ iterations}$

The fastest mode converges in

$\tau_{\min} = \frac{1}{2\mu\, \lambda_{\max}} = \frac{1}{2 \times 0.05 \times 3.2} = 3.125 \text{ iterations}$

The eigenvalue spread $\chi = \lambda_{\max}/\lambda_{\min} = 8$ determines how much slower the slowest mode is compared to the fastest.

Misadjustment

The misadjustment (excess MSE relative to $J_{\min}$ ) is approximately

$\mathcal{M} = \frac{\mu}{2} \text{tr}(\mathbf{R}_{yy}) \approx \frac{\mu\, N_f}{2} \cdot \bar{\lambda}$

where $\bar{\lambda}$ is the average eigenvalue. With $\bar{\lambda} \approx (\lambda_{\max} + \lambda_{\min})/2 = 1.8$ :

$\mathcal{M} \approx \frac{0.05 \times 7 \times 1.8}{2} = 0.315$

So the steady-state MSE is about 31.5% above the Wiener optimum --- this is the price of using a stochastic gradient. $\blacksquare$

Quick Check

What is the main advantage of the RLS algorithm over LMS for adaptive equalization?

RLS has lower computational complexity per symbol

RLS converges faster, especially for channels with large eigenvalue spread

RLS achieves lower steady-state MSE

RLS does not require a training sequence

Correction:

RLS converges faster, especially for channels with large eigenvalue spread

Correct. RLS convergence rate is independent of the eigenvalue spread of $\mathbf{R}_{yy}$ , while LMS convergence slows down proportionally to $\lambda_{\max}/\lambda_{\min}$ .

Common Mistake: Choosing the LMS Step Size

Mistake:

Setting the LMS step size $\mu$ too large for fast convergence without checking the stability condition, causing the algorithm to diverge.

Correction:

The step size must satisfy $\mu < 2 / \text{tr}(\mathbf{R}_{yy})$ . A practical guideline is $\mu \approx 1 / (5 N_f \sigma_y^2)$ , which provides a good trade-off between convergence speed and misadjustment. If convergence is too slow, increase $\mu$ cautiously and monitor the learning curve. If the MSE starts increasing, $\mu$ is too large.

Common Mistake: Premature Switch to Decision-Directed Mode

Mistake:

Switching from training mode to decision-directed mode before the equalizer has sufficiently converged, causing the equalizer to lock onto a wrong solution or diverge.

Correction:

Decision-directed mode requires the BER to be below approximately $10^{-2}$ for reliable adaptation. Always verify that the training-mode MSE has converged to a sufficiently low level before switching. In fast-fading environments, use longer training sequences or pilot-aided adaptation rather than pure decision-directed tracking.

LMS vs. RLS Adaptive Algorithms

Property	LMS	RLS
Complexity per symbol	$O(N_f)$	$O(N_f^2)$
Convergence speed	Depends on eigenvalue spread $\chi$	Independent of $\chi$
Tuning parameter	Step size $\mu$	Forgetting factor $\lambda$
Tracking ability	Good for slow variations	Better for fast variations
Numerical stability	Very stable	Can suffer from finite-precision issues
Memory	$O(N_f)$	$O(N_f^2)$ (stores $\mathbf{P}_k$ )
Typical application	Low-complexity receivers	Fast convergence scenarios

Deeper Treatment in the FSI Book

The Wiener filter and its adaptive implementations (LMS, RLS) are covered in depth in the FSI book (Chapters 6–8), which treats the general LMMSE estimation framework, Kalman filtering for time-varying channels, and convergence analysis with full measure-theoretic rigor. The FSP book (Chapter 8) covers the spectral factorisation underlying the MMSE-DFE from the stochastic processes perspective.

Least Mean Squares (LMS)

A stochastic gradient descent algorithm that adapts filter coefficients by updating in the direction of the instantaneous gradient of the squared error. Complexity is $O(N_f)$ per sample.

Recursive Least Squares (RLS)

An adaptive filtering algorithm that recursively minimises a weighted least-squares cost function. Converges faster than LMS but requires $O(N_f^2)$ operations per sample.

Training Mode

An operating mode of an adaptive equalizer in which known pilot/training symbols are used as the desired output for coefficient adaptation.

Related: Decision-Directed Mode

Decision-Directed Mode

An operating mode of an adaptive equalizer in which the hard decision on the equalizer output is used as the desired signal for continued adaptation, enabling tracking without training overhead.

Related: Training Mode

Adaptive Equalization

Learning the Channel on the Fly

Definition: Least Mean Squares (LMS) Algorithm

Definition: Recursive Least Squares (RLS) Algorithm

Definition: Training Mode

Definition: Decision-Directed Mode

LMS Adaptive Equalizer

LMS Convergence Animation

Parameters

Example: LMS Step Size and Convergence

Stability bound

Convergence time constant

Misadjustment

Quick Check

Common Mistake: Choosing the LMS Step Size

Common Mistake: Premature Switch to Decision-Directed Mode

LMS vs. RLS Adaptive Algorithms

Deeper Treatment in the FSI Book

Least Mean Squares (LMS)

Recursive Least Squares (RLS)

Training Mode

Decision-Directed Mode

Definition:
Least Mean Squares (LMS) Algorithm

Definition:
Recursive Least Squares (RLS) Algorithm

Definition:
Training Mode

Definition:
Decision-Directed Mode