05 - Error-correcting codes: Hamming distance, Hamming and Singleton bounds

You have seven bits coming from a noisy channel and you know that at most one is wrong. If the seven bits are a well-chosen word in a code of only 16 words, you can find which bit to fix with three sums modulo 2. The number that decides how many errors a code can correct is the minimum distance d: a code with distance d corrects every pattern of at most t = ⌊(d-1)/2⌋ errors and detects up to d-1. The Hamming (7,4) code has d = 3, corrects one error and fills the space of vectors without waste; the two bounds of this article, Hamming's and Singleton's, say how much further a code can go. I build the (7,4) from scratch, try it on all the small error vectors and check the bounds by enumeration, because two of the results that keep recurring in lecture notes (the parity-check matrix and the relation between syndrome and position) are easy to get wrong by hand.

Hamming distance and its geometry

The Hamming distance dH(x, y) between two strings of equal length is the number of positions in which they differ. For x = 1011 and y = 1101 the second and third positions differ, so dH = 2. The three properties that make it a true distance are:

• non-negativity, with dH(x, y) = 0 if and only if x = y;
• symmetry, dH(x, y) = dH(y, x);
• the triangle inequality, dH(x, z) ≤ dH(x, y) + dH(y, z).

There is no order among these properties, and the only one that is really needed later is the last: the whole theory of correction follows from it, because it lets you say that two spheres of radius t do not touch if their centres are far enough apart. The other two tell you that you can speak of a "sphere" without ambiguity.

A Hamming sphere of radius t around a string of length n contains all the strings at distance at most t. Choosing exactly j positions to flip can be done in binom(n, j) ways, so the volume is V(n, t) = Σj=0..t binom(n, j). With n = 10 and t = 2 you get 1 + 10 + 45 = 56, the number that the listing on the bounds recomputes later.

Why t = ⌊(d-1)/2⌋: the triangle inequality at work

Let d be the minimum distance of a code, that is the smallest distance between two different codewords. Take t with 2t + 1 ≤ d and suppose that a received string y is at distance at most t from two codewords c and c'. Then dH(c, c') ≤ dH(c, y) + dH(y, c') ≤ 2t < d, against the definition of d. So y is close to only one word and minimum-distance decoding, that is "choose the nearest codeword", returns the right one. The largest integer t with 2t + 1 ≤ d is ⌊(d-1)/2⌋. Guruswami, Rudra and Sudan (proposition 1.4.2) state the full equivalence: distance d, correction of ⌊(d-1)/2⌋ errors and detection of d-1 errors are the same property.

The difference between detecting and correcting is concrete. With d = 2, as in the parity bit, you recognise a single error (the received word is not in the code) but you do not know where it is, because at distance 1 there are several words; with d = 3 you can also correct. The table in the listing on the Singleton bound confirms the parameters: the (4,3) code with one parity bit has d = 2 and t = 0.

The Hamming (7,4) code, built and tested

A linear code [n, k] is a subspace of dimension k of F2n, with 2k codewords. You encode with a generator matrix G of size k × n, c = mG modulo 2, and you check with a parity-check matrix H of size (n-k) × n such that GHT = 0. In systematic form, G = [I | P] and H = [PT | I]: if you get a single entry of PT wrong the two matrices stop being compatible, and that is why the listing starts by computing GHT. Then it encodes all 16 messages, measures the minimum distance by enumeration, writes the syndrome of every single error and decodes every error vector of weight 0, 1 and 2 on each of the 16 codewords.

from itertools import combinations, product

# Generator matrix in systematic form [I4 | P] and parity-check matrix [P^T | I3]
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]]
H = [[1, 1, 0, 1, 1, 0, 0],
     [1, 0, 1, 1, 0, 1, 0],
     [0, 1, 1, 1, 0, 0, 1]]


def encode(m):
    return tuple(sum(m[i] * G[i][j] for i in range(4)) % 2 for j in range(7))


def syndrome(r):
    return tuple(sum(r[j] * H[i][j] for j in range(7)) % 2 for i in range(3))


def dist(x, y):
    return sum(a != b for a, b in zip(x, y))


# 1) G and H are compatible: G H^T = 0 modulo 2
GHt = [[sum(G[i][j] * H[k][j] for j in range(7)) % 2 for k in range(3)] for i in range(4)]
print("G H^T =", GHt)

# 2) The 16 codewords and the minimum distance, by enumeration
words = {m: encode(m) for m in product((0, 1), repeat=4)}
dmin = min(dist(a, b) for a in words.values() for b in words.values() if a != b)
print("codewords:", len(set(words.values())), " minimum distance:", dmin)
c = words[(1, 0, 1, 0)]
print("m = 1010  ->  c =", "".join(map(str, c)))

# 3) The syndrome of a single error at position j is column j of H
print("wrong position -> syndrome")
table = {}
for j in range(7):
    e = [0] * 7
    e[j] = 1
    table[syndrome(e)] = j
    print(f"  {j + 1} -> {''.join(map(str, syndrome(e)))}")


# 4) Syndrome decoding tried on ALL error vectors of weight 0, 1 and 2, for all 16 codewords
def decode(r):
    s = syndrome(r)
    if s == (0, 0, 0):
        return r
    j = table[s]
    return tuple(b ^ (i == j) for i, b in enumerate(r))


results = {0: [0, 0], 1: [0, 0], 2: [0, 0]}  # weight -> [correct, wrong]
for cw in words.values():
    for weight in (0, 1, 2):
        for pos in combinations(range(7), weight):
            r = tuple(b ^ (i in pos) for i, b in enumerate(cw))
            results[weight][0 if decode(r) == cw else 1] += 1
for weight, (ok, ko) in results.items():
    print(f"errors of weight {weight}: {ok} corrected, {ko} wrong")

# 5) With the columns of H in binary order (1..7) the syndrome, read as a number, is the position
Hc = [[(j >> b) & 1 for j in range(1, 8)] for b in (2, 1, 0)]
for j in range(7):
    e = [0] * 7
    e[j] = 1
    s = [sum(e[k] * Hc[i][k] for k in range(7)) % 2 for i in range(3)]
    assert int("".join(map(str, s)), 2) == j + 1
print("H with columns 1..7 in binary: syndrome = position, verified for the 7 positions")

# Output:
# G H^T = [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
# codewords: 16  minimum distance: 3
# m = 1010  ->  c = 1010101
# wrong position -> syndrome
#   1 -> 110
#   2 -> 101
#   3 -> 011
#   4 -> 111
#   5 -> 100
#   6 -> 010
#   7 -> 001
# errors of weight 0: 16 corrected, 0 wrong
# errors of weight 1: 112 corrected, 0 wrong
# errors of weight 2: 0 corrected, 336 wrong
# H with columns 1..7 in binary: syndrome = position, verified for the 7 positions

The first line of the output shows that G and H are compatible, the second that the 16 words are distinct and at distance at least 3 from one another: the code corrects one error and detects two. The message 1010 becomes 1010101, the sum of the first and third rows of G modulo 2. The syndrome of an error in position j is column j of H: the seven columns, 110, 101, 011, 111, 100, 010, 001, are all the nonzero three-bit vectors, each exactly once. That is why every single error has a different syndrome and decoding reduces to reading the table.

The main result is in the last part of the output: out of 16 · 7 = 112 single errors the decoding is right 112 times; out of 16 · 21 = 336 double errors it is wrong 336 times. It is not bad luck: every vector is at distance at most 1 from exactly one codeword, so a double error always ends up near another codeword and is "corrected" towards the wrong one. It is also the reason why the code is perfect. To read the syndrome as a position number you need a different arrangement: if you order the columns of H according to the binary numbers from 1 to 7, the syndrome read in binary is the position of the error, as the last line verifies. The two versions of the code are equivalent up to a permutation of the positions, because they have the same seven columns in a different order.

The Hamming bound and perfect codes

If the spheres of radius t around the 2k codewords do not overlap, they all fit in the 2n points of the space, so 2k · V(n, t) ≤ 2n, that is k ≤ n - log2 V(n, t). This is the Hamming bound (Guruswami, Rudra and Sudan, theorem 1.7.2, who state it for an alphabet of q symbols). A code that reaches it with equality is perfect: the spheres fill the space without leaving any point uncovered. MacKay (§13.3) rephrases the equality like this: the number of noise vectors in a sphere must equal the number of possible syndromes, V(n, t) = 2n-k.

The listing uses only exact integers. It checks that the (7,4) and the Golay (23,12) code satisfy the equality, computes the maximum k allowed for n = 15 and t = 2, searches for n up to 100 the cases in which V(n, t) is a power of two, builds the BCH (15,7) code to check whether the bound is tight and, at the end, compares Hamming and Singleton on an alphabet of 256 symbols.

import math
from itertools import product


def V(n, t):
    """Number of points of a Hamming sphere of radius t in {0,1}^n."""
    return sum(math.comb(n, j) for j in range(t + 1))


def k_max_hamming(n, t):
    """Largest integer k with 2^k * V(n,t) <= 2^n (Hamming bound), in exact integer arithmetic."""
    k = 0
    while 2 ** (k + 1) * V(n, t) <= 2**n:
        k += 1
    return k


# 1) Volumes and the Hamming bound for known cases
print("V(10,2) =", V(10, 2))
print("(7,4), t=1:  2^4 * V(7,1) =", 2**4 * V(7, 1), " 2^7 =", 2**7)
print("Golay (23,12), t=3:  V(23,3) =", V(23, 3), " 2^11 =", 2**11)
print("n=15, t=2:  V =", V(15, 2), " maximum k for the Hamming bound =", k_max_hamming(15, 2))

# 2) Which (n, t) satisfy the numerical condition V(n,t) = 2^m, for n up to 100
# (excluding repetition codes of odd length, which have t = (n-1)/2)
print("(n, t) with V(n,t) a power of two, 1 <= t < (n-1)/2, n <= 100:")
for n in range(3, 101):
    for t in range(1, (n - 1) // 2):
        v = V(n, t)
        if v & (v - 1) == 0:
            print(f"  n={n:3d} t={t:2d}  V = 2^{v.bit_length() - 1}")

# 3) The BCH (15,7) code with generator polynomial g(x) = x^8 + x^7 + x^6 + x^4 + 1: minimum distance by enumeration
g = 0b111010001  # coefficients from x^8 to x^0


def multiply(a, b):
    """Product of polynomials over F2, with integers as bit vectors."""
    r = 0
    while b:
        if b & 1:
            r ^= a
        a <<= 1
        b >>= 1
    return r


weights = [bin(multiply(m, g)).count("1") for m in range(1, 2**7)]
print("BCH (15,7): nonzero codewords", len(weights), " minimum weight =", min(weights))

# 4) Reed-Solomon [255,223] over an alphabet of 256 symbols: q-ary Hamming bound (Guruswami-Rudra-Sudan, theorem 1.7.2)
#    against the Singleton bound, with t = 16
q, n, t = 256, 255, 16
volume = sum(math.comb(n, i) * (q - 1) ** i for i in range(t + 1))
k_hamming = 0
while q ** (k_hamming + 1) * volume <= q**n:
    k_hamming += 1
print(f"q=256, n=255, t=16:  maximum k for Hamming = {k_hamming},  maximum k for Singleton (d=33) = {n - 33 + 1}")

# Output:
# V(10,2) = 56
# (7,4), t=1:  2^4 * V(7,1) = 128  2^7 = 128
# Golay (23,12), t=3:  V(23,3) = 2048  2^11 = 2048
# n=15, t=2:  V = 121  maximum k for the Hamming bound = 8
# (n, t) with V(n,t) a power of two, 1 <= t < (n-1)/2, n <= 100:
#   n=  7 t= 1  V = 2^3
#   n= 15 t= 1  V = 2^4
#   n= 23 t= 3  V = 2^11
#   n= 31 t= 1  V = 2^5
#   n= 63 t= 1  V = 2^6
#   n= 90 t= 2  V = 2^12
# BCH (15,7): nonzero codewords 127  minimum weight = 5
# q=256, n=255, t=16:  maximum k for Hamming = 228,  maximum k for Singleton (d=33) = 223

The (7,4) satisfies 16 · 8 = 128 = 27; the Golay (23,12) code satisfies V(23, 3) = 2048 = 211. For n = 15 and t = 2 the bound allows k ≤ 8, but the BCH (15,7) code, with generator polynomial x8 + x7 + x6 + x4 + 1, has distance 5 and k = 7: the bound is a ceiling, it does not guarantee that a code with those parameters exists. The search for n ≤ 100 shows other numerical coincidences, among them n = 90 and t = 2 (V = 4096 = 212). Satisfying the numerical condition is therefore necessary but not sufficient: MacKay (§13.3) lists as the only nontrivial perfect binary codes the Hamming codes (t = 1, n = 2m - 1), the repetition codes of odd length and the Golay code, and concludes that there are no others.

Two clarifications on facts that tend to be repeated badly: repetition codes are perfect only for odd n, because with even n there are strings halfway between two codewords, at equal distance from both; and the Hamming code is named after Richard Hamming, not Shannon, who in his 1948 paper cites it with attribution to Hamming (as Guruswami, Rudra and Sudan report in the bibliographic notes; I did not read Shannon's passage). The rarity of perfect codes is a practical fact: most codes in use sacrifice perfection, and with it easy syndrome decoding, in exchange for distance or for arbitrary lengths.

The Singleton bound and MDS codes

The Singleton bound concerns the distance and holds for any alphabet: a code (n, k, d)q has k ≤ n - d + 1, that is d ≤ n - k + 1 (Guruswami, Rudra and Sudan, theorem 4.3.1). The proof is short: if you truncate every codeword to its first n - d + 1 symbols, the prefixes of two different codewords must stay different, because otherwise the two words would coincide in n - d + 1 positions and differ in at most d - 1, against the minimum distance d. Then the codewords are at most as many as the possible prefixes, that is qk ≤ qn-d+1. Codes with d = n - k + 1 are called MDS, for maximum distance separable.

The listing has two parts. In the first it tries all the binary linear codes with n ≤ 6 and k ≤ 4: every code has a basis, that is k independent vectors, so it is enough to try every subset of k nonzero vectors and take the best distance. In the second it builds the Reed-Solomon code [7, 3] over the field GF(8) as an evaluation code: the word associated with a polynomial f of degree less than 3 is (f(1), f(α), …, f(α6)), with α a root of x3 + x + 1. The minimum distance follows from the fact that a nonzero polynomial of degree less than 3 has at most two roots.

import math
from itertools import combinations, product


def best_linear_distance(n, k):
    """Largest minimum distance among ALL binary linear codes [n,k]: every code has a basis,
    that is k independent nonzero vectors, so it is enough to try all subsets of k vectors."""
    best = 0
    for basis in combinations(range(1, 2**n), k):
        weights = []
        for mask in range(1, 2**k):
            w = 0
            for i in range(k):
                if (mask >> i) & 1:
                    w ^= basis[i]
            weights.append(bin(w).count("1") if w else 0)
        if min(weights) > 0:  # w = 0 for some combination: the vectors are not independent
            best = max(best, min(weights))
    return best


def hamming_t_max(n, k):
    """Largest t for which the Hamming bound admits 2^k codewords: 2^k * V(n,t) <= 2^n."""
    best = 0
    for t in range(0, n + 1):
        v = sum(math.comb(n, j) for j in range(t + 1))
        if 2**k * v <= 2**n:
            best = t
    return best


print(" n  k  best d    Singleton n-k+1  real t  max t (Hamming)")
for n, ks in ((3, (1, 2)), (4, (1, 2, 3)), (5, (1, 2, 3, 4)), (6, (1, 2, 3, 4))):
    for k in ks:
        d = best_linear_distance(n, k)
        print(f"{n:2d} {k:2d}  {d:9d}  {n - k + 1:15d}  {(d - 1) // 2:7d}  {hamming_t_max(n, k):14d}")

# Reed-Solomon [7,3] over GF(8): the codewords are (f(a^0), ..., f(a^6)) with f of degree < 3. Field with x^3 + x + 1.
LOG, EXP = {}, [0] * 14
x = 1
for i in range(7):
    EXP[i] = EXP[i + 7] = x
    LOG[x] = i
    x <<= 1
    if x & 8:
        x ^= 0b1011


def mul(a, b):
    return 0 if a == 0 or b == 0 else EXP[LOG[a] + LOG[b]]


def evaluate(coeffs, point):
    r = 0
    for c in reversed(coeffs):  # Horner scheme; addition in the field is XOR
        r = mul(r, point) ^ c
    return r


points = [EXP[i] for i in range(7)]
words = [tuple(evaluate(f, p) for p in points) for f in product(range(8), repeat=3)]
dmin = min(sum(a != b for a, b in zip(u, v)) for u, v in combinations(words, 2))
print()
print(f"RS [7,3] over GF(8): {len(words)} codewords, minimum distance {dmin} = n-k+1 = {7 - 3 + 1}")

# Minimum-distance decoding of ALL error vectors of weight <= 3 on the zero codeword
# (by linearity the other codewords behave the same way)
for weight in (0, 1, 2, 3):
    right = wrong = 0
    for pos in combinations(range(7), weight):
        for val in product(range(1, 8), repeat=weight):
            r = [0] * 7
            for p_, v_ in zip(pos, val):
                r[p_] = v_
            d_zero = weight
            nearest = min(sum(a != b for a, b in zip(r, w)) for w in words if any(w))
            # correct if the zero codeword is strictly the nearest
            if d_zero < nearest:
                right += 1
            else:
                wrong += 1
    print(f"errors of weight {weight}: {right} decoded correctly, {wrong} not or ambiguous")

# Output:
#  n  k  best d    Singleton n-k+1  real t  max t (Hamming)
#  3  1          3                3        1               1
#  3  2          2                2        0               0
#  4  1          4                4        1               1
#  4  2          2                3        0               0
#  4  3          2                2        0               0
#  5  1          5                5        2               2
#  5  2          3                4        1               1
#  5  3          2                3        0               0
#  5  4          2                2        0               0
#  6  1          6                6        2               2
#  6  2          4                5        1               1
#  6  3          3                4        1               1
#  6  4          2                3        0               0
#
# RS [7,3] over GF(8): 512 codewords, minimum distance 5 = n-k+1 = 5
# errors of weight 0: 1 decoded correctly, 0 not or ambiguous
# errors of weight 1: 49 decoded correctly, 0 not or ambiguous
# errors of weight 2: 1029 decoded correctly, 0 not or ambiguous
# errors of weight 3: 0 decoded correctly, 12005 not or ambiguous

The table shows that, among the binary codes examined, only the trivial ones touch the bound: with k = 1 (repetition, d = n) and with k = n - 1 (a parity bit, d = 2) we have d = n - k + 1, while for example n = 5, k = 2 reaches at most d = 3 against a bound of 4. In the same table the Hamming column coincides with the real t in all 13 cases, so in this range the Hamming bound is tight, even though it does not hold in general (the case n = 15, t = 2 above). The Reed-Solomon code [7, 3] over GF(8) instead is MDS: d = 5 = n - k + 1. Over 1 + 49 + 1029 error vectors of weight at most 2, minimum-distance decoding always succeeded, and none of the 12005 vectors of weight 3 is decoded uniquely.

The same scheme over GF(256) gives the Reed-Solomon code [255, 223], with d = 255 - 223 + 1 = 33 and therefore t = 16 corrected symbols, where each symbol is a byte. This is a calculation from the bound, not an enumeration: the construction is identical to that of the listing, but 256223 words cannot be enumerated. The difference from binary codes is the alphabet: the existence of MDS codes requires a large alphabet, and in the construction of the listing the length is n = q - 1, that is 7 over GF(8) and 255 over GF(256).

How the two bounds compare

The Hamming bound exploits the geometry of the space, spheres that do not overlap, and gives a ceiling on the number of codewords once t is fixed. The Singleton bound exploits the structure of the prefixes and gives a ceiling on the distance once n and k are fixed. In the binary sample of the listing Hamming is the tighter: the (4,2) code has d = 2, Singleton would allow 3, and Hamming allows t = 0. Over an alphabet of 256 symbols the roles are reversed: the last line of the second listing says that for n = 255 and t = 16 Hamming allows k ≤ 228, while Singleton allows k ≤ 223, a value that Reed-Solomon reaches. The [255, 223] code is therefore MDS but not perfect: its spheres do not fill the space, and no bound on spheres decides its quality.

The choice of code is therefore a choice of alphabet before it is a choice of bound. If the data are bytes and errors hit whole symbols, an MDS code uses redundancy in the best way; if the bits are independent and rare, the Hamming sphere is the right picture and the Hamming code or a BCH are the natural candidates. I have not measured performance on real channels: the comparison is between the theoretical parameters of the codes.

Common mistakes

• Confusing d with the number of correctable errors. With d = 5 you correct t = 2 errors, not 5; you detect 4.
• Believing that the Hamming bound is reached: only perfect codes reach it. The BCH (15,7) stays at k = 7 against a ceiling of 8.
• Declaring a repetition code of even length perfect. For even n it is not.
• Ordering the columns of H badly and reading the syndrome as the position. It holds only with the columns in binary order; in systematic form you need the table.
• Applying Singleton as if it were tight for binary codes. For intermediate k it is not, as the table shows.

Three of the five mistakes (the second, the third and the fifth) have the same origin: treating as reached a bound that is only a ceiling. When a formula has a "≤", ask which code turns it into an equality and whether that code exists. The fourth is one of notation: the rule "syndrome equals position" depends on how you order the columns.

What you can do now

You can define the Hamming distance, prove why t = ⌊(d-1)/2⌋ and use the syndrome table to correct an error of the (7,4) code, limits included: a double error is not corrected, it is decoded wrongly with certainty. You can compute the Hamming bound with exact integers and recognise that the numerical coincidence is not enough to guarantee existence (n = 90, t = 2). You can state and prove the Singleton bound and recognise an MDS code. The Hamming code is a constructive example of what Shannon's theorem in article 4 only promises in existence; and when the bits are no longer needed, the lossy compression of article 6 repeats the same scheme with a different quantity. To review the role of the mutual information, which enters Shannon's limit, use article 2. All the articles are in the series index.

Frequently asked questions

The same series also includes article 01 on Shannon entropy and article 03 on source coding.