Chapter 6: Turbo & LDPC Codes

For 45 years after Shannon's 1948 paper, the best known codes were still 3 dB or more from his theoretical limit. Then in 1993, Berrou et al. announced turbo codes—a construction so close to Shannon capacity that many researchers suspected an error. This chapter explains how iterative decoding, sparse graph codes, and polar codes finally conquered the Shannon limit.

Turbo Codes

A turbo code (Berrou, Glavieux & Thitimajshima, 1993) uses two or more convolutional codes connected through an interleaver. The key breakthrough was the iterative (turbo) decoding algorithm that passes soft information back and forth between component decoders.

Parallel Concatenated Structure

The message \( u \) is fed to two recursive systematic convolutional (RSC) encoders. Encoder 2 receives a permuted (interleaved) copy \( \Pi(u) \).

The transmitted codeword is \( (u, v_1, v_2) \):

\( u \): systematic (message) bits
\( v_1 \): parity from RSC encoder 1
\( v_2 \): parity from RSC encoder 2 (on permuted input)

Rate: \( R = 1/3 \) (or higher with puncturing).

Iterative (BCJR) Decoding

Each component decoder computes Log-Likelihood Ratios (LLRs)using the BCJR (forward-backward) algorithm:

\( L(u_t) = \log \frac{P(u_t=1 \mid r)}{P(u_t=0 \mid r)} \)

Decoder 1 computes an extrinsic LLR, passes it (after interleaving) as a prior to Decoder 2. Decoder 2 returns its extrinsic LLR (after de-interleaving) to Decoder 1. After ~10 iterations, the combined LLR gives a near-MAP decision.

Why Does It Work? The "Turbo" Intuition

The interleaver breaks up burst errors. What looks like a strong constraint for one encoder is a spread-out, weak constraint for the other, and vice versa. As soft information passes between decoders, each iteration refines the estimate — like a turbocharger recycling exhaust energy.

The weight enumerator of a good turbo code has a large free distance growing with block length, ensuring exponentially decreasing error rate. Berrou's original code operated at \( E_b/N_0 = 0.7 \text{ dB} \) for BER \( 10^{-5} \)— just 0.5 dB from the Shannon limit at rate 1/3.

LDPC Codes & Tanner Graphs

Low-Density Parity-Check (LDPC) codes were invented by Gallager (1962) but ignored for 30 years. MacKay and Neal (1996) rediscovered them and showed they approach Shannon capacity under belief propagation (sum-product) decoding.

Definition

An LDPC code is a linear code defined by a sparseparity-check matrix \( H \). Each row has exactly \( d_c \) ones (check node degree); each column has exactly \( d_v \) ones (variable node degree).

Regular \( (d_v, d_c) \)-LDPC: all variable nodes have degree \( d_v \), all check nodes have degree \( d_c \). Rate: \( R = 1 - d_v/d_c \).

Sparsity means \( O(n) \) edges in the Tanner graph — enabling\( O(n) \) encoding and decoding complexity.

Belief Propagation (Sum-Product)

Messages are LLRs passed along Tanner graph edges. Each iteration:

Variable → check: Sum of all incoming check messages plus channel LLR, minus the receiving check's own message.
Check → variable: \( \tanh \)-product rule: \( L_{c \to v} = 2 \tanh^{-1}\!\bigl(\prod_{v' \neq v} \tanh(L_{v' \to c}/2)\bigr) \)
Hard-decide on variable node marginals; stop if all parity checks satisfied.

Tanner Graph for a (3,6)-regular LDPC code — variable nodes (circles) connected to check nodes (squares)

Why LDPC Codes Are Capacity-Achieving

Richardson & Urbanke (2001) proved via density evolutionthat LDPC codes with optimised degree distributions achieve the BEC (binary erasure channel) capacity exactly, and come within a small gap of AWGN capacity. The analysis tracks the distribution of LLR messages across iterations as \( n \to \infty \).

The EXIT chart (extrinsic information transfer) provides a visual tool: plotting check and variable node transfer curves, capacity-approaching codes correspond to configurations where the two curves just touch — a "turbo cliff" in BER performance.

Polar Codes — Provably Capacity-Achieving

Polar codes (Arıkan, 2009) are the first family of error-correcting codes with a constructive, efficient proof of capacity achievement— not just existential arguments. They exploit the phenomenon of channel polarisation.

Channel Polarisation

Apply the recursive Hadamard-like transform:

\( G_N = F^{\otimes \log_2 N}, \quad F = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \)

After \( n = \log_2 N \) levels of combining and splitting, \( N \)copies of a B-DMC with capacity \( C \) polarise into:

\( CN \) near-perfect channels (capacity \( \approx 1 \))
\( (1-C)N \) near-useless channels (capacity \( \approx 0 \))

Encoding & Decoding

Frozen bits: Fix the \( (1-C)N \)bad channels to known constants (typically 0). Only transmit information on the \( CN \)good channels.

Encoding: \( x = u G_N \pmod{2} \), where\( u \) places data bits in good positions, frozen bits elsewhere. Complexity: \( O(N \log N) \).

Successive Cancellation (SC) Decoding: Decode bits sequentially, using already-decoded bits as side information for later decisions. Complexity: \( O(N \log N) \). SCL (list decoding) + CRC improves finite-length performance.

Capacity Achievement Theorem (Arıkan)

For any B-DMC with capacity \( C \) and any \( \beta < 1/2 \):

\( P_e^{(N)} \leq O\!\left(2^{-N^\beta}\right) \quad \text{as } N \to \infty \)

The block error probability decays super-polynomially, and the rate approaches \( C \). Unlike turbo/LDPC, this is a rigorous proof that the code family is capacity-achieving, not an empirical observation.

Polar Codes in Practice: 5G NR

The 5G New Radio standard (3GPP Release 15, 2018) adopted polar codes for the control channel(PBCH, PUCCH, PDCCH) and LDPC codes for the data channel. Polar codes won due to superior short-block performance — an irony that Gallager's 1962 LDPC codes, forgotten for 30 years, now run alongside Arıkan's 2009 polar codes in every modern smartphone.

Modern Codes: A Comparison

Property	Turbo	LDPC	Polar
Gap to Shannon limit	~0.5 dB	~0.1 dB	Provably 0
Decoding algorithm	BCJR + turbo iteration	Belief propagation	Successive cancellation (SC/SCL)
Encoder complexity	\( O(n) \)	\( O(n) \)	\( O(n \log n) \)
Capacity proof	Empirical	Density evolution	Rigorous (Arıkan)
Error floor	Yes (at very low BER)	Yes (cycles in graph)	None with SCL+CRC
Best for block size	Medium (1k–10k)	Large (>1k)	Short–medium
Standard adoption	3G UMTS, 4G LTE	5G data, Wi-Fi, CCSDS	5G control (NR)

Python: BER vs SNR — Uncoded, Hamming, and Repetition Codes

Simulate bit error rate (BER) performance over an AWGN channel for three schemes: uncoded BPSK, Hamming(7,4), and a rate-1/3 repetition code with majority-vote decoding. Visualise BER curves and the coding gain achieved by each scheme at a target BER of 10⁻³.

Python

script.py186 lines

import numpy as np
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt

rng = np.random.default_rng(42)

def awgn(signal, snr_db):
    """Add white Gaussian noise for given Eb/N0 in dB."""
    snr_linear = 10 ** (snr_db / 10)
    sigma = np.sqrt(1 / (2 * snr_linear))
    return signal + rng.normal(0, sigma, signal.shape)

def bpsk_modulate(bits):
    return 2 * bits.astype(float) - 1   # 0 -> -1, 1 -> +1

def hard_decide(received):
    return (received >= 0).astype(int)

# ── Uncoded BPSK ───────────────────────────────────────────────
def simulate_uncoded(snr_db, N=100_000):
    bits = rng.integers(0, 2, N)
    tx = bpsk_modulate(bits)
    rx = awgn(tx, snr_db)
    decoded = hard_decide(rx)
    return np.mean(bits != decoded)

# ── Hamming(7,4) ──────────────────────────────────────────────
G = np.array([
    [1,0,0,0,1,1,0],
    [0,1,0,0,1,0,1],
    [0,0,1,0,0,1,1],
    [0,0,0,1,1,1,1],
], dtype=int)
H = np.array([
    [1,1,0,1,1,0,0],
    [1,0,1,1,0,1,0],
    [0,1,1,1,0,0,1],
], dtype=int)

syndrome_lut = {}
for i in range(7):
    e = np.zeros(7, dtype=int)
    e[i] = 1
    s = tuple(H @ e % 2)
    syndrome_lut[s] = i

def hamming_encode_block(msg4):
    return msg4 @ G % 2

def hamming_decode_block(r7):
    s = tuple(H @ r7 % 2)
    c = r7.copy()
    if any(s):
        pos = syndrome_lut.get(s)
        if pos is not None:
            c[pos] ^= 1
    return c[:4]

def simulate_hamming(snr_db, N_msgs=30_000):
    # Rate = 4/7, so Eb/N0 adjusted for code rate
    effective_snr = snr_db + 10*np.log10(4/7)
    msgs    = rng.integers(0, 2, (N_msgs, 4))
    encoded = np.array([hamming_encode_block(m) for m in msgs])
    tx      = bpsk_modulate(encoded)
    rx      = awgn(tx, effective_snr)
    rx_hard = hard_decide(rx)
    decoded = np.array([hamming_decode_block(r) for r in rx_hard])
    errors  = np.sum(msgs != decoded)
    return errors / (N_msgs * 4)

# ── Rate-1/3 Repetition Code ──────────────────────────────────
def simulate_repetition3(snr_db, N=100_000):
    # Rate = 1/3: each bit sent 3 times; effective Eb/N0 shifted by 10log10(1/3)
    effective_snr = snr_db + 10*np.log10(1/3)
    bits = rng.integers(0, 2, N)
    encoded = np.repeat(bits, 3)
    tx = bpsk_modulate(encoded)
    rx = awgn(tx, effective_snr)
    rx_hard = hard_decide(rx).reshape(-1, 3)
    # Majority vote
    decoded = (rx_hard.sum(axis=1) >= 2).astype(int)
    return np.mean(bits != decoded)

# ── Run Simulation ──────────────────────────────────────────────
snr_range = np.arange(0, 11, 1)
print("=" * 60)
print("BER vs Eb/N0 SIMULATION (BPSK, AWGN)")
print("=" * 60)
print(f"{'Eb/N0 (dB)':<14} {'Uncoded':>12} {'Hamming(7,4)':>14} {'Rep-3':>10}")
print("-" * 54)

ber_uncoded   = []
ber_hamming   = []
ber_rep3      = []

for snr in snr_range:
    bu = simulate_uncoded(snr)
    bh = simulate_hamming(snr)
    br = simulate_repetition3(snr)
    ber_uncoded.append(max(bu, 1e-6))
    ber_hamming.append(max(bh, 1e-6))
    ber_rep3.append(max(br, 1e-6))
    print(f"{snr:<14.1f} {bu:>12.2e} {bh:>14.2e} {br:>10.2e}")

print()
print("Codes and rates:")
print("  Uncoded BPSK:   Rate 1.0  (no redundancy)")
print("  Hamming(7,4):   Rate 4/7 ≈ 0.571  (corrects 1 error/7 bits)")
print("  Repetition-3:   Rate 1/3 ≈ 0.333  (majority vote over 3 copies)")

# ── Figure ────────────────────────────────────────────────────
fig, axes = plt.subplots(1, 2, figsize=(14, 6))
fig.patch.set_facecolor('#0a0a0f')
for ax in axes:
    ax.set_facecolor('#0d1117')
    for spine in ax.spines.values():
        spine.set_edgecolor('#334155')

# ── Plot 1: BER curves ──
axes[0].semilogy(snr_range, ber_uncoded, 'o-', color='#f87171', linewidth=2.5, markersize=7, label='Uncoded BPSK (R=1)')
axes[0].semilogy(snr_range, ber_rep3,    's-', color='#facc15', linewidth=2.5, markersize=7, label='Repetition-3 (R=1/3)')
axes[0].semilogy(snr_range, ber_hamming, '^-', color='#4ade80', linewidth=2.5, markersize=7, label='Hamming(7,4) (R=4/7)')

# Theoretical uncoded BER for BPSK
from scipy.special import erfc as _erfc
snr_fine = np.linspace(0, 10, 200)
ber_theory = 0.5 * _erfc(np.sqrt(10**(snr_fine/10)))
axes[0].semilogy(snr_fine, ber_theory, '--', color='#f87171', linewidth=1.2, alpha=0.5, label='Theory (uncoded)')

axes[0].set_xlabel('Eb/N0 (dB)', color='#94a3b8', fontsize=11)
axes[0].set_ylabel('Bit Error Rate (BER)', color='#94a3b8', fontsize=11)
axes[0].set_title('BER vs Eb/N0 — AWGN Channel', color='#818cf8', fontsize=12, fontweight='bold')
axes[0].legend(facecolor='#1e2030', edgecolor='#334155', labelcolor='#c7d2fe', fontsize=9)
axes[0].tick_params(colors='#94a3b8')
axes[0].set_xlim(0, 10)
axes[0].set_ylim(1e-5, 0.6)
axes[0].grid(True, which='both', color='#1e293b', linewidth=0.6)
axes[0].axhline(1e-5, color='#334155', linewidth=0.5)

# Shade "Shannon limit" region
axes[0].axvline(0.187, color='#a78bfa', linestyle=':', linewidth=1.5, alpha=0.7)
axes[0].text(0.4, 2e-5, 'Shannon\nlimit\n(R=1)', color='#a78bfa', fontsize=8, va='bottom')

# ── Plot 2: Coding gain illustration ──
target_ber = 1e-3
# Find SNR needed for each code to reach ~1e-3 BER (interpolate)
def find_snr_at_ber(snr_arr, ber_arr, target):
    for i in range(len(ber_arr)-1):
        if ber_arr[i] >= target >= ber_arr[i+1]:
            frac = (target - ber_arr[i]) / (ber_arr[i+1] - ber_arr[i])
            return snr_arr[i] + frac * (snr_arr[i+1] - snr_arr[i])
    return None

snr_unc  = find_snr_at_ber(snr_range, ber_uncoded, target_ber)
snr_ham  = find_snr_at_ber(snr_range, ber_hamming, target_ber)
snr_rep  = find_snr_at_ber(snr_range, ber_rep3,    target_ber)

labels  = ['Uncoded\n(R=1)', 'Rep-3\n(R=1/3)', 'Hamming(7,4)\n(R=4/7)']
snr_vals = [snr_unc, snr_rep, snr_ham]
bar_colors = ['#f87171', '#facc15', '#4ade80']
valid = [(l, v, c) for l, v, c in zip(labels, snr_vals, bar_colors) if v is not None]
lbls, vals, cols = zip(*valid)

bars = axes[1].barh(range(len(vals)), vals, color=cols, edgecolor='#1e1e2e', height=0.5)
axes[1].set_yticks(range(len(vals)))
axes[1].set_yticklabels(lbls, color='#94a3b8', fontsize=10)
axes[1].set_xlabel('Eb/N0 required for BER = 10⁻³ (dB)', color='#94a3b8', fontsize=10)
axes[1].set_title('Coding Gain Comparison', color='#818cf8', fontsize=12, fontweight='bold')
axes[1].tick_params(colors='#94a3b8')
for bar, val in zip(bars, vals):
    axes[1].text(val + 0.1, bar.get_y() + bar.get_height()/2,
                  f'{val:.1f} dB', va='center', color='#e2e8f0', fontsize=10)
if snr_unc and snr_ham:
    gain = snr_unc - snr_ham
    axes[1].annotate(f'Coding gain\n≈ {gain:.1f} dB',
                      xy=(snr_ham, 1.5), xytext=(snr_ham - 2.5, 2.3),
                      color='#4ade80', fontsize=9,
                      arrowprops=dict(arrowstyle='->', color='#4ade80'))

plt.suptitle('Channel Coding: BER Performance in AWGN', color='#c7d2fe', fontsize=13, fontweight='bold', y=1.01)
plt.tight_layout()
plt.savefig('output.png', dpi=150, bbox_inches='tight', facecolor='#0a0a0f')
plt.close()
print()
print("Plot saved to output.png")

Click Run to execute the Python code

Code will be executed with Python 3 on the server

← Ch 5: Error-Correcting Codes Ch 7: Differential Entropy →