Error Correction (FEC)

Forward error correction fixes errors without retransmission. Learn Hamming distance and correction capability, linear block codes (generator and parity-check matrices, syndrome decoding), Hamming(7,4), Reed–Solomon, convolutional codes and Viterbi decoding, interleaving, coding gain, and modern LDPC and polar codes — with a Python Hamming decoder.

Deep-space probes, QR codes, DVDs, SSDs, Wi-Fi and 5G all correct errors on the fly. FEC adds structured redundancy so the receiver can locate and fix errors — essential when retransmission is slow or impossible.

An analogy

FEC is like spelling a word with the NATO alphabet: even if some letters are garbled by noise, the redundancy lets the listener reconstruct the message.

Redundancy and distance

Codewords are chosen far apart (Hamming distance). A received word is decoded to the nearest codeword. d_min = 3 corrects 1 error; d_min = 5 corrects 2.

Block codes

Hamming codes (single-error correction, used in ECC memory as SECDED), BCH codes, and Reed–Solomon codes over bytes — excellent against bursts (CDs, QR codes, DVB, deep space RS(255,223) corrects 16 byte errors).

Convolutional codes

Encoders with memory produce output streams from shift registers; the Viterbi algorithm finds the most likely path through a trellis. Interleaving spreads burst errors so they look random to the decoder.

Modern codes

Turbo codes (3G/4G), LDPC (Wi-Fi, DVB-S2, 5G data, SSDs) with iterative belief-propagation decoding, and polar codes (5G control). Soft-decision decoding gains ≈ 2 dB over hard decisions. Coding gain = Eb/N₀ saved at a target BER.

Formulas

Worked example: Correction capability

Given: d_min = 7

Find: Errors corrected / detected.

Answer: Corrects 3, detects 6

Worked example: Reed–Solomon

Given: RS(255, 223)

Find: Correctable bytes and rate.

Answer: 16 bytes per 255-byte block, rate 0.875

Hamming(7,4) encoder and syndrome decoder

import numpy as np

# Hamming(7,4): codeword = [p1 p2 d1 p3 d2 d3 d4]
G = np.array([[1,1,1,0,0,0,0],
              [1,0,0,1,1,0,0],
              [0,1,0,1,0,1,0],
              [1,1,0,1,0,0,1]])
H = np.array([[1,0,1,0,1,0,1],
              [0,1,1,0,0,1,1],
              [0,0,0,1,1,1,1]])

def encode(d):                       # d = 4 data bits
    return (np.array(d) @ G) % 2

def decode(r):
    s = (H @ r) % 2                  # syndrome
    pos = s[0] + 2 * s[1] + 4 * s[2] # 1-based error position (0 = none)
    r = r.copy()
    if pos:
        r[pos - 1] ^= 1              # correct the single-bit error
    return r[[2, 4, 5, 6]], pos

c = encode([1, 0, 1, 1])
print("codeword :", c)
rx = c.copy(); rx[4] ^= 1            # flip bit 5 in the channel
data, pos = decode(rx)
print("received :", rx)
print("error at :", pos, "-> data", data)
# codeword : [0 1 1 0 0 1 1]
# received : [0 1 1 0 1 1 1]
# error at : 5 -> data [1 0 1 1]

The columns of H are the binary numbers 1–7, so the syndrome directly spells out the position of a single-bit error — the elegant idea behind Hamming codes.

Common mistakes

Applications

Key takeaways

Going further