Channel capacity and error-control coding

Every result so far has traded one resource for another: bandwidth for noise performance in FM, power for bits per symbol in QAM, air time for range in the choice of data rate. In 1948 Claude Shannon showed that behind all these trades lies a single hard limit, the capacity of the channel. Below capacity, information can be sent with as few errors as desired by coding cleverly enough; above it, errors are unavoidable however clever the design. This lesson introduces information and entropy, the capacity of the binary symmetric and Gaussian channels, the bandwidth-power plane and the Shannon limit on E_b/N₀, and then the practical tools that approach the limit: error-detecting and error-correcting codes, interleaving and retransmission.

For the TLR-1, the question is practical. Lesson 9 put the pole receiver's requirement at about −105 dBm for one failed packet in a thousand with uncoded GFSK. Daniel asks how much better a radio could possibly do at 50 kb/s, and whether the forward error correction offered by the transceiver chips is worth turning on. Shannon's theory answers the first question; coding theory answers the second.

Information and entropy

Shannon measured information by surprise. An event of probability p carries log₂(1/p) bits of information: a certain event carries none, a fair coin toss carries one bit, and a rare event carries many. The entropy H of a source is the average information per symbol, the expected surprise. It is largest when all symbols are equally likely and smaller when some are much more probable than others. Entropy is the minimum average number of bits per symbol needed to represent the source without loss, and source coding methods such as Huffman coding and the compression algorithms in file formats approach it.

The TLR-1's traffic shows why this matters. A pole station's status report sends the same fault code, normally all clear, almost every time. If all clear has probability 0.97 and three fault codes share the rest, the entropy is only about 0.24 bits per report, so a well-designed protocol sends a one-bit heartbeat when nothing has changed and the full code only on a change. Source coding saves air time before channel coding spends it.

Capacity of a binary symmetric channel

The simplest channel model, the binary symmetric channel (BSC), flips each bit independently with probability p. It describes a hard-decision demodulator followed by a decision device. Its capacity, the largest information rate that can be sent reliably per channel use, is one bit minus the entropy of the noise. A channel with p = 0.01 has capacity 0.919 bits per use: a code of rate up to about 0.92 can, in principle, make errors as rare as desired. A channel with p = 0.5 has capacity zero, since its output is independent of its input.

Capacity of the Gaussian channel

For a channel of bandwidth B with additive white Gaussian noise and an average signal power P, Shannon's capacity formula gives the maximum error-free bit rate. It contains the two resources of a link, bandwidth and SNR, and shows that they are not equal partners: capacity grows linearly with bandwidth but only logarithmically with SNR. Doubling the power adds about one bit per second per hertz at high SNR; doubling the bandwidth nearly doubles the capacity at high SNR, but at low SNR the extra noise collected cancels much of the gain.

The second expression is the capacity with unlimited bandwidth: even an infinitely wide channel has finite capacity, because the noise grows with the bandwidth. It is the regime of deep-space probes, which have tiny received power and plenty of spectrum.

The bandwidth-power plane and the Shannon limit

Writing P = E_b R and requiring R ≤ C, with spectral efficiency η = R/B in b/s/Hz, gives the minimum E_b/N₀ for reliable communication at a given spectral efficiency. As η falls toward zero, using more and more bandwidth per bit, the minimum approaches ln 2, or −1.59 dB. No scheme, however wide its bandwidth or long its code, can work reliably below this Shannon limit. At η = 1 b/s/Hz the limit is 0 dB; at η = 6, appropriate to 64-QAM, it is about 10 dB.

The figure puts the modulations of lessons 8 and 9 in perspective. Uncoded BPSK at an error rate of 10⁻⁶ needs 10.5 dB, while the Shannon limit at its spectral efficiency is close to −1 dB, a gap of more than 11 dB. That gap is the opportunity for error-control coding. For the TLR-1, which uses a tiny fraction of the available spectrum, the theoretical limit is near −1.6 dB, so coding could in principle save more than 15 dB relative to uncoded non-coherent FSK. Practical codes for short packets recover a few decibels of it.

Error-control coding

A channel code adds redundant bits to the data so that errors can be detected or corrected. A block code maps each block of k data bits to an n-bit code word; its rate is r = k/n and its redundancy is n − k bits. The Hamming distance between two code words is the number of positions in which they differ, and the minimum distance d_min of the code over all pairs sets its power. A code with minimum distance d_min can detect up to d_min − 1 errors, or correct up to t = ⌊(d_min − 1)/2⌋ errors, because a received word with t or fewer errors is still closer to the sent code word than to any other.

The simplest example is a single parity bit, which makes the number of ones even. Its minimum distance is 2, so it detects any single error but cannot locate it. The Hamming (7,4) code adds three parity bits to four data bits, each parity bit covering a different subset, so that the pattern of failed checks, the syndrome, points directly at the position of a single error. With d_min = 3 it corrects any single error in a block of seven. Its rate is 4/7, so it costs 75 percent more bits for the same data.

Detecting errors: the CRC

A cyclic redundancy check (CRC) is a block code designed for detection. The message is treated as a polynomial over binary arithmetic and divided by a fixed generator polynomial; the remainder is appended. The receiver repeats the division and checks for a zero remainder. A 16-bit CRC detects all single and double errors, all errors in an odd number of bits for common generators, all bursts of 16 bits or fewer, and all but about one in 65 536 of other error patterns. Nearly every packet radio, including the TLR-1, ends each packet with one, and the receiver discards any packet that fails it. A discarded packet is lost, but a corrupted packet accepted as good, such as a phantom button press, would be far worse.

import math, random
H = lambda ps: -sum(p * math.log2(p) for p in ps if p > 0)
print(f"status report entropy: {H([0.97, 0.01, 0.01, 0.01]):.3f} bits")
print(f"BSC capacity at p = 0.01: {1 - H([0.01, 0.99]):.3f} bits/use")
B, snr_db = 67.5e3, 10.0
print(f"AWGN capacity of 67.5 kHz at 10 dB SNR: {B * math.log2(1 + 10**(snr_db/10))/1e3:.0f} kb/s")
for eta in (0.01, 0.5, 1, 2, 4, 6):
    print(f"spectral efficiency {eta:5.2f} b/s/Hz: Shannon limit Eb/N0 = {10*math.log10((2**eta - 1)/eta):6.2f} dB")
# Hamming (7,4): positions 1..7, parity bits at 1, 2, 4
def encode(d):
    c = [0, 0, d[0], 0, d[1], d[2], d[3]]
    for p in (1, 2, 4):
        c[p-1] = sum(c[i-1] for i in range(1, 8) if i & p and i != p) % 2
    return c
def decode(c):
    s = sum(p for p in (1, 2, 4) if sum(c[i-1] for i in range(1, 8) if i & p) % 2)
    c = c[:]
    if s: c[s-1] ^= 1
    return [c[2], c[4], c[5], c[6]]
ok = all(decode([b ^ (i == e) for i, b in enumerate(encode(d))]) == d
         for n in range(16) for d in ([(n >> k) & 1 for k in range(4)],) for e in range(-1, 7))
print("Hamming (7,4) corrects every single error in all 16 code words:", ok)
random.seed(4)
p, blocks = 0.01, 100000
unc = sum(any(random.random() < p for _ in range(4)) for _ in range(blocks))
cod = 0
for _ in range(blocks):
    d = [random.randint(0, 1) for _ in range(4)]
    r = [b ^ (random.random() < p) for b in encode(d)]
    cod += decode(r) != d
print(f"4-bit block error rate at p = 0.01: uncoded {unc/blocks:.4f}, Hamming coded {cod/blocks:.4f}")
def crc16(data, poly=0x1021, crc=0xFFFF):          # CRC-16/CCITT-FALSE
    for byte in data:
        crc ^= byte << 8
        for _ in range(8):
            crc = ((crc << 1) ^ poly) & 0xFFFF if crc & 0x8000 else (crc << 1) & 0xFFFF
    return crc
msg = b'POLE3 BTN2 PRESS'
print(f"CRC-16 of the message: 0x{crc16(msg):04X}; one bit flipped: 0x{crc16(bytes([msg[0] ^ 1]) + msg[1:]):04X}")
print(f"fraction of random error patterns undetected: about {2**-16:.1e}")

status report entropy: 0.242 bits
BSC capacity at p = 0.01: 0.919 bits/use
AWGN capacity of 67.5 kHz at 10 dB SNR: 234 kb/s
spectral efficiency  0.01 b/s/Hz: Shannon limit Eb/N0 =  -1.58 dB
spectral efficiency  0.50 b/s/Hz: Shannon limit Eb/N0 =  -0.82 dB
spectral efficiency  1.00 b/s/Hz: Shannon limit Eb/N0 =   0.00 dB
spectral efficiency  2.00 b/s/Hz: Shannon limit Eb/N0 =   1.76 dB
spectral efficiency  4.00 b/s/Hz: Shannon limit Eb/N0 =   5.74 dB
spectral efficiency  6.00 b/s/Hz: Shannon limit Eb/N0 =  10.21 dB
Hamming (7,4) corrects every single error in all 16 code words: True
4-bit block error rate at p = 0.01: uncoded 0.0393, Hamming coded 0.0022
CRC-16 of the message: 0x7330; one bit flipped: 0xDB14
fraction of random error patterns undetected: about 1.5e-05

The output shows each idea at work. The status report's entropy is about a quarter of a bit. The 67.5 kHz channel at 10 dB SNR could carry about 234 kb/s in theory, almost five times the planned 50 kb/s. The Shannon limit runs from −1.59 dB at very low spectral efficiency to about 10 dB at 6 b/s/Hz. The Hamming decoder fixes every single error, and on a channel with p = 0.01 it cuts the 4-bit block error rate from about 4 percent to about 0.2 percent, even though it sends 75 percent more bits. Flipping a single bit of the message changes the CRC completely, so the receiver cannot miss it.

Coding gain and soft decisions

Correcting errors is not free: at a fixed transmitter power and data rate, a rate-r code spreads each bit's energy over 1/r channel bits, so each channel bit has energy rE_b and arrives with a higher raw error rate. A code is worthwhile only if its correction more than makes up for that. The coding gain is the reduction in E_b/N₀ needed for a target error rate compared with an uncoded system. Simple block codes with hard decisions give 1 to 3 dB. Decoding with soft decisions, using the demodulator's analog confidence rather than just its ones and zeros, adds roughly 2 dB more, which is why modern decoders accept soft inputs.

Convolutional codes encode a continuous stream: each output bit depends on the current input bit and a few previous ones, held in a shift register whose length is the constraint length K. The Viterbi algorithm decodes them by finding the most likely path through a trellis of encoder states. A rate-½ code with K = 7 gives about 5 dB of gain at 10⁻⁵ with soft decisions and was the standard in satellite and cellular systems for decades. Many sub-gigahertz transceivers include a rate-½ convolutional code with a short constraint length that gives a few dB. Turbo codes, introduced in 1993, and low-density parity-check (LDPC) codes, rediscovered at about the same time, came within about 1 dB of the Shannon limit for long blocks, and with polar codes they now protect cellular, Wi-Fi, satellite television and deep-space links.

Bursts, interleaving and ARQ

Codes designed for independent errors fail against bursts, where many bits in a row are wrong because of a fade or an interfering pulse. An interleaver shuffles the order of coded bits before transmission and the receiver unshuffles them, so a burst is spread across many code words, each of which sees only a few errors it can correct. The cost is delay, since the receiver must wait for the whole interleaving block.

Automatic repeat request (ARQ) takes the other approach: detect errors with a CRC and ask for a retransmission. It adapts automatically, costing air time only when errors occur, but needs a return channel and adds delay per retry. Hybrid ARQ combines both: forward error correction fixes most errors and ARQ handles the rest, and in its incremental-redundancy form the retransmissions send additional parity rather than repeating the packet. The TLR-1's short, latency-sensitive button messages suit simple ARQ with a CRC, which lesson 9 showed can turn a per-attempt PER of 10⁻³ into far less than one loss in a million, provided retries are spread out.