Chapter 5: Error-Correcting Codes

Real channels corrupt data. Error-correcting codes add structured redundancy so that receivers can not only detect but fix errors. From Richard Hamming's 1950 discovery that a mere 3 parity bits can protect 4 data bits, to Reed-Solomon codes guarding spacecraft telemetry, to the modern algebraic machinery underpinning every QR code and hard drive—this chapter builds the theory from first principles.

Hamming Distance & Sphere Packing

The Hamming distance \( d(x, y) \) between two binary strings is the number of positions in which they differ—equivalently, the weight of their XOR:

\( d(x, y) = \mathrm{wt}(x \oplus y) = \sum_{i=1}^n |x_i - y_i| \)

Minimum Distance & Error Correction

A code \( \mathcal{C} \) with minimum distance \( d_{\min} \):

Detects up to \( d_{\min} - 1 \) errors
Corrects up to \( t = \lfloor (d_{\min} - 1)/2 \rfloor \) errors
Corrects \( t \) errors and detects \( t+1 \) simultaneously if \( d_{\min} \geq 2t + 2 \)

Nearest-neighbour (minimum distance) decoding: choose codeword \( \hat{c} = \arg\min_{c \in \mathcal{C}} d(r, c) \).

The Sphere-Packing Bound (Hamming Bound)

A binary \( [n, k, d] \) code with \( 2^k \) codewords, each surrounded by a non-overlapping Hamming sphere of radius \( t \), satisfies:

\( 2^k \sum_{i=0}^{t} \binom{n}{i} \leq 2^n \)

Codes achieving equality are called perfect codes. Hamming codes are perfect: \( 2^{n-k} = n+1 \) (e.g., \( 2^3 = 8 = 7+1 \)for Hamming(7,4)).

Sphere Packing in Hamming Space — 2 codewords with radius-1 spheres (not overlapping when \( d_{\min} \geq 3 \))

Linear Codes: Generator & Parity-Check Matrices

A linear code \( [n, k, d] \) is a\( k \)-dimensional subspace of \( \mathbb{F}_2^n \). The \( 2^k \)codewords are exactly the rows of the coset \( \{mG : m \in \mathbb{F}_2^k\} \).

Generator Matrix \( G \)

A \( k \times n \) matrix whose rows form a basis for \( \mathcal{C} \). Encoding a message \( m \in \mathbb{F}_2^k \):

\( c = mG \pmod{2} \)

In systematic form \( G = [I_k \mid P] \), the first \( k \)bits of \( c \) are the message bits; the last \( n-k \) are parity bits.

Parity-Check Matrix \( H \)

An \( (n-k) \times n \) matrix satisfying \( GH^T = 0 \). For any codeword \( c \in \mathcal{C} \):

\( Hc^T = 0 \pmod{2} \)

The syndrome \( s = Hr^T \) of a received word \( r \)identifies the error pattern. If \( s = 0 \), no detectable error; otherwise\( s \) points to the corrupted bit.

Hamming(7,4): The Classic Example

Parameters: \( n=7, k=4, d_{\min}=3 \), rate \( R = 4/7 \approx 0.571 \)

G = [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]

Syndrome decoding: compute \( s = Hr^T \), look up in table to find error position.

H = [1 1 0 1 | 1 0 0
1 0 1 1 | 0 1 0
0 1 1 1 | 0 0 1]

The columns of \( H \) are the binary representations of 1–7. The syndrome \( s \)is the binary address of the erroneous bit — an elegant construction.

Reed-Solomon Codes

Reed-Solomon (RS) codes (1960) operate over finite fields \( \mathbb{F}_q \) and are Maximum Distance Separable (MDS): they achieve the Singleton bound \( d_{\min} = n - k + 1 \), the maximum possible minimum distance for given \( n \) and \( k \).

Construction

Choose distinct evaluation points \( \alpha_1, \ldots, \alpha_n \in \mathbb{F}_q \). A message \( (m_0, \ldots, m_{k-1}) \) defines a polynomial:

\( f(x) = m_0 + m_1 x + \cdots + m_{k-1} x^{k-1} \)

The codeword is the evaluations: \( c = (f(\alpha_1), \ldots, f(\alpha_n)) \). Since a nonzero polynomial of degree \( k-1 \) has at most \( k-1 \)roots, any two distinct codewords differ in at least \( n - k + 1 \) positions.

Applications

CDs/DVDs/Blu-ray: RS(255,251) corrects burst errors from scratches
QR codes: Up to 30% of data can be restored via RS error correction
Deep space: Voyager, Cassini use RS for telemetry over billions of km
RAID storage: RS parity enables recovery from multiple disk failures
DSL/5G: RS as outer code in concatenated schemes

The Gilbert-Varshamov Bound

A lower bound on the maximum code size: there exist binary \( [n, k, d] \) codes satisfying:

\( \frac{k}{n} \geq 1 - H_2\!\left(\frac{d-1}{n}\right) \)

where \( H_2(\delta) = -\delta \log_2 \delta - (1-\delta)\log_2(1-\delta) \)is the binary entropy function. The GV bound is existential—random codes achieve it, but constructing explicit codes meeting this bound for all parameters remains an open problem. LDPC codes (Chapter 6) provably achieve it under certain conditions.

Python: Hamming(7,4) Encoder & Decoder

Implement Hamming(7,4) from scratch using its generator and parity-check matrices. Encode messages, inject single-bit errors, perform syndrome decoding to correct them, and measure BER before and after correction across a range of channel flip probabilities.

Python

script.py212 lines

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

# ── Hamming(7,4) Implementation ───────────────────────────────
# Generator matrix G (4x7): codeword c = m @ G (mod 2)
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)

# Parity-check matrix H (3x7): H @ c^T = 0 (mod 2)
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 table: syndrome -> error position (1-indexed, 0 = no error)
syndrome_table = {}
for i in range(7):
    e = np.zeros(7, dtype=int)
    e[i] = 1
    s = tuple(H @ e % 2)
    syndrome_table[s] = i

def encode(msg_bits):
    """Encode a 4-bit message using Hamming(7,4)."""
    return np.array(msg_bits) @ G % 2

def inject_error(codeword, error_pos=None):
    """Flip one bit at error_pos (random if None)."""
    c = codeword.copy()
    pos = error_pos if error_pos is not None else random.randint(0, 6)
    c[pos] ^= 1
    return c, pos

def decode(received):
    """Syndrome decode: correct single-bit error, return (corrected, msg_bits, syndrome)."""
    r = np.array(received)
    s = tuple(H @ r % 2)
    corrected = r.copy()
    if any(s):
        err_pos = syndrome_table.get(s, -1)
        if err_pos >= 0:
            corrected[err_pos] ^= 1
    msg = corrected[:4]
    return corrected, msg, s

# ── Demo ──────────────────────────────────────────────────────
print("=" * 65)
print("HAMMING(7,4) ENCODER / DECODER DEMO")
print("=" * 65)
print()
print("Generator Matrix G (4×7):")
for row in G:
    print("  ", row)
print()
print("Parity-Check Matrix H (3×7):")
for row in H:
    print("  ", row)
print()
print(f"{'Message':>10}  {'Codeword':>15}  {'Received':>15}  {'Err Bit':>8}  {'Decoded':>10}  {'OK?':>4}")
print("-" * 70)

random.seed(42)
all_correct = 0
test_messages = [
    [0,0,0,0], [1,0,0,0], [0,1,0,0], [0,0,1,0], [0,0,0,1],
    [1,1,0,0], [1,0,1,0], [1,0,0,1], [0,1,1,0], [1,1,1,1],
]
for msg in test_messages:
    codeword = encode(msg)
    received, err_pos = inject_error(codeword)
    corrected, decoded, syndrome = decode(received)
    ok = np.array_equal(decoded, msg)
    if ok:
        all_correct += 1
    cw_str  = ''.join(map(str, codeword))
    rec_str = ''.join(map(str, received))
    msg_str = ''.join(map(str, msg))
    dec_str = ''.join(map(str, decoded))
    print(f"{msg_str:>10}  {cw_str:>15}  {rec_str:>15}  {err_pos+1:>8}  {dec_str:>10}  {'✓' if ok else '✗':>4}")

print()
print(f"Correctly decoded: {all_correct}/{len(test_messages)}")
print()

# ── Error rate over many trials ──
num_trials = 10000
errors_before = 0
errors_after  = 0
random.seed(0)
for _ in range(num_trials):
    msg = [random.randint(0,1) for _ in range(4)]
    codeword = encode(msg)
    received, _ = inject_error(codeword)
    # Uncorrected
    if not np.array_equal(received[:4], msg):
        errors_before += 1
    # Corrected
    _, decoded, _ = decode(received)
    if not np.array_equal(decoded, msg):
        errors_after += 1

print(f"Over {num_trials} random single-bit error trials:")
print(f"  BER before correction: {errors_before/num_trials:.4f}")
print(f"  BER after  correction: {errors_after/num_trials:.4f}")

# ── Hamming Distance Distribution ──
all_codewords = []
for m0 in range(2):
    for m1 in range(2):
        for m2 in range(2):
            for m3 in range(2):
                all_codewords.append(encode([m0,m1,m2,m3]))

distances = []
for i in range(len(all_codewords)):
    for j in range(i+1, len(all_codewords)):
        d = int(np.sum(np.abs(all_codewords[i] - all_codewords[j])))
        distances.append(d)

min_dist = min(distances)
print()
print(f"Number of codewords: {len(all_codewords)}")
print(f"Minimum Hamming distance d_min = {min_dist}")
print(f"Can detect up to {min_dist-1} errors, correct up to {(min_dist-1)//2} error(s)")

# ── Figure ────────────────────────────────────────────────────
fig, axes = plt.subplots(1, 3, figsize=(16, 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: Parity-check matrix heatmap ──
im = axes[0].imshow(H, cmap='Blues', aspect='auto', vmin=0, vmax=1)
axes[0].set_title('Parity-Check Matrix H (3×7)', color='#818cf8', fontsize=11, fontweight='bold')
axes[0].set_xlabel('Bit position', color='#94a3b8')
axes[0].set_ylabel('Parity equation', color='#94a3b8')
axes[0].set_xticks(range(7))
axes[0].set_xticklabels([f'r{i+1}' for i in range(7)], color='#94a3b8')
axes[0].set_yticks(range(3))
axes[0].set_yticklabels([f'p{i+1}' for i in range(3)], color='#94a3b8')
for i in range(3):
    for j in range(7):
        axes[0].text(j, i, str(H[i,j]), ha='center', va='center',
                     color='white' if H[i,j] else '#334155', fontsize=12, fontweight='bold')

# ── Plot 2: Hamming distance histogram ──
from collections import Counter
dist_counts = Counter(distances)
xs = sorted(dist_counts.keys())
ys = [dist_counts[x] for x in xs]
bar_colors = ['#ef4444' if x == min_dist else '#6366f1' for x in xs]
axes[1].bar(xs, ys, color=bar_colors, edgecolor='#1e1e2e', width=0.6)
axes[1].set_title('Pairwise Hamming Distances', color='#818cf8', fontsize=11, fontweight='bold')
axes[1].set_xlabel('Hamming distance', color='#94a3b8')
axes[1].set_ylabel('Count', color='#94a3b8')
axes[1].tick_params(colors='#94a3b8')
axes[1].axvline(min_dist - 0.3, color='#f472b6', linestyle='--', linewidth=1.5, label=f'd_min={min_dist}')
axes[1].legend(facecolor='#1e2030', edgecolor='#334155', labelcolor='#94a3b8', fontsize=9)

# ── Plot 3: BER comparison ──
# BER vs number of bit-flips per 7-bit word for uncoded 4-bit vs Hamming(7,4)
snr_points = np.linspace(0.0, 0.5, 30)  # channel bit-flip probability
ber_uncoded  = []
ber_hamming  = []
N = 3000
random.seed(1)
np.random.seed(1)
for p_flip in snr_points:
    err_unc = 0
    err_ham = 0
    for _ in range(N):
        msg = [random.randint(0,1) for _ in range(4)]
        codeword = encode(msg)
        # Apply independent bit flips with probability p_flip
        noise = np.random.binomial(1, p_flip, 7)
        received = (np.array(codeword) ^ noise) % 2
        # Uncoded: just take first 4 bits
        if not np.array_equal(received[:4], msg):
            err_unc += 1
        # Hamming decode
        _, decoded, _ = decode(received)
        if not np.array_equal(decoded, msg):
            err_ham += 1
    ber_uncoded.append(err_unc / N)
    ber_hamming.append(err_ham / N)

axes[2].plot(snr_points, ber_uncoded, color='#f87171', linewidth=2, label='Uncoded (4-bit)')
axes[2].plot(snr_points, ber_hamming, color='#4ade80', linewidth=2, label='Hamming(7,4)')
axes[2].set_title('BER vs Bit-Flip Probability', color='#818cf8', fontsize=11, fontweight='bold')
axes[2].set_xlabel('Channel bit-flip probability p', color='#94a3b8')
axes[2].set_ylabel('Bit Error Rate', color='#94a3b8')
axes[2].legend(facecolor='#1e2030', edgecolor='#334155', labelcolor='#94a3b8', fontsize=9)
axes[2].tick_params(colors='#94a3b8')
axes[2].set_yscale('log')
axes[2].set_ylim(bottom=1e-4)

plt.suptitle('Hamming(7,4) Error-Correcting Code Analysis', 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 4: Huffman & Arithmetic Codes Ch 6: Turbo & LDPC Codes →