Text from the interactive explanation
Nonbinary LDPC-Coded Sphere-Packed Transmit Diversity
Osamah Alamri, Soon X. Ng, Feng Guo, Salam Zummo, Lajos Hanzo
Original paperHow two antennas, a four-dimensional alphabet and two decoders that pass notes can get a message through a fading radio channel on less power.
Every wireless link is a bargain with noise. Turn the transmitter up and you spend energy; turn it down and the message dissolves. Osamah Alamri, Soon X. Ng, Feng Guo, Salam Zummo and Lajos Hanzo asked whether a receiver could rebuild the message from a weaker signal if it never chopped its symbols into bits. Their computer simulations say it can.
Two receivers hear the same signal at the same strength. Each rebuilds the message by letting two internal decoders swap notes. Which one gets there first?
Top · Keeps whole symbols — nonbinary LDPC over GF(16)
Bottom · Works bit by bit — binary LDPC
Chapter 1The stormWhy radio signals fade, and how a second antenna covers for the first.
Chapter 2One symbol, four numbersAn alphabet designed in four dimensions, and a receiver weighing its guesses.
Chapter 3Don’t split the symbolChop a belief into bits yourself and see what falls out.
Chapter 4Two decoders passing notesBuild the staircase that decides whether decoding succeeds.
Chapter 5The cliffFind the signal strength where the bit-based receiver breaks first.
Chapter 6Back to the whisperWhat the simulations show, under which assumptions — and what comes next.
The storm: why radio signals fade
A radio wave never takes just one path. It bounces off walls, cars and trees, and the copies reach the receiver a fraction of a moment apart. Sometimes they arrive in step and reinforce each other; sometimes they cancel. Move a few centimetres and the balance changes, so the received strength flickers up and down. Engineers call this Rayleigh fading . In a deep fade the signal sinks into the noise, and whatever was sent at that instant arrives badly blurred.
The classic fix is transmit diversity : send from two antennas whose paths fade independently. In 1998 Siavash Alamouti found a beautifully simple way to do it. In time slot 1, antenna 1 sends x1 and antenna 2 sends x2; in slot 2 they send −x2* and x1* (the star means the mirror image, or complex conjugate). Combining the two slots, the receiver gets each symbol scaled by |h1|² + |h2|², the strengths of both paths added together. It is in trouble only when both paths are weak at once.
Alamouti’s two-slot grid
Rows are time slots, columns are antennas (the paper’s eq. (1)). The second row is a rearranged mirror of the first, which lets the receiver pull x1 and x2 apart cleanly.
Simulated live on this page with a standard fading model: each path is a sum of 16 sinusoids with random arrival angles and phases (Jakes-style), scaled so its average power is 1 (0 dB). In two-antenna mode the same total power is split between the antennas, so the combined strength is (|h1|² + |h2|²)/2. Time is slowed down so you can watch.
The paper’s simulations use exactly this kind of channel: two transmit antennas, one receive antenna, uncorrelated Rayleigh fading generated with the Jakes model, fading held constant over each two-slot block, and a receiver that knows the channel perfectly.
With one receive antenna, the two slots deliver
The receiver forms x̃1 = h1*y1 + h2y2* and x̃2 = h2*y1 − h1y2*. The cross terms cancel and
which is the combined signal the paper starts from in Sec. IV. For Rayleigh fading, the chance that one path is more than 10 dB below average is 1 − e−0.1 ≈ 9.5%. The chance that the power-shared sum (|h1|² + |h2|²)/2 is that low is 1 − e−0.2(1 + 0.2) ≈ 1.8%. The live counts above wander around these values.
One symbol, four numbers
Look again at Alamouti’s grid. Each two-slot block carries two numbers, x1 and x2, and each one is a point on a plane: an amplitude and a phase, or equivalently two coordinates. So one block is really four real numbers (a1, a2, a3, a4), with x1 = a1 + ja2 and x2 = a3 + ja4 — a single point in four-dimensional space (the paper’s eq. (2)).
Alamouti picked x1 and x2 independently. In 2003 Weifeng Su, Zoltan Safar and K. J. Ray Liu chose the pair jointly instead. The receiver’s error rate is governed by the minimum distance between the possible points, so the transmitter should pick 4-D points that sit as far apart as possible for the energy they cost. This is sphere packing (SP) .
The best known arrangement in four dimensions is the D4 lattice : all integer points (a1, a2, a3, a4) whose coordinates add up to an even number. Its innermost shell holds 24 points such as (1, 1, 0, 0) or (1, 0, −1, 0). Every one has energy 2, and the closest pairs are √2 apart. The transmitter uses L of them: with L = 4, 8 or 16, each block carries log2L = 2, 3 or 4 bits over two time slots, a throughput of ½, ¾ or 1 bit per channel use (the paper’s schemes 1–3). The paper picks its L points with the lowest energy and the largest minimum distance, following its ref. [14].
Notice the joint design: if slot 1 is a corner, slot 2 must be silent (0) — the pair is designed together. Symbols that share a position are drawn as small petals around it.
An example selection that meets the paper’s rule; the exact points follow ref. [14]. Every 0.3 s a random symbol is sent through simulated Rayleigh fading and noise, and the white dots show what arrives after Alamouti combining. Drag a white dot (or pause, focus the planes and use the arrow keys; Shift moves the slot-2 dot) to see the probabilities respond. Illustrative calculation on this page, not a result from the paper.
The 24-cell
D4’s innermost shell: 24 points in four dimensions, each with 8 nearest neighbours (lines). This shape is called the 24-cell. Amber points: the symbols in use.
It is turning in two independent planes at once — one mixing the first and fourth coordinates, one mixing the second and third — then projected down to your screen. Switch between L = 4, 8 and 16 above to light up different subsets.
(1) The Alamouti grid: rows are time slots, columns are antennas, G2(x1, x2) = [ x1 x2 ; −x2* x1* ].
(2) One SP symbol fills both slots: {x1, x2} = {a1 + ja2, a3 + ja4}.
(3) The L chosen points are scaled by √(2L/E), where E is their total energy, so that the average energy is fixed whichever L is used.
(4) After combining, the receiver sees a 4-D point
with Gaussian noise w of variance h·σ² in each of the four dimensions.
(5)–(6) The chance of seeing r if sl was sent falls off as exp(−distance² / 2σw²). Bayes’ rule turns these likelihoods into the probability of each symbol given r, normalised so the L numbers add up to 1. That list is what the demapper hands on.
On this page the received point is shown divided by its combining gain, r = s + n, with noise variance σ²/g per dimension, g = (|h1|² + |h2|²)/2 and σ² = 1/(2·10SNR/10); probabilities are ∝ exp(−g|r − sl|²/2σ²). This is an illustrative normalisation.
Throughput. log2L bits travel in two slots: (log2L)/2 bits per channel use. Why minimum distance? Noise most often pushes a point towards its nearest neighbour, and the probability of that mistake shrinks very quickly as the gap grows — so the closest pair sets the error rate.
Don’t split the symbol
With L = 16, each symbol stands for 4 bits. A binary error-correcting code reasons about those bits one at a time. A nonbinary code reasons about the 16-way choice as a whole.
The paper makes its LDPC code work over a 16-letter number system, the Galois field GF(16), where you can add, subtract, multiply and divide without ever leaving the 16 letters. That way each code symbol maps directly onto one sphere-packed symbol — “a natural one-to-one mapping … L = q” (Sec. II). Nothing is chopped up.
In the bit-based comparison scheme, every message passed between the rate-1 decoder and the binary LDPC decoder has to be converted from symbols to bits and back again (Sec. II). What can go missing in that conversion? Try it.
Belief about the symbol
Drag a bar sideways — or focus the list, choose a row with ↑/↓ and change it with ←/→. It always adds up to 100%.
What each bit believes on its own
Chance that the bit is 1: add up every symbol whose label has a 1 in that place.
Rebuilt from the bits
Multiply the four bit beliefs back together — the best you can do once only bits were kept.
Nothing lost — this belief only hesitates about bits that are independent of one another.
Nothing is lost only when the bits are independent of each other. Whenever a belief says “these bits go together” — 0110 or 1001, but nothing in between — splitting throws that away. The rebuilt belief then spreads over all 16 combinations of the uncertain bits.
A calculation on this page that illustrates the mechanism. The paper measures the end-to-end effect with EXIT charts and error rates (next chapters). The 4-bit patterns are example labels. Uncertainty is measured as entropy in bits: H(whole symbol) versus the sum of the four bits’ entropies, which can never be smaller.
GF(q) in one paragraph. A Galois field is a finite set of “numbers” with addition, subtraction, multiplication and division that never leave the set. GF(16) can be written as the 16 four-bit patterns: addition is bitwise XOR, and multiplication is a special rule (polynomial multiplication modulo a fixed degree-4 polynomial) that makes every non-zero element invertible.
A nonbinary parity check says that a weighted sum of a few code symbols must equal zero in GF(16). A binary code asks the same of individual bits.
The code in this paper has rate ½, is randomly constructed with an average column weight of 2.5 (each symbol takes part in 2.5 checks on average), follows Davey and MacKay’s nonbinary LDPC design, and is decoded with Richardson’s fast-Fourier-transform-based algorithm (Sec. II, Table I). Its field matches the constellation: GF(4), GF(8) or GF(16) for L = 4, 8 or 16.
Two decoders passing notes
Here is the whole chain, after the paper’s Fig. 1. Source bits enter a nonbinary LDPC encoder of rate ½: for every message symbol it adds one check symbol, and each parity check ties together a few randomly chosen symbols — which also scrambles them, doing the job of an interleaver. A rate-1 precoder then replaces each symbol with the running total, modulo q, of all the symbols so far. It adds no redundancy, but it spreads information along the block and helps avoid an error floor. The SP mapper turns each symbol into a 4-D point, and the Alamouti encoder sends it from two antennas over two time slots.
At the receiver, the Alamouti decoder combines the two slots and the SP demapper turns each received point into L probabilities, one for every possible symbol. Then the rate-1 decoder and the LDPC decoder take turns . Each passes on only its extrinsic information — what it learned beyond what it was told — computed by dividing out the belief it received, element by element. They stop when all the LDPC parity checks are satisfied or the iteration budget is spent.
In the bit-based twin everything is the same except that the LDPC code is binary, so every note crossing the loop must be converted symbols → bits and bits → symbols (Sec. II). Watch the tokens split into four pieces and merge again — the conversion you tried in Chapter 3.
How can you tell whether the note-passing will succeed? Stephan ten Brink’s EXIT chart (2000) answers with two curves. Across : the information the LDPC decoder has about each symbol, from 0 up to log2L bits (2 for L = 4, 4 for L = 16). Up : the information the rate-1 decoder has. The upper curve is the rate-1 decoder’s response, and it depends on signal strength. The lower curve is the LDPC decoder’s response, drawn flipped; it does not depend on signal strength at all.
Bounce up to the upper curve (the rate-1 decoder’s turn), then across to the lower curve (the LDPC decoder’s turn), and repeat. If the curves touch, the bouncing stalls: decoding fails. If there is an open tunnel, the staircase reaches the right-hand wall — and a wider tunnel means fewer exchanges.
Curves traced from the paper’s Figs. 2–5 (approximate). The staircase for Figs. 2–3 is the idealised path between the curves; Figs. 4–5 show the paper’s actual simulated trajectories, which deviate slightly from the idealised path because the code blocks are finite (6,000 bits).
Both axes are mutual information , averaged over the symbols of a block (eqs. (9)–(10)). IA is how much a decoder’s incoming (a priori) beliefs say about the true symbols; IE is how much its outgoing extrinsic beliefs say. The horizontal axis is IA of the rate-1 decoder, which equals IE of the LDPC decoder; the vertical axis is the other way round. Each decoder’s curve maps what it is told to what it can add.
The maximum is log2L bits per symbol: complete certainty about which of the L symbols was sent. The paper estimates IE directly from a decoder’s output probabilities (eq. (11)): log2L minus the average uncertainty that remains in them.
Narrow tunnels. As the paper notes, the narrower the tunnel, the closer the system operates to channel capacity — and the more iterations are needed to reach the top-right corner. A tunnel that is open but tight is efficient but slow; one that closes means the decoders talk themselves into a stalemate.
The cliff
After all the note-passing, what fraction of the bits are still wrong? That is the bit error ratio (BER) . The paper’s Fig. 6 plots it against signal strength for all three throughputs, after 5 joint iterations and 3 internal LDPC iterations, on blocks of 12,000 bits.
Each curve falls off a turbo cliff : once the tunnel opens, errors vanish within a fraction of a decibel. The whole-symbol cliffs sit to the left, so the same reliability needs a weaker signal. In decibels, −0.5 dB is about 11% less power and −1 dB about 21% less.
Curves traced from Fig. 6 (approximate); each ends where it crosses a BER of 10⁻⁵. Postcard pixels are flipped at random at the plotted error rate — an illustration of what that rate means, not a decoded image.
What the paper reports
From the abstract. The conclusion adds that “both designs had an edge over Alamouti’s now classic STBC scheme”. On the traced Fig. 6 curves above, the whole-symbol cliff reaches a BER of 10⁻⁵ roughly 0.5–0.6 dB sooner at every throughput. All of these results come from the paper’s simulations.
Back to the whisper
Design the pair, not the parts
Sphere-packed 4-D symbols spread across two antennas and two time slots, chosen as points of the D4 lattice that sit as far apart as possible.
Speak the same alphabet end to end
A nonbinary LDPC code over GF(L): one code symbol per transmitted symbol, and no bit conversions anywhere in the receiver.
Let two decoders talk
A recursive rate-1 precoder and symbol-based turbo detection, with convergence tracked by nonbinary EXIT charts.
Could a radio whisper and still be understood? In the scenarios the authors simulated — two transmit antennas, one receive antenna, Rayleigh fading, perfect channel knowledge — the whole-symbol receiver opened its tunnel at lower signal strength, converged in fewer exchanges and reached a bit error ratio of 1 in 100,000 with less power than its bit-based twin.
Every fraction of a decibel is transmit power that does not have to be spent. The authors’ conclusion points to what comes next: differentially encoded, low-complexity sphere-packing designs that need no channel estimation at all, and space–time equalised systems.
Source & credits
Osamah Alamri, Soon X. Ng, Feng Guo, Salam Zummo and Lajos Hanzo, “Nonbinary LDPC-Coded Sphere-Packed Transmit Diversity,” IEEE Transactions on Vehicular Technology, vol. 57, no. 5, pp. 3200–3205, September 2008.
DOI: 10.1109/TVT.2008.917217 · Author-hosted PDF
Curves on this page were traced approximately from Figs. 2–6 of the paper and redrawn; original figures © 2008 IEEE. Fading, received-symbol and belief-splitting demonstrations are illustrative calculations made live in your browser, not results from the paper.
Works mentioned: S. Alamouti, “A simple transmit diversity technique for wireless communications,” IEEE J. Sel. Areas Commun., 1998. W. Su, Z. Safar and K. J. R. Liu, “Space–time signal design for time-correlated Rayleigh fading channels,” Proc. IEEE ICC, 2003. M. C. Davey and D. J. C. MacKay, “Low density parity check codes over GF(q),” IEEE Commun. Lett., 1998. J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, Springer, 1999. S. ten Brink, “Designing iterative decoding schemes with the extrinsic information transfer chart,” AEÜ Int. J. Electron. Commun., 2000.
Topics in this iPaper
Engineering
The adverse effects of channel fading may significantly be reduced by employing space–time (ST) coding that invokes multiple antennas
Section I, page 3200
Computer science
we propose a purely symbol-based, low-density parity-check (LDPC)-coded scheme
Abstract, page 3200
low density parity check codes
The source bits are encoded by a rate R = 1/2 nonbinary LDPC encoder
Section II, page 3200
space time block codes
In this contribution, ST systems employing two transmit antennas are considered
Section III, page 3201
sphere packing
the lattice D4 is defined as an SP constellation having the best MED
Section III, page 3202
iterative decoding
SYMBOL-BASED ITERATIVE DECODING
Section IV, page 3202
extrinsic information transfer charts
The main objective of employing EXIT charts [16] is to predict the convergence behavior of the iterative decoder
Section V, page 3202
rayleigh fading
we considered an uncorrelated narrowband Rayleigh fading channel based on the Jakes fading model
Section II, page 3201