Linear Block Codes

The algebraic backbone of error correction — generator matrices, syndrome decoding, and the geometry of codewords

Roadmap

Vector Spaces over GF(2)

Subspaces & Linear Codes

The [n, k, d] Code

Error correction capability: t = ⌊(d-1)/2⌋    Error detection: d-1 errors

Generator Matrix G

Generator Matrix Example

The code has 2⁴ = 16 codewords, can correct 1 error (t = ⌊(3-1)/2⌋ = 1).

Parity-Check Matrix H

H and Minimum Distance

Encoding Process

import numpy as np

def encode_linear(message, G):
    """Encode message using generator matrix over GF(2)."""
    return np.dot(message, G) % 2

# Hamming [7,4,3] generator matrix (systematic)
G = np.array([
    [1, 0, 0, 0, 1, 1, 0],
    [0, 1, 0, 0, 0, 1, 1],
    [0, 0, 1, 0, 1, 1, 1],
    [0, 0, 0, 1, 1, 0, 1]
])

# Encode all 16 messages
for i in range(16):
    m = np.array([(i >> 3)&1, (i >> 2)&1, (i >> 1)&1, i&1])
    c = encode_linear(m, G)
    print(f"m={m} -> c={c}, weight={sum(c)}")

Syndrome Decoding

Syndrome Decoding: Step by Step

Standard Array & Coset Leaders

Syndrome Lookup Table

Only 2^n-k = 8 entries needed vs. 2ⁿ = 128 for full standard array

Dual Codes

Weight Distribution

MacWilliams Identity

Maximum Likelihood Decoding

Singleton Bound

Hamming Bound (Sphere-Packing)

Proved in 1973 (Tietäväinen, van Lint): these are the ONLY binary perfect codes!

Plotkin Bound

Classic Linear Codes

Python: Linear Code Toolkit

import numpy as np

class LinearCode:
    def __init__(self, G):
        """Initialize linear code from generator matrix G over GF(2)."""
        self.G = np.array(G) % 2
        self.k, self.n = self.G.shape
        self.H = self._compute_parity_check()

    def _compute_parity_check(self):
        """Compute H from systematic G = [I_k | P] -> H = [P^T | I_{n-k}]."""
        P = self.G[:, self.k:]       # extract parity part
        r = self.n - self.k
        return np.hstack([P.T, np.eye(r, dtype=int)]) % 2

    def encode(self, message):
        """Encode k-bit message to n-bit codeword."""
        return np.dot(message, self.G) % 2

    def syndrome(self, received):
        """Compute syndrome s = H @ r^T."""
        return np.dot(self.H, received) % 2

    def decode(self, received):
        """Syndrome decode: correct single errors."""
        s = self.syndrome(received)
        if not np.any(s):
            return received[:self.k]  # no error
        # Find matching column in H
        for i in range(self.n):
            if np.array_equal(s, self.H[:, i]):
                corrected = received.copy()
                corrected[i] ^= 1
                return corrected[:self.k]
        return None  # uncorrectable

Python: Encode & Decode Demo

# Create Hamming [7,4,3] code
G = [[1,0,0,0, 1,1,0],
     [0,1,0,0, 0,1,1],
     [0,0,1,0, 1,1,1],
     [0,0,0,1, 1,0,1]]

hamming = LinearCode(G)

# Encode
msg = np.array([1, 0, 1, 1])
codeword = hamming.encode(msg)
print(f"Message:  {msg}")
print(f"Codeword: {codeword}")  # [1 0 1 1 1 0 0]

# Simulate single-bit error on position 2
received = codeword.copy()
received[2] ^= 1  # flip bit 2
print(f"Received: {received}")  # [1 0 0 1 1 0 0]

# Decode
s = hamming.syndrome(received)
print(f"Syndrome: {s}")  # [1 1 1] -> column 2 of H

decoded = hamming.decode(received)
print(f"Decoded:  {decoded}")   # [1 0 1 1] ✓

# Verify: test all single-error patterns
errors_corrected = 0
for msg_int in range(16):
    m = np.array([(msg_int>>i)&1 for i in range(3,-1,-1)])
    c = hamming.encode(m)
    for pos in range(7):
        r = c.copy()
        r[pos] ^= 1
        d = hamming.decode(r)
        if np.array_equal(d, m):
            errors_corrected += 1
print(f"Corrected {errors_corrected}/112 single errors")  # 112/112

Summary