Paper
Part IILinear Block Codes

Vector Spaces over Finite Fields

November 15, 202654 min readbeginner

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}C_5 = \{00000, 01101, 10110, 11011\} has 4=224 = 2^2 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 00 and 11 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 C5C_5 turns out to be its dimension, the number of message bits the code carries, and a two-word basis of C5C_5 is a recipe for encoding.

The chapter proves that a space of dimension kk over a field of qq elements has exactly qkq^k 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.

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

01.Bit Strings That Can Be Scaled

Take the eight words of three bits, 000000 through 111111. Groups and Cosets combined two such words by XOR, which adds them bit by bit with 1⊕1=01 \oplus 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=110101 + 011 = 110. Every word added to itself gives 000000.

A word can also be multiplied by a bit. Multiplying 101101 by 11 leaves 101101, and multiplying it by 00 gives 000000. These are the only two choices. The set of 3-bit words with this addition and this scaling is written GF(2)3\mathrm{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 100100, 010010 or 001001, 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 000000, 011011, 101101 and 110110 form a set EE that is closed under addition, and the odd-weight words form its coset 001+E001 + E.

The eight vectors of GF(2)^3 drawn as the corners of a cube, split into the even-weight subspace and its coset 000 001 010 011 100 101 110 111 subspace E, even weight 000 011 101 110 coset 001 + E, odd weight 001 010 100 111 edge: add 100, 010 or 001 every edge joins E to its coset
Figure 1. The eight words of as the corners of a cube, with an edge wherever two words differ in one bit. The even-weight words form the subspace , and the odd-weight words form its coset .

Now replace the bits by the residues 0,1,2,3,40, 1, 2, 3, 4 modulo 5 and consider pairs (x,y)(x, y) of them, added and multiplied entry by entry modulo 5. The sum (1,2)+(3,4)(1, 2) + (3, 4) is (4,1)(4, 1), because 1+3=41 + 3 = 4 and 2+4=62 + 4 = 6 leaves 11. Scaling by 3 gives 3(1,2)=(3,6)=(3,1)3(1, 2) = (3, 6) = (3, 1). There are 52=255^2 = 25 such pairs, and the set of them is written GF(5)2\mathrm{GF}(5)^2. Over three residues, the triples form GF(3)3\mathrm{GF}(3)^3 with 33=273^3 = 27 members.

Scaling now does something. The multiples of (1,2)(1, 2) by the scalars 00 through 44 are (0,0)(0, 0), (1,2)(1, 2), (2,4)(2, 4), (3,1)(3, 1) and (4,3)(4, 3), four of them nonzero and all different, and adding (1,2)(1, 2) to itself gives (2,4)(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.

02.Fields as Scalars

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=00 + 0 = 0, the second distributive law gives 0a=(0+0)a=0a+0a0a = (0 + 0)a = 0a + 0a. Adding −(0a)-(0a) to both sides and regrouping by associativity leaves 0=0a0 = 0a. ■\blacksquare

The residues modulo a prime pp 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\mathbb{Z}_4, for instance, 2⋅2=02 \cdot 2 = 0 and 22 has no inverse. The field of residues modulo pp is written GF(p)\mathrm{GF}(p), and a field with qq elements is written GF(q)\mathrm{GF}(q), the Galois field named after Évariste Galois. In GF(2)\mathrm{GF}(2) the negative of 11 is 11 itself, and in GF(5)\mathrm{GF}(5) the negative of 22 is 33.

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)\mathrm{GF}(2), GF(3)\mathrm{GF}(3) and GF(5)\mathrm{GF}(5), where every product can be checked by hand.

03.The Vector Space Axioms

The words of GF(2)3\mathrm{GF}(2)^3 and the pairs of GF(5)2\mathrm{GF}(5)^2 obey the same eight rules, and those rules are taken as the definition.

The first four rules say that VV is an abelian group under addition, with an identity 00 called the zero vector and a negative −v-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 ii-th entry of a(u+v)a(u + v) is a(ui+vi)a(u_i + v_i), which equals aui+avia u_i + a v_i by the first distributive law, and that is the ii-th entry of au+avau + av. In the same way the second distributive law gives (a+b)v=av+bv(a + b)v = av + bv, associativity of multiplication gives a(bv)=(ab)va(bv) = (ab)v, and 1vi=vi1 v_i = v_i gives 1v=v1v = 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-v_i as −v-v. ■\blacksquare

The companion script checks all eight rules on every triple of vectors in GF(2)3\mathrm{GF}(2)^3, GF(3)2\mathrm{GF}(3)^2 and GF(5)2\mathrm{GF}(5)^2. Three more facts follow from the rules alone.

Proof. By the last rule, 0v=(0+0)v=0v+0v0v = (0 + 0)v = 0v + 0v. Adding the negative of 0v0v to both sides leaves 0=0v0 = 0v. In the same way c0=c(0+0)=c0+c0c0 = c(0 + 0) = c0 + c0, and cancelling one copy of c0c0 leaves c0=0c0 = 0. Finally v+(−1)v=1v+(−1)v=(1+(−1))v=0v=0v + (-1)v = 1v + (-1)v = (1 + (-1))v = 0v = 0, so (−1)v(-1)v is a negative of vv. 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(-1)v = -v. ■\blacksquare

In GF(5)2\mathrm{GF}(5)^2 the negative of (1,2)(1, 2) is 4(1,2)=(4,8)=(4,3)4(1, 2) = (4, 8) = (4, 3), and indeed (1,2)+(4,3)=(5,5)=(0,0)(1, 2) + (4, 3) = (5, 5) = (0, 0). Over GF(2)\mathrm{GF}(2) the scalar −1-1 is 11, so −v=v-v = v, which is the fact behind v+v=0v + v = 0 for bit strings.

04.Subspaces

The set EE of even-weight words of length 3 is a vector space in its own right, sitting inside GF(2)3\mathrm{GF}(2)^3.

A subspace is a vector space under the same operations. The eight rules already hold for all vectors of VV, and the closure conditions keep every sum and multiple inside WW. The negative of each uu in WW lies in WW as well, since it is (−1)u(-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 cucu by closure under scaling and then cu+vcu + v by closure under addition. Conversely, suppose WW passes the test, and pick any uu in WW, which exists because WW is nonempty. Taking c=−1c = -1 and v=uv = u gives (−1)u+u=0(-1)u + u = 0 in WW, by the previous lemma. Taking v=0v = 0 then gives cu+0=cucu + 0 = cu in WW for every scalar cc, and taking c=1c = 1 gives u+vu + v in WW for all uu and vv. ■\blacksquare

Over GF(2)\mathrm{GF}(2) the only scalars are 00 and 11, so closure under scaling holds as soon as 00 is in WW, and 0=u+u0 = 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=2562^8 = 256 subsets of GF(2)3\mathrm{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 C5C_5, closed under addition, is therefore a subspace of GF(2)5\mathrm{GF}(2)^5.

The same shortcut works over any prime field, since a scalar cc of GF(p)\mathrm{GF}(p), read as an integer from 00 to p−1p - 1, gives cv=(1+⋯+1)v=v+⋯+vcv = (1 + \cdots + 1)v = v + \cdots + v with cc copies of vv, so the subspaces of GF(p)n\mathrm{GF}(p)^n are exactly its subgroups. Over the four-element field GF(4)\mathrm{GF}(4) it fails, since {0,1}\{0, 1\} is closed under addition there but not under scaling.

A code that is a subspace of GF(q)n\mathrm{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.

05.Span

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=0a_i = 0 is 00, so the span is nonempty. For two combinations u=∑aiviu = \sum a_i v_i and w=∑biviw = \sum b_i v_i and a scalar cc, the rules of a vector space regroup cu+wcu + w as ∑(cai+bi)vi\sum (c a_i + b_i) v_i, which is again a combination of the viv_i. The subspace test applies. A subspace containing every viv_i contains every aivia_i v_i by closure under scaling and every sum of those by closure under addition, so it contains the span. ■\blacksquare

Over GF(2)\mathrm{GF}(2) each coefficient is 00 or 11, so a linear combination is the sum of some of the vectors. Figure 2 builds the span of 11001100, 01100110 and 00110011 one vector at a time. The span of nothing is {0000}\{0000\}. Adding 11001100 gives {0000,1100}\{0000, 1100\}. Adding 01100110 brings in 01100110 and 1100+0110=10101100 + 0110 = 1010, so the span becomes {0000,0110,1010,1100}\{0000, 0110, 1010, 1100\}. Adding 00110011 doubles it again, to the eight even-weight words of length 4.

The span of 1100, 0110 and 0011 built one vector at a time, doubling from 1 word to 8 span of nothing 1 word 0000 add 1100 2 words 0000 1100 add 0110 4 words 0000 1100 0110 1010 add 0011 8 words 0000 1100 0110 1010 0011 1111 0101 1001 new word: an earlier word plus the vector just added
Figure 2. The span of , and 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)\mathrm{GF}(2), if SS is the current span and ww is a new vector outside it, the new span is SS together with the coset w+Sw + S, because each new combination either uses ww or does not. The two sets share no word, since a common word s=w+s′s = w + s' would put w=s−s′w = s - s' inside SS. They have the same size, because s↦w+ss \mapsto w + s matches each word of SS with one word of w+Sw + S, and w+s=w+s′w + s = w + s' forces s=s′s = s'. So the span exactly doubles whenever the new vector lies outside it. Over GF(q)\mathrm{GF}(q) the same argument with the qq sets cw+Scw + S for c=0,1,…,q−1c = 0, 1, \ldots, q - 1 multiplies it by qq.

Over GF(5)\mathrm{GF}(5) a single vector already spans five points. The span of (1,2)(1, 2) is the line L={(0,0),(1,2),(2,4),(3,1),(4,3)}L = \{(0, 0), (1, 2), (2, 4), (3, 1), (4, 3)\} through the origin. Adding (0,1)(0, 1), which is not on LL, gives a span of 25 points, the whole plane. Adding (2,4)(2, 4) instead gives back the same 5 points, because (2,4)=2(1,2)(2, 4) = 2(1, 2) was on LL already.

Figure 3 draws the plane as a grid and writes in each point the residue y−2x mod 5y - 2x \bmod 5. The points of LL are exactly those with digit 00, since a point of LL has the form (c,2c)(c, 2c). The digit stays the same along each parallel copy of LL, because moving from (x,y)(x, y) to (x,y)+c(1,2)(x, y) + c(1, 2) changes y−2xy - 2x by 2c−2c=02c - 2c = 0. The five digits therefore name the five cosets of LL, among them (0,1)+L={(0,1),(1,3),(2,0),(3,2),(4,4)}(0, 1) + L = \{(0, 1), (1, 3), (2, 0), (3, 2), (4, 4)\} with digit 11. The digit is a syndrome over GF(5)\mathrm{GF}(5), a number computed from a point that names the coset of the line containing it.

The 25 vectors of GF(5)^2 in a grid, with the line spanned by (1,2) and its four parallel cosets 0 1 2 3 4 0 1 2 3 4 first entry x second entry y 0 1 2 3 4 3 4 0 1 2 1 2 3 4 0 4 0 1 2 3 2 3 4 0 1 digit 0: L, the multiples of (1,2) (0,0) (1,2) (2,4) (3,1) (4,3) digit 1: the coset (0,1) + L (0,1) (1,3) (2,0) (3,2) (4,4) digits 2, 3, 4: the other cosets the digit in each point is y - 2x mod 5, which names one of five parallel lines
Figure 3. The plane as a grid. The multiples of form a line through the origin, and the digit at each point names which of the five parallel copies of it lies on.

06.Linear Independence

In the doubling of Span, each new vector lay outside the span of the ones before it. The list 11001100, 01100110, 10101010 behaves differently, because 1010=1100+01101010 = 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 11001100, 01100110, 10101010 is dependent, since 1100+0110+1010=00001100 + 0110 + 1010 = 0000 with all three coefficients 11. The list 11001100, 01100110, 00110011 is independent. Over GF(5)\mathrm{GF}(5) the pair (1,2)(1, 2), (2,4)(2, 4) is dependent, since 2(1,2)+4(2,4)=(2+8,4+16)=(10,20)=(0,0)2(1, 2) + 4(2, 4) = (2 + 8, 4 + 16) = (10, 20) = (0, 0). The pair (1,2)(1, 2), (0,1)(0, 1) is independent, since a(1,2)+b(0,1)=(a,2a+b)a(1, 2) + b(0, 1) = (a, 2a + b) is zero only when a=0a = 0, and then b=0b = 0 as well.

Over GF(2)\mathrm{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 00.

Proof. Suppose ∑civi=0\sum c_i v_i = 0 with cj≠0c_j \ne 0. Because the scalars form a field, cjc_j has an inverse. Moving the term cjvjc_j v_j to the other side and multiplying by −cj−1-c_j^{-1} gives vj=−cj−1∑i≠jciviv_j = -c_j^{-1} \sum_{i \ne j} c_i v_i, a combination of the others. Conversely, if vj=∑i≠jbiviv_j = \sum_{i \ne j} b_i v_i, then ∑i≠jbivi+(−1)vj=0\sum_{i \ne j} b_i v_i + (-1)v_j = 0, a combination equal to zero whose coefficient on vjv_j is −1≠0-1 \ne 0. ■\blacksquare

Proof. Suppose ∑aivi+bw=0\sum a_i v_i + bw = 0. If b≠0b \ne 0, then w=−b−1∑aiviw = -b^{-1} \sum a_i v_i lies in the span of the viv_i, which is false. So b=0b = 0, the relation reduces to ∑aivi=0\sum a_i v_i = 0, and independence of the viv_i forces every ai=0a_i = 0. ■\blacksquare

07.Basis and Dimension

The even-weight words E={000,011,101,110}E = \{000, 011, 101, 110\} are spanned by 110110 and 011011, and those two are independent. Each word of EE is then a combination of them in exactly one way. The word 101101 is 1⋅110+1⋅0111 \cdot 110 + 1 \cdot 011, so its coordinates in this list are (1,1)(1, 1), and the word 011011 is 0⋅110+1⋅0110 \cdot 110 + 1 \cdot 011, with coordinates (0,1)(0, 1).

The definition of dimension assumes that every basis of VV has the same length. Over a finite field that follows from counting.

Proof. The map reaches every vector of VV because the basis spans VV. It never sends two different coefficient lists to the same vector, because ∑aivi=∑bivi\sum a_i v_i = \sum b_i v_i gives ∑(ai−bi)vi=0\sum (a_i - b_i) v_i = 0, and independence forces ai−bi=0a_i - b_i = 0 for each ii. A bijection between finite sets makes their sizes equal, and GF(q)k\mathrm{GF}(q)^k has qkq^k elements, since each of its kk entries has qq choices. ■\blacksquare

Proof. If VV had bases of lengths kk and k′k', the theorem would give qk=∣V∣=qk′q^k = |V| = q^{k'}. Since q≥2q \ge 2, the powers of qq strictly increase, so k=k′k = k'. ■\blacksquare

The theorem assumes a basis exists, and for subspaces of GF(q)n\mathrm{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}\{0\}. While the span of the list is smaller than WW, choose a vector of WW outside the span and append it. The extension lemma keeps the list independent, and the span stays inside WW because WW is a subspace. After jj steps the list is a basis of its own span, so by the theorem that span has qjq^j vectors, all of them inside GF(q)n\mathrm{GF}(q)^n, which has qnq^n. Hence qj≤qnq^j \le q^n and j≤nj \le n, the process stops after at most nn steps, and it stops only when the list spans WW. ■\blacksquare

In a space VV of dimension kk, any kk independent vectors form a basis, because their span holds qkq^k vectors inside a set of qkq^k, so it is all of VV.

The words 0110101101 and 1011010110 are independent and their sum is 1101111011, so they span C5C_5 and dim⁡C5=2\dim C_5 = 2, matching 4=224 = 2^2. The repetition code R5={00000,11111}R_5 = \{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 nn and dimension kk over GF(q)\mathrm{GF}(q) is called an [n,k][n, k] code, and it has qkq^k codewords. Choosing a basis g1,…,gkg_1, \ldots, g_k turns every message (a1,…,ak)(a_1, \ldots, a_k) of kk symbols into the codeword a1g1+⋯+akgka_1 g_1 + \cdots + a_k g_k, and the theorem that a space of dimension kk has qkq^k vectors says that this encoding uses every codeword exactly once. With the basis 1011010110, 0110101101 of C5C_5, the message 1111 encodes to 1101111011. The basis vectors written as the rows of a table form a generator matrix [3].

08.Counting Bases and Subspaces

Counting the bases of GF(2)3\mathrm{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=1687 \times 6 \times 4 = 168 ordered bases.

Proof. Choose the vectors in order. Once ii independent vectors have been chosen, they form a basis of their span, which therefore has qiq^i 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−qiq^n - q^i choices for the next vector, whichever ii vectors came before, and multiplying the choices over i=0,…,k−1i = 0, \ldots, k - 1 gives the product. ■\blacksquare

With k=nk = n the lists are the ordered bases of GF(q)n\mathrm{GF}(q)^n. The formula gives (4−1)(4−2)=6(4 - 1)(4 - 2) = 6 for GF(2)2\mathrm{GF}(2)^2, 8×6=488 \times 6 = 48 for GF(3)2\mathrm{GF}(3)^2, 24×20=48024 \times 20 = 480 for GF(5)2\mathrm{GF}(5)^2 and 26×24×18=11,23226 \times 24 \times 18 = 11{,}232 for GF(3)3\mathrm{GF}(3)^3.

Proof. Count the pairs made of a kk-dimensional subspace WW and an ordered basis of WW in two ways. Every ordered list of kk 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 WW of dimension kk has qkq^k vectors, and its ordered bases are its ordered lists of kk independent vectors, since kk independent vectors of WW always form a basis of WW. Repeating the previous proof inside WW gives ∏i=0k−1(qk−qi)\prod_{i=0}^{k-1} (q^k - q^i) of them, the same number for every WW. So the number of pairs is also the number of subspaces times that product, and dividing gives the formula. ■\blacksquare

The bracket is called a Gaussian binomial coefficient. For GF(2)3\mathrm{GF}(2)^3 it gives 7/1=77/1 = 7 lines and (8−1)(8−2)/((4−1)(4−2))=42/6=7(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=161 + 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

SpaceVectorsOrdered basesSubspaces by dimensionTotal
GF(2)2\mathrm{GF}(2)^2461, 3, 15
GF(2)3\mathrm{GF}(2)^381681, 7, 7, 116
GF(2)4\mathrm{GF}(2)^41620,1601, 15, 35, 15, 167
GF(3)2\mathrm{GF}(3)^29481, 4, 16
GF(3)3\mathrm{GF}(3)^32711,2321, 13, 13, 128
GF(5)2\mathrm{GF}(5)^2254801, 6, 18

Source: reproduced by ch15_vector_spaces_over_finite_fields.py.

Figure 4 sets the Gaussian coefficients for length 7 beside the ordinary binomial coefficients (7k)\binom{7}{k}, which count the ways to choose kk of 7 positions. There are 29,212 subspaces of GF(2)7\mathrm{GF}(2)^7 in all, and both rows read the same backward as forward, so there are as many subspaces of dimension kk as of dimension n−kn - 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].

Subspaces of GF(2)^7 of each dimension beside the sets of k of 7 positions dimension k count, on a logarithmic scale 0 1 2 3 4 5 6 7 1 10 100 1000 10000 100000 1 7 21 35 35 21 7 1 1 127 2667 11811 11811 2667 127 1 subspaces of dimension k sets of k of the 7 positions
Figure 4. The subspaces of of each dimension , 29,212 in all, beside the ways to choose 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 nn vectors of GF(q)n\mathrm{GF}(q)^n chosen at random form a basis. Dividing the number of ordered bases by the qn2q^{n^2} equally likely lists gives

1qn2∏i=0n−1(qn−qi)=∏j=1n(1−q−j),\frac{1}{q^{n^2}} \prod_{i=0}^{n-1} \left(q^n - q^i\right) = \prod_{j=1}^{n} \left(1 - q^{-j}\right),
(6)

where each factor qn−qiq^n - q^i was divided by qnq^n and j=n−ij = n - i. For GF(2)2\mathrm{GF}(2)^2 the fraction is 6/16=3/86/16 = 3/8, which the product gives as (1−1/2)(1−1/4)=0.375(1 - 1/2)(1 - 1/4) = 0.375, and for GF(2)3\mathrm{GF}(2)^3 it is 168/512=21/64168/512 = 21/64. Each factor is less than 1, so the product shrinks as nn grows. Over GF(2)\mathrm{GF}(2), multiplying out shows that (1−x)(1−y)≥1−x−y(1 - x)(1 - y) \ge 1 - x - y whenever xx and yy lie between 0 and 1, so the factors after the first keep the product at least 1−14−18−⋯=121 - \tfrac14 - \tfrac18 - \cdots = \tfrac12, and with the first factor 12\tfrac12 the whole product stays at or above 14\tfrac14. A product that only decreases and stays above 14\tfrac14 levels off, as Figure 5 shows. At n=10n = 10 the fraction is about 0.2890.289 over GF(2)\mathrm{GF}(2), 0.5600.560 over GF(3)\mathrm{GF}(3) and 0.7600.760 over GF(5)\mathrm{GF}(5), so ten random binary words of length 10 usually fail to form a basis.

The fraction of lists of n vectors of GF(q)^n that form a basis, for q = 2, 3 and 5 length n, with n vectors chosen at random fraction that form a basis 1 2 3 4 5 6 7 8 9 10 0.0 0.2 0.4 0.6 0.8 1.0 q = 5, settling near 0.760 q = 3, settling near 0.560 q = 2, settling near 0.289
Figure 5. The fraction of lists of vectors of that form a basis, for , 3 and 5. The fraction falls as grows and levels off, lower for smaller fields. Data: computed by ch15_charts.py in the companion repository.

09.Dot Products That Are Not Positive

Over the integers, the word 1111 multiplied entrywise by itself and summed gives 1+1=21 + 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)\mathrm{GF}(2) the same sum is 1+1=01 + 1 = 0, so a nonzero word has a dot product of zero with itself.

Over GF(2)\mathrm{GF}(2) the product xiyix_i y_i is 11 only where both words have a 11, so x⋅yx \cdot y is the number of such shared positions, reduced modulo 2. The word 11111111 has 1111⋅1111=01111 \cdot 1111 = 0, while 111⋅111=1111 \cdot 111 = 1. The words 11001100 and 10101010 share only position 1, so 1100⋅1010=11100 \cdot 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⋅11111111 \cdot 1111. A parity check is such a circuit, with the checked positions marked by the 1s of yy.

The dot product of 1111 with itself over GF(2), four AND gates feeding a tree of XOR gates that outputs 0 multiply, AND add, XOR add, XOR x1 = 1 y1 = 1 1 x2 = 1 y2 = 1 1 x3 = 1 y3 = 1 1 x4 = 1 y4 = 1 1 0 0 dot product 0 x = 1111 and y = 1111 over GF(2): four products of 1, and 1 + 1 + 1 + 1 = 0
Figure 6. The dot product over as a circuit. Each product of entries is an AND gate and the sum is a tree of XOR gates, here computing .

Proof. Symmetry holds because xiyi=yixix_i y_i = y_i x_i in the field. For the second rule, the ii-th term of (ax+by)⋅z(ax + by) \cdot z is (axi+byi)zi=axizi+byizi(a x_i + b y_i) z_i = a x_i z_i + b y_i z_i by distributivity, and summing over ii gives a(x⋅z)+b(y⋅z)a(x \cdot z) + b(y \cdot z). ■\blacksquare

Proof. Each entry is 00 or 11, and 0⋅0=00 \cdot 0 = 0 and 1⋅1=11 \cdot 1 = 1, so vi2=viv_i^2 = v_i. Therefore v⋅v=v1+⋯+vnv \cdot v = v_1 + \cdots + v_n, which is the number of 1s in vv reduced modulo 2. That is 00 exactly when the weight is even. ■\blacksquare

A vector with v⋅v=0v \cdot v = 0 is called self-orthogonal. In GF(2)4\mathrm{GF}(2)^4 the self-orthogonal vectors are the 8 even-weight words, the zero word among them. In GF(3)\mathrm{GF}(3) both nonzero elements square to 1, since 12=11^2 = 1 and 22=42^2 = 4 leaves 11, so a ternary vector has v⋅vv \cdot v equal to its number of nonzero entries modulo 3, and (1,1,1)⋅(1,1,1)=3=0(1, 1, 1) \cdot (1, 1, 1) = 3 = 0. In GF(3)2\mathrm{GF}(3)^2 no nonzero vector is self-orthogonal, as an exercise shows. In GF(5)\mathrm{GF}(5) the sum 1+4=51 + 4 = 5 vanishes, so (1,2)⋅(1,2)=0(1, 2) \cdot (1, 2) = 0. The plane GF(5)2\mathrm{GF}(5)^2 has 8 nonzero self-orthogonal vectors, (1,2)(1, 2), (1,3)(1, 3), (2,1)(2, 1), (2,4)(2, 4), (3,1)(3, 1), (3,4)(3, 4), (4,2)(4, 2) and (4,3)(4, 3), which are the nonzero points of two lines, the line through (1,2)(1, 2) and the line through (1,3)(1, 3).

Orthogonality keeps its algebra and loses its geometry. The syndrome of C5C_5 in Groups and Cosets computed three parity bits, x1+x2+x3x_1 + x_2 + x_3, x1+x4x_1 + x_4 and x2+x5x_2 + x_5, and these are the dot products of the word x=x1x2x3x4x5x = x_1 x_2 x_3 x_4 x_5 with 1110011100, 1001010010 and 0100101001. The digit y−2xy - 2x of a point (x,y)(x, y) of the plane over GF(5)\mathrm{GF}(5), where xx is now a single coordinate, is a dot product too, (x,y)⋅(3,1)(x, y) \cdot (3, 1), since −2-2 and 33 are the same residue modulo 5.

10.Orthogonal Complements and Dual Codes

The three check words of C5C_5 are orthogonal to every codeword, and collecting every word with that property gives a second code.

Proof. The zero vector has 0⋅c=00 \cdot c = 0 for every cc. If yy and zz lie in C⊥C^{\perp} and aa is a scalar, bilinearity gives (ay+z)⋅c=a(y⋅c)+z⋅c=0(ay + z) \cdot c = a(y \cdot c) + z \cdot c = 0 for every cc in CC, so the subspace test applies. For the second claim, one direction is immediate. In the other, if y⋅ci=0y \cdot c_i = 0 for each ii, then every c=∑aicic = \sum a_i c_i in CC has y⋅c=∑ai(y⋅ci)=0y \cdot c = \sum a_i (y \cdot c_i) = 0, again by bilinearity. ■\blacksquare

The dual of C5C_5 can now be computed from its basis 1011010110, 0110101101. A word yy has y⋅10110=y1+y3+y4y \cdot 10110 = y_1 + y_3 + y_4 and y⋅01101=y2+y3+y5y \cdot 01101 = y_2 + y_3 + y_5, so yy lies in the dual exactly when

y1+y3+y4=0,y2+y3+y5=0.y_1 + y_3 + y_4 = 0, \qquad y_2 + y_3 + y_5 = 0.
(8)

Over GF(2)\mathrm{GF}(2) the scalar −1-1 is 11, so these say y1=y3+y4y_1 = y_3 + y_4 and y2=y3+y5y_2 = y_3 + y_5. The entries y3y_3, y4y_4 and y5y_5 can be chosen freely, 23=82^3 = 8 ways, and each choice fixes y1y_1 and y2y_2. The free choices 100100, 010010 and 001001 give 1110011100, 1001010010 and 0100101001, the three syndrome checks. On positions 3, 4 and 5 they read 100100, 010010 and 001001, so they are independent, and every yy in the dual equals y3(11100)+y4(10010)+y5(01001)y_3(11100) + y_4(10010) + y_5(01001), so they span it. Figure 7 lists the result,

C5⊥={00000,00111,01001,01110,10010,10101,11011,11100},C_5^{\perp} = \{00000, 00111, 01001, 01110, 10010, 10101, 11011, 11100\},

a code of dimension 3 holding every parity check C5C_5 satisfies. Unlike a line and its perpendicular in the ordinary plane, which meet only at the origin, C5C_5 and its dual share the nonzero word 1101111011.

The four words of the code C5 beside the eight words of its dual code the code C5 4 words, dimension 2 00000 01101 10110 11011 its dual 8 words, dimension 3 00000 00111 01001 x2+x5 01110 10010 x1+x4 10101 11011 11100 x1+x2+x3 in both C5 and its dual a dual word that is one of the three syndrome checks, named on its right
Figure 7. The code and its dual . The dual holds the three parity checks of the syndrome and every sum of them, and the two codes share the words and .

The dimensions 22 and 33 add up to the length 5, and that is no accident. The proof rests on the positions where a code shows its message.

In C5C_5, positions 1 and 2 take the patterns 0000, 0101, 1010 and 1111, one for each codeword, and the other three entries follow from them by x3=x1+x2x_3 = x_1 + x_2, x4=x1x_4 = x_1 and x5=x2x_5 = x_2, as Figure 8 shows.

The four words of C5 in a table, with positions 1 and 2 forming an information set x1 x2 x3 x4 x5 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 free free x1+x2 x1 x2 information set {1, 2} positions 1 and 2 take 00, 01, 10, 11 each exactly once across the four words positions 3, 4 and 5 are fixed by them x3 = x1 + x2, x4 = x1, x5 = x2 2 free positions, so 4 words and dimension 2
Figure 8. Positions 1 and 2 form an information set of . They take each of the four patterns once, and the other three entries follow from them.

Proof. By induction on kk. If k=0k = 0, then C={0}C = \{0\} and the empty set of positions works, since the one codeword shows the one empty pattern. If k≥1k \ge 1, choose a nonzero codeword cc and a position ii with ci≠0c_i \ne 0. The map f(x)=xif(x) = x_i from CC to GF(q)\mathrm{GF}(q) respects addition, and it is onto, because f(tci−1c)=tf(t c_i^{-1} c) = t for every scalar tt. Its kernel C′={x∈C∣xi=0}C' = \{x \in C \mid x_i = 0\} is a subspace. By the theorem on kernels, images and fibers in Groups and Cosets, each of the qq fibers of ff is a coset of the kernel, and by the coset rules each coset has as many elements as the kernel, so ∣C∣=q ∣C′∣|C| = q\,|C'| and ∣C′∣=qk−1|C'| = q^{k-1}. A basis of C′C', which exists by the basis lemma, therefore has k−1k - 1 vectors, so the induction hypothesis gives an information set S′S' of C′C' with k−1k - 1 positions. Position ii is not in S′S', since every word of C′C' shows 00 there and S′S' must show every pattern. Let S=S′∪{i}S = S' \cup \{i\}, a set of kk positions. If two codewords xx and yy agree on SS, then x−yx - y is a codeword with 00 at position ii, so it lies in C′C', and it is 00 on S′S'. The zero word of C′C' already shows the all-zero pattern on S′S', and each pattern appears only once, so x−y=0x - y = 0. Reading off the entries on SS is therefore one-to-one from the qkq^k codewords to the qkq^k patterns, and a one-to-one map between finite sets of equal size is a bijection. ■\blacksquare

Proof. Let k=dim⁡Ck = \dim C, let SS be an information set of CC, and let TT be the other n−kn - k positions. For each ss in SS let ese_s be the codeword whose entries on SS are 11 at ss and 00 elsewhere, which exists and is unique because SS is an information set. These kk codewords span CC, because for any codeword cc the codeword c−∑s∈Scsesc - \sum_{s \in S} c_s e_s is 00 on all of SS and so equals 00. By the lemma that the dual is a subspace fixed by a basis, yy lies in C⊥C^{\perp} exactly when y⋅es=0y \cdot e_s = 0 for every ss in SS. Since ese_s has a 11 at ss and 00 at the other positions of SS,

y⋅es=ys+∑t∈T(es)t yt,y \cdot e_s = y_s + \sum_{t \in T} (e_s)_t \, y_t,

so yy lies in C⊥C^{\perp} exactly when ys=−∑t∈T(es)t yty_s = -\sum_{t \in T} (e_s)_t \, y_t for every ss in SS. The entries of yy on TT can be chosen freely, in qn−kq^{n-k} ways, and each choice fixes the entries on SS. So C⊥C^{\perp} has qn−kq^{n-k} vectors. It is a subspace, so it has a basis, and the theorem that a space of dimension kk has qkq^k vectors makes that basis n−kn - k vectors long. ■\blacksquare

Proof. Each cc in CC has c⋅y=y⋅c=0c \cdot y = y \cdot c = 0 for every yy in C⊥C^{\perp}, so CC lies inside (C⊥)⊥(C^{\perp})^{\perp}. Applying the theorem twice, (C⊥)⊥(C^{\perp})^{\perp} has dimension n−(n−k)=kn - (n - k) = k, so both sets have qkq^k vectors, and a subset of a finite set with the same size is the whole set. ■\blacksquare

By the corollary, a word xx belongs to CC exactly when x⋅y=0x \cdot y = 0 for every yy in C⊥C^{\perp}, and by the lemma on duals it is enough to test yy on a basis of C⊥C^{\perp}, so n−kn - 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 kk to one of dimension n−kn - k, and doing it twice returns the start, so it pairs the two kinds off one to one and [nk]q=[nn−k]q\left[\begin{smallmatrix} n \\ k \end{smallmatrix}\right]_q = \left[\begin{smallmatrix} n \\ n-k \end{smallmatrix}\right]_q.

Table 2 collects the duals met so far. The dual of R3={000,111}R_3 = \{000, 111\} is {y∣y1+y2+y3=0}\{y \mid y_1 + y_2 + y_3 = 0\}, the even-weight set EE of Bit Strings That Can Be Scaled, and the dual of R5R_5 is the 16 even-weight words of length 5. The code spanned by 11001100 and 01110111 shares only the zero word with its dual, C5C_5 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

CodeLength nndim⁡C\dim CDual C⊥C^{\perp}dim⁡C⊥\dim C^{\perp}
{00,11}\{00, 11\}21itself1
R3R_331{000,011,101,110}\{000, 011, 101, 110\}2
C5C_552the 8 words of the dual of C5C_53
R5R_551the 16 even-weight words4
span⁡{1100,0111}\operatorname{span}\{1100, 0111\}42{0000,0011,1101,1110}\{0000, 0011, 1101, 1110\}2
span⁡{(1,2)}\operatorname{span}\{(1, 2)\} in GF(5)2\mathrm{GF}(5)^221itself1
the length-8 code of Self-Dual Codes84itself4
the ternary code TT of Self-Dual Codes42itself2

Source: reproduced by ch15_vector_spaces_over_finite_fields.py.

MacWilliams showed in 1963 that the weights of the words of CC determine those of C⊥C^{\perp}, 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].

11.Self-Dual Codes

The code {00,11}\{00, 11\} is its own dual. Its word 1111 has 11⋅11=011 \cdot 11 = 0, so the code lies inside its dual, and the dual has dimension 2−1=12 - 1 = 1, the same as the code, so the two are equal.

Proof. If C=C⊥C = C^{\perp}, the theorem that a code and its dual fill the length gives k=n−kk = n - k, so n=2kn = 2k. If C⊆C⊥C \subseteq C^{\perp} and dim⁡C=n/2\dim C = n/2, then dim⁡C⊥=n/2\dim C^{\perp} = n/2 too, both have qn/2q^{n/2} vectors, and so they are equal. In a binary self-orthogonal code each word has c⋅c=0c \cdot c = 0, so its weight is even by the lemma on binary words. Finally, for every codeword cc the dot product of cc with the all-ones word 1\mathbf{1} is c1+⋯+cnc_1 + \cdots + c_n, its weight modulo 2, which is 00. So 1\mathbf{1} lies in C⊥C^{\perp}, which is CC when the code is self-dual. ■\blacksquare

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)\prod_{i=1}^{n/2-1}(2^i + 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, 0011, 1100, 1111\}, {0000,0101,1010,1111}\{0000, 0101, 1010, 1111\} and {0000,0110,1001,1111}\{0000, 0110, 1001, 1111\}, and each holds 11111111, as the lemma requires.

A self-dual code of length 8 is spanned by the four words 1111000011110000, 0011110000111100, 0000111100001111 and 0101010101010101. It has 16 codewords, and apart from the zero word and 1111111111111111, 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)\mathrm{GF}(3) the two words 11101110 and 01210121 span a code TT of 9 words. The three dot products among them are 1110⋅1110=3=01110 \cdot 1110 = 3 = 0, 0121⋅0121=0+1+4+1=6=00121 \cdot 0121 = 0 + 1 + 4 + 1 = 6 = 0 and 1110⋅0121=0+1+2+0=3=01110 \cdot 0121 = 0 + 1 + 2 + 0 = 3 = 0, so TT is self-orthogonal by bilinearity. The two words are independent, since a(1110)+b(0121)=(a,a+b,a+2b,b)a(1110) + b(0121) = (a, a + b, a + 2b, b) vanishes only when a=b=0a = b = 0, so TT has dimension 2=4/22 = 4/2 and is self-dual. Its eight nonzero words all have weight 3, as they must, since c⋅c=0c \cdot c = 0 makes the weight divisible by 3 and the length is 4. In GF(5)2\mathrm{GF}(5)^2 the lines through (1,2)(1, 2) and (1,3)(1, 3) are self-dual, as an exercise shows, while GF(3)2\mathrm{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.

12.Looking Ahead

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 kk 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.

13.Worked Examples

14.Exercises

References

  1. [1]Peano, Giuseppe (2000). “Geometric Calculus: According to the Ausdehnungslehre of H. Grassmann.” Birkhäuser. doi:10.1007/978-1-4612-2132-6
  2. [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. [3]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
  4. [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. [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. [6]Huffman, W. Cary and Pless, Vera (2003). “Fundamentals of Error-Correcting Codes.” Cambridge University Press. doi:10.1017/CBO9780511807077
  7. [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. [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.

FeedbackBook modePaper
error-correction-codinglinear-block-codes