Paper
Part IILinear Block Codes

Bounds on Codes

November 16, 202652 min readbeginner

Fifteen wires, every pair of words at distance d. How many words fit? The chapter proves the Hamming, Singleton, Plotkin, Griesmer and Gilbert–Varshamov bounds, states the Elias bound and tests them on real codes.

Most chapters of this part built codes. This chapter asks instead what no construction can ever produce.

Picture a designer with 15 wires. Each clock cycle the wires carry one 15-bit word, and the receiver has to tell the allowed words apart even after some wires flip. If every two allowed words differ in at least dd positions, the receiver can correct up to ⌊(d−1)/2⌋\lfloor (d - 1)/2 \rfloor flipped wires, as Distance, Detection and Correction showed. More allowed words carry more data, so the designer wants as many as possible. How many can 15 wires hold at distance 3, at distance 5, or at distance 9?

An upper bound proves that no code, however clever, has more words than some number. A lower bound proves that some code has at least some number of words, sometimes without naming the code. When an upper bound meets a code someone has built, the search at that length and distance is over. The chapter proves five bounds, states a sixth, and evaluates all of them at length 15 beside the codes that earlier chapters built.

Every number in the chapter is recomputed by ch27_bounds_on_codes.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch27_charts.py in the same folder. The GNU Octave twin ch27_bounds_on_codes.m prints the same lines, as The Octave Route explains.

01.Fifteen Wires and a Distance

Start with what the earlier chapters already supply at length 15. The (15,11,3)(15, 11, 3) Hamming code of Hamming Codes and Perfect Codes has 211=20482^{11} = 2048 codewords at distance 3. The even-weight code, every word with an even number of ones, has 214=163842^{14} = 16384 codewords at distance 2. The repetition code has 2, the all-zeros word and the all-ones word, at distance 15. Between these the earlier chapters say little. Is there a code of length 15 with distance 5 and 256 codewords? One with distance 9 and 8 codewords? Trying every set of words is hopeless, since there are 215=327682^{15} = 32768 words to choose from and far more sets of them.

Two arguments drive almost every bound in the chapter, and Figure 1 draws both on a grid where the distance between two dots is the number of steps between them. On the left the codewords sit three steps apart, so a ball of radius one step around each of them, the codeword together with its neighbors, never touches another ball. Counting the words inside the balls caps how many codewords there can be, which is a packing argument. On the right no further dot can join the code without coming within two steps of a codeword, so balls of radius two steps reach every dot. Counting again shows that the code cannot be too small, which is a covering argument.

Two copies of the same grid of words with the same six codewords, three steps apart. On the left, balls of radius one step around the codewords never overlap and leave many words outside every ball, which is the packing argument behind the Hamming bound. On the right, balls of radius two steps around the same codewords overlap and reach every word, which is the covering argument behind the Gilbert bound. Packing (Hamming bound) Covering (Gilbert bound) codeword any other word, one step between neighbors Balls of radius t = 1 step never No word can be added, so balls of overlap and miss many words, so radius d - 1 = 2 steps reach every M V(n, t) is at most 2^n. word, and M V(n, d - 1) is at least 2^n.
Figure 1. Packing and covering on a grid where distance counts steps. Balls of radius around the codewords of a code with distance cannot overlap, which gives the Hamming bound. Balls of radius around a code to which no word can be added must reach every word, which gives the Gilbert bound.

Some bounds speak about every code and some only about linear codes, and the difference between the two already matters at length 8.

02.The Largest Code for a Length and a Distance

A linear code of dimension kk has qkq^k codewords, so every linear code of length nn and distance at least dd shows that Aq(n,d)≥qkA_q(n, d) \ge q^k. The chapter writes [n,k,d][n, k, d] with square brackets when the question is whether a linear code with those parameters exists at all, and keeps (n,k,d)(n, k, d) for codes already built.

Proof. Two different words differ in at least one position, so all qnq^n words together form a code of distance 1. Two words at distance nn differ in every position, the first included, so the codewords of a code of distance nn all have different first symbols and there are at most qq of them. The qq words that repeat one symbol nn times reach that number. For distance 2, delete the last position from every codeword of a binary code. Two codewords that became equal would have differed only in that position, at distance 1, which the code forbids. So the shortened words are distinct words of length n−1n - 1 and number at most 2n−12^{n-1}. The even-weight code reaches that number. Its first n−1n - 1 bits are free and the last bit makes the count of ones even, and two even-weight words cannot differ in exactly one position, since flipping one bit changes the parity. ■\blacksquare

Modifying and Combining Codes extended a linear code by an overall parity bit and punctured one by deleting a position. The same two moves work for any binary code, linear or not, and together they tie each odd distance to the even distance above it.

Proof. Take a binary code of length nn and distance dd, and append to each codeword the XOR of its bits. Every extended word has even weight. The distance between two words aa and bb equals wt(a)+wt(b)−2 wt(a∧b)\mathrm{wt}(a) + \mathrm{wt}(b) - 2\,\mathrm{wt}(a \wedge b), where a∧ba \wedge b has a 1 exactly where both aa and bb do, so the distance between two even-weight words is even. Appending a bit never lowers a distance, so two extended codewords lie at an even distance of at least the odd number dd, which means at least d+1d + 1. That gives A2(n+1,d+1)≥A2(n,d)A_2(n + 1, d + 1) \ge A_2(n, d). In the other direction, delete the last position of every codeword of a code of length n+1n + 1 and distance d+1d + 1. Each distance drops by at most 1, so the words stay distinct and lie at distance at least dd, which gives A2(n,d)≥A2(n+1,d+1)A_2(n, d) \ge A_2(n + 1, d + 1). ■\blacksquare

A few small values follow from a bound and a code that meets it. At length 5 the four words 00000, 10101, 01111 and 11010 lie at distance at least 3 from one another, and the XOR of any two of them is a third, so they form a (5,2,3)(5, 2, 3) linear code. At length 6 the shortened Hamming code with generator rows 100011, 010101 and 001110 has 8 codewords at distance 3, and at length 7 the Hamming code has 16. Upper bounds proved later in the chapter show that none of the three can grow, the Plotkin bound for the first two and the Hamming bound for the third. So A2(5,3)=4A_2(5, 3) = 4, A2(6,3)=8A_2(6, 3) = 8 and A2(7,3)=16A_2(7, 3) = 16.

Length 8 breaks the pattern, because there a nonlinear code beats every linear one. The (8,4,4)(8, 4, 4) extended Hamming code has 16 codewords at distance at least 3, and no linear code does better, because an [8,5,3][8, 5, 3] code would put 25=322^5 = 32 disjoint balls of radius 1, each holding 1+8=91 + 8 = 9 words, into a space of 28=2562^8 = 256 words, and 32×9=288>25632 \times 9 = 288 > 256. Yet a nonlinear code of length 8 with 20 codewords at distance 3 exists. The script stores one, found by a computer search, and checks all 190 pairs of its words. Proving that 21 words cannot fit takes heavier tools than this chapter's. The table of Best, Brouwer, MacWilliams, Odlyzko and Sloane [1] and Brouwer's online table of small binary codes [2] list even distances only, and record the value as A2(9,4)=20A_2(9, 4) = 20, which the extension identity turns into A2(8,3)=20A_2(8, 3) = 20.

03.The Hamming Bound Again

The packing argument of Figure 1 is the oldest bound of all [3], and Hamming Codes and Perfect Codes proved it in the section The Sphere-Packing Bound.

Proof. The balls of radius tt around the codewords are disjoint, each holds Vq(n,t)V_q(n, t) words, and together they fit inside the qnq^n words of the space, as The Sphere-Packing Bound in Hamming Codes and Perfect Codes showed. ■\blacksquare

For binary words of length 15 the ball sizes V2(15,t)V_2(15, t) for tt from 0 to 7 are 1, 16, 121, 576, 1941, 4944, 9949 and 16384. A distance dd allows t=⌊(d−1)/2⌋t = \lfloor (d - 1)/2 \rfloor, so distances 3 and 4 share the ball of radius 1, distances 5 and 6 the ball of radius 2, and so on. Dividing 2152^{15} by the ball and taking the largest power of 2 at or below the result gives the largest dimension a linear code could have. It is 11 at d=3d = 3 and 4, 8 at d=5d = 5 and 6, 5 at d=7d = 7 and 8, 4 at d=9d = 9 and 10, 2 at d=11d = 11 and 12, and 1 from there to 15. At d=2d = 2 the ball has radius 0 and the bound allows k=15k = 15, the whole space, which is no help at all.

The bound is sharp at small distances and loose at large ones. At d=3d = 3 the Hamming code meets it exactly, since 211×16=2152^{11} \times 16 = 2^{15}. At d=11d = 11 it allows 6 codewords where only 2 fit, as a worked example at the end shows, because at large distances the limit is not room for balls but the difficulty of keeping many words far apart at once.

04.The Singleton Bound

The next bound needs no balls at all. Delete the same d−1d - 1 positions from every codeword. Two codewords differ in at least dd positions, so at least one of their differences survives the deletion, and the shortened words are still all different. Figure 2 does this for the (7,4,3)(7, 4, 3) Hamming code. Its 16 codewords, cut down to their first five bits, are 16 different words of length 5.

The 16 codewords of the (7,4,3) Hamming code with their last two positions deleted, all still distinct deleted 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 deleted 1 2 3 4 5 6 7 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 The first five positions still tell all 16 codewords apart, so 16 words fit among the 2^5 = 32 words of length 5.
Figure 2. The 16 codewords of the Hamming code with their last positions deleted. The shortened words are still distinct, so 16 words fit among the words of length 5. Data: computed by ch27_charts.py in the companion repository.

Proof. Deleting the same d−1d - 1 positions from every codeword leaves words of length n−d+1n - d + 1. Two codewords that agreed on all the remaining positions would differ in at most the d−1d - 1 deleted ones, which contradicts distance dd. So the MM shortened words are distinct, and only qn−d+1q^{n - d + 1} words of that length exist. For a linear code M=qkM = q^k, and comparing exponents gives k≤n−d+1k \le n - d + 1. ■\blacksquare

The bound carries the name of Singleton [4]. At length 15 it allows k=16−dk = 16 - d, which runs from 14 at d=2d = 2 down to 1 at d=15d = 15. The even-weight code and the repetition code meet it. The (7,4,3)(7, 4, 3) Hamming code does not, since 4<7−3+1=54 < 7 - 3 + 1 = 5, and in Figure 2 its 16 shortened words fill only half of the 32 words of length 5.

Proof. Linear Codes showed that row reduction, with the positions reordered where needed, puts a generator matrix in the systematic form G=[ Ik∣A ]G = [\,I_k \mid A\,], where IkI_k is the k×kk \times k identity matrix and AA has n−kn - k columns. Reordering positions changes no distance. Row ii of GG is a codeword with a single 1 in its identity part, so its part in AA must hold at least d−1=n−kd - 1 = n - k ones. That part has only n−kn - k positions, so every row of AA is all ones. If k=1k = 1, the single row is the all-ones word and the code is the repetition code. If k≥2k \ge 2, add rows 1 and 2. Their parts in AA cancel, and the sum has exactly two ones, so d≤2d \le 2. Then n−k+1≤2n - k + 1 \le 2, which leaves k=n−1k = n - 1 with d=2d = 2, where every row has weight 2 and the code is the even-weight code, or k=nk = n with d=1d = 1, the whole space. ■\blacksquare

Over larger alphabets the picture changes completely, and Reed–Solomon Codes builds a whole family of MDS codes that are far from trivial.

05.The Plotkin Bound

When the distance is more than half the length, a direct count of distances beats every ball argument. Plotkin found it [5]. Take the (5,2,3)(5, 2, 3) code from above and add up the distance between every ordered pair of different codewords, counting each pair twice, once in each order. There are 4×3=124 \times 3 = 12 ordered pairs, each at distance at least 3, so the total is at least 36. Now count the same total a second way, one position at a time. A position where ww of the MM codewords hold a 1 separates each of those ww from each of the other M−wM - w, in both orders, so it adds 2w(M−w)2w(M - w) to the total. Figure 3 shows that every position of the (5,2,3)(5, 2, 3) code holds exactly two ones, so each adds 2×2×2=82 \times 2 \times 2 = 8 and the total is exactly 40. The product 2w(M−w)2w(M - w) is largest at w=M/2w = M/2, where it equals M2/2M^2/2, so with four codewords no position can ever add more than 8.

The four codewords of the (5,2,3) code, the ones in each column and the two sides of the Plotkin double count position 1 2 3 4 5 c1 0 0 0 0 0 c2 1 0 1 0 1 c3 0 1 1 1 1 c4 1 1 0 1 0 w 2w(M - w) 2 8 2 8 2 8 2 8 2 8 column total 8 + 8 + 8 + 8 + 8 = 40 The distance sum, two ways pairs at distance at least 3 M(M - 1)d = 36 column by column, exactly sum of 2w(M - w) = 40 no column beats w = M/2 n M^2 / 2 = 40 36 is at most 40, which is at most 40, for M = 4 words of length 5
Figure 3. The Plotkin double count on the code. Each column holds two ones and adds ordered pairs that differ there, 40 in all, against the at least the distance demands and the at most any five columns can give. Data: computed by ch27_charts.py in the companion repository.

Proof. The left side counts the M(M−1)M(M - 1) ordered pairs of different codewords, each at distance at least dd. The middle sum counts the same distances position by position, since a position with ww ones adds 1 to the distance of exactly 2w(M−w)2w(M - w) ordered pairs. The right inequality uses 2w(M−w)≤M2/22w(M - w) \le M^2/2, which holds because M2/2−2w(M−w)=(M−2w)2/2≥0M^2/2 - 2w(M - w) = (M - 2w)^2/2 \ge 0. Dividing M(M−1)d≤nM2/2M(M - 1)d \le nM^2/2 by MM gives (M−1)d≤nM/2(M - 1)d \le nM/2, so M(2d−n)≤2dM(2d - n) \le 2d, and since 2d−n>02d - n > 0, dividing by it gives the bound. ■\blacksquare

The count can be sharpened, because MM is a whole number, and so is M/2M/2 whenever MM is even.

Proof. Write x=d/(2d−n)x = d/(2d - n), and note that x≥1x \ge 1 because d≤nd \le n. If MM is even, the Plotkin bound gives M≤2xM \le 2x, so the whole number M/2M/2 is at most xx and therefore at most ⌊x⌋\lfloor x \rfloor. If M=1M = 1, then M≤2≤2⌊x⌋M \le 2 \le 2\lfloor x \rfloor. If MM is odd and at least 3, then w(M−w)w(M - w) is largest at w=(M±1)/2w = (M \pm 1)/2, so 2w(M−w)≤(M2−1)/22w(M - w) \le (M^2 - 1)/2. The count becomes M(M−1)d≤n(M2−1)/2M(M - 1)d \le n(M^2 - 1)/2, and dividing by M−1M - 1 gives Md≤n(M+1)/2Md \le n(M + 1)/2, so M(2d−n)≤nM(2d - n) \le n and M≤n/(2d−n)=2x−1M \le n/(2d - n) = 2x - 1. A whole number at most 2x−12x - 1 is at most ⌊2x⌋−1\lfloor 2x \rfloor - 1, and ⌊2x⌋≤2⌊x⌋+1\lfloor 2x \rfloor \le 2\lfloor x \rfloor + 1, so M≤2⌊x⌋M \le 2 \lfloor x \rfloor again. ■\blacksquare

Odd distances do better still through the extension identity, which raises nn and dd together, as the first worked example shows at length 5. In the same way A2(6,3)=A2(7,4)≤2⌊4/1⌋=8A_2(6, 3) = A_2(7, 4) \le 2 \lfloor 4/1 \rfloor = 8, which the shortened Hamming code meets.

When n=2dn = 2d the denominator 2d−n2d - n vanishes and the bound says nothing, but one more step recovers it.

Proof. Take a binary code of length 2d2d and distance dd with MM codewords. In the first position one of the two bit values is held by at least M/2M/2 codewords. Keep those, which agree in that position, and delete it, which is the shortening of Modifying and Combining Codes applied to the majority value. Their distances are unchanged, so they form a code of length 2d−12d - 1 and distance dd, and 2d>2d−12d > 2d - 1. The sharpened bound gives M/2≤2⌊d/1⌋=2dM/2 \le 2\lfloor d/1 \rfloor = 2d, so M≤4dM \le 4d. ■\blacksquare

At length 15 the Plotkin bound applies from d=8d = 8 on. The plain form gives 16, 6 and 4 codewords at d=8d = 8, 9 and 10. The sharpened form with the extension identity gives 16, 4, 4, 2, 2, 2, 2 and 2 for dd from 8 to 15, where the value 4 at d=9d = 9 comes from A2(15,9)=A2(16,10)≤2⌊10/4⌋=4A_2(15, 9) = A_2(16, 10) \le 2\lfloor 10/4 \rfloor = 4. At d=8d = 8 the bound is met by the (15,4,8)(15, 4, 8) simplex code, the dual of the (15,11)(15, 11) Hamming code, whose 15 nonzero codewords all have weight 8, by the argument that proves the constant-weight theorem of Linear Codes for length 7. So A2(15,8)=16A_2(15, 8) = 16. An exercise at the end carries the bound to lengths of at least twice the distance.

Over qq symbols the same double count works with one change.

Proof. In one position let mam_a be the number of codewords holding the symbol aa, so that the qq numbers mam_a add up to MM. The ordered pairs that differ there number M2−∑ama2M^2 - \sum_a m_a^2. Expanding ∑a(ma−M/q)2≥0\sum_a (m_a - M/q)^2 \ge 0 gives ∑ama2≥M2/q\sum_a m_a^2 \ge M^2/q, an instance of the Cauchy–Schwarz inequality, so each position adds at most M2(1−1/q)=θM2M^2(1 - 1/q) = \theta M^2. The double count becomes M(M−1)d≤θnM2M(M - 1)d \le \theta n M^2, so (M−1)d≤θnM(M - 1)d \le \theta n M and M(d−θn)≤dM(d - \theta n) \le d, which gives the bound because d−θn>0d - \theta n > 0. ■\blacksquare

For q=2q = 2, θ=1/2\theta = 1/2 and the bound reads d/(d−n/2)=2d/(2d−n)d/(d - n/2) = 2d/(2d - n), the binary form again.

06.The Griesmer Bound

The Singleton bound deletes d−1d - 1 positions and keeps every codeword. The Griesmer bound deletes dd positions, chosen with care, and loses only one dimension each time. It holds only for linear codes. Griesmer proved it for binary codes [6], and the form over qq symbols given here follows Huffman and Pless [7].

Pick a codeword cc of minimum weight dd in a linear [n,k,d][n, k, d] code over qq symbols. Multiplying the symbols in one position of every codeword by a fixed nonzero constant changes no weight, so the code may be rescaled position by position until cc holds the symbol 1 wherever it is nonzero. A binary code needs no rescaling. Reorder the positions so that the dd ones of cc come first, and write a generator matrix with cc as its first row, as Figure 4 draws. The block G2G_2 under the zeros of cc is what remains after deleting the dd columns where cc is nonzero.

A generator matrix whose first row is a codeword c of weight d, scaled to all ones on its support and moved to the first d positions. Deleting the first row and those d columns leaves the block G2, which generates the residual code of length n - d, dimension k - 1 and distance at least d/q rounded up. d columns, deleted n - d columns 1 1 1 ... 1 0 0 0 ... 0 G1 G2 c, weight d k - 1 rows residual code, generated by G2 length n - d, dimension k - 1, distance at least d/q, rounded up
Figure 4. The residual code. The first row is a codeword of weight , rescaled to hold ones on its support. Deleting those columns leaves the block , which generates a code of length , dimension and distance at least .

Proof. Rescaling a position and reordering positions change no weight, so the proof may assume, as above, that cc holds 1 in its first dd positions and 0 elsewhere. Deleting positions is linear, so the result is a linear code of length n−dn - d. A codeword uu that becomes 0 under the deletion is zero outside the support of cc. If u≠0u \ne 0, its weight of at least dd must sit inside those dd positions, so it is nonzero in every one of them. Let u1u_1 be its symbol in the first. Then u−u1cu - u_1 c is a codeword that is zero outside the support of cc and zero in that first position, so its weight is below dd and it must be 0. Thus u=u1cu = u_1 c, and exactly the qq multiples of cc become 0. Each word of the residual code is therefore the image of exactly qq codewords, so the residual code has qk/q=qk−1q^k/q = q^{k-1} words and dimension k−1k - 1. For the distance, take a nonzero residual word vv, the image of a codeword u=(u′,v)u = (u', v) whose part u′u' sits on the support of cc. Let 1\mathbf{1} be the all-ones word of length dd. For every symbol α\alpha, the word u−αc=(u′−α1,v)u - \alpha c = (u' - \alpha \mathbf{1}, v) is a nonzero codeword, so wt(u′−α1)+wt(v)≥d\mathrm{wt}(u' - \alpha\mathbf{1}) + \mathrm{wt}(v) \ge d. Add these qq inequalities. In each of the dd positions of u′u' exactly one α\alpha matches the symbol there, so the weights wt(u′−α1)\mathrm{wt}(u' - \alpha\mathbf{1}) add up to d(q−1)d(q - 1) and the sum reads d(q−1)+q wt(v)≥qdd(q - 1) + q\,\mathrm{wt}(v) \ge qd. Hence wt(v)≥d/q\mathrm{wt}(v) \ge d/q, and since a weight is a whole number, wt(v)≥⌈d/q⌉\mathrm{wt}(v) \ge \lceil d/q \rceil. ■\blacksquare

Proof. Induct on kk. For k=1k = 1 the sum is dd, and a nonzero codeword of weight at least dd needs n≥dn \ge d positions. For k≥2k \ge 2 the residual code is an [n−d,k−1,d′][n - d, k - 1, d'] code with d′≥⌈d/q⌉d' \ge \lceil d/q \rceil, so by induction n−d≥∑i=0k−2⌈d′/qi⌉≥∑i=0k−2⌈⌈d/q⌉/qi⌉n - d \ge \sum_{i=0}^{k-2} \lceil d'/q^i \rceil \ge \sum_{i=0}^{k-2} \lceil \lceil d/q \rceil / q^i \rceil. A whole number mm satisfies mqi≥⌈d/q⌉m q^i \ge \lceil d/q \rceil exactly when mqi+1≥dm q^{i+1} \ge d, because mqim q^i is itself a whole number, so the smallest such mm is the same on both sides and ⌈⌈d/q⌉/qi⌉=⌈d/qi+1⌉\lceil \lceil d/q \rceil / q^i \rceil = \lceil d/q^{i+1} \rceil. The sum is therefore ∑i=1k−1⌈d/qi⌉\sum_{i=1}^{k-1} \lceil d/q^i \rceil, and adding d=⌈d/q0⌉d = \lceil d/q^0 \rceil to both sides gives the bound. ■\blacksquare

For binary codes the sum halves the distance again and again, rounding up each time. The (7,4,3)(7, 4, 3) Hamming code needs 3+2+1+1=73 + 2 + 1 + 1 = 7 positions and has exactly 7. The (8,4,4)(8, 4, 4) extended Hamming code needs 4+2+1+1=84 + 2 + 1 + 1 = 8, the (15,4,8)(15, 4, 8) simplex code 8+4+2+1=158 + 4 + 2 + 1 = 15, the (16,5,8)(16, 5, 8) and (32,6,16)(32, 6, 16) first-order Reed–Muller codes 16 and 32, and the (15,5,7)(15, 5, 7) code of the section Real Codes at Length 15 needs 7+4+2+1+1=157 + 4 + 2 + 1 + 1 = 15. All six meet the bound with equality. Other good codes fall short by one position. The (15,11,3)(15, 11, 3) Hamming code would fit in 14 positions by this count, and so would the (15,7,5)(15, 7, 5) code.

The Golay codes show that the Hamming bound and the Griesmer bound measure different things. The (23,12,7)(23, 12, 7) Golay code is perfect, since 212⋅V2(23,3)=212⋅2048=2232^{12} \cdot V_2(23, 3) = 2^{12} \cdot 2048 = 2^{23}, yet its Griesmer sum is 7, 4 and 2 followed by nine 1s, 22 in all, and the (24,12,8)(24, 12, 8) extended Golay code sums to 23, each one short of its length. A perfect code wastes no word of the space, and a code that meets the Griesmer bound wastes no position.

At length 15 the Griesmer bound allows the largest dimensions 14, 12, 11, 8, 7, 5, 4, 2 and 2 for dd from 2 to 10, and 1 for every distance from 11 to 15. It is weaker than the Hamming bound only at d=3d = 3, where it allows 12 against 11. It matches the Hamming bound at d=4d = 4, 5 and 7 and from 13 on, and is stronger at the other seven distances, 2, 6, 8, 9, 10, 11 and 12, for example 7 against 8 at d=6d = 6 and 2 against 4 at d=9d = 9.

07.The Gilbert–Varshamov Bound

Upper bounds say what cannot be built. The next two results say what can. The first is Gilbert's [8], and it is the covering argument of Figure 1.

Proof. Build a code by adding words one at a time, each at distance at least dd from all the words already chosen, until no word can be added. Every word of the space is then within distance d−1d - 1 of some codeword, or it could still be added. So the balls of radius d−1d - 1 around the MM codewords cover all qnq^n words, and M⋅Vq(n,d−1)≥qnM \cdot V_q(n, d - 1) \ge q^n. ■\blacksquare

At length 7 and distance 3 the ball of radius 2 holds V2(7,2)=1+7+21=29V_2(7, 2) = 1 + 7 + 21 = 29 words, and 27/29≈4.412^7/29 \approx 4.41, so a code built this way has at least 5 codewords, far below the 16 of the Hamming code, because the covering balls overlap heavily. The largest distance from any word to its nearest codeword is the covering radius of the code, the subject of Covering Radius.

Varshamov's version builds a linear code, and it chooses columns of a parity-check matrix instead of codewords. It appeared in 1957, and the form used here follows Huffman and Pless [7]. Linear Codes showed how the columns of a parity-check matrix set the distance. A binary linear code has minimum distance at least dd exactly when no nonempty set of at most d−1d - 1 of those columns adds up to zero.

Proof. Let r=n−kr = n - k and choose nn columns of rr bits one at a time. When column jj is chosen, forbid every sum of at most d−2d - 2 of the j−1j - 1 columns already chosen, the empty sum, which is the zero column, included. There are at most ∑i=0d−2(j−1i)=V2(j−1,d−2)\sum_{i=0}^{d-2} \binom{j-1}{i} = V_2(j - 1, d - 2) forbidden columns, which is at most V2(n−1,d−2)<2rV_2(n - 1, d - 2) < 2^r, so some column of rr bits is still free. Suppose now that some nonempty set of at most d−1d - 1 chosen columns added up to zero, and let hjh_j be the one chosen last. Then hjh_j equals the sum of the others, at most d−2d - 2 columns chosen before it, which the choice of hjh_j forbade. So no such set exists, and the code with these columns as its parity-check matrix has distance at least dd. Its dimension is nn minus the rank of that matrix, at least n−r=kn - r = k, and any subcode of dimension kk keeps the distance. ■\blacksquare

Figure 5 runs the construction at d=3d = 3 with r=3r = 3 check bits. Distance 3 forbids only the zero column and the columns already chosen, so step jj forbids exactly jj of the 8 columns of 3 bits. Seven steps succeed, and at the eighth every column is forbidden. The seven columns are all the nonzero columns of 3 bits, which is the parity-check matrix of the (7,4,3)(7, 4, 3) Hamming code, so the construction rebuilds the code that the Hamming bound says is best. The theorem itself promises as much, since V2(n−1,1)=nV_2(n - 1, 1) = n, and n<8n < 8 allows every length up to 7.

Choosing three-bit parity-check columns one at a time for distance 3, until none is left after seven 000 001 010 011 100 101 110 111 step 1 x take 1 forbidden step 2 x x take 2 forbidden step 3 x x x take 3 forbidden step 4 x x x x take 4 forbidden step 5 x x x x x take 5 forbidden step 6 x x x x x x take 6 forbidden step 7 x x x x x x x take 7 forbidden step 8 x x x x x x x x none left taken at this step a sum of at most d - 2 = 1 earlier column still free Seven columns fit, and they are the columns of the (7,4) Hamming code.
Figure 5. The Varshamov construction at with check bits. Each step forbids the zero column and every column already taken, then takes a free one. Seven columns fit before all eight are forbidden, and they form the parity-check matrix of the Hamming code. Data: computed by ch27_charts.py in the companion repository.

At length 15 the Varshamov bound guarantees linear codes of dimension 14, 11, 8, 6, 4, 3 and 2 for dd from 2 to 8, and of dimension 1 for every larger distance. The Gilbert bound is much weaker there. It guarantees 211.0002^{11.000}, 28.0812^{8.081}, 25.8302^{5.830}, 24.0772^{4.077}, 22.7292^{2.729}, 21.7202^{1.720} and 21.0002^{1.000} codewords for dd from 2 to 8, about 28.082^{8.08} at d=3d = 3 where Varshamov promises 2112^{11}. Gilbert divides by a ball of radius d−1d - 1 in length nn, while Varshamov compares against a ball of radius d−2d - 2 in length n−1n - 1, which is much smaller. Even Varshamov's count is cautious, since many forbidden sums coincide. At d=4d = 4 with 4 check bits the theorem guarantees only length 5, while taking the smallest free column at every step reaches length 8, as one of the exercises shows.

08.The Elias Bound

The Hamming bound is strong at small distances and the Plotkin bound at large ones. The Elias bound mixes the two ideas, and at length 15 it settles directly a case that the Hamming bound settles only after a change of length. It is the one result in the chapter stated without proof, and Linear Programming and Asymptotic Bounds proves it. The idea is short enough to sketch. The balls of radius rr around all 2n2^n words cover each codeword V2(n,r)V_2(n, r) times, so some ball contains at least the average share M⋅V2(n,r)/2nM \cdot V_2(n, r)/2^n of the codewords. Translating by its center turns those codewords into words of weight at most rr that still lie at distance at least dd from one another, and a Plotkin count over such light words limits how many there can be. The statement below follows Huffman and Pless [7].

Every allowed rr gives a bound, and the smallest of them is the one to use. At length 15 the best radius is 1 for d=2d = 2 and 3, 2 for d=4d = 4 and 5, 3 for d=6d = 6, 4 for d=7d = 7, and 7 from d=8d = 8 on. Rounded down, the bound on the number of codewords is 30720, 5421, 2031, 883, 284, 104, 30, 11, 7, 6, 5, 4, 4 and 3 for dd from 2 to 15, and the largest dimension it allows a linear code is 14, 12, 10, 9, 8, 6, 4, 3, 2, 2, 2, 2, 2 and 1.

Most of these lose to another bound. The one that matters is at d=4d = 4. With r=2r = 2 the denominator is r2−15r+30=4r^2 - 15r + 30 = 4 and the ball is V2(15,2)=121V_2(15, 2) = 121, so the bound is (30/4)⋅32768/121(30/4) \cdot 32768/121, which rounds down to 2031. That is below 211=20482^{11} = 2048, so no binary code of length 15 and distance 4 has 2048 codewords, linear or not. Applied directly at length 15, the Hamming and Griesmer bounds both allow k=11k = 11 at d=4d = 4, and the Elias bound is the first applied there to rule it out. The section Real Codes at Length 15 reaches a sharper verdict through length 14.

09.Real Codes at Length 15

Table 1 lists one code of length 15 for every distance. Several are built from a polynomial, a construction the part on cyclic codes develops properly, and the recipe needs only this much. Write the coefficients of a polynomial g(x)g(x) of degree n−kn - k as a row of nn bits, constant term first, and shift that row one place at a time to make kk rows. Those rows generate the code. For g(x)=x4+x+1g(x) = x^4 + x + 1 the row is 110010000000000, and its 11 shifts generate a (15,11,3)(15, 11, 3) Hamming code. Multiplying g(x)g(x) by x+1x + 1 gives x5+x4+x2+1x^5 + x^4 + x^2 + 1, whose 10 shifts generate a code in which every codeword is a multiple of x+1x + 1. Setting x=1x = 1 in a codeword counts its ones modulo 2, and setting x=1x = 1 in a multiple of x+1x + 1 gives 0, so every codeword has even weight. The code also sits inside the Hamming code, so its distance is at least 3 and even, hence at least 4, and the script finds exactly 4.

The degree-8 polynomial x8+x7+x6+x4+1x^8 + x^7 + x^6 + x^4 + 1 and the degree-10 polynomial x10+x8+x5+x4+x2+x+1x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1 generate the (15,7,5)(15, 7, 5) and (15,5,7)(15, 5, 7) codes, which BCH Codes constructs and explains. Multiplying the degree-8 polynomial by x+1x + 1 keeps its even-weight codewords, as before, and gives a (15,6,6)(15, 6, 6) code. The script generates every codeword of every code in the table and confirms each distance.

Table 1. A binary code of length 15 for each distance, with how it is built. The distance column names every the code serves, since a code of distance 10 also has distance at least 9.

Distances servedCode (n,k,d)(n, k, d)Built from
2(15,14,2)(15, 14, 2) even-weight codeevery word with an even number of ones
3(15,11,3)(15, 11, 3) Hamming codeshifts of x4+x+1x^4 + x + 1
4(15,10,4)(15, 10, 4) even-weight subcodeshifts of (x+1)(x4+x+1)(x + 1)(x^4 + x + 1)
5(15,7,5)(15, 7, 5)shifts of x8+x7+x6+x4+1x^8 + x^7 + x^6 + x^4 + 1
6(15,6,6)(15, 6, 6)shifts of (x+1)(x8+x7+x6+x4+1)(x + 1)(x^8 + x^7 + x^6 + x^4 + 1)
7(15,5,7)(15, 5, 7)shifts of x10+x8+x5+x4+x2+x+1x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1
8(15,4,8)(15, 4, 8) simplex codethe dual of the Hamming code
9 and 10(15,2,10)(15, 2, 10)rows with ones in bits 0 to 9 and in bits 5 to 14
11 to 15(15,1,15)(15, 1, 15) repetition codethe all-zeros and all-ones words

Source: reproduced by ch27_bounds_on_codes.py.

Two kinds of agreement close a case. The first is equality. The simplex code meets two bounds at once, with Griesmer sum 8+4+2+1=158 + 4 + 2 + 1 = 15 and with 16 codewords, the Plotkin value at d=8d = 8. The second kind needs no equality. At d=7d = 7 the Hamming bound allows 32768/576≈56.932768/576 \approx 56.9 codewords. The (15,5,7)(15, 5, 7) code has only 32, but 64 would exceed 56.9, so no linear code of length 15 and distance 7 has dimension 6, and k=5k = 5 is the best.

A bound applied to a modified code can say more than the same bound applied directly. Suppose a [15,11,4][15, 11, 4] code existed. Puncturing it, deleting one position, gives a [14,11,3][14, 11, 3] code, and the Hamming bound at length 14 needs 211(1+14)≤2142^{11}(1 + 14) \le 2^{14}, that is 15≤815 \le 8, which is false. So no [15,11,4][15, 11, 4] code exists, and the (15,10,4)(15, 10, 4) code is the best linear code at distance 4. Deleting a position works for nonlinear codes too, which is the extension identity, so A2(15,4)=A2(14,3)≤⌊214/15⌋=1092A_2(15, 4) = A_2(14, 3) \le \lfloor 2^{14}/15 \rfloor = 1092 for every code, linear or not, well below the 2031 of the Elias bound.

Table 2 collects every bound at length 15 beside the codes of Table 1, and Figure 6 draws the same numbers. For linear codes a bound applied directly closes a case wherever the smallest upper bound equals the dimension of a code that exists, and that happens at twelve of the fourteen distances. At d=5d = 5 the best code here has dimension 7 while the Hamming and Griesmer bounds allow 8, and at d=6d = 6 the code has dimension 6 while the Griesmer bound allows 7. The residual code closes both gaps. A [15,8,5][15, 8, 5] code would leave a [10,7,3][10, 7, 3] residual code, a [15,7,6][15, 7, 6] code a [9,6,3][9, 6, 3] one, and the Hamming bound rules out both, as a worked example at the end proves. So every code of Table 1 is the best linear code for its distances.

Table 2. The largest dimension each bound allows at length 15, the Varshamov guarantee, and the dimension of the code in the previous table. A case is closed when the smallest upper bound equals the code's dimension, or, at and 6, when the Hamming bound applied to the residual code rules out one dimension more.

ddSingletonHammingPlotkinGriesmerEliasVarshamovCodeStatus
21415n/a14141414closed
31311n/a12121111closed
41211n/a1110810closed
5118n/a8967closed, residual
6108n/a7846closed, residual
795n/a5635closed
88544424closed
97422312closed
106422212closed
115211211closed
124211211closed
133111211closed
142111211closed
151111111closed

Source: reproduced by ch27_bounds_on_codes.py.

The largest dimension k allowed by each bound at length 15, for distances 2 to 15, with the codes that exist 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 3 6 9 12 15 minimum distance d, at length n = 15 largest dimension k Singleton, k = n - d + 1 Hamming, sphere packing Griesmer, linear codes Elias Plotkin, for d at least 8 Varshamov, a code exists a code listed in the text
Figure 6. The largest dimension each bound allows at length 15, for from 2 to 15, with the codes that exist. Singleton, Hamming, Griesmer, Elias and Plotkin are upper bounds, Varshamov is a guarantee from below, and the codes of the text sit between them. Data: computed by ch27_charts.py in the companion repository.

10.What the Bounds Tell a Designer

A memory word of 64 data bits is the case hardware meets most often, and the bounds turn directly into check-bit budgets. A single-error-correcting linear code with rr check bits has length n=64+rn = 64 + r and needs 2r≥n+12^r \ge n + 1, the Hamming bound at radius 1, and the smallest such rr is 7. A double-error-correcting code needs the Hamming bound at radius 2, 1+n+(n2)≤2r1 + n + \binom{n}{2} \le 2^r, and the smallest rr that passes is 12, since 1+76+(762)=2927≤40961 + 76 + \binom{76}{2} = 2927 \le 4096.

A SECDED code needs 8. Seven check bits pass the radius-1 count at length 71, since 27=128≥722^7 = 128 \ge 72. But a [71,64,4][71, 64, 4] code, punctured, would give a [70,64,3][70, 64, 3] code, which needs 26=64≥1+70=712^6 = 64 \ge 1 + 70 = 71, and that fails. So 8 is the floor, and the Hsiao codes of SECDED and Hsiao Codes meet it. The same move shows that a code correcting two errors and detecting three needs at least 13 check bits, because puncturing it leaves a double-error-correcting code with one check bit fewer.

Beyond SECDED built a (78,64)(78, 64) double-error-correcting code with 14 check bits and a (79,64)(79, 64) code that also detects three errors, with 15. Each sits two bits above its floor. The bounds of this chapter do not say whether either floor can be reached, only that nothing below it can.

Table 3. Check bits needed for a data width of bits. The SEC and SECDED columns are met by Hamming and Hsiao codes. The DEC column is a floor from the Hamming bound at radius 2, which no double-error-correcting code can go below.

Data bits kkSECSECDEDDEC floor
4346
8457
16569
326710
647812
1288914
25691016

Source: reproduced by ch27_bounds_on_codes.py.

Table 3 extends the budget from 4 to 256 data bits, and Figure 7 plots it. Each doubling of the data width adds one check bit for single correction, and one or two for double correction, because a ball of radius 2 holds about n2/2n^2/2 words and so grows fourfold when nn doubles.

Check bits needed for single error correction, single error correction with double error detection, and double error correction, against the data width 4 8 16 32 64 128 256 0 4 8 12 16 20 data bits k, on a doubling scale check bits r SEC SECDED DEC SEC, smallest r with 2^r at least k + r + 1 SECDED, one check bit more than SEC DEC, the sphere-packing floor for radius 2 At 64 data bits: 7, 8 and at least 12
Figure 7. Check bits against data width on a doubling scale. Single error correction needs the smallest with , SECDED one bit more, and double error correction at least the sphere-packing floor for radius 2. At 64 data bits the three are 7, 8 and at least 12. Data: computed by ch27_charts.py in the companion repository.

A bound tells a designer when to stop searching. At 64 data bits the 7-bit Hamming code and the 8-bit SECDED code meet their bounds, so no cleverer check matrix will save a bit. Where a gap remains, the bound caps what any search could win, two bits for the 14-bit double-error-correcting code.

Nonlinear codes are the one escape that a bound on linear codes leaves open, and the length-8 example shows how small the prize is, log⁡220≈4.322\log_2 20 \approx 4.322 bits against the 4 bits of the 16-word linear code. Without linearity there is no generator matrix, so the encoder becomes a lookup table, and there is no parity-check matrix, so the decoder in general must compare the received word against stored codewords instead of computing a syndrome with XOR trees. That is why the codes in memories and on buses throughout this part are linear, and why the linear bounds are the ones that set their budgets.

11.Looking Ahead

The next chapter, Verifying ECC Hardware, turns from the codes to the circuits that encode and decode them, and to showing that a circuit computes exactly the code it was meant to compute.

Every bound here was evaluated at one length. Linear Programming and Asymptotic Bounds lets the length grow with the ratio δ=d/n\delta = d/n held fixed, so that each bound becomes a curve for the best rate k/nk/n. There the Gilbert–Varshamov argument guarantees rates near 1−h(δ)1 - h(\delta), where hh is the binary entropy function of Information and Entropy, the Elias bound becomes a curve that lies below the Hamming and Plotkin curves, and the Delsarte linear programming bound and the McEliece–Rodemich–Rumsey–Welch bound push the upper curve down further. How far apart the best curves from above and from below truly are is still an open question.

12.Worked Examples

13.Exercises

References

  1. [1]Best, M. R. and Brouwer, A. E. and MacWilliams, F. J. and Odlyzko, A. M. and Sloane, N. J. A. (1978). “Bounds for Binary Codes of Length Less Than 25.” IEEE Transactions on Information Theory, 24(1), pp. 81–93. doi:10.1109/TIT.1978.1055827
  2. [2]Brouwer, Andries E. (2026). “Small Binary Codes: Table of General Binary Codes.” Online table. Accessed 2026-11-15. https://aeb.win.tue.nl/codes/binary-1.html
  3. [3]Hamming, Richard W. (1950). “Error Detecting and Error Correcting Codes.” Bell System Technical Journal, 29(2), pp. 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x
  4. [4]Singleton, Richard C. (1964). “Maximum Distance q-nary Codes.” IEEE Transactions on Information Theory, 10(2), pp. 116–118. doi:10.1109/TIT.1964.1053661
  5. [5]Plotkin, Morris (1960). “Binary Codes with Specified Minimum Distance.” IRE Transactions on Information Theory, 6(4), pp. 445–450. doi:10.1109/TIT.1960.1057584
  6. [6]Griesmer, J. H. (1960). “A Bound for Error-Correcting Codes.” IBM Journal of Research and Development, 4(5), pp. 532–542. doi:10.1147/rd.45.0532
  7. [7]Huffman, W. Cary and Pless, Vera (2003). “Fundamentals of Error-Correcting Codes.” Cambridge University Press. doi:10.1017/CBO9780511807077
  8. [8]Gilbert, E. N. (1952). “A Comparison of Signalling Alphabets.” Bell System Technical Journal, 31(3), pp. 504–522. doi:10.1002/j.1538-7305.1952.tb01393.x

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes