Hamming Distance - Learning Module

Loading content...

0/228

Minimum Distance: The Central Code Parameter

The Number That Defines a Code

Among all the parameters that characterize an error-correcting code, minimum distance stands supreme. It determines how many errors can be detected, how many can be corrected, and how reliable the code is against noise. When comparing codes or choosing one for an application, minimum distance is often the first question asked.

But minimum distance doesn't exist in isolation. It trades off against code rate (efficiency), codeword length, and computational complexity. Understanding these tradeoffs—and the theoretical bounds that constrain them—is essential for selecting the right code for any application.

What You Will Learn

By the end of this page, you will understand standard code notation (n, k, dmin), fundamental bounds on achievable codes (Singleton, Hamming, Gilbert-Varshamov), how to compute minimum distance for different code types, and the rate-distance tradeoff that underlies all code design.

Standard Code Notation

Error-correcting codes are characterized by three fundamental parameters, captured in standard notation:

The (n, k, d) or [n, k, d] Notation:

n: Codeword length (total bits after encoding)
k: Message length (data bits before encoding) or log₂(M) for M codewords
d or dmin: Minimum Hamming distance between any pair of codewords

The notation [n, k, d] is typically used for linear codes, while (n, M, d) is used for general codes where M is the number of codewords (M = 2^k for linear codes).

Common Error-Correcting Codes with Parameters
Code Name	Notation	Rate k/n	Detection	Correction
Single parity bit	(n, n-1, 2)	(n-1)/n	1 bit	0 bits
Repetition (3x)	(3, 1, 3)	1/3 = 0.33	2 bits	1 bit
Hamming (7,4)	[7, 4, 3]	4/7 ≈ 0.57	2 bits	1 bit
Hamming (15,11)	[15, 11, 3]	11/15 ≈ 0.73	2 bits	1 bit
Extended Hamming	[8, 4, 4]	4/8 = 0.5	3 bits	1 bit (SEC-DED)
Golay	[23, 12, 7]	12/23 ≈ 0.52	6 bits	3 bits
Extended Golay	[24, 12, 8]	12/24 = 0.5	7 bits	3 bits

Derived Parameters:

Code rate: R = k/n — the fraction of bits that carry information
Redundancy: r = n - k — the number of check bits added
Detection capability: e = d - 1
Correction capability: t = ⌊(d-1)/2⌋

Example Analysis:

The Hamming [7, 4, 3] code:

Encodes 4 data bits into 7 bits
Rate R = 4/7 ≈ 57% efficiency
Adds r = 3 check bits
Can detect 2-bit errors (d - 1 = 2)
Can correct 1-bit errors (⌊2/2⌋ = 1)

Reading Code Parameters

When you see "[7, 4, 3] code," immediately know: 7 bits transmitted, 4 bits of data, minimum distance 3 → single-error correcting (SEC). This notation encapsulates everything essential about the code's capabilities.

Computing Minimum Distance

For a given code, how do we determine its minimum distance? The approach depends on the code structure.

Brute Force: All Pairs

For any code with M codewords, compute distances between all pairs and take the minimum. This requires M(M-1)/2 distance calculations—exponential in k for M = 2^k codewords.

Linear Codes: Minimum Weight

For linear codes, minimum distance equals the minimum Hamming weight of any non-zero codeword:

$$d_{min} = \min_{c \neq 0} w(c)$$

This is because the all-zeros word is always a codeword, and d(c₁, c₂) = w(c₁ ⊕ c₂) where c₁ ⊕ c₂ is also a codeword.

From Parity-Check Matrix:

For linear codes with parity-check matrix H, the minimum distance equals the minimum number of linearly dependent columns of H.

compute_min_distance.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
from itertools import combinations
import numpy as np
 
def hamming_weight(x: int) -> int:
    """Count number of 1-bits in an integer."""
    return bin(x).count('1')
 
def minimum_distance_brute_force(codewords: list[int]) -> int:
    """
    Compute minimum distance by checking all pairs.
    Time: O(M²) where M = number of codewords.
    """
    min_dist = float('inf')
    for c1, c2 in combinations(codewords, 2):
        dist = hamming_weight(c1 ^ c2)
        min_dist = min(min_dist, dist)
    return min_dist
 
def minimum_distance_linear(generator_matrix: np.ndarray) -> int:
    """
    Compute minimum distance for linear code via minimum weight.
    Generate all non-zero codewords and find minimum weight.
    """
    k, n = generator_matrix.shape
    min_weight = float('inf')
    
    # Generate all 2^k - 1 non-zero codewords
    for data in range(1, 2**k):
        # Encode: multiply data vector by generator matrix (mod 2)
        data_bits = np.array([(data >> i) & 1 for i in range(k)], dtype=np.uint8)
        codeword = data_bits @ generator_matrix % 2
        weight = np.sum(codeword)
        min_weight = min(min_weight, weight)
    
    return min_weight
 
def minimum_distance_from_H(H: np.ndarray) -> int:
    """
    Compute minimum distance from parity-check matrix.
    Find minimum number of linearly dependent columns.
    """
    r, n = H.shape  # r = n-k check bits, n columns
    
    # Check if d columns are linearly dependent
    for d in range(1, n + 1):
        for cols in combinations(range(n), d):
            submatrix = H[:, cols]
            # If these columns are linearly dependent (sum to zero mod 2)
            # then d is a possible distance
            col_sum = submatrix.sum(axis=1) % 2
            if np.all(col_sum == 0):
                # Check for XOR combinations that yield zero
                for subset in range(1, 2**d):
                    combo = np.zeros(r, dtype=np.uint8)
                    for i, c in enumerate(cols):
                        if subset & (1 << i):
                            combo = (combo + H[:, c]) % 2
                    if np.all(combo == 0):
                        return d
    
    return n  # Maximum distance if no dependencies found
 
# Example: Hamming (7,4) code
# Generator matrix (systematic form)
G_74 = 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=np.uint8)
 
print("Hamming (7,4) code analysis:")
print(f"Minimum distance: {minimum_distance_linear(G_74)}")
 
# Verify with parity-check matrix
H_74 = np.array([
    [1, 1, 0, 1, 1, 0, 0],
    [1, 0, 1, 1, 0, 1, 0],
    [0, 1, 1, 1, 0, 0, 1],
], dtype=np.uint8)
 
# Output: Minimum distance: 3

Computational Complexity

Finding minimum distance is computationally hard for general codes (NP-hard in general). For structured codes like Hamming, BCH, and Reed-Solomon, algebraic methods provide efficient formulas to determine or bound the minimum distance without enumeration.

The Singleton Bound

What's the best possible minimum distance for a code with given length n and size M (or dimension k)? Several fundamental bounds constrain achievable codes. The Singleton bound is one of the simplest and most important.

Singleton Bound:

$$d \leq n - k + 1$$

Equivalently, for a code with n-bit codewords, M codewords, and distance d:

$$M \leq q^{n-d+1}$$

where q is the alphabet size (q = 2 for binary codes).

Intuition:

If we delete d-1 positions from all codewords, the remaining n-d+1 positions must still uniquely identify each codeword (otherwise two codewords would differ in fewer than d positions). This means M ≤ 2^(n-d+1).

Maximum Distance Separable (MDS) Codes:

Codes that achieve the Singleton bound with equality are called MDS codes:

$$d = n - k + 1$$

MDS codes are "optimal" in the sense that they achieve maximum distance for given length and dimension.

Examples:

Code	Parameters	Singleton Bound	MDS?
Repetition (n,1)	d = n	n - 1 + 1 = n	Yes
Trivial (n,n)	d = 1	n - n + 1 = 1	Yes
Hamming (7,4)	d = 3	7 - 4 + 1 = 4	No (d < bound)
Reed-Solomon	d = n-k+1	n - k + 1	Yes

Reed-Solomon codes are the most important family of MDS codes, widely used in storage and communications.

Binary MDS Codes are Rare

Over binary alphabets, MDS codes are very restricted. The only binary MDS codes are trivial: repetition codes, single parity bit codes, and the full space. Non-trivial binary codes like Hamming always fall short of the Singleton bound. Reed-Solomon codes achieve MDS status by using larger alphabets (e.g., bytes rather than bits).

The Hamming Bound (Sphere-Packing)

The Hamming bound (also called the sphere-packing bound) constrains codes based on the geometry of correction spheres in Hamming space.

Hamming Bound:

For a code that corrects t errors, correction spheres of radius t must not overlap. The total volume of all spheres cannot exceed the space:

$$M \cdot V(n, t) \leq 2^n$$

where V(n, t) is the volume of a Hamming sphere:

$$V(n, t) = \sum_{i=0}^{t} \binom{n}{i}$$

Since t = ⌊(d-1)/2⌋, this bound relates to minimum distance:

$$M \leq \frac{2^n}{\sum_{i=0}^{\lfloor(d-1)/2\rfloor} \binom{n}{i}}$$

hamming_bound_analysis.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from math import comb, log2, floor
 
def sphere_volume(n: int, t: int) -> int:
    """Volume of Hamming sphere of radius t in n dimensions."""
    return sum(comb(n, i) for i in range(t + 1))
 
def hamming_bound_M(n: int, d: int) -> int:
    """Maximum number of codewords by Hamming bound."""
    t = (d - 1) // 2  # Correction capability
    return 2**n // sphere_volume(n, t)
 
def hamming_bound_k(n: int, d: int) -> float:
    """Maximum dimension k by Hamming bound."""
    return log2(hamming_bound_M(n, d))
 
def singleton_bound_d(n: int, k: int) -> int:
    """Maximum distance by Singleton bound."""
    return n - k + 1
 
def analyze_code_bounds(n: int, k: int, d: int, name: str):
    """Analyze how a code compares to theoretical bounds."""
    print(f"\n{name} [{n}, {k}, {d}] Analysis")
    print("=" * 50)
    
    # Singleton bound
    singleton_d = singleton_bound_d(n, k)
    print(f"Singleton bound: d ≤ {singleton_d}")
    print(f"  Actual d = {d} → {'MDS!' if d == singleton_d else f'Gap of {singleton_d - d}'}")
    
    # Hamming bound
    t = (d - 1) // 2
    max_k = hamming_bound_k(n, d)
    print(f"Hamming bound (t={t}): k ≤ {max_k:.2f}")
    print(f"  Actual k = {k} → {'Perfect!' if abs(k - max_k) < 0.01 else f'k is {k - max_k:.2f} from bound'}")
    
    # Rate and efficiency
    rate = k / n
    print(f"Code rate: {k}/{n} = {rate:.4f}")
 
# Analyze various codes
analyze_code_bounds(7, 4, 3, "Hamming")
analyze_code_bounds(15, 11, 3, "Hamming")
analyze_code_bounds(23, 12, 7, "Binary Golay")
analyze_code_bounds(8, 4, 4, "Extended Hamming")
 
# Output:
# Hamming [7, 4, 3] Analysis
# ==================================================
# Singleton bound: d ≤ 4
#   Actual d = 3 → Gap of 1
# Hamming bound (t=1): k ≤ 4.00
#   Actual k = 4 → Perfect!
# Code rate: 4/7 = 0.5714

Perfect Codes:

When the Hamming bound holds with equality, the code is perfect—correction spheres exactly tile the space:

Hamming codes: (2^r - 1, 2^r - 1 - r, 3) codes are perfect for any r ≥ 2
Golay code: The binary [23, 12, 7] Golay code is perfect (the only other non-trivial one!)
Repetition codes: (2t+1, 1, 2t+1) codes are perfect

Perfect codes are rare and special. Most practical codes leave gaps between correction spheres—space that would represent detectable but uncorrectable errors.

The Perfection Theorem

It's proven that the only binary perfect codes are Hamming codes, the Golay code, repetition codes, and trivial codes. No other perfect binary codes exist! This remarkable result, proved in 1973, shows how special perfect codes are.

The Gilbert-Varshamov Bound

The Singleton and Hamming bounds are upper bounds—they say "no code can be better than this." The Gilbert-Varshamov (GV) bound is a lower bound—it guarantees codes exist that are at least this good.

Gilbert-Varshamov Bound (for linear codes):

There exists a binary linear [n, k, d] code if:

$$\sum_{i=0}^{d-2} \binom{n-1}{i} < 2^{n-k}$$

Intuitively: if adding each new codeword eliminates fewer than 2^(n-k) possibilities (by excluding everything within distance d-1), we can keep adding codewords.

Asymptotic Form:

As n → ∞, the GV bound says good codes exist with:

$$\frac{k}{n} \geq 1 - H_2(\delta)$$

where δ = d/n is the relative distance and H₂ is the binary entropy function:

$$H_2(p) = -p \log_2(p) - (1-p) \log_2(1-p)$$

Significance of the GV Bound:

The GV bound is existential—it proves good codes exist but doesn't say how to find them. For decades, explicitly constructing codes achieving the GV bound was a major open problem.

Remarkable Progress:

Random codes: Codes picked randomly almost always achieve the GV bound
Algebraic geometry codes: In 1982, codes exceeding the GV bound over large alphabets were discovered!
Expander codes: Some explicit constructions approach the GV bound
Polar codes: Achieve channel capacity (related asymptotic limit)

Practical Implication:

If a code you're considering is far from the GV bound, better codes definitely exist. The GV bound guides code designers: there's no excuse for codes much worse than GV-bound-achieving codes.

The Gap Between Bounds

At distance d where Singleton says dmax = 4 and Hamming says dmax = 3.5, and GV says dmin = 3 exists: the true best code has d in [3, 3.5]. This gap is the playground of coding theory research—narrowing it for various parameters.

The Rate-Distance Tradeoff

Every code faces a fundamental tradeoff: more protection requires more redundancy. High minimum distance means low code rate, and vice versa.

The Singleton Constraint:

$$d \leq n - k + 1$$

Rearranging: k ≤ n - d + 1

As d increases, maximum k decreases proportionally. Double the distance? Halve the data rate (approximately).

Practical Tradeoff Examples:

Rate-Distance Tradeoff in Practice
Scenario	Priority	Typical Code Choice	Rate	Distance
High-speed network	Throughput	Low redundancy CRC	~99%	Low (detection)
SSD storage	Reliability + speed	LDPC codes	85-95%	Moderate
Archival storage	Long-term reliability	Reed-Solomon	70-80%	High
Deep space	Maximum reliability	Turbo/LDPC + interleaving	30-50%	Very high
QR code (high)	Damage tolerance	Reed-Solomon level H	~50%	High (~30% correction)

Application-Driven Selection:

The right code depends on the error environment and application requirements:

Error probability: Higher error rates need larger dmin
Latency tolerance: Can we retransmit, or must we correct?
Bandwidth constraints: How much overhead can we afford?
Computation resources: Can we decode complex codes fast enough?

The Fundamental Limit: Shannon Capacity

Shannon's noisy channel coding theorem proves that for any channel with capacity C, codes exist that reliably communicate at rate R < C. But the closer R approaches C, the more complex the required code becomes. Modern codes like Turbo, LDPC, and Polar approach Shannon capacity—the theoretical limit—remarkably closely.

Shannon's Optimism

Shannon proved in 1948 that arbitrarily reliable communication is possible at rates below channel capacity. But he didn't show how to construct such codes. It took until 1993 (Turbo codes) and 1996 (LDPC rediscovery) to find practical codes approaching Shannon's limit. Polar codes in 2009 were the first proven to achieve it.

Designing Codes with Target Distance

Given a target minimum distance, how do we construct codes achieving it? Different code families have different relationships between parameters and structure.

Hamming Codes: dmin = 3

Hamming codes always have dmin = 3 (single-error correcting). The parity-check matrix H has all non-zero r-bit columns, ensuring no two codeword positions have identical syndromes. For SEC:

n = 2^r - 1
k = n - r
d = 3

Code Families and Distance Design

•Repetition codes: d = n (just repeat each bit). Maximum distance, minimum rate.
•Hamming codes: d = 3 always. Rate approaches 1 as n grows. Perfect but limited correction.
•Extended Hamming: d = 4 by adding overall parity. SEC-DED capability.
•BCH codes: Designed for specific d. Parameters satisfy d ≥ 2t + 1 for t-error correction.
•Reed-Solomon: MDS codes with d = n - k + 1. Maximum distance for given redundancy.
•LDPC codes: Designed via graph properties. Distance grows with careful construction.
•Polar codes: Distance depends on frozen bit positions. Achieves capacity.

BCH Code Design:

BCH (Bose-Chaudhuri-Hocquenghem) codes are designed for a target correction capability t:

Choose n = 2^m - 1
Choose t (number of errors to correct)
The resulting code has guaranteed dmin ≥ 2t + 1

Example: For m = 4 (n = 15):

t = 1: [15, 11, 3] (same as Hamming-15)
t = 2: [15, 7, 5]
t = 3: [15, 5, 7]

BCH codes provide a systematic way to trade rate for distance.

Code Selection Process

Determine error rate and required reliability. 2. Calculate needed dmin for correction/detection. 3. Check rate constraints. 4. Select code family meeting all requirements. 5. Verify decoder complexity is acceptable.

Summary: Minimum Distance as the Master Parameter

Minimum distance is the central parameter of error-correcting codes. It determines detection capability (dmin - 1), correction capability (⌊(dmin-1)/2⌋), and trades off against code rate. Understanding the bounds and tradeoffs is essential for selecting appropriate codes.

Key Takeaways

•Standard notation [n, k, d]: n = codeword length, k = data bits, d = minimum distance. Captures everything essential.
•Computing dmin: Brute force (all pairs), or for linear codes, find minimum non-zero codeword weight.
•Singleton bound: d ≤ n - k + 1. MDS codes achieve equality (e.g., Reed-Solomon).
•Hamming bound: Sphere-packing constraint. Perfect codes achieve equality (Hamming, Golay).
•Gilbert-Varshamov bound: Guarantees good codes exist. Shows what's achievable.
•Rate-distance tradeoff: More protection requires more redundancy. Application determines optimal balance.
•Code family selection: Different families (BCH, RS, LDPC) offer different rate-distance-complexity profiles.

What's Next:

With a deep understanding of Hamming distance, detection, correction, and minimum distance, the final page explores code design—how to construct codes with desired distance properties, including generator and parity-check matrices, and the relationship between code structure and minimum distance.

Page Complete

You now understand minimum distance as the central parameter of error-correcting codes. The bounds (Singleton, Hamming, GV) constrain what's possible, while the rate-distance tradeoff guides practical selection. Next, we'll synthesize everything into code design principles.

Minimum Distance: The Central Code Parameter

The Number That Defines a Code

What You Will Learn

Standard Code Notation

Error-correcting codes are characterized by three fundamental parameters, captured in standard notation:

The (n, k, d) or [n, k, d] Notation:

n: Codeword length (total bits after encoding)
k: Message length (data bits before encoding) or log₂(M) for M codewords
d or dmin: Minimum Hamming distance between any pair of codewords

The notation [n, k, d] is typically used for linear codes, while (n, M, d) is used for general codes where M is the number of codewords (M = 2^k for linear codes).

Common Error-Correcting Codes with Parameters
Code Name	Notation	Rate k/n	Detection	Correction
Single parity bit	(n, n-1, 2)	(n-1)/n	1 bit	0 bits
Repetition (3x)	(3, 1, 3)	1/3 = 0.33	2 bits	1 bit
Hamming (7,4)	[7, 4, 3]	4/7 ≈ 0.57	2 bits	1 bit
Hamming (15,11)	[15, 11, 3]	11/15 ≈ 0.73	2 bits	1 bit
Extended Hamming	[8, 4, 4]	4/8 = 0.5	3 bits	1 bit (SEC-DED)
Golay	[23, 12, 7]	12/23 ≈ 0.52	6 bits	3 bits
Extended Golay	[24, 12, 8]	12/24 = 0.5	7 bits	3 bits

Derived Parameters:

Code rate: R = k/n — the fraction of bits that carry information
Redundancy: r = n - k — the number of check bits added
Detection capability: e = d - 1
Correction capability: t = ⌊(d-1)/2⌋

Example Analysis:

The Hamming [7, 4, 3] code:

Encodes 4 data bits into 7 bits
Rate R = 4/7 ≈ 57% efficiency
Adds r = 3 check bits
Can detect 2-bit errors (d - 1 = 2)
Can correct 1-bit errors (⌊2/2⌋ = 1)

Reading Code Parameters

Computing Minimum Distance

For a given code, how do we determine its minimum distance? The approach depends on the code structure.

Brute Force: All Pairs

For any code with M codewords, compute distances between all pairs and take the minimum. This requires M(M-1)/2 distance calculations—exponential in k for M = 2^k codewords.

Linear Codes: Minimum Weight

For linear codes, minimum distance equals the minimum Hamming weight of any non-zero codeword:

$$d_{min} = \min_{c \neq 0} w(c)$$

This is because the all-zeros word is always a codeword, and d(c₁, c₂) = w(c₁ ⊕ c₂) where c₁ ⊕ c₂ is also a codeword.

From Parity-Check Matrix:

For linear codes with parity-check matrix H, the minimum distance equals the minimum number of linearly dependent columns of H.

compute_min_distance.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
from itertools import combinations
import numpy as np
 
def hamming_weight(x: int) -> int:
    """Count number of 1-bits in an integer."""
    return bin(x).count('1')
 
def minimum_distance_brute_force(codewords: list[int]) -> int:
    """
    Compute minimum distance by checking all pairs.
    Time: O(M²) where M = number of codewords.
    """
    min_dist = float('inf')
    for c1, c2 in combinations(codewords, 2):
        dist = hamming_weight(c1 ^ c2)
        min_dist = min(min_dist, dist)
    return min_dist
 
def minimum_distance_linear(generator_matrix: np.ndarray) -> int:
    """
    Compute minimum distance for linear code via minimum weight.
    Generate all non-zero codewords and find minimum weight.
    """
    k, n = generator_matrix.shape
    min_weight = float('inf')
    
    # Generate all 2^k - 1 non-zero codewords
    for data in range(1, 2**k):
        # Encode: multiply data vector by generator matrix (mod 2)
        data_bits = np.array([(data >> i) & 1 for i in range(k)], dtype=np.uint8)
        codeword = data_bits @ generator_matrix % 2
        weight = np.sum(codeword)
        min_weight = min(min_weight, weight)
    
    return min_weight
 
def minimum_distance_from_H(H: np.ndarray) -> int:
    """
    Compute minimum distance from parity-check matrix.
    Find minimum number of linearly dependent columns.
    """
    r, n = H.shape  # r = n-k check bits, n columns
    
    # Check if d columns are linearly dependent
    for d in range(1, n + 1):
        for cols in combinations(range(n), d):
            submatrix = H[:, cols]
            # If these columns are linearly dependent (sum to zero mod 2)
            # then d is a possible distance
            col_sum = submatrix.sum(axis=1) % 2
            if np.all(col_sum == 0):
                # Check for XOR combinations that yield zero
                for subset in range(1, 2**d):
                    combo = np.zeros(r, dtype=np.uint8)
                    for i, c in enumerate(cols):
                        if subset & (1 << i):
                            combo = (combo + H[:, c]) % 2
                    if np.all(combo == 0):
                        return d
    
    return n  # Maximum distance if no dependencies found
 
# Example: Hamming (7,4) code
# Generator matrix (systematic form)
G_74 = 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=np.uint8)
 
print("Hamming (7,4) code analysis:")
print(f"Minimum distance: {minimum_distance_linear(G_74)}")
 
# Verify with parity-check matrix
H_74 = np.array([
    [1, 1, 0, 1, 1, 0, 0],
    [1, 0, 1, 1, 0, 1, 0],
    [0, 1, 1, 1, 0, 0, 1],
], dtype=np.uint8)
 
# Output: Minimum distance: 3

Computational Complexity

The Singleton Bound

Singleton Bound:

$$d \leq n - k + 1$$

Equivalently, for a code with n-bit codewords, M codewords, and distance d:

$$M \leq q^{n-d+1}$$

where q is the alphabet size (q = 2 for binary codes).

Intuition:

Maximum Distance Separable (MDS) Codes:

Codes that achieve the Singleton bound with equality are called MDS codes:

$$d = n - k + 1$$

MDS codes are "optimal" in the sense that they achieve maximum distance for given length and dimension.

Examples:

Code	Parameters	Singleton Bound	MDS?
Repetition (n,1)	d = n	n - 1 + 1 = n	Yes
Trivial (n,n)	d = 1	n - n + 1 = 1	Yes
Hamming (7,4)	d = 3	7 - 4 + 1 = 4	No (d < bound)
Reed-Solomon	d = n-k+1	n - k + 1	Yes

Reed-Solomon codes are the most important family of MDS codes, widely used in storage and communications.

Binary MDS Codes are Rare

The Hamming Bound (Sphere-Packing)

The Hamming bound (also called the sphere-packing bound) constrains codes based on the geometry of correction spheres in Hamming space.

Hamming Bound:

For a code that corrects t errors, correction spheres of radius t must not overlap. The total volume of all spheres cannot exceed the space:

$$M \cdot V(n, t) \leq 2^n$$

where V(n, t) is the volume of a Hamming sphere:

$$V(n, t) = \sum_{i=0}^{t} \binom{n}{i}$$

Since t = ⌊(d-1)/2⌋, this bound relates to minimum distance:

$$M \leq \frac{2^n}{\sum_{i=0}^{\lfloor(d-1)/2\rfloor} \binom{n}{i}}$$

hamming_bound_analysis.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from math import comb, log2, floor
 
def sphere_volume(n: int, t: int) -> int:
    """Volume of Hamming sphere of radius t in n dimensions."""
    return sum(comb(n, i) for i in range(t + 1))
 
def hamming_bound_M(n: int, d: int) -> int:
    """Maximum number of codewords by Hamming bound."""
    t = (d - 1) // 2  # Correction capability
    return 2**n // sphere_volume(n, t)
 
def hamming_bound_k(n: int, d: int) -> float:
    """Maximum dimension k by Hamming bound."""
    return log2(hamming_bound_M(n, d))
 
def singleton_bound_d(n: int, k: int) -> int:
    """Maximum distance by Singleton bound."""
    return n - k + 1
 
def analyze_code_bounds(n: int, k: int, d: int, name: str):
    """Analyze how a code compares to theoretical bounds."""
    print(f"\n{name} [{n}, {k}, {d}] Analysis")
    print("=" * 50)
    
    # Singleton bound
    singleton_d = singleton_bound_d(n, k)
    print(f"Singleton bound: d ≤ {singleton_d}")
    print(f"  Actual d = {d} → {'MDS!' if d == singleton_d else f'Gap of {singleton_d - d}'}")
    
    # Hamming bound
    t = (d - 1) // 2
    max_k = hamming_bound_k(n, d)
    print(f"Hamming bound (t={t}): k ≤ {max_k:.2f}")
    print(f"  Actual k = {k} → {'Perfect!' if abs(k - max_k) < 0.01 else f'k is {k - max_k:.2f} from bound'}")
    
    # Rate and efficiency
    rate = k / n
    print(f"Code rate: {k}/{n} = {rate:.4f}")
 
# Analyze various codes
analyze_code_bounds(7, 4, 3, "Hamming")
analyze_code_bounds(15, 11, 3, "Hamming")
analyze_code_bounds(23, 12, 7, "Binary Golay")
analyze_code_bounds(8, 4, 4, "Extended Hamming")
 
# Output:
# Hamming [7, 4, 3] Analysis
# ==================================================
# Singleton bound: d ≤ 4
#   Actual d = 3 → Gap of 1
# Hamming bound (t=1): k ≤ 4.00
#   Actual k = 4 → Perfect!
# Code rate: 4/7 = 0.5714

Perfect Codes:

When the Hamming bound holds with equality, the code is perfect—correction spheres exactly tile the space:

Hamming codes: (2^r - 1, 2^r - 1 - r, 3) codes are perfect for any r ≥ 2
Golay code: The binary [23, 12, 7] Golay code is perfect (the only other non-trivial one!)
Repetition codes: (2t+1, 1, 2t+1) codes are perfect

Perfect codes are rare and special. Most practical codes leave gaps between correction spheres—space that would represent detectable but uncorrectable errors.

The Perfection Theorem

The Gilbert-Varshamov Bound

Gilbert-Varshamov Bound (for linear codes):

There exists a binary linear [n, k, d] code if:

$$\sum_{i=0}^{d-2} \binom{n-1}{i} < 2^{n-k}$$

Intuitively: if adding each new codeword eliminates fewer than 2^(n-k) possibilities (by excluding everything within distance d-1), we can keep adding codewords.

Asymptotic Form:

As n → ∞, the GV bound says good codes exist with:

$$\frac{k}{n} \geq 1 - H_2(\delta)$$

where δ = d/n is the relative distance and H₂ is the binary entropy function:

$$H_2(p) = -p \log_2(p) - (1-p) \log_2(1-p)$$

Significance of the GV Bound:

The GV bound is existential—it proves good codes exist but doesn't say how to find them. For decades, explicitly constructing codes achieving the GV bound was a major open problem.

Remarkable Progress:

Random codes: Codes picked randomly almost always achieve the GV bound
Algebraic geometry codes: In 1982, codes exceeding the GV bound over large alphabets were discovered!
Expander codes: Some explicit constructions approach the GV bound
Polar codes: Achieve channel capacity (related asymptotic limit)

Practical Implication:

If a code you're considering is far from the GV bound, better codes definitely exist. The GV bound guides code designers: there's no excuse for codes much worse than GV-bound-achieving codes.

The Gap Between Bounds

The Rate-Distance Tradeoff

Every code faces a fundamental tradeoff: more protection requires more redundancy. High minimum distance means low code rate, and vice versa.

The Singleton Constraint:

$$d \leq n - k + 1$$

Rearranging: k ≤ n - d + 1

As d increases, maximum k decreases proportionally. Double the distance? Halve the data rate (approximately).

Practical Tradeoff Examples:

Rate-Distance Tradeoff in Practice
Scenario	Priority	Typical Code Choice	Rate	Distance
High-speed network	Throughput	Low redundancy CRC	~99%	Low (detection)
SSD storage	Reliability + speed	LDPC codes	85-95%	Moderate
Archival storage	Long-term reliability	Reed-Solomon	70-80%	High
Deep space	Maximum reliability	Turbo/LDPC + interleaving	30-50%	Very high
QR code (high)	Damage tolerance	Reed-Solomon level H	~50%	High (~30% correction)

Application-Driven Selection:

The right code depends on the error environment and application requirements:

Error probability: Higher error rates need larger dmin
Latency tolerance: Can we retransmit, or must we correct?
Bandwidth constraints: How much overhead can we afford?
Computation resources: Can we decode complex codes fast enough?

The Fundamental Limit: Shannon Capacity

Shannon's Optimism

Designing Codes with Target Distance

Given a target minimum distance, how do we construct codes achieving it? Different code families have different relationships between parameters and structure.

Hamming Codes: dmin = 3

Hamming codes always have dmin = 3 (single-error correcting). The parity-check matrix H has all non-zero r-bit columns, ensuring no two codeword positions have identical syndromes. For SEC:

n = 2^r - 1
k = n - r
d = 3

Code Families and Distance Design

•Repetition codes: d = n (just repeat each bit). Maximum distance, minimum rate.
•Hamming codes: d = 3 always. Rate approaches 1 as n grows. Perfect but limited correction.
•Extended Hamming: d = 4 by adding overall parity. SEC-DED capability.
•BCH codes: Designed for specific d. Parameters satisfy d ≥ 2t + 1 for t-error correction.
•Reed-Solomon: MDS codes with d = n - k + 1. Maximum distance for given redundancy.
•LDPC codes: Designed via graph properties. Distance grows with careful construction.
•Polar codes: Distance depends on frozen bit positions. Achieves capacity.

BCH Code Design:

BCH (Bose-Chaudhuri-Hocquenghem) codes are designed for a target correction capability t:

Choose n = 2^m - 1
Choose t (number of errors to correct)
The resulting code has guaranteed dmin ≥ 2t + 1

Example: For m = 4 (n = 15):

t = 1: [15, 11, 3] (same as Hamming-15)
t = 2: [15, 7, 5]
t = 3: [15, 5, 7]

BCH codes provide a systematic way to trade rate for distance.

Code Selection Process

Determine error rate and required reliability. 2. Calculate needed dmin for correction/detection. 3. Check rate constraints. 4. Select code family meeting all requirements. 5. Verify decoder complexity is acceptable.

Summary: Minimum Distance as the Master Parameter

Key Takeaways

•Standard notation [n, k, d]: n = codeword length, k = data bits, d = minimum distance. Captures everything essential.
•Computing dmin: Brute force (all pairs), or for linear codes, find minimum non-zero codeword weight.
•Singleton bound: d ≤ n - k + 1. MDS codes achieve equality (e.g., Reed-Solomon).
•Hamming bound: Sphere-packing constraint. Perfect codes achieve equality (Hamming, Golay).
•Gilbert-Varshamov bound: Guarantees good codes exist. Shows what's achievable.
•Rate-distance tradeoff: More protection requires more redundancy. Application determines optimal balance.
•Code family selection: Different families (BCH, RS, LDPC) offer different rate-distance-complexity profiles.

What's Next:

Page Complete