Make your paper interactiveCreate

Text from the interactive explanation

Near-Capacity Turbo Trellis Coded Modulation Design Based on EXIT Charts and Union Bounds

Soon Xin Ng, Osamah Rashed Alamri, Yonghui Li, Jörg Kliewer, Lajos Hanzo

Original paper

An interactive reading of a turbo-coding paper

How close can a phone signal get to Shannon’s limit when the airwaves fade?

In 1948 Claude Shannon proved that a message needs a minimum amount of energy per bit to get through reliably. For a fading radio channel carrying 2 bits in every transmitted symbol, that minimum is 5.38 dB . The authors designed codes that decode within a fraction of a decibel of it, by watching a tunnel.

Soon Xin Ng, Osamah Rashed Alamri, Yonghui Li, Jörg Kliewer, Lajos Hanzo · “Near-Capacity Turbo Trellis Coded Modulation Design Based on EXIT Charts and Union Bounds” · IEEE Transactions on Communications 56(12): 2030–2039, 2008 · doi:10.1109/TCOMM.2008.06039522

What arrives

The 12,288-bit picture as the receiver currently reads it. Straight off the air it is speckled with errors; every decoder turn repairs some. Wrong pixels flash coral.

Slide toward the limit. Where does the tunnel close?

Receiving a block…

Ring (8PSK): each glowing dot is one received symbol, pulled off its point by fading and noise; coral = deep fade.

Chart : x = what decoder 1 is told, y = what it tells back (bits per symbol, 0 to 2). decoder 1 decoder 2 (mirrored) tunnel. The steps are the live exchange; reaching the top-right corner means decoded.

The live decoding is a simplified re-implementation running in your browser of the paper’s 8PSK scheme (code [13 2 4]8, I/Q shuffling on, up to 16 exchanges); each block carries 12,288 message bits. The curves are this re-implementation’s predictions, not the paper’s figures.

1 · The wall

A minimum energy for every bit

Every radio receiver hears hiss: random electrical noise. What matters is how much energy the transmitter spends on each bit of the message compared with that noise, a ratio engineers write as Eb/N0. It is measured in decibels (dB), a logarithmic scale: 10 dB is ten times the energy, 3 dB is about double, 1 dB is about 26 % more.

Shannon’s capacity theorem draws a wall on this scale. For a given channel and a given number of message bits per transmitted symbol, there is an Eb/N0 below which no code, however clever, can deliver the message reliably. Above it, a good enough code can in principle make errors as rare as you like. The question of the paper is how close a practical code can get to that wall.

Feel the decibel

×1.26 the energy per bit (26 % more)

So the 0.09 dB gap you will meet at the end of this story is only about 2 % more energy.

Where the wall stands

Capacity limits ω for uncorrelated Rayleigh fading at the throughput of each scheme, as listed in Table I of the paper.

More bits per symbol means the points of the constellation are packed tighter, so each bit needs more energy. This page focuses on 8PSK (8 points on a circle, 2 message bits per symbol), the scheme our browser simulation re-implements.

2 · A channel that fades

Shuffle I and Q

Each 8PSK symbol is one of 8 points on a circle. Its horizontal coordinate is called the in-phase part (I), its vertical one the quadrature part (Q). On a mobile link, reflections from buildings add up and cancel as you move, so the received strength dips at random, sometimes almost to nothing. This is Rayleigh fading ; the paper assumes it changes independently from one symbol to the next.

Normally a fade shrinks both coordinates of a symbol together and drags the point toward the centre, where it is easily confused with its neighbours. The paper’s IQ-TTCM uses two separate shufflers (“IQ interleavers”) for the I and Q values before transmission, undone at the receiver. A deep fade now usually hits only one coordinate of a symbol; the point slides toward an axis but keeps half of its information.

I amplitude · Q amplitude · bars below the line = deep fade (coral). Simulated at 5.9 dB; illustrative.

Predict, then test

Same code, same energy ( 5.9 dB ). Will shuffling I and Q separately change whether the message gets through?

No blocks sent yet.

Each block: 6,144 message bits (3,072 symbols), code [13 2 4]8, up to 16 exchanges, fresh noise and fades. Computed now by the simplified in-browser re-implementation.

Why it works: for a decoding error to survive, the noise must fool the decoder on several symbols at once. With I and Q faded independently, a would-be error has to survive roughly twice as many independent fades, so it becomes much rarer. Engineers call this extra diversity. Earlier work by two of the authors [15] showed that IQ-interleaved TTCM has a lower error floor than conventional TTCM, which is why the paper’s designs use separate I and Q interleavers. In our re-implementation, shuffling also lets the decoders converge with less energy: the EXIT tunnel of [13 2 4]8 opens at ≈5.4 dB with I/Q shuffling, but only at ≈6.1 dB without.

3 · Hiding a parity bit

The encoder you can rewire

Error correction needs spare bits. Sending them separately would cost bandwidth, so trellis coded modulation (TCM) hides them in the constellation instead: 2 message bits only need 4 symbols, but 8PSK offers 8 points, so each symbol can carry one extra parity bit . The parity bit comes from a tiny circuit with memory (Fig. 3 of the paper): three delay cells D , adders that add modulo 2 (1+1=0), and connection “taps”.

The taps are written as octal numbers, G = [gr g1 g2]8: gr says where the parity bit is fed back, g1 and g2 where Bit 1 and Bit 2 enter. Toggle the two middle feedback taps and watch the code change.

G = [13 2 4]₈ gr = 1011₂

Rolling trellis: the 8 possible memory states (rows) over the last steps; the bright path is the encoder’s actual route.

Because the parity bit depends on the past, only certain sequences of points are legal. Noise that knocks one symbol onto a wrong point usually produces an illegal sequence, which the decoder can detect and repair by searching the trellis for the closest legal path. The circuit is recursive (the parity is fed back) and systematic (the message bits are sent as they are), as required for the turbo scheme that follows.

4 · Two decoders that gossip

Turbo exchange

Turbo TCM (TTCM, Fig. 1 of the paper) uses two identical encoders. The upper one reads the message in order; the lower one reads it after a shuffler (an odd–even symbol interleaver). A selector sends the upper encoder’s symbol at odd times and the lower encoder’s at even times, so every message bit is transmitted exactly once and each encoder’s parity bits are sent only half of the time.

At the receiver, two decoders take turns. Each one combines what the channel told it with what the other decoder believes, and passes on only its extrinsic information: what it learned from its own code that the other decoder did not already tell it. Passing back the other’s own opinion would create an echo chamber; passing only news lets beliefs sharpen with every exchange.

Belief board: 32 symbols of the current hero block

decoder 1 belief · decoder 2 belief · four bars = the four possible 2-bit values (00, 01, 10, 11) · white tick = what was really sent · coral outline = currently decided wrongly

–

5 · The tunnel

Reading an EXIT chart

An EXIT chart (EXtrinsic Information Transfer, Section IV of the paper) tracks the gossip as numbers. On the horizontal axis: how much decoder 1 is told, measured in bits per symbol from 0 (nothing) to 2 (everything, since each symbol carries 2 message bits). On the vertical axis: how much it tells back. Decoder 2 is identical, so its curve is drawn mirrored across the diagonal.

x: what decoder 1 is told · y: what it tells back (bits per symbol, 0–2)

Live turns. Each amber dot is one actual turn of decoder 1 in a live block: told x bits, it hands back y.

The staircase. An amber vertical move is decoder 1 talking; a cyan horizontal move is decoder 2 answering.

The prediction. The curves are computed in advance from the code alone. If they leave an open tunnel, the staircase can squeeze through to the top-right corner (all 2 bits known: the message is decoded). If they touch, it gets stuck.

–

Predict: at what signal level does the tunnel pinch shut?

Move the marker to your guess for code [13 2 4]8 with I/Q shuffling, then reveal the computed answer.

Not revealed yet.

Why live blocks wander: the predicted tunnel describes very long messages. A finite block can drift off the predicted path right at the edge, which is why our 12,288-bit blocks often need a few tenths of a decibel more than the curves suggest. The same effect appears in the paper: its simulated threshold (5.47 dB with 100,000-symbol blocks) sits above its EXIT estimate (5.17 dB), and longer blocks came closer to the estimates (Fig. 11). The authors also note a modelling limit: the charts assume a decoder’s extrinsic and systematic information are independent, which is only approximately true.

After each turn a decoder holds, for every symbol k, a probability e(uk(i)) for each of the M = 4 possible 2-bit values. Its information is the maximum, log2M = 2 bits, minus the average uncertainty (entropy) of those probabilities:

IE = log2(M) − (1/N) Σk Σi e(uk(i)) log2 e(uk(i))

A decoder that is sure of every symbol scores 2 bits; one that has no idea scores 0. The paper uses this formula because it is far cheaper than estimating histograms of decoder outputs. Our in-browser re-implementation measures every point and step in this chart with exactly this formula.

6 · Be the code designer

Choosing the wiring: the paper’s contribution

The old rule. Earlier TTCM designs (Robertson and Wörz [4]) picked the component code with the largest “punctured minimal distance”: the code whose two most similar legal sequences are furthest apart. The authors found that this guaranteed the best gain only in the first decoding iteration, not convergence at the lowest signal level. For 8-state 8PSK, the old rule gives [11 2 4]8.

The new rule. Choose the code whose EXIT tunnel opens at the lowest Eb/N0, while checking that its error floor (Section 7) stays acceptable. To keep the search small, each data bit is wired to its own adder (g1 = 2, g2 = 4), and only the feedback taps gr are searched.

Tunnels computed by our in-browser re-implementation (I/Q shuffling on). The four wirings shown are those whose feedback uses all three memory cells; the other half of the 8 feedback patterns degenerate to fewer states.

The authors’ search (Fig. 4), run on our curves

Start at γ = ω + 0.5 dB = 5.88 dB with step κ = 0.2 dB. Test every candidate’s EXIT chart at γ. If more than one tunnel is open, keep only those and step down; if none is open, step up; halve κ whenever a value would be revisited; stop when exactly one survives.

Press the button to start the search.

Sequence quoted from Section V-A of the paper: three −0.2 dB steps, then +0.1 and +0.05 dB, ending with an estimated convergence threshold of 10.03 dB.

7 · The second danger

Error floors and the union bound

A code can fail in two ways. If the tunnel is closed, the decoders never converge: no “waterfall” in the error rate at all. But even with an open tunnel, rare look-alike sequences can still be confused, and the error rate stops plunging and flattens into an error floor . The paper estimates that floor with a union bound (Section III): it adds up the chances of every way of mistaking one legal sequence for another.

On a fading channel, the chance of one such mistake is governed by two numbers (Eq. 4): ΔH , how many symbols differ (each must be wrecked by its own fade, so ΔH sets the slope), and ΔP , the product of the squared distances between the differing points (the offset).

Error-event builder

With pairing on, the lower encoder sees the same wrong message bits in shuffled order and adds its own differing symbols; here we let it add as many as the upper one, with the same distances (illustrative). Hamming distances add and product distances multiply (Eqs. 6–7).

–

–

Eq. (4): P ≤ C(2ΔH−1, ΔH−1) · (Es/N0)−ΔH · ΔP−1, with Es/N0 = 2·Eb/N0 for 2 bits per symbol and 8PSK squared distances 0.586, 2, 3.414, 4 for points 45°, 90°, 135°, 180° apart.

Waterfalls and floors: the paper’s results

Redrawn from Fig. 11 of Ng et al. (2008): IQ-TTCM with 10,000-symbol blocks, the authors’ Monte-Carlo simulations (solid, markers) and their truncated union bounds (dotted); vertical lines are the capacity limits. Values read from the plot are approximate.

8 · What they found

Distance to the wall, code by code

Table I of the paper lists the best code found for each modulation and number of states, with two thresholds: the EXIT-chart estimate and the actual Eb/N0 at which the authors’ simulations reached a bit error rate of about 10−4 with 100,000-symbol blocks.

Values from Table I of Ng et al. (2008); distances are relative to each scheme’s capacity limit. All thresholds are from the authors’ computer simulations, not over-the-air measurements.

1 dB better than the old choice

For 8PSK, IQ-TTCM with the proposed [13 2 4]8 performs about 1 dB better than with [11 2 4]8 adopted from [4]. Our re-implementation’s tunnels show the same ranking: –.

The old rule can pick a dead end

For 16QAM, the code chosen by the punctured-distance criterion, [21 2 4 10]8, could not fully converge because its EXIT tunnel was closed; the proposed [27 2 4 10]8 performed significantly better (Fig. 8).

Within 1 dB

Most of the designed codes perform within 1.0 dB of channel capacity; the starred ones within 0.5 dB.

The bound predicts the floor

The truncated TTCM union bound matches the error floors of the simulated IQ-TTCM schemes well (Figs. 7–10), so floors can be estimated without long simulations.

Longer blocks help

With longer blocks (Fig. 11) the floors drop and convergence moves closer to the EXIT-chart estimates.

Limitation

The EXIT charts assume that a decoder’s extrinsic and systematic information are independent. This has limited validity, so charts and real decoding trajectories show some mismatch, though the authors found the charts accurate enough for code design.

9 · Back to the wall

Two percent from Shannon

For 8PSK carrying 2 bits per symbol over a fading channel, Shannon’s limit is 5.38 dB . The paper’s design, [13 2 4]8 with I/Q shuffling, reached a bit error rate of about 10−4 at 5.47 dB in the authors’ simulations with 100,000-symbol blocks: about 2 % more energy than the theoretical minimum.

The same live transmission at 5.47 dB . With our short 12,288-bit blocks the decoders sometimes squeeze through and sometimes stall at the pinch: this is the very edge of the tunnel.

–

What next. The authors suggest the same recipe, choosing component codes by the lowest SNR at which the EXIT tunnel opens and checking the floor with a union bound, could design symbol-interleaved space-time TTCM for multiple-antenna (MIMO) systems.

Source

Soon Xin Ng, Osamah Rashed Alamri, Yonghui Li, Jörg Kliewer and Lajos Hanzo, “Near-Capacity Turbo Trellis Coded Modulation Design Based on EXIT Charts and Union Bounds,” IEEE Transactions on Communications, vol. 56, no. 12, pp. 2030–2039, December 2008. doi:10.1109/TCOMM.2008.06039522 · author copy (PDF)

Interactive simulations are a simplified re-implementation of the 8PSK scheme running in your browser; paper figures are redrawn from published values (Fig. 11 and Table I), and plot read-offs are approximate. Reference numbers in brackets follow the paper’s bibliography.

Topics in this iPaper

Engineering
Bandwidth efficient parallel-concatenated Turbo Trellis Coded Modulation (TTCM) schemes were designed for communicating over uncorrelated Rayleigh fading channels.

Abstract, page 2030

Computer science
the symbol-based extrinsic mutual information can be computed using Eq. (20) at a considerably lower complexity

Section IV, page 2034

Mathematics
The union bound of the average BER of a coding scheme communicating over uncorrelated Rayleigh fading channels can be derived

Section III, page 2032

turbo codes
Turbo Trellis Coded Modulation (TTCM) [4] is a more recent joint coding and modulation scheme that has a structure similar to that of the family of power-efficient binary turbo codes

Section I, page 2030

trellis coded modulation
A TCM encoder consists of a Recursive Systematic Convolutional (RSC) encoder and a signal mapper.

Section II, page 2031

extrinsic information transfer charts
the prime design criterion is to find a constituent TCM code, where the corresponding EXIT charts exhibit an open tunnel at the lowest possible SNR value

Section V, page 2034

rayleigh fading
designed for communicating over uncorrelated Rayleigh fading channels

Abstract, page 2030

union bound
A symbol-based union bound was derived for analysing the error floor of the proposed TTCM schemes.

Abstract, page 2030

quadrature amplitude modulation
capacity-approaching IQ-TTCM schemes in the context of 8PSK, 16QAM, 32QAM and 64QAM modulation schemes

Abstract, page 2030

channel coding
We have designed capacity-approaching TTCM schemes by performing a search for good constituent TCM component codes

Section VII, page 2038

Near-Capacity Turbo Trellis Coded Modulation Design Based on EXIT Charts and Union Bounds — Interactive explanation | iPaper.ai