Make your paper interactiveCreate

Text from the interactive explanation

TTCM Assisted Genetic-Algorithm Aided Reduced-complexity Multiuser Detection

S. X. Ng, K. Yen, L. Hanzo

Original paper

Ng, Yen & Hanzo · Electronics Letters · 2002

Ten phones talk at once on one frequency. To untangle them perfectly, a listener would have to check every combination of what they might have sent: over a million for every symbol, or a trillion with richer 16-point signals. This paper breeds the answer instead.

Could a cell tower untangle many phones sharing one frequency nearly as well as a perfect, exhaustive detector — with millions of times less work?

received signal: 31 chips, in-phase (top) and quadrature (bottom) halves

signal rebuilt from the best guess so far

mismatch between the two

each row is one guess (one tile per phone, colour = symbol), fittest on top; amber glow = best

outlined row: what the phones really sent; dots turn green where the best guess is right

Live simulation in your browser: virtual phones, random noise, a real genetic algorithm (settings from the paper's Table 1).

Chapter 1

Sharing the air

The paper studies the uplink of a CDMA mobile network: several phones transmit to one cell tower at the same moment, on the same frequency band. Each phone sends a stream of symbols. With QPSK a symbol is one of 4 points on a map called a constellation and carries 2 bits; with 16QAM it is one of 16 points and carries 4 bits.

To keep the phones apart, each multiplies every symbol by its own signature: a fast pattern of 31 “chips”, each +1 or −1. In the air all these patterns simply add up, together with random background hiss (noise).

The tower's simplest trick is a matched filter: multiply what arrives by one phone's signature, chip by chip, and add everything up. That phone's own contribution adds up perfectly; the others mostly cancel. Mostly. Signatures are never perfectly distinct, so a little of every other phone leaks in: crosstalk.

crosstalk on phone 1: 0.00

Press “Send 500 symbols” to test the matched filter.

Add phones one by one, then press “Send 500 symbols”. What happens to the cloud?

With one phone the cloud is a tight ball of noise around each point. Every extra phone adds another leak, the cloud smears, and points start landing in the wrong quadrant even when noise is low. Listening to one phone at a time ignores what the others are doing. The fix: decide all phones together.

Chapter 2

The perfect listener

Instead of treating the other phones as noise, the tower can ask a better question: which combination of symbols, from all phones together, best explains what I received? Rebuild the signal each combination would have produced, compare it with what arrived, keep the closest. That is the maximum-likelihood or optimum multiuser detector (MUD). Try being it.

Untangle three phones

Three phones each sent one of four QPSK symbols. Pick a symbol for every phone so the amber rebuilt signal lies on the cyan received one.

mismatch: –

‖received − rebuilt‖², lower is better

The perfect listener would test all 4 × 4 × 4 = 64 combinations and keep the one with the smallest mismatch.

Picking the combination that best explains the signal is exactly what the optimum detector does, and with three phones it is easy: 64 checks. The trouble is how that number grows.

Predict

Ten phones, each sending one of 16 symbols (16QAM). How many combinations must the perfect listener test, for every single symbol?

Make a guess.

The explosion

64

Chapter 3

Evolve, don't enumerate

Ng, Yen and Hanzo search the haystack the way nature does. A genetic algorithm (GA) keeps a small population of guesses. Each guess is a chromosome with one gene per phone: that phone's symbol, written as bits.

The paper's settings (its Table 1): a population of P = K·M guesses, stopped after Y = ½·K·M generations, where K is the number of phones and M the number of constellation points. For six phones using QPSK that is 24 guesses × 12 generations = 288 checks, instead of 46 = 4,096.

The GA lab

generation 1 / 12

24 guesses checked vs 4,096 for the perfect listener

searching…

The tower receives r (t) = Σk bk ak(t) + n(t). Matched filters give z = (z1 … zK), and the signatures' overlaps form the K×K cross-correlation matrix R . For a candidate vector of symbols b (the channel C is the identity over AWGN):

LLF( b ) = −‖ r − A b ‖² / (2σ²) = [Ω( b ) − ‖ r ‖²] / (2σ²)

Ω( b ) = 2·Re[ b H C * z ] − b H C * R C b

optimum decision: b̂ = arg max b Ω( b ) over all MK vectors

The GA uses exp(Ω( b )) as its fitness and returns one best vector b̂ , a hard decision. Each phone's channel decoder then receives the metrics

Pk,m = −|b̂k − bk,m|² / (2σ²), m = 1 … M.

A soft metric for symbol m of phone k would instead add up exp(LLF( b )) over every vector b whose k-th symbol is m: that needs all MK vectors, the full search the GA avoids. In our pictures, “mismatch” is ‖ r − A b ‖² = ‖ r ‖² − Ω( b ).

Chapter 4

How many guesses are enough?

How big must the population be, and for how many generations should it breed? The authors report a rule of thumb found in simulations that, for lack of space, are not shown in the letter: P ≈ K·M and Y ≈ ½·K·M , so about ½·K²·M² fitness checks per symbol give performance similar to the optimum detector.

Rerun that experiment here. Each cell is one choice of population and generations; clicking it runs the GA on a fixed set of 60 noisy signals and counts how often its answer agrees with the exhaustive search.

Preparing 60 signals and their exhaustive answers…

Click a cell to run the GA on all 60 signals.

Chapter 5

A safety net that costs no extra bandwidth

Even a perfect detector makes mistakes when the noise is strong. Error-correcting codes add carefully chosen check bits so the receiver can repair mistakes. The usual price: more bits to send, so either slower data or more symbols per second, which needs a wider slice of radio spectrum.

Turbo trellis coded modulation (TTCM), a code “with a structure similar to binary turbo codes”, avoids that price by tucking the check bit into a bigger alphabet. To carry 1 data bit per symbol it sends QPSK (1 data bit + 1 check bit) instead of plain BPSK; to carry 3 data bits it sends 16QAM (3 + 1) instead of plain 8PSK. Same symbols per second, same bandwidth.

Bandwidth for the same data rate

How a trellis code repairs mistakes

A trellis code's check bits depend on the recent past, so only some sequences of symbols are allowed. The decoder picks the allowed sequence closest to what it received. Hit a symbol with a burst of noise and watch the decoder route around it.

Hard and soft decisions

A decoder works best when it knows not just what the detector decided but how sure it was. The optimum detector can supply that confidence, a soft decision, by weighing every combination. The GA hands over only its best guess, a hard decision: a single dot instead of a glowing cloud of confidence. That is part of what it trades for speed, and the evidence below shows the price.

Chapter 6

The evidence

The authors simulated the whole chain (TTCM encoding, CDMA spreading over 31 chips, the GA detector, turbo decoding) on a channel that adds random noise only (AWGN), in packets of 1000 symbols. Their Figure 2 plots the bit error rate against signal strength.

BER = fraction of bits received wrong (10⁻⁴ = 1 in 10,000). Eb/N0 = signal energy per bit compared with noise, in decibels: +3 dB ≈ twice the power.

≈0.3 dB The optimum detector with 4 phones loses only about 0.3 dB compared with a phone that has the band to itself.

≈1 dB / ≈3 dB With 10 phones, the GA detector loses about 1 dB against a lone phone with hard decisions, and about 3 dB against a lone phone with soft decisions, for QPSK and 16QAM alike.

3.8 dB / 2.9 dB At a BER of 10⁻⁴, ten phones using TTCM with the GA detector need 3.8 dB (QPSK) and 2.9 dB (16QAM) less Eb/N0 than a single uncoded phone using BPSK or 8PSK at the same 1 and 3 bits per symbol, without extra bandwidth.

Checks per symbol

Chapter 7

Back to the air

Ten phones, 16QAM, one symbol period. On the left, the perfect listener works through all 1,099,511,627,776 combinations. On the right, the GA with the paper's settings (160 guesses × 80 generations = 12,800 checks) works on a fresh simulated signal. Both check at the same rate.

Race starting…

So, could a tower untangle many phones nearly as well as a perfect listener, with far less work? In the authors' simulations, yes. Their GA detector runs on a budget of about ½·K²·M² checks instead of MK, which for ten phones is about 1,310 times fewer checks with QPSK and millions of times fewer with 16QAM, and performs similarly to the optimum detector: with ten phones sharing the band it came within about 1 dB of a lone phone using the same code with hard decisions.

Paired with TTCM, which buys error protection with a bigger alphabet instead of extra bandwidth, ten phones at a BER of 10⁻⁴ needed 3.8 dB (QPSK) and 2.9 dB (16QAM) less signal energy per bit than a single uncoded phone at the same throughput (simulated over AWGN channels).

Source

The paper

S. X. Ng, K. Yen and L. Hanzo, “TTCM Assisted Genetic-Algorithm Aided Reduced-complexity Multiuser Detection”, Electronics Letters, vol. 38, no. 14, pp. 722–724, 4 July 2002. doi: 10.1049/el:20020489.

Author manuscript, University of Southampton: southampton.ac.uk/~sxn/paper/11-el02.pdf. All research credit belongs to the authors.

What is what on this page

Reported Numbers and curves from the paper: the GA settings of Table 1, the complexity rule of thumb, the reduction factors and the bit-error-rate results of Figure 2 (data points digitized and replotted).

Live simulation Our in-browser re-creation of the paper's model: real CDMA sums with 31-chip Gold signatures (our choice; the letter specifies 31 chips but not the family), random noise, a real genetic algorithm with the Table 1 settings and a real exhaustive search, on our own toy problems. It does not include the TTCM decoder.

Illustration The small trellis-code demo, the hard/soft sketch and the one-check-per-nanosecond time comparisons.

Figure 2 data digitized and replotted from the paper. The uncoded BPSK and 8PSK reference curves are computed from standard formulas.

Topics in this iPaper

Engineering
The optimal Code Division Multiple Access (CDMA) Multiuser Detector (MUD)[1] based on the Maximum-Likelihood (ML) detection rule performs an exhaustive search

Introduction, page 1

Computer science
Genetic Algorithms (GAs) have been used for efficiently solving combinatorial optimisation problems in numerous applications

Introduction, page 1

multiuser detection
Genetic-Algorithm aided reduced-complexity Multiuser Detection (TTCM-GA-MUD)

Abstract, page 1

code division multiple access
We consider a synchronous CDMA uplink system as illustrated in Figure 1

TTCM-GA-MUD section, page 1

genetic algorithms
The configuration of the GA employed in our system is shown in Table 1.

TTCM-GA-MUD section, page 2

turbo trellis coded modulation
Turbo Trellis Coded Modulation (TTCM) [5] is a channel coding scheme

Introduction, page 1

maximum likelihood detection
The decision rule for the optimum-MUD scheme based on the ML criterion

TTCM-GA-MUD section, page 2

TTCM Assisted Genetic-Algorithm Aided Reduced-complexity Multiuser Detection — Interactive explanation | iPaper.ai