Make your paper interactiveCreate

Text from the interactive explanation

Equivalent Capacity-Based Joint Multilevel Coding and Space–Time Transmit Diversity Design

Ronald Yee Siong Tee, Osamah Rashed Alamri, Soon Xin Ng, Lajos Hanzo

Original paper

Tee · Alamri · Ng · Hanzo — IEEE Transactions on Vehicular Technology, 2008

Every time you move with a phone, its signal flickers. A second transmitting antenna helps. This paper goes further: it treats what two antennas send over two moments as one point in four-dimensional space , and designs those points, their bit labels and their error-correcting codes together.

In the authors’ simulations of a fast-fading mobile link, the design reached one error in 100,000 bits with about 3 dB less energy per bit . That’s roughly half the energy of a conventional two-antenna design.

Or tap a 4-bit label to light its point:

Live visualisationThe 16 points and their bit labels are the paper’s own (Table II, “L1-BSA” labels). The tumbling is our way to show a 4-D object on a flat screen. Drag it, or focus it and press the arrow keys, to turn it through the fourth dimension.

01 · THE PROBLEM

Why your signal flickers

Radio waves reach your phone along many paths. Some come straight from the mast, some bounce off buildings, and some scatter off trees. Where the waves meet, they add up or cancel. As you move, that pattern shifts, so the received strength swoops up and down. Engineers call this fading . The deep dips are where messages get lost.

The paper simulates exactly this situation: a correlated Rayleigh fading channel with a fast-moving receiver (a “normalised Doppler” of 0.1, meaning the fading changes noticeably every few symbols).

Watch the single-antenna signal. What share of the time is it in a deep fade, ten times weaker than average?

Now press Add the second antenna . With Alamouti’s space–time block code (1998), the receiver adds up the strengths of both paths. Both paths would have to fade together to cause trouble. That is rare, so the deep fades shrink about fivefold. This transmit diversity is the foundation the paper builds on.

After space–time decoding, the receiver sees the sent symbol X scaled by the summed strengths of the two paths, plus noise Ω. A single Rayleigh path has an exponential strength distribution, so it spends 1 − e−0.1 ≈ 9.5 % of the time below a tenth of its average. The average of two independent paths follows a chi-square law with four degrees of freedom, and spends only 1 − e−0.2(1 + 0.2) ≈ 1.8 % there.

Two antennas give the receiver two chances. But what exactly should each antenna say?

Illustrative modelTwo independent Rayleigh-fading paths simulated live in your browser. The paper’s own channel uses normalised Doppler 0.1, the right end of the slider.

Illustrative modelQPSK with random noise (and optional Rayleigh fading), simulated live.

02 · THE ALPHABET

A message is a dot

Digital radios don’t send 0s and 1s directly. They send symbols : short pulses whose strength and timing (amplitude and phase) pick one point from a small menu called a constellation . The simplest useful one, QPSK, has four points, so each symbol carries two bits.

The receiver never sees the exact point. Noise blurs it, and fading squashes it towards the centre. So the receiver just guesses the nearest point. On the left, every grey speck is one received symbol. A red flash means the guess was wrong.

Lower the signal-to-noise ratio and the clouds spread into their neighbours’ territory. Press Add fading and many symbols collapse towards the middle, where guesses become coin flips.

Points far apart survive more noise, but pushing them apart costs energy. So the craft is to place the points cleverly for a fixed energy budget. You also have to decide which bits ride on which point.

Two antennas over two moments give us four numbers to play with, not two. What does a constellation look like in four dimensions?

03 · SPHERE PACKING

Stacking oranges in four dimensions

Greengrocers know the best way to stack oranges: each one ends up touching 12 others. Mathematicians call this sphere packing , and it works in any number of dimensions. Coins on a table can each touch 6 neighbours. In four dimensions, the densest regular stacking, called D4 , lets every sphere touch 24 .

Dense packing is what a constellation designer wants: the most points for a given spacing and energy. The paper uses D4 because it is the densest 4-D lattice. The 24 neighbours of its centre are all the arrangements of ±1, ±1, 0, 0 . They are the corners of a famous 4-D shape called the 24-cell , and each sits √2 from its nearest neighbours.

The design needs 16 points (16 = 2⁴, so each carries 4 bits). The authors ran an exhaustive computer search for the 16 that sit farthest apart. Spin their choice through different pairs of axes, and reveal the 8 points they left out.

A point belongs to D4 if its four coordinates are whole numbers adding up to an even number. Grouped by distance from the origin:

The chosen 16 all come from layer 1. A second design (“L2-BSA”) mixes 8 layer-1 points with the 8 (±2, 0, 0, 0)-type points of layer 2.

We now have 16 points in four dimensions. But each antenna sends one complex number, which is only 2-D. How does a 4-D point leave the antennas?

Rotate in the plane of axes:

Exact geometryPoints from the paper’s Table II; the lines join points at the minimum spacing √2.

Exact countsShadow frequencies follow from the 16 chosen points (the paper’s Fig. 2); the streaming symbols are random.

04 · THE SPLIT

One point, two antennas, two moments

Split the point’s four coordinates into two pairs. The first pair becomes antenna 1’s complex symbol, x₁ = a₁ + j·a₂. The second becomes antenna 2’s, x₂ = a₃ + j·a₄. In the next moment, Alamouti’s trick has the antennas swap and flip their symbols (the table on the left). That lets the receiver separate them and add up both paths.

Each antenna therefore transmits only a shadow of the 4-D point.

Every chosen point has exactly two non-zero coordinates. How often do you think antenna 1 sends nothing at all?

Watch the bars fill. The 16 points cast only 9 distinct shadows per antenna, and they are used unequally. The centre is used ¼ of the time, the four edge spots ⅛ each, and the four corners 1⁄16 each, just as in the paper’s Fig. 2. Neither antenna alone pins down the message. Only the pair does.

That is what joint design means. Earlier two-antenna schemes chose each antenna’s symbols separately. Here, the space (two antennas) and time (two moments) parts of the signal are designed as one object.

Which 4-bit pattern should sit on which point? It turns out to matter a lot.

05 · THE LABELS

The labelling puzzle: keep the twins apart

Each point carries a 4-bit label. Call two labels twins if they differ in exactly one bit, like 0110 and 0100. Every label has four twins, one per bit.

Here is why twins matter. The receiver decodes in rounds, and its error-correcting codes gradually firm up its beliefs. Suppose it is already confident about three of a symbol’s four bits. Then only two candidates remain: the point and one of its twins. If those two sit far apart, the last bit is easy to read.

The paper scores a labelling by adding up 1 ÷ distance² over every twin pair (its Eq. 11). Lower is better. Then it improves the labelling with the Binary Switching Algorithm . Find the label with the worst twins. Swap it with whichever other label lowers the total most. Repeat until no swap helps.

Try it. Faint lines join every twin pair, coloured by how far apart they are: red for nearest neighbours, through amber and teal, to white for exact opposites. Tap a point to see its four twins (line colour = which bit differs). Tap two points one after another to swap their labels. Or let the algorithm do it.

Ŝk is the twin of symbol Sk across bit i. Squared distances between the chosen points can only be 2, 4, 6 or 8 (8 = exactly opposite). The paper assumes the other bits are already known (“perfect a priori information”), which it notes is a good approximation at high signal-to-noise ratio.

For comparison, here is our own calculation, which is not in the paper. Suppose each antenna sent its own QPSK symbol with its own labels, at the same energy. Then a twin could never be more than one QPSK square away, and the best possible score is 24. Labelling all four dimensions jointly lets a twin sit on the far side of the crystal.

This puzzle scores only the twin cost. Where a swap search ends up depends on where it starts. The paper tested its finished labellings (SET, L1-BSA, L2-BSA and UEP1 in Table II) inside complete simulated links.

Labels decide how hard each bit is to read, and the four bits are not equally hard. That is the next idea.

Exact costEq. 11 computed on the paper’s 16 points. The binary switching search runs live in your browser.

06 · MULTILEVEL CODING

Four bits, four shields

Error-correcting codes add carefully designed redundancy so the receiver can repair mistakes. Instead of one code for everything, multilevel coding gives each of the four bit positions its own code. The paper uses LDPC (low-density parity-check) codes.

The receiver decodes like a staircase. Level 1 goes first, while everything is still uncertain. Each decided level narrows the choices for the next. Extra outer iterations send what the decoders learned back to the start for another, sharper pass.

IllustrativeThe candidate sets are exact for the paper’s L1-BSA labels; the decoding steps are schematic.

Budget the four levels yourself

Each level faces a different amount of confusion, so each behaves like its own channel with its own capacity : the most information it can reliably carry. The chain rule of information splits the total exactly into these four parts. The paper’s equivalent-capacity design gives each level a code rate equal to its own capacity.

The link must deliver 2 bits per 4-D symbol in total (that is, 1 bit per channel use after rate-½ coding). Drag the rates and see how much signal the weakest level would need.

TracedLevel capacities traced approximately from the paper’s Fig. 4 (L1-BSA labels, 2 transmit and 1 receive antenna, Rayleigh fading). This is a capacity estimate; real codes need a little more signal.

The actual LDPC codes in the paper (Table IV, L1-BSA) carry this many message bits in each 640-bit codeword:

The information the received signal R carries about the whole symbol S equals the sum of what it carries about each bit, given the bits already decoded. Each term is the capacity of one “equivalent channel”. At the point where the total reaches 2 bits per symbol (about 0.7 dB in Fig. 4), the paper reads off rates of 0.2717, 0.3152, 0.6196 and 0.7826. The codes in Table IV use 176, 204, 398 and 502 message bits per 640-bit block: 1280 of 2560 bits overall, a rate of ½.

All the pieces are in place: two antennas, a 4-D constellation, careful labels and right-sized codes. Did it work?

07 · THE EVIDENCE

Racing to one error in 100,000

The authors simulated complete links: 5000 frames of 2560 coded bits each, over a fast-fading channel, with two transmit antennas and one receive antenna. They measured the bit error rate (the share of bits received wrong) while raising the energy per bit (Eb/N0, in decibels). Every extra 3 dB doubles the energy. Slide the energy and watch which designs reach the target of 10⁻⁵, one wrong bit in 100,000.

Simulated by the authorsCorrelated Rayleigh fading, normalised Doppler 0.1, 2 transmit and 1 receive antenna. Curves traced approximately from the paper’s Fig. 5.

Both 4-D designs reach about 10⁻⁶ at 6 dB. The decoder’s work per level grows with the iterations: 153,600 additions and 537,600 multiplications per pass, according to the paper’s count.

08 · BACK TO THE FLICKER

Same message, about half the energy

We started with a phone signal that keeps dipping into fades. A second antenna softens the dips. This paper’s contribution is what to send through the pair, and three choices make it work.

One 4-D symbol. Two antennas × two moments are treated as a single point drawn from D4, the densest 4-D packing.

Twin-aware labels. Bits are placed so that one-bit “twins” sit far apart, tuned with the Binary Switching Algorithm.

Right-sized shields. Each bit level gets an LDPC code whose rate matches its own equivalent capacity.

In the authors’ simulations, this took about 3 dB off the energy per bit needed for one error in 100,000, compared with a conventional QPSK-based design. That is roughly half the energy for the same reliability, or a sturdier link at the same power. A hybrid labelling (UEP) can also give the most important bits the safest lane, which is useful for speech and video.

What the evidence covers

The results are computer simulations of 16-point constellations, with two transmit antennas and one receive antenna, over a correlated Rayleigh channel with normalised Doppler 0.1 and 640-bit component codes. The authors note that longer component codes lower the remaining error floor. They suggest their cost-function approach could carry unequal protection to even larger multidimensional constellations for multimedia communications.

Source and notes

Ronald Yee Siong Tee, Osamah Rashed Alamri, Soon Xin Ng and Lajos Hanzo, “Equivalent Capacity-Based Joint Multilevel Coding and Space–Time Transmit Diversity Design,” IEEE Transactions on Vehicular Technology, vol. 57, no. 5, pp. 3006–3014, September 2008. DOI: 10.1109/TVT.2008.915513. Author-hosted copy: southampton.ac.uk/~sxn/paper/tee-tvt08.pdf.

Every figure on this page is redrawn. Curves in sections 6 and 7 are traced approximately from the paper’s Figs. 4–7, and the numbers quoted come from its text and Tables I–IV. The fading chart, the noisy constellation and the labelling puzzle are illustrative models running in your browser, not the authors’ simulator. The original paper is © 2008 IEEE.

Glossary

Topics in this iPaper

Engineering
which combines an MLC-based scheme with a twin-antenna-aided STBC for the sake of providing a transmit diversity gain

Abstract and Index Terms, page 3006

space time block coding
A novel space–time block-coding-assisted and sphere-packed multilevel-coded (STBC-SP-MLC) modulation arrangement is proposed

Abstract, page 3006

multilevel coding
Equivalent capacity-based code design, multilevel coding, sphere-packing modulation, transmit diversity

Index Terms, page 3006

sphere packing
The SP modulation invokes a 4-D D4 constellation space

Abstract, page 3006

low density parity check codes
We employ LDPC component codes owing to their powerful error-correcting capability

Section II (System Overview), page 3007

unequal error protection
which is capable of providing unequal error protection

Abstract, page 3006

rayleigh fading
when communicating over a correlated Rayleigh channel having a Doppler frequency of 0.1

Fig. 5 caption, page 3012

Equivalent Capacity-Based Joint Multilevel Coding and Space–Time Transmit Diversity Design — Interactive explanation | iPaper.ai