Channels and equalisation

Echoes in a channel smear each symbol onto its neighbours. Below, many short pieces of a received signal are drawn on top of each other: watch the open gap at their centre, the eye, shut as the echoes come in.

Echoes close the eye

In “Pulses that keep out of each other’s way” of Digital modulation and OFDM (27.5), raised-cosine pulses carried symbols without disturbing each other at the symbol times. The receiver read every symbol cleanly. That page then met a channel with echoes, and OFDM dodged them by splitting the signal into many slow subcarriers.

This page keeps one fast stream of symbols. It undoes the echoes with a filter at the receiver instead, and I build that filter three ways.

Several paths at once

A radio signal bounces off buildings and hills, so it reaches the receiver along several paths, each with its own delay and strength. This is called multipath. A long cable smears pulses in a similar way, because it weakens high frequencies more than low ones.

As in “Same rule, different h” of Discrete convolution (5.2), the channel is an impulse response. Mine has three paths, one symbol apart, for $k$ = 0, 1 and 2:

The index $k$ counts symbols, not samples: the channel is written at symbol spacing. The strongest path, 1, is the main path. The two weaker paths are echoes: one arrives a symbol early, with 0.4, and one a symbol late, with 0.7.

Each symbol now arrives three times, and the extra copies land on its neighbours’ symbol times. In 27.5 that leak was called intersymbol interference, ISI for short. There the pulse shape could cause it; here the channel does.

The link on this page

Every signal on this page is synthetic, made from stated formulas and the site’s seeded generator. I draw 6000 numbers between 0 and 1 with seed 332. A draw of at least 0.5 is the bit 1, and 3024 of the 6000 bits are 1. Each bit becomes a symbol $A_m$: +1 for a 1, −1 for a 0.

Each symbol is sent as 27.5’s raised-cosine pulse, with roll-off $\alpha=0.35$ and 8 samples per symbol. The channel adds the three paths, 0, 8 and 16 samples late.

The receiver takes one sample per symbol, at the symbol times. The raised cosine is a Nyquist pulse, so at those times each pulse contributes only its own symbol (27.5). What remains is the channel at symbol spacing, plus noise:

Here $m$ counts symbols, and $v[m]$ is white noise of standard deviation $\sigma_v$, from 6000 Gaussian draws with seed 3320. The sample $x[m]$ carries mostly $A_{m-1}$, through the main path, so the receiver decides that symbol from it. It decides +1 when $x[m]$ is above 0 and −1 when it is below; 0 is the threshold.

How strong is the noise? The symbols are uncorrelated with power 1, so without noise $x[m]$ has power $0.4^2+1^2+0.7^2=1.65$ on average. I set the noise 25 dB below that, a signal-to-noise ratio (SNR) of 25 dB: $\sigma_v^2=1.65\times10^{-2.5}=0.00522$, so $\sigma_v=0.0722$. These draws measure 25.0 dB.

I skip the first 200 symbols, while the equalisers further down are still filling up, and count decisions on the other 5800.

The eye diagram

How can I see whether the symbols can still be told apart? Cut the received waveform into pieces two symbols long, each centred on a symbol time. Then draw all the pieces on top of each other. This overlay is an eye diagram.

It works like laying many people’s handwriting of the same word on top of each other. When they agree, the letters stay clear; when each is pushed about, they smudge into a blur.

With no interference, every piece passes through +1 or −1 at its centre. The pieces leave an open gap around 0 there, shaped like an eye. The centre is the decision instant.

How open is the eye? Leave the noise out. The worst case at the decision instant is the main path with every echo pushing the other way. So I define the worst-case opening as the main path’s tap minus the sum of the other taps’ sizes, all divided by the main path’s tap.

An opening of 1 means no interference. At 0 or below the eye is shut: some pattern of neighbours puts a sample on the wrong side of the threshold, even without noise. For this channel the echoes add to 1.1, more than the main path, and the worst-case opening is $(1-0.4-0.7)/1=-0.10$.

Now look again at the picture at the top of the page. Its traces leave out the noise, so the eye shows the interference alone. They are the 200 traces around the first 200 decisions I count, those at $m$ = 200 to 399. The dots at the centre are the noisy decision samples, so you can see what the noise adds.

The picture’s eye opening measures the eye it draws. Among its 200 traces it finds the one that comes closest to the threshold at the decision instant, or crosses it furthest. It takes that sample, counted positive on its own symbol’s side, and divides by the main path’s tap. A drawn eye is never less open than the worst case. Watch it as the sent traces turn into received ones: it shuts, at an opening of −0.10.

Notice the end frame: 1307 of 5800 decisions are wrong, 22.5 %. Every one of them comes from the same pattern. Both neighbours had the other sign from the symbol being decided, so the noise-free sample was −0.1 instead of +1. The worked example below counts them.

Opening the eye again

An equaliser is a filter after the channel that tries to undo it. Mine is an FIR filter with 15 taps $h_0,\dots,h_{14}$, one per symbol:

Its output should be a symbol sent a few symbols earlier. That wait, a whole number of symbols, is the decision delay. I explain below why it is needed.

The channel and the equaliser in a row act as one filter, their convolution $h_\text{ch}*h$, with 17 taps (5.2). Both openings follow the same rules as before, with the main tap at the decision delay. A perfect equaliser would turn it into a single spike: 1 at the decision delay and 0 everywhere else.

Zero-forcing: undo the channel, ignore the noise

The first idea forgets the noise. Zero-forcing picks the 15 taps that bring $h_\text{ch}*h$ as close as possible to that spike: the sum of the squared misses over all 17 taps is as small as it can be. The equaliser has only 15 taps, so it cannot hit all 17 targets exactly.

With unlimited taps and a long enough delay it could come as close as you like, and the eye would open fully. But look at what undoing the channel asks for. Its gain, the size of its frequency response $H_\text{ch}(e^{j\Omega})$, runs from 2.100 at $\Omega=0$ down to 0.098 at $\Omega=0.940\pi$, 20.2 dB down.

To undo the channel there, an equaliser needs a gain of about $1/0.098=10.2$. The noise is white, so it has as much power at $0.940\pi$ as anywhere, and the equaliser amplifies it too. This is noise enhancement.

MMSE: the Wiener filter

The second idea is the one from “The best FIR filter, from correlations” in The Wiener filter (26.2). The MMSE equaliser is the Wiener filter whose desired signal is the symbol one decision delay back. MMSE stands for minimum mean-square error. For a delay of 10 symbols, $d_\text{des}[m]=A_{m-10}$, and the error $e[m]=A_{m-10}-y[m]$ holds interference and noise together.

The best taps $\mathbf{h}_\text{MMSE}$ solve the Wiener–Hopf equations $\mathbf{R}\mathbf{h}_\text{MMSE}=\mathbf{r}$. Both sides come straight from the channel. The symbols are uncorrelated with power 1, and the noise is white and uncorrelated with them, so

That is $1.65+\sigma_v^2$ at lag 0, $0.4+0.7=1.1$ at lags ±1, $0.4\cdot0.7=0.28$ at lags ±2, and 0 beyond. The right side has the entries $\mathbb{E}\{A_{m-10}\,{x[m-k]}\}={h_\text{ch}[10-k]}$: 0.7, 1 and 0.4 at $k$ = 8, 9 and 10, and 0 elsewhere.

One more fact links the two. Set $\sigma_v^2$ to 0, and these are exactly the equations of the zero-forcing fit for the same delay. Setting the slope of its sum of squared misses to 0 along each tap gives the channel’s own autocorrelation on the left and the same right side. So the two equalisers differ only by the noise power on the diagonal of $\mathbf{R}$.

That small term changes the answer where the channel is weak. Allow unlimited taps, reaching into the future as well as the past. At a frequency where the channel’s gain is $\lvert H_\text{ch}\rvert$, the MMSE equaliser then has the first gain below, and zero-forcing the second:

Where the channel is strong, $\lvert H_\text{ch}\rvert^2$ is far above $\sigma_v^2$ and the two agree. At $0.940\pi$, $\lvert H_\text{ch}\rvert^2=0.0096$ is close to $\sigma_v^2=0.0052$, and MMSE’s gain is 6.61 instead of 10.2. It backs off where undoing the channel would mostly amplify noise. This is the Wiener deconvolution that 26.2 mentioned at the end.

LMS: learn the taps from known symbols

Both equalisers so far need the channel. A receiver does not know it in advance, and a moving phone’s channel keeps changing. So the transmitter starts with symbols the receiver already knows, a training sequence.

The receiver then runs the LMS update of “Downhill, one noisy step at a time” in Adaptive filters: LMS (26.3), counted in symbols, with the known $A_{m-12}$ as the desired signal, for a delay of 12:

Here $\mathbf{x}_m=(x[m],\dots,{x[m-14]})^\top$ is the tap-input vector, newest first, and the taps $\mathbf{h}_m$ start at 0. I use the step size $\mu=0.03$, train on the first 3000 known symbols, then freeze the taps. That step is well inside 26.3’s limit $2/\lambda_\text{max}$, which is 0.46 for this $\mathbf{R}$.

What each equaliser gets

Each equaliser needs a decision delay, from 0 to 16 symbols. Here the mean-square error is the average of the squared miss between $y[m]$ and the symbol it should equal, 26.2’s $J$ measured on the record. Each equaliser uses the delay that gives it the smallest mean-square error: 8 for zero-forcing and 10 for MMSE, over symbols 200 to 5999, and 12 for LMS, over symbols 3000 to 5999.

The next picture runs the same link as the first, with the noise unchanged, through each equaliser in turn.

Watch the dots at the centre of the eye as the clip moves from zero-forcing to MMSE: they gather tighter, and the 6 wrong decisions go to none.

Notice the noise. The sum of the squared taps is the factor by which white noise power grows, and I call it the noise power gain: 13.755 for zero-forcing and 9.119 for MMSE. Its square root is the noise gain of Simple smoothing filters (18.2), which scales the noise’s RMS: 3.71 and 3.02.

Why zero-forcing makes more errors

In the worst case zero-forcing opens the eye further, 0.65 against MMSE’s 0.60. Yet it makes 6 wrong decisions in 5800, about 0.1 %, and MMSE none. The noise explains it.

At the frequency where the channel is weakest, the zero-forcing taps amplify by 8.48 and the MMSE taps by 6.7. Over all frequencies, the noise that comes out has power $0.00522\times13.755=0.0718$ after zero-forcing and $0.00522\times9.119=0.0476$ after MMSE.

In theory the mean-square error is the noise plus what the taps leave undone. Zero-forcing leaves 0.0165, for a total of 0.088. MMSE leaves 0.0188, a little more, for a total of 0.066. The record measures 0.091 and 0.066.

So MMSE gives up a little of the worst-case opening, and a little of the undoing, for much less noise. Its main tap in $h_\text{ch}*h$ is also 0.934 rather than 1: it shrinks its answer slightly, which costs less than the noise it saves.

Why, then, is MMSE’s drawn eye the wider one, 0.723 against 0.681? The worst case needs every neighbour to push the wrong way at once. With 17 taps in $h_\text{ch}*h$ there are $2^{16}=65536$ patterns of the other symbols, and 200 traces show only a few of them. So every drawn eye is wider than its worst case, LMS’s too at 0.545 against 0.46, and in these 200 traces MMSE’s is the widest.

How close LMS gets

LMS gets close to the MMSE answer from known symbols alone. Over symbols 3000 to 5999 its error is 0.069, against MMSE’s 0.066 over the same symbols, and both make no wrong decisions. The bottom of LMS’s own bowl is the MMSE solution for its delay, 12. Its taps differ from those by a vector of length 0.39, while those taps have length 3.02.

Where is the gap? Almost all of it, 95.7 % of its square, lies along one direction of 26.3’s error bowl: the shallowest, with $\lambda_\text{min}=0.016$. Its time constant, $1/(\mu\lambda_\text{min})$, is 2080 symbols, so 3000 symbols of training leave LMS still on its way.

That direction is cheap, though, because the bowl is nearly flat along it. In theory the whole gap adds 0.0039 to the error; on the record the difference is 0.0028. The eigenvalue spread is 270 here, against 4 in 26.3. Along the shallow direction the taps alternate in sign, a pattern at the top of the band, where the channel is weak.

Why the decision has to wait

Why not decide at once, at the main path’s delay of 1 symbol? Forced to do that, even the MMSE equaliser leaves 387 of 5800 decisions wrong. At its delay of 10 it leaves none.

The reason is in “Undoing a filter” of Minimum phase (17.2). Only a minimum-phase filter has an inverse that is both causal and stable. This channel’s zeros are $-1.25\pm0.433j$, at distance 1.32 from the origin: both outside the unit circle, so the channel is maximum phase.

Its stable inverse needs samples from the future. Waiting provides them. With a delay of 10, each symbol is decided from received samples up to 10 symbol times after it was sent, and the 15 taps can hold enough of that inverse.

Worked example

1. The worst-case opening. The main path is 1, the early echo 0.4 and the late echo 0.7. The opening is $(1-0.4-0.7)/1=-0.10$, so the eye is shut.

2. Why a quarter of the decisions fail. Take a symbol of +1. Its noise-free sample is $1\pm0.4\pm0.7$, one of 2.1, 0.7, 1.3 and −0.1. Only the last, both echoes against it, is on the wrong side. With random symbols that pattern comes once in four; here it came 1433 times in 5800.

The noise rescues such a sample only when it is above 0.1, which is 1.38 standard deviations. Gaussian noise does that with probability 0.083. So about $1433\times0.917=1314$ stay wrong, against the 1307 counted. The next worst sample, 0.7, is 9.7 standard deviations from the threshold.

3. The MMSE equations. With $\sigma_v^2=0.00522$, $\mathbf{R}$ has $1.65522$ on its diagonal, 1.1 next to it and 0.28 next to that. For a delay of 10, $\mathbf{r}$ is 0 except for 0.7, 1 and 0.4 in entries 8, 9 and 10, counting from 0.

4. The noise out. White noise of power $\sigma_v^2$ through taps $h_k$ comes out with power $\sigma_v^2\sum_kh_k^2$. Zero-forcing gives $0.00522\times13.755=0.0718$, and MMSE $0.00522\times9.119=0.0476$. As RMS values these are 0.268 and 0.218, against 0.0722 going in.

Where you’ll meet this

Dial-up modems were among the first to use adaptive equalisers. R. W. Lucky’s automatic equaliser of 1965 used the zero-forcing idea, and later modems trained theirs with LMS. Gigabit Ethernet over copper cable runs an adaptive equaliser on each of its four pairs.

GSM phones learn the channel from a known training sequence of 26 bits in the middle of every burst. Hard-disk read channels equalise the read-back signal before deciding each bit. DSL modems use discrete multitone, the form of OFDM named in 27.5. They still shorten the line’s response with an equaliser, so that their cyclic prefix covers it.

Digital modulation and OFDM (27.5) avoids long equalisers: its cyclic prefix turns the channel into one gain per subcarrier. A single-carrier link pays for its simpler signal with the equaliser on this page.

My LMS stopped learning after the training sequence. Real receivers carry on, using their own decisions as the desired signal; this is called decision-directed adaptation. It lets the equaliser follow a channel that changes, as long as most decisions are right.

I left out several designs. A fractionally spaced equaliser has taps closer than one symbol apart. A decision-feedback equaliser subtracts the interference of symbols it has already decided. Blind equalisers learn without a training sequence, and real links add error-correcting codes.

For more, see Proakis and Salehi, Digital Communications (5th ed., 2008), chapters 9 and 10; Haykin and Moher, Introduction to Analog and Digital Communications (2nd ed., 2007), chapter 8; and Johnson, Sethares and Klein, Software Receiver Design (2011), chapter 13.

Reference card