Make your paper interactiveCreate

Text from the interactive explanation

Self-Concatenated Code Design and its Application in Power-Efficient Cooperative Communications

Muhammad Fasih Uddin Butt, Soon Xin Ng, Lajos Hanzo

Original paper

At the fringe of a mobile cell, your phone's signal reaches the tower as a whisper buried in hiss. Can it still be heard perfectly — with a decoder simple enough for a pocket, and on less than half the power? This tutorial's answer begins with a code that argues with itself.

Live simulation running in your browser: a real encoder, a fading radio channel and the paper's self-concatenated decoder, freshly computed every frame — not a recording. Picture: 8,192 bits. Right panel: horizontal axis = hints going in, vertical = knowledge coming out (both from 0 to 1); the goal is the top-right corner.

Turn the whisper up or down

Your challenge: slide left to find the weakest signal that still gets the picture through clean. Your best so far: —

1 · What noise does

2 · Shannon's line

3 · Talking to its echo

4 · A map of certainty

5 · The cliff

6 · Borrow a second path

7 · What it changes

What noise does to a message

A phone sends data as bits , 1s and 0s. Here the message is a little night-time picture: each of its 8,192 pixels is one bit. The radio sends the bits in pairs as QPSK symbols — a wave nudged into one of four positions, the four corners on the left-hand plot below. (Most of the picture is dark sky, a run of 0s, so most symbols aim at the top-right corner.)

On the way, two things go wrong. Noise (the hiss every receiver hears) jitters each symbol. Fading is worse: as you move, echoes off buildings add up or cancel, so some symbols arrive almost at zero strength and collapse into the middle, where a 1 and a 0 look the same. Engineers call this Rayleigh fading; it is the channel the paper designs for.

Predict first

In the hero above, at 2.8 dB, the coded picture came through perfectly. If the same picture is sent at 2.8 dB through the fading channel with no code at all, roughly what fraction of pixels will flip?

Choose an answer to see a live measurement.

—

Decibels (dB) measure how loud the signal is compared with the hiss, per bit of message: every +10 dB is ten times the power. Try pushing the slider far right in the fading channel — errors linger long after the steady channel is clean, because a few deep fades always strike.

The cure is redundancy : send extra check bits, computed from the message, so the receiver can work out what was meant even when some symbols are lost in a fade. The question this whole field asks is: how little extra power and how little computation can you get away with?

Shannon's line, and the long chase towards it

In 1948 Claude Shannon proved that every channel has a capacity : for a given data rate there is a minimum signal strength below which no code, however clever, can get a message through reliably — and above which a good enough code can make errors as rare as you like.

For the hero's set-up — two-thirds of a message bit per QPSK symbol, through Rayleigh fading — the paper puts that line at 0.54 dB . The decoder you just ran gets clean pictures at about 2 dB. The gap between "possible in principle" and "achieved in practice" is what decades of coding research tried to close.

The code in this paper adds two check bits for every message bit, so it sends 3 bits per picture pixel (a rate-1/3 code). Its building block is a convolutional encoder : a tiny machine with a two-bit memory, whose check bit depends on the current bit and on what came before, so each message bit leaves its fingerprint on several transmitted bits.

Look inside the encoder

The paper's memory-2 recursive encoder (generator polynomials 7 and 5 in octal). Feed it bits and watch the memory cells and the check (parity) bit it emits alongside each message bit.

—

Seventy years of chasing the line (selected milestones from the paper's Tables I and II)

1948 Shannon's capacity theorem sets the limit.

1950 Hamming codes: the first practical error-correcting codes.

1955 Elias introduces convolutional codes.

1966 Forney's concatenated codes: chain two codes together — thought too complex at the time.

1971 Viterbi algorithm for decoding convolutional codes.

1974 Bahl et al.'s MAP algorithm: a decoder that outputs how sure it is about each bit.

1993 Turbo codes: two decoders trading hints come within a whisker of Shannon's line.

1997 Nickl, Hagenauer and Burkett report codes within 0.27 dB of the Gaussian-channel limit.

1998 Benedetto et al.: self-concatenated codes — one encoder, one decoder.

2000 ten Brink's EXIT charts: a picture of how iterative decoders converge.

2008 Arıkan's polar codes, proven to reach capacity.

One encoder, talking to its own echo

The 1993 breakthrough, turbo codes , used two encoders. The second one sees the message after a scrambler (engineers say interleaver) has shuffled its order. At the receiver, two decoders take turns: each passes the other a fresh hint about every bit — what it learned from its own check bits, not what it was told — and the hints snowball.

A self-concatenated code gets the same effect with half the hardware. One encoder is fed the message and its scrambled copy, zipped together. Every bit therefore passes through the same encoder twice, at two distant moments. Tap any bit below to follow it.

Or click / tap a square in the top row.

—

The decoder sweeps along the zipped stream once per pass. Whatever it concludes about a bit at one moment travels along the thread to become a hint for the same bit's twin. Physically there is one decoder; mathematically it behaves like two identical decoders trading hints.

Three ways to concatenate

—

Redrawn after the paper's Figs. 1–3 (simplified).

A map of growing certainty

Will the twins' conversation snowball into a perfect picture, or fizzle out? Running millions of test messages to find out is slow. The paper's main design tool, the EXIT chart (extrinsic information transfer chart), answers it with one picture.

It measures how much the decoder knows about the bits on a scale from 0 (pure coin flips) to 1 (certain of every bit) — information theorists call this mutual information. Give the decoder hints of a known quality, run it once, and measure the quality of the fresh hints it hands back. That gives one point. Build the curve yourself:

No points yet. Pick a hint quality and press Measure.

Why a mirror? The two "hypothetical" decoders are identical, so the second one's curve is the first one reflected in the diagonal. Decoding is a staircase : decoder 1 turns hints into knowledge (a step up to the amber curve), which becomes decoder 2's hints (a step across to the cyan mirror), and so on. If the curves leave an open tunnel , the staircase climbs to the top-right corner — every bit known. If they touch, it hits a wall.

The authors' key point for the bit-based design they propose: the staircase you measure by actually decoding lands on the curves you predicted. An earlier symbol-based version of the idea did not match this well, because bits sent in the same symbol are correlated.

Tunnel or wall? Predict, then test

Each round shows the predicted EXIT tunnel at a hidden signal strength. Decide whether a real picture sent at that strength will get through, then watch the live decoder settle it.

Look at the gap between the curves. Then choose.

Score: 0 of 0

The cliff — and what the paper measured

Plot the bit error ratio (the fraction of bits that come out wrong) against signal strength and an iteratively decoded code shows a turbo cliff : almost useless below a threshold, then a sudden plunge. The EXIT chart predicts where the cliff begins — the strength at which the tunnel first opens.

Paper curves redrawn from Fig. 13 of Butt, Ng & Hanzo (2012): QPSK, rate 1/3, memory 2, 40 decoding iterations, uncorrelated Rayleigh fading; points read from the published plot, approximate.

Your points will appear in cyan.

Your runs use 8,192-bit frames and 16 passes; the paper used 120,000-bit frames and 40 iterations, which sharpens the cliff and moves it left. A run with no errors is drawn at the bottom edge.

Two findings stand out in the paper's measurements. First, the cliffs land where the EXIT charts said they would: Gray mapping at about 1.8 dB, matching its predicted threshold of 1.81 dB. Second, a smarter way of placing bits on the four QPSK points (set partitioning) combined with letting the decoder and the symbol detector also trade hints ( SECCC-ID ) moves the cliff to 1.35 dB in the EXIT analysis — 0.46 dB better, and only 0.81 dB from Shannon's line. In the simulated error curve it operates 0.93 dB from capacity at an error ratio of one in a thousand.

With the soft demapper (the part that turns received symbols into bit guesses) joining in, three components trade hints: the demapper and the two hypothetical halves of the decoder. Each output now depends on two inputs, so the authors draw EXIT surfaces in three dimensions (their Figs. 10–11). The decoding trajectory threads between the surfaces exactly as predicted, and projecting it back onto two dimensions gives the 1.35 dB threshold. With Gray mapping the demapper gains nothing from feedback, so a 2-D chart suffices.

Below the cliff the paper's curves flatten out near one error in a million: an error floor, caused by rare message patterns whose encoded versions differ in only a few bits. EXIT charts cannot see it, so the authors derive a truncated union bound , adding up the chances of confusing the message with each of its closest look-alikes. To count those look-alikes for a code that is fed its own scrambled copy, they introduce a "uniform self-interleaver" — an average over every possible scrambling. Their simulations (Figs. 15–16) show the bound tracking the measured floors closely, so designers can now predict both the cliff (EXIT charts) and the floor (union bound) before building anything.

Borrow a second path

Big base stations fight fading with several antennas, so that when one path fades another probably doesn't. A phone is too small for antennas far enough apart. Cooperative communication borrows the idea anyway: a relay — another terminal between the phone and the tower — gives the message a second, independently fading path. The paper's last contribution puts its cheap self-concatenated code to work in exactly this situation.

Slot 1: the phone broadcasts its self-concatenated frame; the tower and the relay both hear it. Slot 2: the relay decodes, re-encodes with an even simpler code, and sends only the new check bits — a frame a third as long. The tower's decoder then lets its self-concatenated half and the relay-code half trade hints.

Drag the relay (triangle), or use the slider.

—

Radio power in free space falls with the square of distance (path-loss exponent 2). A relay halfway is twice as close to each end, so each hop arrives four times (6 dB) stronger than the direct link — the set-up analysed in the paper.

Send the picture both ways

Both transmitters use the same power setting , measured as the signal-to-noise ratio a receiver at the full phone–tower distance would see. The phone alone uses the stronger memory-3 self-concatenated code with 16 passes. The relay-aided tower uses the same frame plus the relay's check bits, decoded as the paper describes. Live simulation, 8,192-bit frames.

Press Send. Then lower the power until the relay-aided picture fails too.

Redrawn from Fig. 25 of Butt, Ng & Hanzo (2012): 120,000-bit frames, relay halfway, uncorrelated Rayleigh fading; points read from the published plot, approximate.

What the paper found simulated in the paper

The relay-aided scheme ( DSECCC-ID ) reaches an error ratio of 1 in 100,000 at about 3.3 dB less power setting than the phone alone with its self-concatenated code — each transmitter needs less than half the power.

Counting the relay's extra airtime (0.5 instead of 0.67 bits per symbol), the energy per delivered bit still drops by 2.05 dB .

It works within about 1.5 dB of the relay network's own Shannon limit (−5 dB), even though the relay is allowed to make mistakes.

It is cheap. Counting decoder operations (add–compare–select steps):

704 = 64 at the relay (8 passes × 8 states) + 640 at the tower; the comparison scheme reaches similar performance (and its detector is not even counted in the 960).

The phone→relay hop. The relay must decode almost perfectly, or it forwards mistakes. EXIT charts show the memory-3 self-concatenated code opens its tunnel at a received −0.15 dB, so with the 6 dB relay advantage the phone could go as low as −6.17 dB. They run at −3.5 dB to give the relay margin and only 8 passes.

Match the relay code. They compared relay codes with memory 2, 3 and 4: at −3.5 dB the memory-4 curve crossed the tower's self-concatenated curve (tunnel closed), while memory 2 and 3 stayed clear — so they chose memory 2, the simplest.

Check the whole tower decoder. The tunnel opens from about −3.65 dB; at −3.5 dB a measured decoding staircase, with up to 10 rounds of hint exchange, follows the predicted curves.

Back to the edge of the cell

We started with a phone at the fringe of a cell, whispering. Here is what this tutorial brings closer:

One encoder, one decoder. A self-concatenated code feeds a single small encoder the message and its scrambled copy; a single decoder argues with itself. Bit-based designs of this kind work within about 1 dB of Shannon's limit over both steady and fading channels.

Design by picture, not by brute force. EXIT charts predict where the cliff will be — and for these bit-based codes the measured staircases follow the prediction. A union bound predicts the floor. Together they let engineers pick a code before running long simulations.

Cooperation on a budget. Splitting the code between the phone and a relay, with a three-part decoder at the tower, cuts the power each transmitter needs by about 3.3 dB at the same reliability, close to the relay network's limit and with fewer decoder operations than a turbo-coded rival.

The authors' own design advice follows from the experiments you just ran: decide first how much computation and delay you can afford; protect the phone-to-relay hop most strongly, so mistakes do not propagate; and judge codes by whether their EXIT tunnel opens at low power rather than by their minimum distance alone.

They close with open questions: relays that forward soft hints rather than hard decisions, decoders that skip channel estimation altogether (non-coherent detection), and cutting the total power of a relay network — the transmitters and the chips doing the decoding. For a phone at the edge of the cell, every one of those decibels is battery life and a call that does not drop.

The paper Muhammad Fasih Uddin Butt, Soon Xin Ng and Lajos Hanzo, “Self-Concatenated Code Design and its Application in Power-Efficient Cooperative Communications,” IEEE Communications Surveys & Tutorials, vol. 14, no. 3, pp. 858–883, 2012. DOI: 10.1109/SURV.2011.081511.00104. Author-hosted copy: southampton.ac.uk.

About this page. All visuals are original drawings. Charts marked “redrawn” plot values read by eye from the paper's Figs. 13 and 25 (approximate); thresholds and capacities are quoted from its text and Table IV. The live simulations implement the paper's schemes in your browser: memory-2 (generators 7, 5) and memory-3 (13, 15) recursive encoders, self-interleaver, rate-3/4 puncturing, Gray-mapped QPSK, uncorrelated Rayleigh fading with perfect channel knowledge (as assumed in the paper) and log-MAP decoding; the relay scheme follows the paper's Section IV with the relay halfway by default. They use 8,192-bit frames instead of the paper's 120,000, so their cliffs are softer and sit slightly higher.

Topics in this iPaper

Engineering
The design methodology of future iteratively decoded self-concatenated aided cooperative communication schemes is presented.

Abstract, page 858

Computer science
Forward Error Correction (FEC) or Channel Coding in the context of digital communication has a history dating back to the middle of the twentieth century.

Section II, page 859

channel coding
In this tutorial, we have presented a brief history of channel coding

Section I, page 858

convolutional codes
The scheme employs binary RSC codes as constituent codes

Section III-A, page 863

iterative decoding
Iterative decoding works by exchanging extrinsic information between the component decoders 1 and 2.

Section II-C, page 860

extrinsic information transfer charts
EXtrinsic Information Transfer (EXIT) charts were used as our main design tools.

Section I, page 858

cooperative communications
we propose a Distributed Binary Self-Concatenated Coding scheme using Iterative Decoding (DSECCC-ID) for cooperative communications

Section IV, page 871

rayleigh fading
SECCC schemes that are designed for transmission over Additive White Gaussian Noise (AWGN) and uncorrelated Rayleigh fading channels

Section I, page 858

Self-Concatenated Code Design and its Application in Power-Efficient Cooperative Communications — Interactive explanation | iPaper.ai