Make your paper interactiveCreate

Text from the interactive explanation

Iteratively Decoded Variable Length Space-Time Coded Modulation: Code Construction and Convergence Analysis

Soon Xin Ng, Jin Wang, Meixia Tao, Lie-Liang Yang, Lajos Hanzo

Original paper

Wireless coding · 2007

In this code from Southampton and Singapore, the most common messages are sent mostly as silence — and that silence is what makes the rest of the signal stronger.

“+” pulse

“−” pulse

silence (antenna off)

thread = one message's three pieces

IllustrationThe mechanism, with messages drawn at random from the chosen source. Pulse size follows the amplitude; glow follows the energy. Time runs toward the antennas on the right.

A transmitter with three antennas sends one of eight possible messages at every instant: 3 bits each time. In the paper's code, the most common message switches on just one antenna, and the other two stay silent. Silence costs no energy, so the energy those slots would have used goes into the pulses that remain.

How can staying silent make a radio link stronger?

Follow the seven short chapters below, then come back to this scene.

In the authors' computer simulations, the full scheme reached an error rate of 1 in 10,000 messages with 14.6 dB less energy per bit than a conventional fixed-length design.

It came within about 1.75–2.75 dB of the theoretical limit for this antenna setup.

Some messages are far more common than others

Picture a source, such as a video or audio encoder, that hands the radio one of eight messages at every instant. If all eight were equally likely, each would carry exactly 3 bits : three yes-or-no questions would pin it down.

Real encoders don't behave like that. Even after compression, some values turn up far more often than others. Information theory measures a source's average surprise as its entropy : the more lopsided the odds, the lower the entropy. The paper calls such a lopsided source correlated, and an equally likely one uncorrelated.

Each message is 0.60× as common as the one before it (r = 1: all equally likely).

Bet on the next message

Pick a number. The source then draws its next message from the odds on the left.

No bets yet · blind guessing wins 12.5%

Keep betting on message 1 with the paper's lopsided source, then slide back to r = 1.00.

When some messages are favourites, betting on the favourite wins far more often than the 12.5% of blind guessing. That predictability is exactly what the paper's code exploits.

The trouble with short codes

The classic way to exploit favourites is Morse's trick: give common messages short codes and rare ones long codes. A Huffman code does this as efficiently as possible. For the paper's example source, a Huffman code looks like this (our illustration, not part of the paper):

That averages 2.35 bits per message instead of 3. But there is a catch: the receiver finds where one message ends and the next begins by reading the bits themselves. Flip a single bit, as a noisy radio channel will, and the boundaries slide.

Row A · short codes in time

Row B · the paper's code in space

+ pulse (“0”)

− pulse (“1”)

silent (“x”)

IllustrationA simplified sync demo: Row A decodes with the Huffman code above; Row B checks each instant's three pieces against the paper's eight codewords.

The paper's move: make the length vary in space (how many antennas speak) instead of in time. Every message still gets exactly one instant, so the length of a frame is fixed by the number of messages. The authors point out that this avoids the synchronisation problem, needs no side information about where messages start, and keeps one error from spreading into its neighbours. A damaged instant is just one damaged message.

Make the common messages quiet

These are the paper's eight codewords (its Equation 5). Each column is one codeword; its three cells are what antennas 1, 2 and 3 do at that instant. Three codewords switch on one antenna, three switch on two, and two use all three.

Which message gets which codeword is a design choice. The paper's rule: give the most common messages the codewords with the most silences.

Tap a message chip, then another, to swap their codewords. The percentage is how often that message occurs.

Try the worst assignment. Then switch to the random source: does the assignment still matter?

Why do fewer active antennas mean stronger pulses? The paper keeps the average energy per instant the same as three always-on antennas. Silent slots spend nothing, so that budget is shared among fewer pulses: the energy of each pulse is A² = 3 ÷ Lave, where Lave is the average number of active antennas. With the paper's assignment, Lave = 1.233, so each pulse carries 2.433× the energy, or +3.86 dB.

The more predictable the source, the more often the quiet codewords are used and the stronger the pulses become. In the authors' words, the source correlation is converted into a larger minimum distance between codewords, and so into a coding gain, where an ordinary variable-length code would turn it into compression.

Why not make every message nearly silent?

Each pair of codewords must still differ on at least two antennas (next chapter). The authors found that the fixed-length benchmark code, in which some pairs differ on only one antenna, gave an iterative decoder too little to work with: its decoding curve was too flat to gain anything from extra rounds.

The eight codewords also keep the rate at 3 bits per instant, using ± pulses that on their own carry 1 bit each. The paper counts this as a spatial multiplexing gain of log₂(8/2) = 2.

Two chances instead of one

Radio waves bounce off walls and buildings, and the echoes can cancel each other. The strength of each antenna-to-antenna path therefore swings between strong and weak. This is called fading . In the paper's simulations the fading changes from one instant to the next.

The paper adds a tiny delay: antenna 2 waits one instant and antenna 3 waits two before sending their pieces (two small memory cells do this). So each message's three pieces leave at three different instants, on a diagonal of the space-time grid. One bad instant can wipe out at most one piece of any message.

Ten messages on diagonals across twelve instants. Tap an instant (number or column) to hit it with a deep fade.

With the paper's code, can one fade make any message ambiguous? Now switch to the fixed-length code.

Simplified illustrationA fade is treated as totally erasing every piece sent at that instant. A message counts as identifiable when exactly one of the eight codewords matches its surviving pieces.

Because any two of the paper's codewords differ on at least two antennas (a minimum Hamming distance of 2), losing one piece never makes two messages look alike. The paper calls this a transmit-diversity order of 2 . Its minimum product distance, a measure of how far apart the closest codewords are once pulse energy is included, is 5.92 against 4 for the fixed-length code, whose closest pairs differ on only one antenna.

The delay cells also give the transmitter a memory. The encoder becomes a trellis with 24 states and 8 branches leaving each one, and the receiver's decoder works along that trellis, weighing every possible path. The authors note that this is the minimum decoding complexity for this combination of diversity and multiplexing.

A state is whatever is still waiting in the three delay cells: pieces 2 and 3 of the previous message and piece 3 of the one before. Each cell holds +, − or silence, which makes 27 combinations, of which only 24 can occur with these codewords. From every state, the next message (one of 8) picks one of 8 branches. The decoder (a MAP decoder) scores every branch using the received signals and the message odds.

A receiver that thinks in rounds

The code so far (the paper calls it VL-STCM) is decoded in a single pass. The iterative version, VL-STCM-ID , adds two small things to each antenna's stream before the pulses go out: a shuffler (a random interleaver, 10,000 symbols long in the simulations) and a running-sum precoder . The precoder is a "unity-rate code": instead of each symbol, it sends the running total so far, counted modulo 3, with silence counted as 2.

The running sum on one antenna

Tap an input to change it. Output = (input + previous output) mod 3, starting from 0. Values: “0” = 0, “1” = 1, silent = 2.

IllustrationOne antenna's precoder in isolation (no shuffler), following the paper's description of its modulo-3 adder.

Changing one input changes every output after it. That memory is what lets the decoders help each other. The receiver is three kinds of expert:

The antenna listener

The running-sum undoers

The codebook expert

They pass only new evidence back and forth (decoding specialists call it extrinsic information), so no expert hears its own opinion echoed back. An EXIT chart tracks how much each side knows, in bits, after every exchange. The paper introduced 3D symbol-based EXIT charts for this three-stage receiver; below is its 2D projection.

Eb/N0 compares the energy spent on each bit with the background noise. Every +3 dB roughly doubles that energy.

Precoder experts (y = what they hand over)

Codebook expert (x = what it hands over)

Decoding rounds

Each vertical step is the precoder experts' turn; each horizontal step is the codebook expert's. If a tunnel stays open between the curves, the staircase climbs to the top-right corner (full knowledge: 4.68 bits). If the curves touch, it gets stuck.

TracedCurves at 4 dB traced from the paper's Fig. 8 (uncorrelated source); other SNRs use an illustrative interpolation. With the predictable source, the authors found the tunnel opens 1 dB earlier, at 3 dB.

Remove the precoder and the antenna listener talks to the codebook expert directly. Its curve is nearly flat, so it meets the codebook expert's curve well before full knowledge. The authors found that without the precoder, decoding cannot converge at 4 dB.

What the simulations showed

The authors simulated three schemes over a fading channel with 3 transmit and 2 receive antennas, ± pulses (BPSK) and blocks of 10,000 symbols, and counted the symbol error ratio (SER): the fraction of messages decoded wrongly. Lower curves are better; curves further left need less energy.

▲ Fixed-length (benchmark)

■ Variable-length, one pass

● Variable-length + rounds: 1st round

● Variable-length + rounds: 8th round

SimulatedSimulation results from the paper's Fig. 10, traced and redrawn (approximate). Rayleigh fading, 3 transmit / 2 receive antennas, 10,000-symbol blocks. Drag the gold target line or use the slider; values are read from the traced curves.

At an error rate of 10⁻⁴, the paper reports that after 8 rounds the iterative scheme is about 7.5 dB (random source) or 6.5 dB (predictable source) better than the one-pass variable-length scheme, and 14.6 dB or 15 dB better than the fixed-length benchmark.

In its first round, the iterative scheme is actually worse than one-pass. Before any hints are exchanged, the precoder stage hands over less than the antenna listener alone would; the precoder only pays off once the experts start trading.

The capacity limit for this antenna setup and pulse alphabet at 3 bits per instant is Eb/N0 = 1.25 dB. The iterative decoder converges at about 4 dB with the random source and 3 dB with the predictable one: within roughly 2.75 dB and 1.75 dB of that limit.

The price is delay and effort: the receiver works on whole 10,000-symbol blocks and runs several decoders over several rounds. For delay-sensitive, complexity-constrained systems the authors recommend the one-pass VL-STCM; where higher performance is worth the extra delay and complexity, VL-STCM-ID.

Back to the quiet antennas

So how can staying silent make a radio link stronger? Three ideas stack up:

Predictability → silence → stronger pulses

Common messages switch on fewer antennas. The energy they don't spend goes into the pulses that remain: 2.43× with the paper's example source.

Distance 2 → two chances

Every pair of messages differs on at least two antennas, sent at different instants, so one deep fade cannot make two messages look alike.

Rounds of hints → near the limit

A running-sum precoder and experts that trade only new evidence climb the EXIT tunnel, to within about 1.75–2.75 dB of capacity in the simulations.

As the authors frame it, this brings closer the near-capacity transmission of variable-length data over multi-antenna links: compressed MPEG-2, -3 and -4 video and audio, or ordinary computer data packed into variable-length symbols. Their stated next step was to add explicit channel coding and to work with real-time multimedia source codecs.

Source & credits

Soon Xin Ng, Jin Wang, Meixia Tao, Lie-Liang Yang and Lajos Hanzo, “Iteratively Decoded Variable Length Space-Time Coded Modulation: Code Construction and Convergence Analysis,” IEEE Transactions on Wireless Communications, vol. 6, no. 5, pp. 1953–1963, May 2007.

DOI: 10.1109/TWC.2007.05698 · Author copy: southampton.ac.uk/~sxn/paper/ToW052007.pdf

A shorter version appeared at IEEE VTC 2005 Fall.

All visuals are original code-drawn illustrations. Fig. 8 and Fig. 10 data were traced from the published plots (approximate) and redrawn.

EXIT curves away from 4 dB, the hero animation and the fade, sync and running-sum demos are illustrative simplifications. The Huffman code in Chapter 2 is our own example.

© of the original article: IEEE 2007.

Topics in this iPaper

Engineering
The wireless communication systems of future generations are required to provide reliable transmissions at high data rates

Section I (Introduction), page 1953

Computer science
it is often more efficient to use jointly designed source and channel encoders.

Section I (Introduction), page 1953

space time coding
we propose a jointly designed source coding and Space Time Coded Modulation (STCM) scheme

Section I (Introduction), page 1953

multiple input multiple output
the high channel capacity potential of Multiple-Input Multiple-Output (MIMO) channels

Section I (Introduction), page 1953

joint source channel coding
a jointly designed iteratively decoded scheme combining source coding, channel coding, modulation as well as spatial diversity/multiplexing

Abstract, page 1953

variable length codes
two dimensional (2D) Variable Length Codes (VLCs)

Section I (Introduction), page 1953

iterative decoding
Non-binary unity-rate precoders are employed for assisting the iterative decoding of the VL-STCM-ID scheme.

Abstract, page 1953

extrinsic information transfer charts
requires the employment of novel three Dimensional (3D) non-binary EXIT charts

Section VI (Convergence Analysis), page 1958

trellis coded modulation
Since VL-STCM also belongs to the TCM family

Section I (Introduction), page 1954

rayleigh fading
when communicating over uncorrelated Rayleigh fading channels using BPSK

Section VII (Simulation Results), page 1961

Iteratively Decoded Variable Length Space-Time Coded Modulation: Code Construction and Convergence Analysis — Interactive explanation | iPaper.ai