Bit strings under XOR gain a scaling by field elements and become a vector space. The chapter counts bases and subspaces, meets words orthogonal to themselves, and finds the parity checks inside the dual code.
The previous chapter, Groups and Cosets, showed that a binary code closed under XOR is a subgroup of the group of all words, and Lagrange's theorem fixed its size at a power of 2. The code C5={00000,01101,10110,11011} has 4=22 words, but the group axioms say nothing about what the exponent 2 counts. The missing ingredient came from Integers and Modular Arithmetic, which built number systems in which every nonzero element has a multiplicative inverse.
A codeword can be multiplied by a number as well as added to another codeword. Over the bits 0 and 1 that scaling is nearly invisible, but over the residues modulo 5 a nonzero word has four different nonzero multiples. Adding scaling to the group structure produces a vector space. The exponent 2 of C5 turns out to be its dimension, the number of message bits the code carries, and a two-word basis of C5 is a recipe for encoding.
The chapter proves that a space of dimension k over a field of q elements has exactly qk vectors, counts bases and subspaces, and meets a dot product under which a nonzero word can be orthogonal to itself. Its last sections prove that the dimensions of a code and its dual, the set of words orthogonal to every codeword, add up to the length, and find the parity checks of the code inside the dual.
Take the eight words of three bits, 000 through 111. Groups and Cosets combined two such words by XOR, which adds them bit by bit with 1⊕1=0. From here on that operation is written with an ordinary plus sign, because it is addition modulo 2 in each position. So 101+011=110. Every word added to itself gives 000.
A word can also be multiplied by a bit. Multiplying 101 by 1 leaves 101, and multiplying it by 0 gives 000. These are the only two choices. The set of 3-bit words with this addition and this scaling is written GF(2)3, and its eight members are called vectors.
Figure 1 draws the eight vectors as the corners of a cube, joining two corners whenever their words differ in one bit. Moving along an edge adds one of the words 100, 010 or 001, and each such step changes the weight by one, so every edge joins an even-weight word to an odd-weight word. The four even-weight words 000, 011, 101 and 110 form a set E that is closed under addition, and the odd-weight words form its coset 001+E.
Figure 1. The eight words of GF(2)3 as the corners of a cube, with an edge wherever two words differ in one bit. The even-weight words form the subspace E, and the odd-weight words form its coset 001+E.
Now replace the bits by the residues 0,1,2,3,4 modulo 5 and consider pairs (x,y) of them, added and multiplied entry by entry modulo 5. The sum (1,2)+(3,4) is (4,1), because 1+3=4 and 2+4=6 leaves 1. Scaling by 3 gives 3(1,2)=(3,6)=(3,1). There are 52=25 such pairs, and the set of them is written GF(5)2. Over three residues, the triples form GF(3)3 with 33=27 members.
Scaling now does something. The multiples of (1,2) by the scalars 0 through 4 are (0,0), (1,2), (2,4), (3,1) and (4,3), four of them nonzero and all different, and adding (1,2) to itself gives (2,4) rather than the zero vector. A nonzero binary word has exactly one nonzero multiple, itself, which is why the binary codes of earlier chapters could be studied with addition alone.
The scalars in both examples share the property that made Integers and Modular Arithmetic single out prime moduli, which is that every nonzero element has a multiplicative inverse. Scalars with that property form a field, and the definition below repeats the one in Integers and Modular Arithmetic with both distributive laws written out.
Proof. Since 0+0=0, the second distributive law gives 0a=(0+0)a=0a+0a. Adding −(0a) to both sides and regrouping by associativity leaves 0=0a. ■
The residues modulo a prime p form a field, and the residues modulo a composite number do not, by the theorem in Integers and Modular Arithmetic on when modular arithmetic forms a field. In Z4, for instance, 2⋅2=0 and 2 has no inverse. The field of residues modulo p is written GF(p), and a field with q elements is written GF(q), the Galois field named after Évariste Galois. In GF(2) the negative of 1 is 1 itself, and in GF(5) the negative of 2 is 3.
Fields with 4, 8 and 9 elements do exist, but they are not residues of the integers, and Part III, Finite Fields and Their Arithmetic, builds them. Every proof in this chapter uses only the rules of the definition, so each result holds over those fields as well. The examples stay with GF(2), GF(3) and GF(5), where every product can be checked by hand.
The words of GF(2)3 and the pairs of GF(5)2 obey the same eight rules, and those rules are taken as the definition.
The first four rules say that V is an abelian group under addition, with an identity 0 called the zero vector and a negative −v for every vector. The last four tie the scaling to the field. Giuseppe Peano gave the first axiomatic definition of a vector space in 1888, with the real numbers as scalars [1], and the same rules work over any field.
Proof. Each rule, read one position at a time, is a rule of the field. The i-th entry of a(u+v) is a(ui+vi), which equals aui+avi by the first distributive law, and that is the i-th entry of au+av. In the same way the second distributive law gives (a+b)v=av+bv, associativity of multiplication gives a(bv)=(ab)v, and 1vi=vi gives 1v=v. The four addition rules come from the field's addition, with the list of zeros as the zero vector and the list of negatives −vi as −v. ■
The companion script checks all eight rules on every triple of vectors in GF(2)3, GF(3)2 and GF(5)2. Three more facts follow from the rules alone.
Proof. By the last rule, 0v=(0+0)v=0v+0v. Adding the negative of 0v to both sides leaves 0=0v. In the same way c0=c(0+0)=c0+c0, and cancelling one copy of c0 leaves c0=0. Finally v+(−1)v=1v+(−1)v=(1+(−1))v=0v=0, so (−1)v is a negative of v. A group has only one inverse for each element, by the lemma in Groups and Cosets that a group has one identity and one inverse, so (−1)v=−v. ■
In GF(5)2 the negative of (1,2) is 4(1,2)=(4,8)=(4,3), and indeed (1,2)+(4,3)=(5,5)=(0,0). Over GF(2) the scalar −1 is 1, so −v=v, which is the fact behind v+v=0 for bit strings.
The set E of even-weight words of length 3 is a vector space in its own right, sitting inside GF(2)3.
A subspace is a vector space under the same operations. The eight rules already hold for all vectors of V, and the closure conditions keep every sum and multiple inside W. The negative of each u in W lies in W as well, since it is (−1)u by the lemma on scaling by zero and by minus one. One condition is enough to check in practice.
Proof. A subspace contains cu by closure under scaling and then cu+v by closure under addition. Conversely, suppose W passes the test, and pick any u in W, which exists because W is nonempty. Taking c=−1 and v=u gives (−1)u+u=0 in W, by the previous lemma. Taking v=0 then gives cu+0=cu in W for every scalar c, and taking c=1 gives u+v in W for all u and v. ■
Over GF(2) the only scalars are 0 and 1, so closure under scaling holds as soon as 0 is in W, and 0=u+u is in any nonempty set closed under addition. A nonempty set of binary words closed under addition is therefore a subspace. Of the 28=256 subsets of GF(2)3, the companion script finds 16 that pass the subspace test, and they are exactly the 16 nonempty subsets closed under addition alone. The code C5, closed under addition, is therefore a subspace of GF(2)5.
The same shortcut works over any prime field, since a scalar c of GF(p), read as an integer from 0 to p−1, gives cv=(1+⋯+1)v=v+⋯+v with c copies of v, so the subspaces of GF(p)n are exactly its subgroups. Over the four-element field GF(4) it fails, since {0,1} is closed under addition there but not under scaling.
A code that is a subspace of GF(q)n is called a linear code. Slepian's 1956 study treated binary codes closed under addition as groups and decoded them through their cosets [2], and the vector space view adds the scaling that larger fields need.
The quickest way to produce a subspace is to start from a few vectors and take everything they can build.
Proof. The combination with every ai=0 is 0, so the span is nonempty. For two combinations u=∑aivi and w=∑bivi and a scalar c, the rules of a vector space regroup cu+w as ∑(cai+bi)vi, which is again a combination of the vi. The subspace test applies. A subspace containing every vi contains every aivi by closure under scaling and every sum of those by closure under addition, so it contains the span. ■
Over GF(2) each coefficient is 0 or 1, so a linear combination is the sum of some of the vectors. Figure 2 builds the span of 1100, 0110 and 0011 one vector at a time. The span of nothing is {0000}. Adding 1100 gives {0000,1100}. Adding 0110 brings in 0110 and 1100+0110=1010, so the span becomes {0000,0110,1010,1100}. Adding 0011 doubles it again, to the eight even-weight words of length 4.
Figure 2. The span of 1100, 0110 and 0011 built one vector at a time. Each vector outside the current span doubles it, from 1 word to 2, 4 and 8.
Over GF(2), if S is the current span and w is a new vector outside it, the new span is S together with the coset w+S, because each new combination either uses w or does not. The two sets share no word, since a common word s=w+s′ would put w=s−s′ inside S. They have the same size, because s↦w+s matches each word of S with one word of w+S, and w+s=w+s′ forces s=s′. So the span exactly doubles whenever the new vector lies outside it. Over GF(q) the same argument with the q sets cw+S for c=0,1,…,q−1 multiplies it by q.
Over GF(5) a single vector already spans five points. The span of (1,2) is the line L={(0,0),(1,2),(2,4),(3,1),(4,3)} through the origin. Adding (0,1), which is not on L, gives a span of 25 points, the whole plane. Adding (2,4) instead gives back the same 5 points, because (2,4)=2(1,2) was on L already.
Figure 3 draws the plane as a grid and writes in each point the residue y−2xmod5. The points of L are exactly those with digit 0, since a point of L has the form (c,2c). The digit stays the same along each parallel copy of L, because moving from (x,y) to (x,y)+c(1,2) changes y−2x by 2c−2c=0. The five digits therefore name the five cosets of L, among them (0,1)+L={(0,1),(1,3),(2,0),(3,2),(4,4)} with digit 1. The digit is a syndrome over GF(5), a number computed from a point that names the coset of the line containing it.
Figure 3. The plane GF(5)2 as a grid. The multiples of (1,2) form a line L through the origin, and the digit y−2xmod5 at each point names which of the five parallel copies of L it lies on.
In the doubling of Span, each new vector lay outside the span of the ones before it. The list 1100, 0110, 1010 behaves differently, because 1010=1100+0110 already lies in the span of the first two, and adding it builds nothing new. Independence is the name for a list in which no vector is wasted that way.
The list 1100, 0110, 1010 is dependent, since 1100+0110+1010=0000 with all three coefficients 1. The list 1100, 0110, 0011 is independent. Over GF(5) the pair (1,2), (2,4) is dependent, since 2(1,2)+4(2,4)=(2+8,4+16)=(10,20)=(0,0). The pair (1,2), (0,1) is independent, since a(1,2)+b(0,1)=(a,2a+b) is zero only when a=0, and then b=0 as well.
Over GF(2) a combination with some nonzero coefficient is the sum of a nonempty part of the list, so a binary list is independent exactly when no nonempty part of it sums to 0.
Proof. Suppose ∑civi=0 with cj=0. Because the scalars form a field, cj has an inverse. Moving the term cjvj to the other side and multiplying by −cj−1 gives vj=−cj−1∑i=jcivi, a combination of the others. Conversely, if vj=∑i=jbivi, then ∑i=jbivi+(−1)vj=0, a combination equal to zero whose coefficient on vj is −1=0. ■
Proof. Suppose ∑aivi+bw=0. If b=0, then w=−b−1∑aivi lies in the span of the vi, which is false. So b=0, the relation reduces to ∑aivi=0, and independence of the vi forces every ai=0. ■
The even-weight words E={000,011,101,110} are spanned by 110 and 011, and those two are independent. Each word of E is then a combination of them in exactly one way. The word 101 is 1⋅110+1⋅011, so its coordinates in this list are (1,1), and the word 011 is 0⋅110+1⋅011, with coordinates (0,1).
The definition of dimension assumes that every basis of V has the same length. Over a finite field that follows from counting.
Proof. The map reaches every vector of V because the basis spans V. It never sends two different coefficient lists to the same vector, because ∑aivi=∑bivi gives ∑(ai−bi)vi=0, and independence forces ai−bi=0 for each i. A bijection between finite sets makes their sizes equal, and GF(q)k has qk elements, since each of its k entries has q choices. ■
Proof. If V had bases of lengths k and k′, the theorem would give qk=∣V∣=qk′. Since q≥2, the powers of q strictly increase, so k=k′. ■
The theorem assumes a basis exists, and for subspaces of GF(q)n one always does.
Proof. Build a list one vector at a time. Start with the empty list, which is independent and spans {0}. While the span of the list is smaller than W, choose a vector of W outside the span and append it. The extension lemma keeps the list independent, and the span stays inside W because W is a subspace. After j steps the list is a basis of its own span, so by the theorem that span has qj vectors, all of them inside GF(q)n, which has qn. Hence qj≤qn and j≤n, the process stops after at most n steps, and it stops only when the list spans W. ■
In a space V of dimension k, any k independent vectors form a basis, because their span holds qk vectors inside a set of qk, so it is all of V.
The words 01101 and 10110 are independent and their sum is 11011, so they span C5 and dimC5=2, matching 4=22. The repetition code R5={00000,11111} has dimension 1, and the even-weight words of length 4 have dimension 3.
This is the meaning of the exponent left open in Groups and Cosets. A linear code of length n and dimension k over GF(q) is called an [n,k] code, and it has qk codewords. Choosing a basis g1,…,gk turns every message (a1,…,ak) of k symbols into the codeword a1g1+⋯+akgk, and the theorem that a space of dimension k has qk vectors says that this encoding uses every codeword exactly once. With the basis 10110, 01101 of C5, the message 11 encodes to 11011. The basis vectors written as the rows of a table form a generator matrix [3].
Counting the bases of GF(2)3 shows how independence constrains each choice. The first vector can be any of the 7 nonzero words. The second must avoid the 2 words in the span of the first, leaving 6 choices. The third must avoid the 4 words spanned by the first two, leaving 4. So there are 7×6×4=168 ordered bases.
Proof. Choose the vectors in order. Once i independent vectors have been chosen, they form a basis of their span, which therefore has qi vectors. A next vector inside that span would make the list dependent, by the dependence lemma, and a next vector outside it keeps the list independent, by the extension lemma. So there are exactly qn−qi choices for the next vector, whichever i vectors came before, and multiplying the choices over i=0,…,k−1 gives the product. ■
With k=n the lists are the ordered bases of GF(q)n. The formula gives (4−1)(4−2)=6 for GF(2)2, 8×6=48 for GF(3)2, 24×20=480 for GF(5)2 and 26×24×18=11,232 for GF(3)3.
Proof. Count the pairs made of a k-dimensional subspace W and an ordered basis of W in two ways. Every ordered list of k independent vectors is a basis of exactly one such subspace, its span, so the number of pairs is the product of Equation 4. On the other hand, a subspace W of dimension k has qk vectors, and its ordered bases are its ordered lists of k independent vectors, since k independent vectors of W always form a basis of W. Repeating the previous proof inside W gives ∏i=0k−1(qk−qi) of them, the same number for every W. So the number of pairs is also the number of subspaces times that product, and dividing gives the formula. ■
The bracket is called a Gaussian binomial coefficient. For GF(2)3 it gives 7/1=7 lines and (8−1)(8−2)/((4−1)(4−2))=42/6=7 planes. With the zero subspace and the whole space that makes 1+7+7+1=16, the same 16 subspaces the subspace test found among the 256 subsets. Table 1 lists the counts for six small spaces, each found both by the formulas and by building every subspace directly.
Table 1. Vectors, ordered bases and subspaces of six small spaces, with the subspaces listed by dimension from 0 up to n
Space
Vectors
Ordered bases
Subspaces by dimension
Total
GF(2)2
4
6
1, 3, 1
5
GF(2)3
8
168
1, 7, 7, 1
16
GF(2)4
16
20,160
1, 15, 35, 15, 1
67
GF(3)2
9
48
1, 4, 1
6
GF(3)3
27
11,232
1, 13, 13, 1
28
GF(5)2
25
480
1, 6, 1
8
Source: reproduced by ch15_vector_spaces_over_finite_fields.py.
Figure 4 sets the Gaussian coefficients for length 7 beside the ordinary binomial coefficients (k7), which count the ways to choose k of 7 positions. There are 29,212 subspaces of GF(2)7 in all, and both rows read the same backward as forward, so there are as many subspaces of dimension k as of dimension n−k. Orthogonal Complements and Dual Codes explains why. Goldman and Rota developed the counting of subspaces of a finite vector space as a parallel to the counting of subsets [4].
Figure 4. The subspaces of GF(2)7 of each dimension k, 29,212 in all, beside the (k7) ways to choose k of the 7 positions. Both rows read the same backward as forward. Data: computed by ch15_charts.py in the companion repository.
The formula also gives the chance that n vectors of GF(q)n chosen at random form a basis. Dividing the number of ordered bases by the qn2 equally likely lists gives
qn21i=0∏n−1(qn−qi)=j=1∏n(1−q−j),
(6)
where each factor qn−qi was divided by qn and j=n−i. For GF(2)2 the fraction is 6/16=3/8, which the product gives as (1−1/2)(1−1/4)=0.375, and for GF(2)3 it is 168/512=21/64. Each factor is less than 1, so the product shrinks as n grows. Over GF(2), multiplying out shows that (1−x)(1−y)≥1−x−y whenever x and y lie between 0 and 1, so the factors after the first keep the product at least 1−41−81−⋯=21, and with the first factor 21 the whole product stays at or above 41. A product that only decreases and stays above 41 levels off, as Figure 5 shows. At n=10 the fraction is about 0.289 over GF(2), 0.560 over GF(3) and 0.760 over GF(5), so ten random binary words of length 10 usually fail to form a basis.
Figure 5. The fraction of lists of n vectors of GF(q)n that form a basis, for q=2, 3 and 5. The fraction falls as n grows and levels off, lower for smaller fields. Data: computed by ch15_charts.py in the companion repository.
Over the integers, the word 11 multiplied entrywise by itself and summed gives 1+1=2. In ordinary geometry that sum of squares is the squared length of a vector, and it is positive for every vector except zero, which is what makes lengths and angles possible. Over GF(2) the same sum is 1+1=0, so a nonzero word has a dot product of zero with itself.
Over GF(2) the product xiyi is 1 only where both words have a 1, so x⋅y is the number of such shared positions, reduced modulo 2. The word 1111 has 1111⋅1111=0, while 111⋅111=1. The words 1100 and 1010 share only position 1, so 1100⋅1010=1.
In hardware the binary dot product is a row of AND gates feeding a tree of XOR gates, as Figure 6 draws for 1111⋅1111. A parity check is such a circuit, with the checked positions marked by the 1s of y.
Figure 6. The dot product over GF(2) as a circuit. Each product of entries is an AND gate and the sum is a tree of XOR gates, here computing 1111⋅1111=0.
Proof. Symmetry holds because xiyi=yixi in the field. For the second rule, the i-th term of (ax+by)⋅z is (axi+byi)zi=axizi+byizi by distributivity, and summing over i gives a(x⋅z)+b(y⋅z). ■
Proof. Each entry is 0 or 1, and 0⋅0=0 and 1⋅1=1, so vi2=vi. Therefore v⋅v=v1+⋯+vn, which is the number of 1s in v reduced modulo 2. That is 0 exactly when the weight is even. ■
A vector with v⋅v=0 is called self-orthogonal. In GF(2)4 the self-orthogonal vectors are the 8 even-weight words, the zero word among them. In GF(3) both nonzero elements square to 1, since 12=1 and 22=4 leaves 1, so a ternary vector has v⋅v equal to its number of nonzero entries modulo 3, and (1,1,1)⋅(1,1,1)=3=0. In GF(3)2 no nonzero vector is self-orthogonal, as an exercise shows. In GF(5) the sum 1+4=5 vanishes, so (1,2)⋅(1,2)=0. The plane GF(5)2 has 8 nonzero self-orthogonal vectors, (1,2), (1,3), (2,1), (2,4), (3,1), (3,4), (4,2) and (4,3), which are the nonzero points of two lines, the line through (1,2) and the line through (1,3).
Orthogonality keeps its algebra and loses its geometry. The syndrome of C5 in Groups and Cosets computed three parity bits, x1+x2+x3, x1+x4 and x2+x5, and these are the dot products of the word x=x1x2x3x4x5 with 11100, 10010 and 01001. The digit y−2x of a point (x,y) of the plane over GF(5), where x is now a single coordinate, is a dot product too, (x,y)⋅(3,1), since −2 and 3 are the same residue modulo 5.
The three check words of C5 are orthogonal to every codeword, and collecting every word with that property gives a second code.
Proof. The zero vector has 0⋅c=0 for every c. If y and z lie in C⊥ and a is a scalar, bilinearity gives (ay+z)⋅c=a(y⋅c)+z⋅c=0 for every c in C, so the subspace test applies. For the second claim, one direction is immediate. In the other, if y⋅ci=0 for each i, then every c=∑aici in C has y⋅c=∑ai(y⋅ci)=0, again by bilinearity. ■
The dual of C5 can now be computed from its basis 10110, 01101. A word y has y⋅10110=y1+y3+y4 and y⋅01101=y2+y3+y5, so y lies in the dual exactly when
y1+y3+y4=0,y2+y3+y5=0.
(8)
Over GF(2) the scalar −1 is 1, so these say y1=y3+y4 and y2=y3+y5. The entries y3, y4 and y5 can be chosen freely, 23=8 ways, and each choice fixes y1 and y2. The free choices 100, 010 and 001 give 11100, 10010 and 01001, the three syndrome checks. On positions 3, 4 and 5 they read 100, 010 and 001, so they are independent, and every y in the dual equals y3(11100)+y4(10010)+y5(01001), so they span it. Figure 7 lists the result,
a code of dimension 3 holding every parity check C5 satisfies. Unlike a line and its perpendicular in the ordinary plane, which meet only at the origin, C5 and its dual share the nonzero word 11011.
Figure 7. The code C5 and its dual C5⊥. The dual holds the three parity checks of the syndrome and every sum of them, and the two codes share the words 00000 and 11011.
The dimensions 2 and 3 add up to the length 5, and that is no accident. The proof rests on the positions where a code shows its message.
In C5, positions 1 and 2 take the patterns 00, 01, 10 and 11, one for each codeword, and the other three entries follow from them by x3=x1+x2, x4=x1 and x5=x2, as Figure 8 shows.
Figure 8. Positions 1 and 2 form an information set of C5. They take each of the four patterns once, and the other three entries follow from them.
Proof. By induction on k. If k=0, then C={0} and the empty set of positions works, since the one codeword shows the one empty pattern. If k≥1, choose a nonzero codeword c and a position i with ci=0. The map f(x)=xi from C to GF(q) respects addition, and it is onto, because f(tci−1c)=t for every scalar t. Its kernel C′={x∈C∣xi=0} is a subspace. By the theorem on kernels, images and fibers in Groups and Cosets, each of the q fibers of f is a coset of the kernel, and by the coset rules each coset has as many elements as the kernel, so ∣C∣=q∣C′∣ and ∣C′∣=qk−1. A basis of C′, which exists by the basis lemma, therefore has k−1 vectors, so the induction hypothesis gives an information set S′ of C′ with k−1 positions. Position i is not in S′, since every word of C′ shows 0 there and S′ must show every pattern. Let S=S′∪{i}, a set of k positions. If two codewords x and y agree on S, then x−y is a codeword with 0 at position i, so it lies in C′, and it is 0 on S′. The zero word of C′ already shows the all-zero pattern on S′, and each pattern appears only once, so x−y=0. Reading off the entries on S is therefore one-to-one from the qk codewords to the qk patterns, and a one-to-one map between finite sets of equal size is a bijection. ■
Proof. Let k=dimC, let S be an information set of C, and let T be the other n−k positions. For each s in S let es be the codeword whose entries on S are 1 at s and 0 elsewhere, which exists and is unique because S is an information set. These k codewords span C, because for any codeword c the codeword c−∑s∈Scses is 0 on all of S and so equals 0. By the lemma that the dual is a subspace fixed by a basis, y lies in C⊥ exactly when y⋅es=0 for every s in S. Since es has a 1 at s and 0 at the other positions of S,
y⋅es=ys+t∈T∑(es)tyt,
so y lies in C⊥ exactly when ys=−∑t∈T(es)tyt for every s in S. The entries of y on T can be chosen freely, in qn−k ways, and each choice fixes the entries on S. So C⊥ has qn−k vectors. It is a subspace, so it has a basis, and the theorem that a space of dimension k has qk vectors makes that basis n−k vectors long. ■
Proof. Each c in C has c⋅y=y⋅c=0 for every y in C⊥, so C lies inside (C⊥)⊥. Applying the theorem twice, (C⊥)⊥ has dimension n−(n−k)=k, so both sets have qk vectors, and a subset of a finite set with the same size is the whole set. ■
By the corollary, a word x belongs to C exactly when x⋅y=0 for every y in C⊥, and by the lemma on duals it is enough to test y on a basis of C⊥, so n−k dot products, the components of a syndrome, decide membership.
Duality also explains the symmetry of the subspace counts. Taking the dual sends each subspace of dimension k to one of dimension n−k, and doing it twice returns the start, so it pairs the two kinds off one to one and [nk]q=[nn−k]q.
Table 2 collects the duals met so far. The dual of R3={000,111} is {y∣y1+y2+y3=0}, the even-weight set E of Bit Strings That Can Be Scaled, and the dual of R5 is the 16 even-weight words of length 5. The code spanned by 1100 and 0111 shares only the zero word with its dual, C5 shares part of itself with its dual, and a self-dual code shares everything.
Table 2. Codes met in the chapter, their lengths and dimensions, and their duals
Code
Length n
dimC
Dual C⊥
dimC⊥
{00,11}
2
1
itself
1
R3
3
1
{000,011,101,110}
2
C5
5
2
the 8 words of the dual of C5
3
R5
5
1
the 16 even-weight words
4
span{1100,0111}
4
2
{0000,0011,1101,1110}
2
span{(1,2)} in GF(5)2
2
1
itself
1
the length-8 code of Self-Dual Codes
8
4
itself
4
the ternary code T of Self-Dual Codes
4
2
itself
2
Source: reproduced by ch15_vector_spaces_over_finite_fields.py.
MacWilliams showed in 1963 that the weights of the words of C determine those of C⊥, and her identity returns in Part XIII, Advanced Algebraic Coding Theory [5]. Huffman and Pless give a full textbook treatment of dual and self-dual codes [6].
The code {00,11} is its own dual. Its word 11 has 11⋅11=0, so the code lies inside its dual, and the dual has dimension 2−1=1, the same as the code, so the two are equal.
Proof. If C=C⊥, the theorem that a code and its dual fill the length gives k=n−k, so n=2k. If C⊆C⊥ and dimC=n/2, then dimC⊥=n/2 too, both have qn/2 vectors, and so they are equal. In a binary self-orthogonal code each word has c⋅c=0, so its weight is even by the lemma on binary words. Finally, for every codeword c the dot product of c with the all-ones word 1 is c1+⋯+cn, its weight modulo 2, which is 0. So 1 lies in C⊥, which is C when the code is self-dual. ■
There is 1 binary self-dual code of length 2, there are 3 of length 4 and 15 of length 6, counted as distinct codes. The product ∏i=1n/2−1(2i+1) gives these counts, and the companion script checks them by building every code. Pless and Sloane classified these codes up to a reordering of the positions, under which the three of length 4 are one code [7]. The three of length 4 are {0000,0011,1100,1111}, {0000,0101,1010,1111} and {0000,0110,1001,1111}, and each holds 1111, as the lemma requires.
A self-dual code of length 8 is spanned by the four words 11110000, 00111100, 00001111 and 01010101. It has 16 codewords, and apart from the zero word and 11111111, all fourteen have weight 4, as Worked Examples shows. Length 8, 16 words and smallest nonzero weight 4 are the parameters of the extended Hamming code that grows out of Hamming's 1950 paper [8], which a later chapter builds.
Over GF(3) the two words 1110 and 0121 span a code T of 9 words. The three dot products among them are 1110⋅1110=3=0, 0121⋅0121=0+1+4+1=6=0 and 1110⋅0121=0+1+2+0=3=0, so T is self-orthogonal by bilinearity. The two words are independent, since a(1110)+b(0121)=(a,a+b,a+2b,b) vanishes only when a=b=0, so T has dimension 2=4/2 and is self-dual. Its eight nonzero words all have weight 3, as they must, since c⋅c=0 makes the weight divisible by 3 and the length is 4. In GF(5)2 the lines through (1,2) and (1,3) are self-dual, as an exercise shows, while GF(3)2 has no self-dual line, because it has no nonzero self-orthogonal vector.
In a self-dual code the basis that encodes messages is also a basis of the dual, so the same words serve as the parity checks.
Every system of equations in the chapter, such as Equation 8, was solved by hand, one free choice at a time.
The next chapter, Matrices and Elimination over Finite Fields, stacks a list of vectors into the rows of a matrix and solves such systems by row reduction, which turns the greedy arguments of this chapter into an algorithm. Rank, the dimension of the span of a matrix's rows, comes out of the reduction, and so does the systematic form, in which an information set sits in the first k positions. After it, Linear Codes takes the subspace view as its definition and builds a generator matrix from a basis of the code and a parity-check matrix from a basis of its dual.
[1]Peano, Giuseppe (2000). “Geometric Calculus: According to the Ausdehnungslehre of H. Grassmann.” Birkhäuser. doi:10.1007/978-1-4612-2132-6
[2]Slepian, David (1956). “A Class of Binary Signaling Alphabets.” Bell System Technical Journal, 35(1), pp. 203–234. doi:10.1002/j.1538-7305.1956.tb02379.x
[3]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
[4]Goldman, Jay and Rota, Gian-Carlo (1970). “On the Foundations of Combinatorial Theory IV: Finite Vector Spaces and Eulerian Generating Functions.” Studies in Applied Mathematics, 49(3), pp. 239–258. doi:10.1002/sapm1970493239
[5]MacWilliams, Jessie (1963). “A Theorem on the Distribution of Weights in a Systematic Code.” Bell System Technical Journal, 42(1), pp. 79–94. doi:10.1002/j.1538-7305.1963.tb04003.x
[6]Huffman, W. Cary and Pless, Vera (2003). “Fundamentals of Error-Correcting Codes.” Cambridge University Press. doi:10.1017/CBO9780511807077
[7]Pless, Vera and Sloane, N. J. A. (1975). “On the Classification and Enumeration of Self-Dual Codes.” Journal of Combinatorial Theory, Series A, 18(3), pp. 313–335. doi:10.1016/0097-3165(75)90042-4
[8]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
— Anirban
Hardware–software at the seam where compilers meet microcode.