Paper
Part IILinear Block Codes

Groups and Cosets

November 15, 202653 min readbeginner

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 nn runs around a clock with nn hours, and multiplication modulo a prime pp 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}C_5 = \{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 C5C_5 into a decoder.

The tables, orders, cosets and syndromes in the chapter are recomputed by ch14_groups_and_cosets.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch14_charts.py in the same folder. The GNU Octave twin ch14_groups_and_cosets.m prints the same lines, as The Octave Route explains.

01.Three Tables That Behave Alike

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=12 + 3 = 1 on this clock, which is the residue of 55 modulo 4. Writing out every such sum gives a four-by-four table, the addition table of Z4={0,1,2,3}\mathbb{Z}_4 = \{0, 1, 2, 3\}.

The 2-bit strings 0000, 0101, 1010 and 1111 give a second table under bitwise XOR, where 01⊕11=1001 \oplus 11 = 10 because the two words differ only in their first bit. The nonzero residues modulo 5, which are 11, 22, 33 and 44, give a third table under multiplication modulo 5, where 3⋅4=123 \cdot 4 = 12 leaves the residue 22. Figure 1 sets the three tables side by side.

Three Cayley tables of four elements Z4, addition mod 4 + 0 0 1 1 2 2 3 3 0 1 2 3 1 2 3 0 2 3 0 1 3 0 1 2 identity 0 nonzero residues mod 5, times × 1 1 2 2 3 3 4 4 1 2 3 4 2 4 1 3 3 1 4 2 4 3 2 1 identity 1 2-bit strings, XOR XOR 00 00 01 01 10 10 11 11 00 01 10 11 01 00 11 10 10 11 00 01 11 10 01 00 identity 00
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, 00 for the clock, 11 for multiplication and 0000 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 kk of Z4\mathbb{Z}_4 as the residue 2k mod 52^k \bmod 5, so that 0,1,2,30, 1, 2, 3 become 1,2,4,31, 2, 4, 3. Adding exponents modulo 4 then matches multiplying modulo 5, since 2a+b=2a⋅2b2^{a+b} = 2^a \cdot 2^b and 24 mod 5=12^4 \bmod 5 = 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=00x \oplus x = 00, so each element undoes itself. On the clock only 00 and 22 undo themselves, because 1+1=21 + 1 = 2 rather than 00, 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.

02.The Group Axioms

The requirement that a∗ba \ast b lands back in GG is called closure. Under addition the identity is written 00, the inverse of aa is −a-a, and a+a+aa + a + a is 3a3a. Under multiplication the identity is written 11 and the product sign is often dropped.

Three families of groups run through the book. The first is Zn={0,1,…,n−1}\mathbb{Z}_n = \{0, 1, \ldots, n - 1\} under addition modulo nn, an abelian group of order nn. Its identity is 00, the inverse of a nonzero aa is n−an - a, so −4=8-4 = 8 in Z12\mathbb{Z}_{12}, 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\{0, 1\}^n, the words of nn bits under XOR, an abelian group of order 2n2^n. 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∗\mathbb{Z}_n^*, the residues between 11 and n−1n - 1 that share no factor greater than 1 with nn, under multiplication modulo nn. For a prime pp this is every nonzero residue, so Z5∗={1,2,3,4}\mathbb{Z}_5^* = \{1, 2, 3, 4\}, and the inverses of 11, 22, 33 and 44 modulo 5 are 11, 33, 22 and 44.

Proof. Take aa and bb in Zn∗\mathbb{Z}_n^*. Bezout's identity from Integers and Modular Arithmetic gives integers with xa+yn=1xa + yn = 1 and ub+vn=1ub + vn = 1. Multiplying the two equations gives

(xu) ab+(xav+yub+yvn) n=1,(xu)\,ab + (xav + yub + yvn)\,n = 1,

so every common divisor of abab and nn divides 11, and the residue of abab is again coprime to nn. That is closure. Associativity and commutativity hold because they hold for integers and survive reduction. The identity is 11. For the inverse, the equation xa+yn=1xa + yn = 1 says xa≡1(modn)xa \equiv 1 \pmod{n}, and the same equation shows that every common divisor of xx and nn divides 11, so the residue of xx lies in Zn∗\mathbb{Z}_n^* and is the inverse of aa. ■\blacksquare

Two failures show what the axioms exclude. The nonzero residues modulo 6 are not closed under multiplication, since 2⋅3=62 \cdot 3 = 6 leaves the residue 00, which is outside the set. Subtraction of integers is closed but not associative, since (5−3)−1=1(5 - 3) - 1 = 1 while 5−(3−1)=35 - (3 - 1) = 3. Neither is a group.

Proof. Suppose ee and e′e' are both identities. Since e′e' is an identity, e∗e′=ee \ast e' = e, and since ee is an identity, e∗e′=e′e \ast e' = e'. So e=e′e = e'. Next suppose bb and cc are both inverses of aa. Then

b=b∗e=b∗(a∗c)=(b∗a)∗c=e∗c=c,b = b \ast e = b \ast (a \ast c) = (b \ast a) \ast c = e \ast c = c,

using associativity in the middle step. Finally, the equations a−1∗a=a∗a−1=ea^{-1} \ast a = a \ast a^{-1} = e say that aa is an inverse of a−1a^{-1}, and since that inverse is unique, it equals (a−1)−1(a^{-1})^{-1}. ■\blacksquare

Proof. Combine both sides of a∗x=a∗ya \ast x = a \ast y with a−1a^{-1} on the left. Associativity gives (a−1∗a)∗x=(a−1∗a)∗y(a^{-1} \ast a) \ast x = (a^{-1} \ast a) \ast y, which is e∗x=e∗ye \ast x = e \ast y, so x=yx = y. The right-hand case combines with a−1a^{-1} on the right. The row of aa in the Cayley table lists a∗ga \ast g for the ∣G∣|G| elements gg, and by cancellation no two of these entries agree. That is ∣G∣|G| different elements of a set with ∣G∣|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,(a \ast b) \ast (b^{-1} \ast a^{-1}) = a \ast (b \ast b^{-1}) \ast a^{-1} = a \ast e \ast a^{-1} = e,

and the product in the other order also gives ee by the same regrouping, so b−1∗a−1b^{-1} \ast a^{-1} is the unique inverse of a∗ba \ast b. ■\blacksquare

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.

03.Subgroups

The even residues {0,2,4,6,8,10}\{0, 2, 4, 6, 8, 10\} of Z12\mathbb{Z}_{12} form a group of their own. A sum of two even numbers is even, and stays even after subtracting 12. The identity 00 is even, and the inverse of an even residue is even, as in −4=8-4 = 8. The smaller set {0,4,8}\{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}\{1, 5, 9\} the sum 1+5=61 + 5 = 6 falls outside, and the identity 00 is missing besides, while in {0,1,2,3,4,5}\{0, 1, 2, 3, 4, 5\} the sum 3+4=73 + 4 = 7 falls outside.

Associativity never needs checking, since it holds for all of GG. The next two results cut the rest down to one test.

Proof. A subgroup contains b−1b^{-1} and is closed, so it passes the test. Conversely, suppose HH passes. Pick any aa in HH, which exists because HH is nonempty, and apply the test with b=ab = a to get a∗a−1=ea \ast a^{-1} = e in HH. Apply it to the pair ee and bb to get e∗b−1=b−1e \ast b^{-1} = b^{-1} in HH, so HH holds every inverse. Finally, for aa and bb in HH, the element b−1b^{-1} is in HH, so the test applied to aa and b−1b^{-1} gives a∗(b−1)−1=a∗ba \ast (b^{-1})^{-1} = a \ast b in HH, using (b−1)−1=b(b^{-1})^{-1} = b. Associativity is inherited from GG. ■\blacksquare

For finite subsets even the inverse can be dropped from the test, and closure alone decides.

Proof. A subgroup is closed. Conversely, let HH be closed and pick aa in HH. The map that sends xx to a∗xa \ast x takes elements of HH to elements of HH, by closure. By cancellation its ∣H∣|H| values are all different, and they lie in a set of size ∣H∣|H|, so the map reaches every element. So some xx in HH has a∗x=a=a∗ea \ast x = a = a \ast e, and cancellation gives x=ex = e, so ee lies in HH. The map also reaches ee, so some yy in HH has a∗y=ea \ast y = e. Combining with a−1a^{-1} on the left gives y=a−1y = a^{-1}, so a−1a^{-1} lies in HH. With identity, inverses, closure and inherited associativity, HH is a group. ■\blacksquare

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 aa never reaches aa.

Proof. The set is finite, since {0,1}n\{0, 1\}^n has 2n2^n elements, and it is closed by assumption, so the finite subgroup test applies. ■\blacksquare

For C5C_5 the three sums of different nonzero codewords are 01101⊕10110=1101101101 \oplus 10110 = 11011, 01101⊕11011=1011001101 \oplus 11011 = 10110 and 10110⊕11011=0110110110 \oplus 11011 = 01101. A codeword XORed with itself gives 0000000000, and XOR with 0000000000 changes nothing, so every sum stays in the code and C5C_5 is a subgroup of {0,1}5\{0, 1\}^5 of order 4. The even-weight words {000,011,101,110}\{000, 011, 101, 110\} form a subgroup of {0,1}3\{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.

04.Cyclic Groups and the Order of an Element

Start at 33 and keep multiplying by 33 modulo 7. The residues visited are 3,2,6,4,5,13, 2, 6, 4, 5, 1, and the next step returns to 33. Six steps reach all six nonzero residues. Starting at 22 instead gives 2,4,12, 4, 1 and then repeats, so the powers of 22 reach only half of the group. The element 66 returns at once, since 6⋅6=366 \cdot 6 = 36 leaves the residue 11. Figure 2 draws the two journeys as paths around the residues.

Powers of 3 and of 2 modulo 7 multiply by 3, starting at 3 3 2 6 4 5 1 six steps reach all six residues multiply by 2, starting at 2 or at 3 2 4 1 3 6 5 the subgroup {1, 2, 4} the coset {3, 5, 6} three steps return to the start
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 99 in Z12\mathbb{Z}_{12} visits 9,6,3,09, 6, 3, 0, so four additions of 99 return to the identity. In a group written with multiplication, write a0=ea^0 = e, aka^k for the product of kk copies of aa, and a−ka^{-k} for the product of kk copies of a−1a^{-1}. Counting the copies in each factor gives the laws ai∗aj=ai+ja^i \ast a^j = a^{i+j} and (ai)j=aij(a^i)^j = a^{ij} for all integers ii and jj. With addition, aka^k is written kaka.

In a finite group every element has an order. The powers e,a,a2,…e, a, a^2, \ldots all lie in a finite set, so two of them coincide, say ai=aja^i = a^j with i<ji < j. Cancelling aia^i from both sides leaves aj−i=ea^{j-i} = e with j−ij - i positive, so some positive power equals ee, and the smallest such power is the order.

Proof. Suppose ai=aja^i = a^j with 0≤i<j<m0 \le i < j < m. Cancelling aia^i leaves aj−i=ea^{j-i} = e with 0<j−i<m0 < j - i < m, which contradicts the choice of mm as the smallest such exponent. So the mm listed powers are different. For any integer kk, the division algorithm gives k=qm+rk = qm + r with 0≤r<m0 \le r < m, and then

ak=(am)q∗ar=eq∗ar=ar,a^k = (a^m)^q \ast a^r = e^q \ast a^r = a^r,

so every power of aa is one of the mm listed. The product of two powers is a power, so ⟨a⟩\langle a \rangle is closed and finite, and the finite subgroup test makes it a subgroup. Finally ak=ara^k = a^r, and among e,a,…,am−1e, a, \ldots, a^{m-1} only a0a^0 is the identity, so ak=ea^k = e exactly when r=0r = 0, which means mm divides kk. ■\blacksquare

For the additive groups Zn\mathbb{Z}_n the order of every element follows from one formula.

Proof. The multiple kaka is the identity of Zn\mathbb{Z}_n exactly when nn divides the integer kaka. Let g=gcd⁡(a,n)g = \gcd(a, n) and write a=ga′a = g a' and n=gn′n = g n'. A common divisor dd of a′a' and n′n' would make gdgd a common divisor of aa and nn, so d=1d = 1 and gcd⁡(a′,n′)=1\gcd(a', n') = 1. Now nn divides kaka exactly when gn′g n' divides gka′g k a', that is, when n′n' divides ka′k a'. Bezout's identity gives xn′+ya′=1x n' + y a' = 1, so k=xn′k+y (ka′)k = x n' k + y\,(k a'), and when n′n' divides ka′k a' it divides both terms and hence kk. The converse is clear. So ka=0ka = 0 exactly when n′n' divides kk, and the smallest positive such kk is n′=n/gn' = n/g. The order equals nn exactly when g=1g = 1, and an element of order nn has nn different multiples, which fill Zn\mathbb{Z}_n. ■\blacksquare

In Z12\mathbb{Z}_{12} the orders of 0,1,…,110, 1, \ldots, 11 are 1,12,6,4,3,12,2,12,3,4,6,121, 12, 6, 4, 3, 12, 2, 12, 3, 4, 6, 12. The four generators are 11, 55, 77 and 1111, the residues that share no factor greater than 1 with 12. For a=9a = 9 the formula gives 12/3=412/3 = 4, the four steps counted above.

Proof. The formula above gives ⟨n/d⟩\langle n/d \rangle the order n/gcd⁡(n/d,n)=n/(n/d)=dn / \gcd(n/d, n) = n/(n/d) = d, so a subgroup of each order dd exists. Now let HH be any subgroup other than {0}\{0\}, which is ⟨0⟩\langle 0 \rangle, and let mm be the smallest positive element of HH. Closure puts every multiple of mm in HH. For any hh in HH, divide to get h=qm+rh = qm + r with 0≤r<m0 \le r < m. The element h−qmh - qm lies in HH, and its residue is rr, so minimality of mm forces r=0r = 0 and h=qmh = qm. Thus H=⟨m⟩H = \langle m \rangle. Dividing nn the same way gives n=q′m+r′n = q'm + r' with 0≤r′<m0 \le r' < m, and r′r' is the residue of −q′m-q'm, which lies in HH, so r′=0r' = 0 and mm divides nn. Then ∣H∣=ord⁡(m)=n/m|H| = \operatorname{ord}(m) = n/m, so m=n/∣H∣m = n/|H|. The order of HH fixes mm, and mm fixes HH, so there is one subgroup for each order. ■\blacksquare

The divisors of 12 are 1,2,3,4,61, 2, 3, 4, 6 and 1212, so Z12\mathbb{Z}_{12} has six subgroups, {0}\{0\}, {0,6}\{0, 6\}, {0,4,8}\{0, 4, 8\}, {0,3,6,9}\{0, 3, 6, 9\}, {0,2,4,6,8,10}\{0, 2, 4, 6, 8, 10\} and Z12\mathbb{Z}_{12} itself. Figure 3 arranges them by containment.

The six subgroups of Z12 ×2 ×2 ×2 ×2 ×3 ×3 ×3 {0} order 1, from 0 {0, 6} order 2, from 6 {0, 3, 6, 9} order 4, from 3 {0, 4, 8} order 3, from 4 {0, 2, 4, 6, 8, 10} order 6, from 2 all of Z12 order 12, from 1
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.

05.Cosets

Take H={0,4,8}H = \{0, 4, 8\} in Z12\mathbb{Z}_{12} and add 11 to each of its elements. The result is {1,5,9}\{1, 5, 9\}. Adding 22 gives {2,6,10}\{2, 6, 10\}, adding 33 gives {3,7,11}\{3, 7, 11\}, and adding 44 gives {4,8,0}\{4, 8, 0\}, which is HH 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}K = \{0, 3, 6, 9\} cuts the same group into the three sets KK, {1,4,7,10}\{1, 4, 7, 10\} and {2,5,8,11}\{2, 5, 8, 11\}, four elements each. Figure 4 shows both cuts.

Cosets of two subgroups of Z12 H = {0, 4, 8}: four cosets of 3 0 4 8 H 1 5 9 1+H 2 6 10 2+H 3 7 11 3+H K = {0, 3, 6, 9}: three cosets of 4 0 3 6 9 K 1 4 7 10 1+K 2 5 8 11 2+K
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 22 modulo 7 form the subgroup {1,2,4}\{1, 2, 4\}, and multiplying each of its elements by 33 gives {3,6,12}\{3, 6, 12\}, which reduces to {3,5,6}\{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∗aH \ast a combine on the other side, but in an abelian group the two agree.

Proof. The first rule holds because a=a∗ea = a \ast e and ee lies in HH. For the second, the map sending hh to a∗ha \ast h reaches every element of a∗Ha \ast H by definition, and by cancellation it never sends two elements of HH to the same place, so a∗Ha \ast H has as many elements as HH.

For the third rule, suppose a−1∗b=h0a^{-1} \ast b = h_0 lies in HH, so b=a∗h0b = a \ast h_0. Every element b∗hb \ast h of b∗Hb \ast H equals a∗(h0∗h)a \ast (h_0 \ast h), which lies in a∗Ha \ast H because h0∗hh_0 \ast h lies in HH. Likewise a=b∗h0−1a = b \ast h_0^{-1} puts every element of a∗Ha \ast H into b∗Hb \ast H. So the cosets are equal. Conversely, if a∗H=b∗Ha \ast H = b \ast H, then bb, which lies in b∗Hb \ast H by the first rule, lies in a∗Ha \ast H, so b=a∗hb = a \ast h for some hh in HH and a−1∗b=ha^{-1} \ast b = h lies in HH.

For the fourth rule, suppose cc lies in both a∗Ha \ast H and b∗Hb \ast H, so c=a∗h1=b∗h2c = a \ast h_1 = b \ast h_2. Then a−1∗b=h1∗h2−1a^{-1} \ast b = h_1 \ast h_2^{-1}, which lies in HH, and the third rule makes the cosets equal. So two cosets that share anything share everything. ■\blacksquare

Any element of a coset can serve as its representative, so 1+H1 + H, 5+H5 + H and 9+H9 + H all name the same coset {1,5,9}\{1, 5, 9\}. For bit strings, where every word is its own inverse, the third rule says that xx and yy lie in the same coset of a code CC exactly when x⊕yx \oplus y is a codeword.

The repetition code R3={000,111}R_3 = \{000, 111\} is a subgroup of {0,1}3\{0, 1\}^3, and its cosets are {000,111}\{000, 111\}, {001,110}\{001, 110\}, {010,101}\{010, 101\} and {011,100}\{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.

06.Lagrange's Theorem

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 aa of GG lies in some coset, namely a∗Ha \ast H, by the first coset rule. Two different cosets share no element, by the fourth rule. So the distinct cosets split GG into disjoint pieces, and ∣G∣|G| is the sum of their sizes. By the second rule every piece has exactly ∣H∣|H| elements. If there are [G:H][G : H] pieces, the sum is [G:H]⋅∣H∣[G : H] \cdot |H|, and therefore ∣H∣|H| divides ∣G∣|G|. ■\blacksquare

The number [G:H][G : H] is called the index of HH in GG. For the six subgroups of Z12\mathbb{Z}_{12}, of orders 1,2,3,4,61, 2, 3, 4, 6 and 1212, the numbers of cosets are 12,6,4,3,212, 6, 4, 3, 2 and 11, and each product is 12. The theorem is named after Joseph-Louis Lagrange, and four consequences follow at once.

Proof. The subgroup ⟨a⟩\langle a \rangle has ord⁡(a)\operatorname{ord}(a) elements, by the theorem on the size of a cyclic subgroup, and Lagrange's theorem makes this number divide ∣G∣|G|. Writing ∣G∣=q⋅ord⁡(a)|G| = q \cdot \operatorname{ord}(a) gives a∣G∣=(aord⁡(a))q=eq=ea^{|G|} = (a^{\operatorname{ord}(a)})^q = e^q = e. ■\blacksquare

Table 1 checks the corollary on Z7∗\mathbb{Z}_7^*, 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 aaPowers a,a2,…a, a^2, \ldots modulo 7Order
111
22, 4, 13
33, 2, 6, 4, 5, 16
44, 2, 13
55, 4, 6, 2, 3, 16
66, 12

Source: reproduced by ch14_groups_and_cosets.py.

Proof. The residue of aa lies in Zn∗\mathbb{Z}_n^*, which is a group by the lemma on units, and the group has order φ(n)\varphi(n), by the definition of φ\varphi. The corollary on orders of elements gives aφ(n)=1a^{\varphi(n)} = 1 in that group, which is the congruence on the right. For a prime pp every residue from 1 to p−1p - 1 is coprime to pp, so φ(p)=p−1\varphi(p) = p - 1, and the congruence on the left is the special case. ■\blacksquare

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 nn from 2 to 40.

Proof. By Lagrange's theorem a subgroup has order 1 or pp, the only divisors of pp, so it is {e}\{e\} or the whole group. For a≠ea \ne e, the subgroup ⟨a⟩\langle a \rangle contains both ee and aa, so its order is not 1, and it must be the whole group. ■\blacksquare

Proof. The code is a subgroup of {0,1}n\{0, 1\}^n, so its size mm divides 2n2^n. Write m=2kum = 2^k u with uu odd. Since uu is odd, Bezout's identity gives xu+2y=1xu + 2y = 1. If uu divides 2⋅2j2 \cdot 2^{j}, then multiplying by 2j2^{j} gives 2j=xu⋅2j+y⋅2⋅2j2^{j} = xu \cdot 2^{j} + y \cdot 2 \cdot 2^{j}, a sum of two multiples of uu, so uu divides 2j2^{j}. Starting from u∣2nu \mid 2^n and applying this step nn times gives u∣1u \mid 1, so u=1u = 1 and m=2km = 2^k, with k≤nk \le n because m≤2nm \le 2^n. ■\blacksquare

The subgroups of {0,1}3\{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 kk, 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\{0, 1\}^2 every element has order 1 or 2, because x⊕x=00x \oplus x = 00 for every 2-bit string.

The order of 2 modulo each odd prime below 100 prime p order of 2 modulo p 0 20 40 60 80 100 0 20 40 60 80 100 p - 1, the order of the group (p - 1) / 2 order p - 1: 2 generates every nonzero residue order (p - 1) / 2 order a smaller divisor of p - 1
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∗\mathbb{Z}_p^* for each of the 24 odd primes below 100. Every order divides p−1p - 1. For 12 primes the order is p−1p - 1, so the powers of 2 run through every nonzero residue, and for 8 it is (p−1)/2(p - 1)/2. For the remaining four it is a smaller divisor, as at p=31p = 31, where 25=322^5 = 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.

07.Homomorphisms and Kernels

Reduce each element of Z12\mathbb{Z}_{12} modulo 4. The sum 5+105 + 10 in Z12\mathbb{Z}_{12} leaves 3, which reduces to 3. Reducing first gives 11 and 22, whose sum in Z4\mathbb{Z}_4 is also 3. The routes agree because 4 divides 12, so subtracting 12 never changes a residue modulo 4. The residues sent to 00 are {0,4,8}\{0, 4, 8\}, the subgroup whose cosets were drawn earlier, and those sent to 11 are the coset {1,5,9}\{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\mathbb{Z}_4 and Z5∗\mathbb{Z}_5^*. 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)f(e_G) = f(e_G \ast e_G) = f(e_G) \circ f(e_G), cancelling one copy of f(eG)f(e_G) leaves eH=f(eG)e_H = f(e_G). Then f(a)∘f(a−1)=f(a∗a−1)=f(eG)=eHf(a) \circ f(a^{-1}) = f(a \ast a^{-1}) = f(e_G) = e_H, and the same holds in the other order, so f(a−1)f(a^{-1}) is the unique inverse of f(a)f(a). ■\blacksquare

Proof. The kernel contains eGe_G by the lemma. For aa and bb in the kernel, f(a∗b−1)=f(a)∘f(b)−1=eH∘eH=eHf(a \ast b^{-1}) = f(a) \circ f(b)^{-1} = e_H \circ e_H = e_H, so the subgroup test applies. The image contains eHe_H, and f(a)∘f(b)−1=f(a∗b−1)f(a) \circ f(b)^{-1} = f(a \ast b^{-1}) is again an image, so the test applies there too. Next, f(a−1∗b)=f(a)−1∘f(b)f(a^{-1} \ast b) = f(a)^{-1} \circ f(b), which equals eHe_H exactly when f(a)=f(b)f(a) = f(b). By the coset rules, that means aa and bb lie in the same coset of the kernel. If the kernel is {eG}\{e_G\}, that coset is {a}\{a\}, so distinct elements have distinct images, and if the map is one-to-one, only eGe_G goes to eHe_H. ■\blacksquare

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 xx to p(x)=w(x) mod 2p(x) = w(x) \bmod 2, a single bit. The weight lemma of Distance, Detection and Correction gives w(x⊕y)=w(x)+w(y)−2 w(x∧y)w(x \oplus y) = w(x) + w(y) - 2\,w(x \wedge y), and the last term is even, so p(x⊕y)=p(x)⊕p(y)p(x \oplus y) = p(x) \oplus p(y) and parity is a homomorphism from {0,1}3\{0, 1\}^3 to {0,1}\{0, 1\}. Its kernel is the even-weight code {000,011,101,110}\{000, 011, 101, 110\}, and the other fiber is the odd words {001,010,100,111}\{001, 010, 100, 111\}. Figure 6 draws both maps.

Two homomorphisms and the cosets of their kernels x mod 4 on Z12 0 4 8 0 1 5 9 1 2 6 10 2 3 7 11 3 kernel each value is reached by one coset of {0, 4, 8} parity on 3-bit strings 000 011 101 110 0 001 010 100 111 1 kernel even words to 0, odd words to 1
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)=2k mod 5f(k) = 2^k \bmod 5 from Z4\mathbb{Z}_4 to Z5∗\mathbb{Z}_5^* is a homomorphism, because a sum a+ba + b computed in Z4\mathbb{Z}_4 differs from the integer a+ba + b by 00 or 44, and 24 mod 5=12^4 \bmod 5 = 1 makes that difference vanish, so f(a+b)=2a⋅2b mod 5f(a + b) = 2^a \cdot 2^b \bmod 5. It is one-to-one, because the four powers 1,2,4,31, 2, 4, 3 are different. So Z4≅Z5∗\mathbb{Z}_4 \cong \mathbb{Z}_5^*.

The 2-bit strings are not isomorphic to Z4\mathbb{Z}_4, although both groups have four elements. Suppose ff were an isomorphism from Z4\mathbb{Z}_4 to {0,1}2\{0, 1\}^2. Then f(2)=f(1+1)=f(1)⊕f(1)=00=f(0)f(2) = f(1 + 1) = f(1) \oplus 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)kf(a^k) = f(a)^k and a one-to-one homomorphism sends only ee to the identity, an isomorphism keeps the order of every element, and Z4\mathbb{Z}_4 holds an element of order 4 while {0,1}2\{0, 1\}^2 holds none.

08.Quotient Groups

The cosets of H={0,4,8}H = \{0, 4, 8\} can be added to one another. Take any element of {1,5,9}\{1, 5, 9\} and any element of {2,6,10}\{2, 6, 10\} and add them in Z12\mathbb{Z}_{12}. The choice 1+21 + 2 gives 3, the choice 5+105 + 10 gives 15, which leaves 3, and every one of the nine choices lands in {3,7,11}\{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

++HH1+H1 + H2+H2 + H3+H3 + H
HHHH1+H1 + H2+H2 + H3+H3 + H
1+H1 + H1+H1 + H2+H2 + H3+H3 + HHH
2+H2 + H2+H2 + H3+H3 + HHH1+H1 + H
3+H3 + H3+H3 + HHH1+H1 + H2+H2 + H

Source: reproduced by ch14_groups_and_cosets.py.

The table is the addition table of Z4\mathbb{Z}_4 with k+Hk + H in the place of kk, so the cosets form a group of their own, and reduction modulo 4 identifies it with Z4\mathbb{Z}_4.

Proof. Suppose a+H=a′+Ha + H = a' + H and b+H=b′+Hb + H = b' + H. By the coset rules a′=a+h1a' = a + h_1 and b′=b+h2b' = b + h_2 for some h1h_1 and h2h_2 in HH. Then a′+b′=(a+b)+(h1+h2)a' + b' = (a + b) + (h_1 + h_2), using that addition in GG can be regrouped and reordered. Since h1+h2h_1 + h_2 lies in HH, the coset rules give (a′+b′)+H=(a+b)+H(a' + b') + H = (a + b) + H, so the sum is well defined. Associativity and commutativity of the coset sum follow from those of GG, applied to representatives. The coset H=0+HH = 0 + H is the identity, since (0+H)+(a+H)=a+H(0 + H) + (a + H) = a + H, and (a+H)+((−a)+H)=0+H(a + H) + ((-a) + H) = 0 + H. The order is the number of cosets, which is ∣G∣/∣H∣|G|/|H| by Lagrange's theorem. ■\blacksquare

The proof moved h1h_1 past bb, 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+Ka + K = b + K exactly when f(a)=f(b)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)f(a) in the image is reached, by the coset a+Ka + K. The rule turns the coset sum into the operation of HH, since (a+K)+(b+K)=(a+b)+K(a + K) + (b + K) = (a + b) + K goes to f(a+b)=f(a)+f(b)f(a + b) = f(a) + f(b). So the rule is an isomorphism, the number of cosets equals ∣im⁡f∣|\operatorname{im} f|, and Lagrange's theorem turns that number into ∣G∣/∣K∣|G|/|K|. ■\blacksquare

For reduction modulo 4 the theorem reads 12=3⋅412 = 3 \cdot 4, a kernel of three elements and an image of four.

09.Cosets and Syndromes

Return to the code C5={00000,01101,10110,11011}C_5 = \{00000, 01101, 10110, 11011\}. It is a subgroup of {0,1}5\{0, 1\}^5 of order 4, so Lagrange's theorem cuts the 32 words of five bits into 32/4=832/4 = 8 cosets of four words each. Suppose a codeword cc is sent and the channel adds an error pattern ee, so that r=c⊕er = c \oplus e arrives. Since r⊕e=cr \oplus e = c is a codeword, the coset rules put rr and ee 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 ee without knowing cc.

Naming it without listing all 32 words takes a homomorphism whose kernel is the code. Number the bits of xx as x1x2x3x4x5x_1 x_2 x_3 x_4 x_5 from the left. In C5C_5 the first two bits carry the message and the other three are fixed by x3=x1⊕x2x_3 = x_1 \oplus x_2, x4=x1x_4 = x_1 and x5=x2x_5 = x_2, 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),s(x) = \bigl(x_1 \oplus x_2 \oplus x_3,\; x_1 \oplus x_4,\; x_2 \oplus x_5\bigr),
(7)

called the syndrome of xx. Each check gives 00 on every codeword.

Proof. Each component of s(x⊕y)s(x \oplus y) is an XOR of bits of x⊕yx \oplus y, such as (x1⊕y1)⊕(x2⊕y2)⊕(x3⊕y3)(x_1 \oplus y_1) \oplus (x_2 \oplus y_2) \oplus (x_3 \oplus y_3). XOR can be regrouped and reordered, so this equals (x1⊕x2⊕x3)⊕(y1⊕y2⊕y3)(x_1 \oplus x_2 \oplus x_3) \oplus (y_1 \oplus y_2 \oplus y_3), and the same holds for the other two components. So s(x⊕y)=s(x)⊕s(y)s(x \oplus y) = s(x) \oplus s(y). The syndrome is 000000 exactly when x3=x1⊕x2x_3 = x_1 \oplus x_2, x4=x1x_4 = x_1 and x5=x2x_5 = x_2, and the four choices of the first two bits then give exactly the four words of C5C_5, which is therefore the kernel. The first isomorphism theorem gives the image 32/4=832/4 = 8 elements, all of {0,1}3\{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. ■\blacksquare

Since s(r)=s(c)⊕s(e)=s(e)s(r) = s(c) \oplus 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 C5C_5. 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 eee⊕01101e \oplus 01101e⊕10110e \oplus 10110e⊕11011e \oplus 11011Syndrome
00000011011011011011000
10000111010011001011110
01000001011111010011101
00100010011001011111100
00010011111010011001010
00001011001011111010001
01010001111110010001111
00011011101010111000011

Source: reproduced by ch14_groups_and_cosets.py.

The leaders have weights 0,1,1,1,1,1,2,20, 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.

The eight cosets of the code C5 with their leaders and syndromes leader e e XOR 01101 e XOR 10110 e XOR 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 coset leader, a word of least weight 10001 another word of the same least weight
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 rr and ℓ\ell lie in the same coset, so r⊕ℓr \oplus \ell is a codeword by the coset rules, and its distance from rr is w(r⊕(r⊕ℓ))=w(ℓ)w(r \oplus (r \oplus \ell)) = w(\ell). For any codeword c′c', the word r⊕c′r \oplus c' lies in the coset of rr, since XORing it with rr gives the codeword c′c'. The leader has the least weight in that coset, so d(r,c′)=w(r⊕c′)≥w(ℓ)d(r, c') = w(r \oplus c') \ge w(\ell). So no codeword is closer than r⊕ℓr \oplus \ell. Finally the decoder returns r⊕ℓ=c⊕e⊕ℓr \oplus \ell = c \oplus e \oplus \ell, which equals cc exactly when e⊕ℓ=00000e \oplus \ell = 00000, that is, when e=ℓe = \ell. ■\blacksquare

The rule is a table lookup. Compute the syndrome, look up its leader, and XOR the leader into the received word. For r=11111r = 11111 the syndrome is 100100, the leader for 100100 is 0010000100, and the decoder returns 11111⊕00100=1101111111 \oplus 00100 = 11011, which differs from rr only in the third bit.

The decoder repairs exactly the eight leaders, which are no error, the five single errors and the double errors 0101001010 and 0001100011. 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, 1000110001 beside 0101001010 and 1100011000 beside 0001100011, so for syndromes 111111 and 011011 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.

10.Looking Ahead

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 C5C_5. 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\mathbb{Z}_2 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 kk into the dimension of a code.

11.Worked Examples

12.Exercises

References

  1. [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. [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]Hamming, Richard W. (1950). “Error Detecting and Error Correcting Codes.” Bell System Technical Journal, 29(2), pp. 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x
  4. [4]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.

FeedbackBook modePaper
error-correction-codinglinear-block-codes