Clock arithmetic, XOR and multiplication modulo a prime obey the same three rules. The chapter proves Lagrange's theorem, builds kernels and quotients, and shows that a syndrome decoder lists the cosets of a code.
The previous chapter, Integers and Modular Arithmetic, built arithmetic on finite sets of numbers. Addition modulo n runs around a clock with n hours, and multiplication modulo a prime p gives every nonzero residue an inverse. Distance, Detection and Correction used a third arithmetic without naming it, the XOR of binary words, and noticed that the XOR of any two codewords of C5={00000,01101,10110,11011} is again a codeword.
These arithmetics follow one pattern. Each combines two elements of a set into a third, each has an element that changes nothing, and each lets every step be undone. A set with an operation of that kind is called a group. A code closed under XOR is a group sitting inside the group of all words, and that fact alone splits the received words into slices of equal size, called cosets, which are exactly what a syndrome decoder lists.
Three small operation tables supply the rules. Subgroups, cyclic groups and cosets lead to Lagrange's theorem, which says that the size of a subgroup divides the size of the group, and homomorphisms and quotient groups lead to the last section, which turns C5 into a decoder.
Picture a clock with four hours, labeled 0, 1, 2 and 3. Moving 3 hours forward from hour 2 passes 3 and 0 and lands on 1, so 2+3=1 on this clock, which is the residue of 5 modulo 4. Writing out every such sum gives a four-by-four table, the addition table of Z4={0,1,2,3}.
The 2-bit strings 00, 01, 10 and 11 give a second table under bitwise XOR, where 01⊕11=10 because the two words differ only in their first bit. The nonzero residues modulo 5, which are 1, 2, 3 and 4, give a third table under multiplication modulo 5, where 3⋅4=12 leaves the residue 2. Figure 1 sets the three tables side by side.
Figure 1. The Cayley tables of addition modulo 4, multiplication of the nonzero residues modulo 5, and XOR on 2-bit strings. In each table the identity element, marked in green, appears exactly once in every row and every column, and so does every other element.
Three features are common to the tables. Each has an element that changes nothing, 0 for the clock, 1 for multiplication and 00 for XOR, marked in green. Every row and every column contains each element exactly once, a pattern called a Latin square. And every element can be undone, since the identity appears in every row. A table of all products of a finite set under one operation is called a Cayley table, after Arthur Cayley, whose 1854 paper described groups through such tables [1].
The clock table and the multiplication table modulo 5 are the same table with the elements renamed. Write each element k of Z4 as the residue 2kmod5, so that 0,1,2,3 become 1,2,4,3. Adding exponents modulo 4 then matches multiplying modulo 5, since 2a+b=2a⋅2b and 24mod5=1 makes the exponent wrap around after 4 steps, exactly as the clock does.
The XOR table is different in a way that no renaming can hide. Every 2-bit string satisfies x⊕x=00, so each element undoes itself. On the clock only 0 and 2 undo themselves, because 1+1=2 rather than 0, and the section Homomorphisms and Kernels proves that no renaming bridges the difference. The rules the three tables share are the axioms of a group.
The requirement that a∗b lands back in G is called closure. Under addition the identity is written 0, the inverse of a is −a, and a+a+a is 3a. Under multiplication the identity is written 1 and the product sign is often dropped.
Three families of groups run through the book. The first is Zn={0,1,…,n−1} under addition modulo n, an abelian group of order n. Its identity is 0, the inverse of a nonzero a is n−a, so −4=8 in Z12, and associativity holds because both groupings give the same integer before reduction, and reducing at any stage leaves the same residue.
The second family is {0,1}n, the words of n bits under XOR, an abelian group of order 2n. XOR acts on each position separately, as addition modulo 2, so the rules hold position by position. The identity is the all-zeros word, and every word is its own inverse.
The third family is Zn∗, the residues between 1 and n−1 that share no factor greater than 1 with n, under multiplication modulo n. For a prime p this is every nonzero residue, so Z5∗={1,2,3,4}, and the inverses of 1, 2, 3 and 4 modulo 5 are 1, 3, 2 and 4.
Proof. Take a and b in Zn∗. Bezout's identity from Integers and Modular Arithmetic gives integers with xa+yn=1 and ub+vn=1. Multiplying the two equations gives
(xu)ab+(xav+yub+yvn)n=1,
so every common divisor of ab and n divides 1, and the residue of ab is again coprime to n. That is closure. Associativity and commutativity hold because they hold for integers and survive reduction. The identity is 1. For the inverse, the equation xa+yn=1 says xa≡1(modn), and the same equation shows that every common divisor of x and n divides 1, so the residue of x lies in Zn∗ and is the inverse of a. ■
Two failures show what the axioms exclude. The nonzero residues modulo 6 are not closed under multiplication, since 2⋅3=6 leaves the residue 0, which is outside the set. Subtraction of integers is closed but not associative, since (5−3)−1=1 while 5−(3−1)=3. Neither is a group.
Proof. Suppose e and e′ are both identities. Since e′ is an identity, e∗e′=e, and since e is an identity, e∗e′=e′. So e=e′. Next suppose b and c are both inverses of a. Then
b=b∗e=b∗(a∗c)=(b∗a)∗c=e∗c=c,
using associativity in the middle step. Finally, the equations a−1∗a=a∗a−1=e say that a is an inverse of a−1, and since that inverse is unique, it equals (a−1)−1. ■
Proof. Combine both sides of a∗x=a∗y with a−1 on the left. Associativity gives (a−1∗a)∗x=(a−1∗a)∗y, which is e∗x=e∗y, so x=y. The right-hand case combines with a−1 on the right. The row of a in the Cayley table lists a∗g for the ∣G∣ elements g, and by cancellation no two of these entries agree. That is ∣G∣ different elements of a set with ∣G∣ elements, so every element appears exactly once. Columns follow the same way from cancellation on the right. For the product,
(a∗b)∗(b−1∗a−1)=a∗(b∗b−1)∗a−1=a∗e∗a−1=e,
and the product in the other order also gives e by the same regrouping, so b−1∗a−1 is the unique inverse of a∗b. ■
The reversal is the order in which shoes and socks come off, shoes first. Every group a code in this book is built on is abelian, so there the two orders agree.
The even residues {0,2,4,6,8,10} of Z12 form a group of their own. A sum of two even numbers is even, and stays even after subtracting 12. The identity 0 is even, and the inverse of an even residue is even, as in −4=8. The smaller set {0,4,8} is closed too, since a sum of multiples of 4 is a multiple of 4 and stays one after subtracting 12. Other subsets fail. In {1,5,9} the sum 1+5=6 falls outside, and the identity 0 is missing besides, while in {0,1,2,3,4,5} the sum 3+4=7 falls outside.
Associativity never needs checking, since it holds for all of G. The next two results cut the rest down to one test.
Proof. A subgroup contains b−1 and is closed, so it passes the test. Conversely, suppose H passes. Pick any a in H, which exists because H is nonempty, and apply the test with b=a to get a∗a−1=e in H. Apply it to the pair e and b to get e∗b−1=b−1 in H, so H holds every inverse. Finally, for a and b in H, the element b−1 is in H, so the test applied to a and b−1 gives a∗(b−1)−1=a∗b in H, using (b−1)−1=b. Associativity is inherited from G. ■
For finite subsets even the inverse can be dropped from the test, and closure alone decides.
Proof. A subgroup is closed. Conversely, let H be closed and pick a in H. The map that sends x to a∗x takes elements of H to elements of H, by closure. By cancellation its ∣H∣ values are all different, and they lie in a set of size ∣H∣, so the map reaches every element. So some x in H has a∗x=a=a∗e, and cancellation gives x=e, so e lies in H. The map also reaches e, so some y in H has a∗y=e. Combining with a−1 on the left gives y=a−1, so a−1 lies in H. With identity, inverses, closure and inherited associativity, H is a group. ■
Finiteness carries the argument. The positive integers are closed under addition and contain no identity, because on an infinite set a one-to-one map need not reach every element, and adding a never reaches a.
Proof. The set is finite, since {0,1}n has 2n elements, and it is closed by assumption, so the finite subgroup test applies. ■
For C5 the three sums of different nonzero codewords are 01101⊕10110=11011, 01101⊕11011=10110 and 10110⊕11011=01101. A codeword XORed with itself gives 00000, and XOR with 00000 changes nothing, so every sum stays in the code and C5 is a subgroup of {0,1}5 of order 4. The even-weight words {000,011,101,110} form a subgroup of {0,1}3 by the same check. The chapter Linear Codes takes this closure as the definition of a binary linear code, so every result proved about subgroups from here on is a result about such codes.
Start at 3 and keep multiplying by 3 modulo 7. The residues visited are 3,2,6,4,5,1, and the next step returns to 3. Six steps reach all six nonzero residues. Starting at 2 instead gives 2,4,1 and then repeats, so the powers of 2 reach only half of the group. The element 6 returns at once, since 6⋅6=36 leaves the residue 1. Figure 2 draws the two journeys as paths around the residues.
Figure 2. Powers modulo 7. Repeated multiplication by 3 visits every nonzero residue, so 3 generates the whole group. Repeated multiplication by 2 cycles through the subgroup {1, 2, 4} from 2, and through the coset {3, 5, 6} from 3.
Addition gives the same behavior. Repeatedly adding 9 in Z12 visits 9,6,3,0, so four additions of 9 return to the identity. In a group written with multiplication, write a0=e, ak for the product of k copies of a, and a−k for the product of k copies of a−1. Counting the copies in each factor gives the laws ai∗aj=ai+j and (ai)j=aij for all integers i and j. With addition, ak is written ka.
In a finite group every element has an order. The powers e,a,a2,… all lie in a finite set, so two of them coincide, say ai=aj with i<j. Cancelling ai from both sides leaves aj−i=e with j−i positive, so some positive power equals e, and the smallest such power is the order.
Proof. Suppose ai=aj with 0≤i<j<m. Cancelling ai leaves aj−i=e with 0<j−i<m, which contradicts the choice of m as the smallest such exponent. So the m listed powers are different. For any integer k, the division algorithm gives k=qm+r with 0≤r<m, and then
ak=(am)q∗ar=eq∗ar=ar,
so every power of a is one of the m listed. The product of two powers is a power, so ⟨a⟩ is closed and finite, and the finite subgroup test makes it a subgroup. Finally ak=ar, and among e,a,…,am−1 only a0 is the identity, so ak=e exactly when r=0, which means m divides k. ■
For the additive groups Zn the order of every element follows from one formula.
Proof. The multiple ka is the identity of Zn exactly when n divides the integer ka. Let g=gcd(a,n) and write a=ga′ and n=gn′. A common divisor d of a′ and n′ would make gd a common divisor of a and n, so d=1 and gcd(a′,n′)=1. Now n divides ka exactly when gn′ divides gka′, that is, when n′ divides ka′. Bezout's identity gives xn′+ya′=1, so k=xn′k+y(ka′), and when n′ divides ka′ it divides both terms and hence k. The converse is clear. So ka=0 exactly when n′ divides k, and the smallest positive such k is n′=n/g. The order equals n exactly when g=1, and an element of order n has n different multiples, which fill Zn. ■
In Z12 the orders of 0,1,…,11 are 1,12,6,4,3,12,2,12,3,4,6,12. The four generators are 1, 5, 7 and 11, the residues that share no factor greater than 1 with 12. For a=9 the formula gives 12/3=4, the four steps counted above.
Proof. The formula above gives ⟨n/d⟩ the order n/gcd(n/d,n)=n/(n/d)=d, so a subgroup of each order d exists. Now let H be any subgroup other than {0}, which is ⟨0⟩, and let m be the smallest positive element of H. Closure puts every multiple of m in H. For any h in H, divide to get h=qm+r with 0≤r<m. The element h−qm lies in H, and its residue is r, so minimality of m forces r=0 and h=qm. Thus H=⟨m⟩. Dividing n the same way gives n=q′m+r′ with 0≤r′<m, and r′ is the residue of −q′m, which lies in H, so r′=0 and m divides n. Then ∣H∣=ord(m)=n/m, so m=n/∣H∣. The order of H fixes m, and m fixes H, so there is one subgroup for each order. ■
The divisors of 12 are 1,2,3,4,6 and 12, so Z12 has six subgroups, {0}, {0,6}, {0,4,8}, {0,3,6,9}, {0,2,4,6,8,10} and Z12 itself. Figure 3 arranges them by containment.
Figure 3. The six subgroups of Z12, one for each divisor of 12, with the element that generates each. A line joins two subgroups when the larger contains the smaller and its order is 2 or 3 times as large.
Take H={0,4,8} in Z12 and add 1 to each of its elements. The result is {1,5,9}. Adding 2 gives {2,6,10}, adding 3 gives {3,7,11}, and adding 4 gives {4,8,0}, which is H again. The four sets have three elements each, no two of them share an element, and together they hold all twelve residues. The subgroup K={0,3,6,9} cuts the same group into the three sets K, {1,4,7,10} and {2,5,8,11}, four elements each. Figure 4 shows both cuts.
Figure 4. The cosets of two subgroups of Z12. The subgroup of order 3 cuts the twelve residues into four cosets of three, and the subgroup of order 4 cuts them into three cosets of four. In both cases the cosets have the size of the subgroup and do not overlap.
Multiplication behaves the same way. The powers of 2 modulo 7 form the subgroup {1,2,4}, and multiplying each of its elements by 3 gives {3,6,12}, which reduces to {3,5,6}. The right half of Figure 2 shows this second slice as the cycle of multiplication by 2 from 3.
Strictly these are left cosets, and right cosets H∗a combine on the other side, but in an abelian group the two agree.
Proof. The first rule holds because a=a∗e and e lies in H. For the second, the map sending h to a∗h reaches every element of a∗H by definition, and by cancellation it never sends two elements of H to the same place, so a∗H has as many elements as H.
For the third rule, suppose a−1∗b=h0 lies in H, so b=a∗h0. Every element b∗h of b∗H equals a∗(h0∗h), which lies in a∗H because h0∗h lies in H. Likewise a=b∗h0−1 puts every element of a∗H into b∗H. So the cosets are equal. Conversely, if a∗H=b∗H, then b, which lies in b∗H by the first rule, lies in a∗H, so b=a∗h for some h in H and a−1∗b=h lies in H.
For the fourth rule, suppose c lies in both a∗H and b∗H, so c=a∗h1=b∗h2. Then a−1∗b=h1∗h2−1, which lies in H, and the third rule makes the cosets equal. So two cosets that share anything share everything. ■
Any element of a coset can serve as its representative, so 1+H, 5+H and 9+H all name the same coset {1,5,9}. For bit strings, where every word is its own inverse, the third rule says that x and y lie in the same coset of a code C exactly when x⊕y is a codeword.
The repetition code R3={000,111} is a subgroup of {0,1}3, and its cosets are {000,111}, {001,110}, {010,101} and {011,100}. Each coset pairs a word with its complement, and each holds one word of weight at most 1. That light word is the flip, or absence of one, that majority voting undoes for every word in the coset.
The coset rules say that cosets always have the size of the subgroup and never overlap, so counting them gives the central theorem of the chapter.
Proof. Every element a of G lies in some coset, namely a∗H, by the first coset rule. Two different cosets share no element, by the fourth rule. So the distinct cosets split G into disjoint pieces, and ∣G∣ is the sum of their sizes. By the second rule every piece has exactly ∣H∣ elements. If there are [G:H] pieces, the sum is [G:H]⋅∣H∣, and therefore ∣H∣ divides ∣G∣. ■
The number [G:H] is called the index of H in G. For the six subgroups of Z12, of orders 1,2,3,4,6 and 12, the numbers of cosets are 12,6,4,3,2 and 1, and each product is 12. The theorem is named after Joseph-Louis Lagrange, and four consequences follow at once.
Proof. The subgroup ⟨a⟩ has ord(a) elements, by the theorem on the size of a cyclic subgroup, and Lagrange's theorem makes this number divide ∣G∣. Writing ∣G∣=q⋅ord(a) gives a∣G∣=(aord(a))q=eq=e. ■
Table 1 checks the corollary on Z7∗, a group of order 6. The orders that appear are 1, 2, 3 and 6, all divisors of 6, and no element has order 4 or 5.
Table 1. The powers of each element of the nonzero residues modulo 7, listed until they reach 1, and the order of each element
Element a
Powers a,a2,… modulo 7
Order
1
1
1
2
2, 4, 1
3
3
3, 2, 6, 4, 5, 1
6
4
4, 2, 1
3
5
5, 4, 6, 2, 3, 1
6
6
6, 1
2
Source: reproduced by ch14_groups_and_cosets.py.
Proof. The residue of a lies in Zn∗, which is a group by the lemma on units, and the group has order φ(n), by the definition of φ. The corollary on orders of elements gives aφ(n)=1 in that group, which is the congruence on the right. For a prime p every residue from 1 to p−1 is coprime to p, so φ(p)=p−1, and the congruence on the left is the special case. ■
Integers and Modular Arithmetic met both theorems. Here each costs one line, because Lagrange's theorem did the counting once for every group. The companion script confirms Fermat's congruence for every prime below 60 and Euler's for every n from 2 to 40.
Proof. By Lagrange's theorem a subgroup has order 1 or p, the only divisors of p, so it is {e} or the whole group. For a=e, the subgroup ⟨a⟩ contains both e and a, so its order is not 1, and it must be the whole group. ■
Proof. The code is a subgroup of {0,1}n, so its size m divides 2n. Write m=2ku with u odd. Since u is odd, Bezout's identity gives xu+2y=1. If u divides 2⋅2j, then multiplying by 2j gives 2j=xu⋅2j+y⋅2⋅2j, a sum of two multiples of u, so u divides 2j. Starting from u∣2n and applying this step n times gives u∣1, so u=1 and m=2k, with k≤n because m≤2n. ■
The subgroups of {0,1}3 have sizes 1, 2, 4 and 8, and nothing else occurs. This is why the size of every linear code is described by an exponent k, its number of message bits.
Lagrange's theorem rules sizes out and never promises one. A group of order 4 need not hold an element of order 4. In {0,1}2 every element has order 1 or 2, because x⊕x=00 for every 2-bit string.
Figure 5. The order of 2 modulo each odd prime p below 100. Every order divides p − 1, as Lagrange's theorem requires, and for 12 of the 24 primes the order is p − 1 itself. Data: computed by ch14_charts.py in the companion repository.
Figure 5 applies the corollary on orders to the element 2 in Zp∗ for each of the 24 odd primes below 100. Every order divides p−1. For 12 primes the order is p−1, so the powers of 2 run through every nonzero residue, and for 8 it is (p−1)/2. For the remaining four it is a smaller divisor, as at p=31, where 25=32 leaves the residue 1. An element whose powers reach every nonzero residue of a field is called a primitive element, and the larger finite fields of later chapters are built around such elements.
Reduce each element of Z12 modulo 4. The sum 5+10 in Z12 leaves 3, which reduces to 3. Reducing first gives 1 and 2, whose sum in Z4 is also 3. The routes agree because 4 divides 12, so subtracting 12 never changes a residue modulo 4. The residues sent to 0 are {0,4,8}, the subgroup whose cosets were drawn earlier, and those sent to 1 are the coset {1,5,9}.
An isomorphism is a renaming of elements that turns one Cayley table into the other, which is exactly what the powers of 2 did for Z4 and Z5∗. A homomorphism that is not one-to-one merges elements, and the kernel records which merges happen.
Proof. From f(eG)=f(eG∗eG)=f(eG)∘f(eG), cancelling one copy of f(eG) leaves eH=f(eG). Then f(a)∘f(a−1)=f(a∗a−1)=f(eG)=eH, and the same holds in the other order, so f(a−1) is the unique inverse of f(a). ■
Proof. The kernel contains eG by the lemma. For a and b in the kernel, f(a∗b−1)=f(a)∘f(b)−1=eH∘eH=eH, so the subgroup test applies. The image contains eH, and f(a)∘f(b)−1=f(a∗b−1) is again an image, so the test applies there too. Next, f(a−1∗b)=f(a)−1∘f(b), which equals eH exactly when f(a)=f(b). By the coset rules, that means a and b lie in the same coset of the kernel. If the kernel is {eG}, that coset is {a}, so distinct elements have distinct images, and if the map is one-to-one, only eG goes to eH. ■
The set of elements sent to one value is called the fiber over that value, and the theorem says that every fiber is a coset of the kernel. A second example comes from parity. Send each 3-bit word x to p(x)=w(x)mod2, a single bit. The weight lemma of Distance, Detection and Correction gives w(x⊕y)=w(x)+w(y)−2w(x∧y), and the last term is even, so p(x⊕y)=p(x)⊕p(y) and parity is a homomorphism from {0,1}3 to {0,1}. Its kernel is the even-weight code {000,011,101,110}, and the other fiber is the odd words {001,010,100,111}. Figure 6 draws both maps.
Figure 6. Two homomorphisms. Reduction modulo 4 sends Z12 onto Z4, and parity sends the 3-bit strings onto a single bit. In each, the elements sent to the identity form the kernel, marked in green, and every other value is reached by exactly one coset of the kernel.
The renaming of the first section is an isomorphism. The map f(k)=2kmod5 from Z4 to Z5∗ is a homomorphism, because a sum a+b computed in Z4 differs from the integer a+b by 0 or 4, and 24mod5=1 makes that difference vanish, so f(a+b)=2a⋅2bmod5. It is one-to-one, because the four powers 1,2,4,3 are different. So Z4≅Z5∗.
The 2-bit strings are not isomorphic to Z4, although both groups have four elements. Suppose f were an isomorphism from Z4 to {0,1}2. Then f(2)=f(1+1)=f(1)⊕f(1)=00=f(0), so two different elements would share an image, and a search over all 24 one-to-one correspondences confirms that none is a homomorphism. In general, since f(ak)=f(a)k and a one-to-one homomorphism sends only e to the identity, an isomorphism keeps the order of every element, and Z4 holds an element of order 4 while {0,1}2 holds none.
The cosets of H={0,4,8} can be added to one another. Take any element of {1,5,9} and any element of {2,6,10} and add them in Z12. The choice 1+2 gives 3, the choice 5+10 gives 15, which leaves 3, and every one of the nine choices lands in {3,7,11}. So the sum of the two cosets can be defined as the coset that holds all these sums, and the definition does not depend on which representatives are picked. Table 2 lists every such sum.
Table 2. Addition of the four cosets of H = {0, 4, 8} in Z12, each entry the coset that holds every sum of an element of the row coset and an element of the column coset
+
H
1+H
2+H
3+H
H
H
1+H
2+H
3+H
1+H
1+H
2+H
3+H
H
2+H
2+H
3+H
H
1+H
3+H
3+H
H
1+H
2+H
Source: reproduced by ch14_groups_and_cosets.py.
The table is the addition table of Z4 with k+H in the place of k, so the cosets form a group of their own, and reduction modulo 4 identifies it with Z4.
Proof. Suppose a+H=a′+H and b+H=b′+H. By the coset rules a′=a+h1 and b′=b+h2 for some h1 and h2 in H. Then a′+b′=(a+b)+(h1+h2), using that addition in G can be regrouped and reordered. Since h1+h2 lies in H, the coset rules give (a′+b′)+H=(a+b)+H, so the sum is well defined. Associativity and commutativity of the coset sum follow from those of G, applied to representatives. The coset H=0+H is the identity, since (0+H)+(a+H)=a+H, and (a+H)+((−a)+H)=0+H. The order is the number of cosets, which is ∣G∣/∣H∣ by Lagrange's theorem. ■
The proof moved h1 past b, which needs the operation to commute. In a group whose operation does not commute, the construction works only for subgroups with an extra property, called normal subgroups, which the abelian groups of coding never need.
Proof. By the theorem on fibers, a+K=b+K exactly when f(a)=f(b). One direction says the rule gives one value per coset, whichever representative is used, and the other says that different cosets get different values. Every value f(a) in the image is reached, by the coset a+K. The rule turns the coset sum into the operation of H, since (a+K)+(b+K)=(a+b)+K goes to f(a+b)=f(a)+f(b). So the rule is an isomorphism, the number of cosets equals ∣imf∣, and Lagrange's theorem turns that number into ∣G∣/∣K∣. ■
For reduction modulo 4 the theorem reads 12=3⋅4, a kernel of three elements and an image of four.
Return to the code C5={00000,01101,10110,11011}. It is a subgroup of {0,1}5 of order 4, so Lagrange's theorem cuts the 32 words of five bits into 32/4=8 cosets of four words each. Suppose a codeword c is sent and the channel adds an error pattern e, so that r=c⊕e arrives. Since r⊕e=c is a codeword, the coset rules put r and e in the same coset, so the coset of the received word depends only on the error pattern. Naming that coset tells the receiver something about e without knowing c.
Naming it without listing all 32 words takes a homomorphism whose kernel is the code. Number the bits of x as x1x2x3x4x5 from the left. In C5 the first two bits carry the message and the other three are fixed by x3=x1⊕x2, x4=x1 and x5=x2, so each codeword passes three checks. Collect the results of the three checks into a 3-bit word,
s(x)=(x1⊕x2⊕x3,x1⊕x4,x2⊕x5),
(7)
called the syndrome of x. Each check gives 0 on every codeword.
Proof. Each component of s(x⊕y) is an XOR of bits of x⊕y, such as (x1⊕y1)⊕(x2⊕y2)⊕(x3⊕y3). XOR can be regrouped and reordered, so this equals (x1⊕x2⊕x3)⊕(y1⊕y2⊕y3), and the same holds for the other two components. So s(x⊕y)=s(x)⊕s(y). The syndrome is 000 exactly when x3=x1⊕x2, x4=x1 and x5=x2, and the four choices of the first two bits then give exactly the four words of C5, which is therefore the kernel. The first isomorphism theorem gives the image 32/4=8 elements, all of {0,1}3. The theorem on fibers says that two words share a syndrome exactly when they lie in the same coset of the kernel. ■
Since s(r)=s(c)⊕s(e)=s(e), the syndrome of the received word is the syndrome of the error pattern. Which of the four words in that coset to take as the error is a separate choice. A channel that flips each bit independently with probability below one half makes fewer flips more likely, so the natural choice is a word of least weight.
Table 3 is the standard array of C5. Where two words of a coset share the least weight, the table takes the one with the smaller binary value as leader.
Table 3. The standard array of C5, each row a coset given as its leader e XORed with the four codewords, with the syndrome shared by the whole row
Leader e
e⊕01101
e⊕10110
e⊕11011
Syndrome
00000
01101
10110
11011
000
10000
11101
00110
01011
110
01000
00101
11110
10011
101
00100
01001
10010
11111
100
00010
01111
10100
11001
010
00001
01100
10111
11010
001
01010
00111
11100
10001
111
00011
01110
10101
11000
011
Source: reproduced by ch14_groups_and_cosets.py.
The leaders have weights 0,1,1,1,1,1,2,2, and the rows hold all 32 words, each exactly once. Figure 7 draws the same array and marks the ties.
Figure 7. The eight cosets of C5 as a decoder reads them. Each row is led by a word of least weight and carries one syndrome. In the last two rows a second word, marked in orange, ties with the leader at weight 2. Data: computed by ch14_charts.py in the companion repository.
Proof. The words r and ℓ lie in the same coset, so r⊕ℓ is a codeword by the coset rules, and its distance from r is w(r⊕(r⊕ℓ))=w(ℓ). For any codeword c′, the word r⊕c′ lies in the coset of r, since XORing it with r gives the codeword c′. The leader has the least weight in that coset, so d(r,c′)=w(r⊕c′)≥w(ℓ). So no codeword is closer than r⊕ℓ. Finally the decoder returns r⊕ℓ=c⊕e⊕ℓ, which equals c exactly when e⊕ℓ=00000, that is, when e=ℓ. ■
The rule is a table lookup. Compute the syndrome, look up its leader, and XOR the leader into the received word. For r=11111 the syndrome is 100, the leader for 100 is 00100, and the decoder returns 11111⊕00100=11011, which differs from r only in the third bit.
The decoder repairs exactly the eight leaders, which are no error, the five single errors and the double errors 01010 and 00011. Six of the ten words of weight 2 fall in cosets led by a word of weight 1, so those double errors are decoded wrongly. The two cosets led by words of weight 2 hold a tie, 10001 beside 01010 and 11000 beside 00011, so for syndromes 111 and 011 two codewords lie at distance 2 and the choice between them is a convention. That matches what Distance, Detection and Correction proved for minimum distance 3, which guarantees the single errors and nothing more.
The arrangement is due to Slepian, whose 1956 paper treated binary codes closed under XOR as groups and decoded them through their cosets [2]. Hamming's codes of 1950 [3] are of this kind, and textbooks such as Lin and Costello's build the decoder from the same table [4]. The chapter Linear Codes writes the syndrome as a matrix product, and Syndrome Decoding and the Standard Array builds this table for every code closed under XOR.
Lagrange's theorem fixed the size of every code closed under XOR at a power of 2, the coset rules split the received words into slices of equal size, and the first isomorphism theorem let a 3-bit syndrome name each slice of C5. The decoder of the last section needs nothing more.
The group axioms leave out a second operation that codes use. A codeword can be multiplied by an element of a field, and over fields larger than Z2 that scaling carries real information. The next chapter, Vector Spaces over Finite Fields, adds it to the group structure, which turns subgroups into subspaces and the exponent k into the dimension of a code.
[1]Cayley, Arthur (1854). “On the Theory of Groups, as Depending on the Symbolic Equation θⁿ = 1.” The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 7(42), pp. 40–47. doi:10.1080/14786445408647421
[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]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]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
— Anirban
Hardware–software at the seam where compilers meet microcode.