Make your paper interactiveCreate

Text from the interactive explanation

Binary BCH Turbo Coding Performance: Union Bound and Simulation Results

S. X. Ng, T. H. Liew, L-L. Yang, L. Hanzo

Original paper

Noise on a radio link can do something sneaky: instead of turning your message into gibberish, it can turn it into a different valid message. The receiver then decodes it as if nothing were wrong.

In 2000, a team at the University of Southampton built turbo codes from tiny 7‑bit codes. They counted every one of these look‑alikes and showed how they decide when and how a code fails.

Their goal: shape a code’s error curve to suit each application. Can you see where the errors come from?

1 · Bits in a storm

2 · A 7‑bit safety net

3 · Two guards & a shuffle

4 · The look‑alike census

5 · Who fools the decoder?

6 · A bigger shuffle

7 · Snip the parity

8 · Designing failure

Live simulation in your browser. The bright core is the 40‑bit message that was sent. Each dot is one of the 65,535 other valid messages of the paper’s TBCH(7,4,3) code (16 data bits, 4×4 shuffle). A dot’s distance from the core is the number of bits in which it differs; the angle carries no meaning. Sparks are noisy received signals. A beam means the decoder was fooled into choosing that look‑alike. Notice the dark gap: no valid message lies within 5 bit-flips of the one sent.

Bits in a storm

Digital radio sends each bit as a pulse: here a 0 goes out as +1 and a 1 as −1 (this is called binary phase‑shift keying, BPSK). On the way, random noise is added, like static on a radio. The receiver only checks which side of zero each pulse lands on. If noise pushes a pulse across zero, that bit arrives flipped .

The slider sets Eb/N0 : the energy in each bit compared with the strength of the noise, measured in decibels (dB). Every +3 dB doubles the bit’s energy relative to the noise.

What the receiver sees

Top: the stream of pulses (thin line = sent, dots = received). Amber dots crossed zero and were misread. Bottom: every received value piles up into two bell curves, one for each kind of bit.

Each bell curve shows where received values of one kind of bit land. The part of the “+1” bell that spills below zero, and the part of the “−1” bell that spills above it, are exactly the misread bits. That tail area is given by the complementary error function, erfc. It shrinks extremely fast as the bells move apart: the tail of a bell curve falls off like exp(−x²). The same function sits at the heart of the paper’s main formula (chapter 5).

A 7‑bit safety net

To survive noise, add a little redundancy. The paper’s building block is the BCH(7,4,3) code . It takes 4 data bits and appends 3 parity bits , giving a 7‑bit codeword . Each parity bit is chosen so that its circle below holds an even number of 1s. Of the 128 possible 7‑bit patterns, only 16 are valid codewords.

Any two valid codewords differ in at least 3 positions. The number of positions in which two words differ is their Hamming distance , and 3 is this code’s minimum distance: the “3” in (7,4,3).

The same kind of map as the opening scene, for this small code. Around any codeword sit 7 look‑alikes at distance 3 , 7 at distance 4 and 1 at distance 7. One flip leaves you nearer the truth than any look‑alike. Two flips can land you nearer a look‑alike, and the decoder confidently picks it.

The code is systematic : the 4 data bits are sent unchanged, followed by the 3 parity bits. Its rate is 4/7: 4 of every 7 bits carry data. BCH codes (after Bose, Chaudhuri and Hocquenghem) are a family of error-correcting codes. The (7,4,3) member used here is built from the polynomial g(x) = 1 + x + x³ and is the same as the famous Hamming (7,4) code. In this layout, parity p1 checks d1, d2, d3; p2 checks d2, d3, d4; p3 checks d1, d2, d4.

Two guards and a shuffle

A turbo code runs two of these encoders at once. Encoder 1 protects the data in its original order. Encoder 2 protects the same data after an interleaver has shuffled it. The data is sent once, followed by the parity bits from both encoders (paper Fig. 1).

Our animated redrawing of the encoder schematic in the paper’s Fig. 1.

The block interleaver

Data is written into a grid row by row: each row is one 4‑bit word for encoder 1, whose 3 parity bits sit to its right. It is read out column by column and regrouped into 4‑bit words for encoder 2. The coloured tags mark which encoder‑2 word each bit joins; its 3 parity bits sit below.

Game: find the closest look‑alike

Because the code is linear, the look‑alikes around any message are arranged just like the valid messages around the all‑zero one. So: tap data cells to build a valid message with as few 1s as possible (but not none). Its number of 1s, called its weight , is its distance from the all‑zero message.

Start with a single 1. Then try two 1s in the same row on the 4×2 grid: do they also share an encoder‑2 word? Equations (1)–(3) of the paper: PL = (N/k)·2(n−k), L = N + PL, R = k/(2n−k) = 4/10. The rate does not depend on the grid size.

The look‑alike census

Your browser can list every valid message: all 216 = 65,536 of them for the 4×4 grid. Counting how many sit at each distance gives the code’s weight distribution (the paper’s Fig. 3). The closest non-zero distance is the free distance dfree .

Compare 4×2 with 4×4 . Both have rate 0.40, but with the bigger shuffle the empty zone grows from 4 to 5 bit-flips. The paper reports the same: dfree = 4 versus 5, with “2 and 9” at that distance, counting data‑bit errors. On the 4×4 grid, ring 7 holds 19 look‑alikes, more than rings 5 and 6 combined.

The paper’s recipe for a good turbo code

High free distance.

Low “density” at the free distance: few look‑alikes there.

The first few rings also sparsely populated.

Which look‑alikes fool the decoder?

The decoder is fooled when noise pushes the received signal closer to a look‑alike than to the original. For a look‑alike d bits away, the chance is a bell‑curve tail, the same erfc as in the storm. It shrinks fast as d grows. But the far rings hold vastly more look‑alikes. The union bound (paper Eq. 5) adds up every ring’s contribution:

Wd : data-bit errors carried by all look‑alikes at distance d. N : data bits per block. R : code rate. erfc(…) : the chance noise reaches that far. BER is the bit error rate. It is an upper bound because it treats every look‑alike as the only rival; at weak signals, where rivals overlap, it overestimates.

Each ring’s share of the bound

Bars: share predicted by each term of Eq. 5 at this signal strength. White ticks: share of data-bit errors actually measured in the live simulation below.

Live test: the ideal decoder

The union bound assumes the best possible decoder, which picks the most likely valid message. Your browser runs exactly that decoder: for every noisy block it scores all 65,536 candidate messages (256 for 4×2) and picks the best. It runs at the Eb/N0 set by the slider above, and its results appear as green points on the chart.

At low signal strengths the measurements sit below the bound. As the signal grows they converge on it, as the paper’s own simulations did (its Figs. 2 and 5).

A bigger shuffle

Same 7‑bit encoders, same rate 0.40; only the grid grows from 4×1 to 4×4. A bigger shuffle spreads each data bit’s two guards further apart, pushing the closest look‑alikes outward. The paper found (its Fig. 5) that this always helps, but each step helps less .

Signal needed for 1 error in 10,000 bits

Values computed here from the union bound of each code’s full weight distribution. Without any code, BPSK needs 8.40 dB.

Snip the parity

Sending 24 parity bits with 16 data bits is costly. Puncturing deletes some parity bits according to a fixed pattern. That raises the rate, so more of each transmission is data, at a price in errors (paper Fig. 6). The paper’s striking point (Fig. 7): even at the same rate, which bits you delete matters enormously.

Tap any encoder‑1 or encoder‑2 parity cell to keep or delete it. Data cells glowing amber show the weakest link : one of the closest look‑alikes that remain.

Tip: a data bit is in danger when both of its guards lost most of their parity. Watch the amber weakest link and give it back a parity bit that covers it, then take one away somewhere else.

Designing how a code fails

Below, two codes run side by side through the same noise level. One uses the paper’s best rate‑4/7 pattern; the other uses your pattern from chapter 7. Each is decoded by the ideal decoder, live. Their galaxies show why they fail differently.

Paper’s best: 45BA5C

Your design: FFFFFF

What the authors found

A few rings decide everything. Most errors come from the first few terms of the weight distribution. At weak signals the more crowded rings a little further out dominate; at strong signals the closest ring takes over.

A bigger interleaver moves the closest look‑alikes outward (free distance 4 → 5 from 4×2 to 4×4) at no cost in rate, with diminishing returns.

Puncturing trades errors for rate, and the pattern matters. At rate 4/7 the best pattern, 45BA5C, keeps every look‑alike at least 3 bits away with the fewest damaging ones (W = 20). Our union-bound calculation puts it over 3 dB ahead of a poor pattern such as E381C7 at an error rate of 10−4.

The look‑alike count predicts performance. The union bound computed from it agreed with simulations at higher signal strengths.

What this brings closer

The authors concluded that there is “a certain grade of freedom in shaping the weight distribution and hence the BER curve”. Choosing the interleaver and the puncturing pattern moves look‑alikes between rings, and that reshapes when and how a code fails.

They called for further study toward a more “bespoke” BER curve design for specific applications. A companion paper at the same conference investigated an adaptive‑rate transceiver as one example.

Everything here used short codes and small interleavers, which the authors chose to keep complexity low. Their findings apply to other component codes, interleavers and puncturers.

S. X. Ng, T. H. Liew, L‑L. Yang and L. Hanzo, “Binary BCH Turbo Coding Performance: Union Bound and Simulation Results,” Proceedings of the IEEE 51st Vehicular Technology Conference (VTC 2000‑Spring), Tokyo, Japan, 15–18 May 2000, pp. 849–853. University of Southampton. Read the paper (PDF).

All charts are recomputed in your browser from the paper’s equations (1)–(5) and its code definitions: BCH(7,4,3) component codes, a row‑in, column‑out block interleaver and the hexadecimal puncturing patterns of its Section 7 and Table 1. The paper’s figures are not reproduced; the encoder schematic is our own redrawing. These calculations reproduce the paper’s reported free distances (4 for N = 4×2, 5 for N = 4×4) and the dmin = 3, W = 20 of pattern 45BA5C.

Live simulations are our own Monte Carlo runs of an exhaustive maximum‑likelihood decoder over BPSK with additive white Gaussian noise. They are not the authors’ data, and their counts carry statistical scatter. The galaxies and the three-circle diagram illustrate real code structure; in the galaxies only the distance from the centre is meaningful.

Topics in this iPaper

Engineering
The bit error rate (BER) performance of the turbo codes is evaluated using binary phase shift keying (BPSK) over additive white Gaussian noise (AWGN) channels.

Abstract, page 1 (p. 849)

Computer science
Turbo codes achieve a performance close to the Shannon limit

Section 1 Introduction, page 1 (p. 849)

turbo codes
Turbo codes using short binary BCH codes as component codes are investigated.

Abstract, page 1 (p. 849)

bose chaudhuri hocquenghem codes
Two systematic BCH encoders are used as component codes with an interleaver placed before the second BCH encoder.

Section 2 Turbo Encoder, page 1 (p. 849)

weight distribution
the weight-distribution of turbo codes and its effects on the bit error probability was evaluated

Introduction (right column), page 1 (p. 849)

union bound
The union bounds were computed from Eq.(5).

Section 6 Effects of Block Interleaving, page 3 (p. 851)

puncturing
Puncturing is an often-used technique invoked, in order for a code to achieve the desired code rate.

Section 7.1 Puncturing Patterns, page 4 (p. 852)

interleaving
In this contribution block interleaving was invoked.

Section 2 Turbo Encoder, page 1 (p. 849)

Binary BCH Turbo Coding Performance: Union Bound and Simulation Results — Interactive explanation | iPaper.ai