Paper
Part IILinear Block Codes

Reed–Muller Codes

November 16, 202655 min readbeginner

Reed–Muller codes are truth tables of low-degree Boolean polynomials. The chapter proves their dimension and distance through a recursion and decodes them by majority vote and by the fast Hadamard transform.

A planetary probe photographs a surface and turns each pixel into a brightness from 0 to 63, a 6-bit number. The radio link home is so weak that a few bits in every hundred arrive flipped, and one flipped high-order bit turns a dark pixel bright. A Hamming code fixes one error in a word and is lost at two. The probe needs something much stronger, and it can pay for it in bandwidth, because a picture that arrives slowly is worth more than one full of speckle.

The Mariner probes of 1969 used a code of exactly this kind, sending each 6-bit block of data as one of 64 codewords of 32 bits. Case Study: Codes in the Wild showed that this code, decoded to fix up to 7 errors in a word, lost only 0.000139 of the words at a bit error rate of 0.05. This chapter builds it properly. The 32 bits are the truth table of a Boolean function of five variables, and the code holds the truth tables of every function of degree at most 1. Raising the degree bound gives a whole family, the Reed–Muller codes. Muller described them in 1954 while studying switching circuits [1], and Reed, in the same year, wrote them as polynomials and gave the majority-vote decoder that carries his name [2].

The family earns a chapter because its structure is so regular. One recursion proves the dimension and minimum distance of every member. Reed's decoder needs nothing but XOR gates and vote counters. The first-order codes have a second decoder, the fast Hadamard transform, which finds the nearest of 2m+12^{m+1} codewords with only m2mm 2^m additions.

Every number in the chapter is recomputed by ch26_reed_muller_codes.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch26_charts.py in the same folder. For codes too large to list, such as RM(2,7)\mathrm{RM}(2, 7), RM(3,6)\mathrm{RM}(3, 6) and RM(1,10)\mathrm{RM}(1, 10), the script takes the distance and the radius from the formulas the chapter proves. The GNU Octave twin ch26_reed_muller_codes.m prints the same lines, as The Octave Route explains.

01.A Code Built from Truth Tables

Take three binary variables x1,x2,x3x_1, x_2, x_3. They have eight settings, called points, and each point gets a number by reading its bits as a binary number with x1x_1 as the least significant bit and xmx_m as the most significant,

j=∑i=1mxi 2i−1=x1+2x2+4x3+⋯+2m−1xm.j = \sum_{i=1}^{m} x_i \, 2^{i-1} = x_1 + 2 x_2 + 4 x_3 + \cdots + 2^{m-1} x_m .
(1)

Point 3 is therefore (x1,x2,x3)=(1,1,0)(x_1, x_2, x_3) = (1, 1, 0) and point 6 is (0,1,1)(0, 1, 1). Listing a function's values at points 0 through 7 in order gives an 8-bit word. The variable x1x_1 is 1 at the odd points, so its word is 01010101. The variable x2x_2 gives 00110011, x3x_3 gives 00001111, and the constant function 1 gives 11111111. A product of variables is 1 only where every factor is 1, so the word of x1x2x_1 x_2 is the AND of the first two, 00010001. Figure 1 lists all eight products.

Truth tables of the eight monomials in three binary variables. Each column is one of the points 0 to 7, whose bits are x3 x2 x1 with x1 the least significant. Each row lists the value of one monomial at the eight points: the constant 1, the three variables, the three products of two variables and the product of all three. A frame marks the four rows of degree at most one, which generate RM(1,3). point j x3 x2 x1 0 000 1 001 2 010 3 011 4 100 5 101 6 110 7 111 1 1 1 1 1 1 1 1 1 x1 0 1 0 1 0 1 0 1 x2 0 0 1 1 0 0 1 1 x3 0 0 0 0 1 1 1 1 x1x2 0 0 0 1 0 0 0 1 x1x3 0 0 0 0 0 1 0 1 x2x3 0 0 0 0 0 0 1 1 x1x2x3 0 0 0 0 0 0 0 1 degree 0 degree 1 degree 2 degree 3 the four rows inside the frame generate RM(1,3)
Figure 1. Truth tables of the eight monomials in three variables. The four framed rows, of degree at most 1, are the generator rows of RM(1,3).

Now add words with XOR. The function 1+x2+x31 + x_2 + x_3 has the word 11111111⊕00110011⊕00001111=1100001111111111 \oplus 00110011 \oplus 00001111 = 11000011, of weight 4. Each sum a0+a1x1+a2x2+a3x3a_0 + a_1 x_1 + a_2 x_2 + a_3 x_3 with coefficients in GF(2)\mathrm{GF}(2) gives a word, the sixteen choices of coefficients give sixteen words, and those words form a linear code of length 8 and dimension 4 whose generator matrix has the truth tables of 1, x1x_1, x2x_2 and x3x_3 as rows,

G=[11111111010101010011001100001111].G = \begin{bmatrix} 1&1&1&1&1&1&1&1 \\ 0&1&0&1&0&1&0&1 \\ 0&0&1&1&0&0&1&1 \\ 0&0&0&0&1&1&1&1 \end{bmatrix}.

Column jj of GG is a 1 on top of the three bits of jj. This code is RM(1,3)\mathrm{RM}(1, 3). Adding the three products of two variables as rows gives a code of dimension 7, and adding x1x2x3x_1 x_2 x_3 as well gives all 256 words of length 8.

Two facts keep this algebra small. A binary variable takes only the values 0 and 1, and both satisfy xi2=xix_i^2 = x_i, so no power ever needs to appear, and x12x2x_1^2 x_2 has the same truth table as x1x2x_1 x_2. Coefficients live in GF(2)\mathrm{GF}(2), so f+f=0f + f = 0. A polynomial here is therefore a sum of distinct monomials, each a product of distinct variables, and mm variables have exactly 2m2^m monomials, one for each subset of the variables.

02.Boolean Polynomials and the Möbius Transform

The code was built from eight monomials, and a natural worry is whether some combinations of them collapse. Perhaps two different polynomials share a truth table, or some function is out of reach. Neither happens, and the proof starts from one small example. With two variables, the function that is 1 only at point 1, where (x1,x2)=(1,0)(x_1, x_2) = (1, 0), is x1(x2+1)=x1x2+x1x_1 (x_2 + 1) = x_1 x_2 + x_1, whose word is 0001⊕0101=01000001 \oplus 0101 = 0100.

The two-variable example generalizes. For a point p=(p1,…,pm)p = (p_1, \ldots, p_m), the factor xi+pi+1x_i + p_i + 1 equals 1 when xi=pix_i = p_i and 0 otherwise, so the product

δp(x)=∏i=1m(xi+pi+1)\delta_p(x) = \prod_{i=1}^{m} \left( x_i + p_i + 1 \right)
(2)

is 1 at pp and 0 at every other point.

Proof. Expanding Equation 2 and replacing each xi2x_i^2 by xix_i turns δp\delta_p into a Boolean polynomial. Any function satisfies f=∑pf(p) δpf = \sum_p f(p)\, \delta_p, because both sides agree at every point, so every word of length 2m2^m is the truth table of some polynomial and the map from polynomials to words is onto. There are 22m2^{2^m} polynomials, one for each subset of the 2m2^m monomials, and 22m2^{2^m} words. A map from a finite set onto a set of the same size is one-to-one, so distinct polynomials have distinct truth tables. In particular no nonzero combination of monomials has the zero word as its truth table, so the monomial words are independent, and 2m2^m independent vectors in a space of dimension 2m2^m form a basis. ■\blacksquare

Reading the polynomial back from a truth table is the next job. Write pTp_T for the point whose coordinates are 1 exactly at the positions in TT, so p{1,2}p_{\{1,2\}} is point 3.

Proof. The monomial xRx_R is 1 at pTp_T exactly when R⊆TR \subseteq T, so f(pT)=⨁R⊆TaRf(p_T) = \bigoplus_{R \subseteq T} a_R. Substituting, the right side of Equation 3 is ⨁T⊆S⨁R⊆TaR\bigoplus_{T \subseteq S} \bigoplus_{R \subseteq T} a_R. A fixed R⊆SR \subseteq S appears once for each TT with R⊆T⊆SR \subseteq T \subseteq S, and there are 2∣S∣−∣R∣2^{\lvert S \rvert - \lvert R \rvert} such TT, since each element of SS outside RR may join or not. That count is odd only when R=SR = S, so every other coefficient cancels in pairs and the sum is aSa_S. ■\blacksquare

The formula runs as a network of mm stages. Stage ii replaces the value at every point with xi=1x_i = 1 by its XOR with the value at the point 2i−12^{i-1} lower, the same point with xix_i cleared. After all mm stages, position jj holds the XOR over every point reached by clearing some of the 1 bits of jj, which is Equation 3. Each stage costs 2m−12^{m-1} XORs, so the transform costs m2m−1m 2^{m-1}, which is 12 at m=3m = 3. Table 1 runs it on the word of x3+x1x2x_3 + x_1 x_2.

Table 1. The Möbius transform of the truth table of x3 + x1x2, one stage per variable

StepPositions 0 to 7
Truth table00011110
After the x1x_1 stage00011011
After the x2x_2 stage00011001
After the x3x_3 stage00011000

Source: reproduced by ch26_reed_muller_codes.py.

The two 1s sit at positions 3 and 4. Position 3 is the subset {1,2}\{1, 2\} and position 4 is {3}\{3\}, so the polynomial is x1x2+x3x_1 x_2 + x_3, as it should be. Run in the other direction, the relation f(pT)=⨁R⊆TaRf(p_T) = \bigoplus_{R \subseteq T} a_R from the proof has the same shape as Equation 3, so the same network turns coefficients into a truth table, and the transform is its own inverse. Ordered by point number the system is triangular, since R⊆TR \subseteq T forces the number of RR to be at most that of TT, which is why the elimination of Matrices and Elimination over Finite Fields would solve it by back-substitution alone.

03.Defining the Reed–Muller Codes

With the basis in hand, a code is a choice of which monomials to allow, and the natural choice caps the degree.

Table 2 lists all sixteen codewords of RM(1,3)\mathrm{RM}(1, 3). Each row fixes (a1,a2,a3)(a_1, a_2, a_3), and the two columns give a0=0a_0 = 0 and a0=1a_0 = 1, which are complements of each other.

Table 2. The sixteen codewords of RM(1,3)

(a1,a2,a3)(a_1, a_2, a_3)Linear parta0=0a_0 = 0a0=1a_0 = 1
000000000000011111111
100x1x_10101010110101010
010x2x_20011001111001100
110x1+x2x_1 + x_20110011010011001
001x3x_30000111111110000
101x1+x3x_1 + x_30101101010100101
011x2+x3x_2 + x_30011110011000011
111x1+x2+x3x_1 + x_2 + x_30110100110010110

Source: reproduced by ch26_reed_muller_codes.py.

Proof. The monomials of degree at most rr are part of the basis of the theorem on monomials, so their truth tables are independent and span RM(r,m)\mathrm{RM}(r, m). The dimension is the number of such monomials, which is the number of subsets of {1,…,m}\{1, \ldots, m\} with at most rr elements. ■\blacksquare

Table 3. Dimension k of RM(r,m) for r = 0 to m

mmnnkk for r=0,1,…,mr = 0, 1, \ldots, m
121, 2
241, 3, 4
381, 4, 7, 8
4161, 5, 11, 15, 16
5321, 6, 16, 26, 31, 32
6641, 7, 22, 42, 57, 63, 64
71281, 8, 29, 64, 99, 120, 127, 128

Source: reproduced by ch26_reed_muller_codes.py.

The rows grow like Pascal's triangle. The entry 16 for RM(2,5)\mathrm{RM}(2, 5) is 11+511 + 5, the entries for RM(2,4)\mathrm{RM}(2, 4) and RM(1,4)\mathrm{RM}(1, 4), and the recursion of the next section explains why. Three members of each row are codes met before.

Proof. Degree 0 allows only the constants 0 and 1, whose words are all 0s and all 1s. For r=mr = m, the dimension is 2m2^m, so the code is the whole space. For r=m−1r = m - 1, the monomial xSx_S is 1 at the 2m−∣S∣2^{m - \lvert S \rvert} points where every variable in SS is 1, an even number when ∣S∣≤m−1\lvert S \rvert \le m - 1. Since wt⁡(a⊕b)=wt⁡(a)+wt⁡(b)−2wt⁡(a∧b)\operatorname{wt}(a \oplus b) = \operatorname{wt}(a) + \operatorname{wt}(b) - 2 \operatorname{wt}(a \wedge b), a sum of even-weight words has even weight, so every codeword has even weight. The code's dimension is 2m−12^m - 1, the same as the even-weight code's, and a subspace of the same dimension is the whole space. ■\blacksquare

For m=3m = 3 the four codes are (8,1,8)(8, 1, 8), (8,4,4)(8, 4, 4), (8,7,2)(8, 7, 2) and (8,8,1)(8, 8, 1), with the minimum distances proved two sections ahead.

04.The Recursive Structure

Take f=1+x1+x4f = 1 + x_1 + x_4 with m=4m = 4. On the first eight points x4=0x_4 = 0 and ff reduces to 1+x11 + x_1, whose 3-variable word is u=10101010u = 10101010. On the last eight points x4=1x_4 = 1, so ff is 1+x11 + x_1 plus 1, and its word there is u⊕vu \oplus v with v=11111111v = 11111111, the word of the constant 1. The codeword is (u∣u⊕v)=1010101001010101(u \mid u \oplus v) = 1010101001010101, of weight 8. Every polynomial splits this way.

Proof. Collect the monomials of ff that contain xmx_m and factor it out. What remains is gg, and the cofactor is hh, which lost one variable and so has degree at most r−1r - 1. The split is unique because the monomials are a basis. By Equation 1, the first 2m−12^{m-1} points have xm=0x_m = 0 and list the points of m−1m - 1 variables in order, so there f=gf = g and the word is u=ev⁡(g)u = \operatorname{ev}(g). The last 2m−12^{m-1} points have xm=1x_m = 1 and repeat the same order, so there f=g+hf = g + h and the word is u⊕vu \oplus v with v=ev⁡(h)v = \operatorname{ev}(h). Every pair (g,h)(g, h) with the stated degrees arises, so every pair (u,v)(u, v) does. ■\blacksquare

In matrix form, with G(r,m)G(r, m) the generator matrix,

G(r,m)=[G(r,m−1)G(r,m−1)0G(r−1,m−1)].G(r, m) = \begin{bmatrix} G(r, m-1) & G(r, m-1) \\ 0 & G(r-1, m-1) \end{bmatrix} .

For RM(1,4)\mathrm{RM}(1, 4) the top block repeats the four rows of RM(1,3)\mathrm{RM}(1, 3) twice, and the bottom block adds one row, 00000000111111110000000011111111, the word of x4x_4. The count of rows also explains the Pascal pattern, k(r,m)=k(r,m−1)+k(r−1,m−1)k(r, m) = k(r, m-1) + k(r-1, m-1). Figure 2 draws the recursion as a lattice in which every code is fed by two codes of half its length.

The Reed-Muller codes RM(r,m) for m from 1 to 5, each box giving the length, dimension and minimum distance. Every code with 0 less than r less than m is built from two codes of half the length: a solid arrow brings u from RM(r, m-1) in the same row, and a dashed arrow brings v from RM(r-1, m-1) one row up. Shaded boxes are the base cases. The arrows into RM(1,3), the (8,4,4) code, are highlighted. m = 1 length 2 m = 2 length 4 m = 3 length 8 m = 4 length 16 m = 5 length 32 r = 0 r = 1 r = 2 r = 3 r = 4 r = 5 RM(0,1) (2,1,2) RM(1,1) (2,2,1) RM(0,2) (4,1,4) RM(1,2) (4,3,2) RM(2,2) (4,4,1) RM(0,3) (8,1,8) RM(1,3) (8,4,4) RM(2,3) (8,7,2) RM(3,3) (8,8,1) RM(0,4) (16,1,16) RM(1,4) (16,5,8) RM(2,4) (16,11,4) RM(3,4) (16,15,2) RM(4,4) (16,16,1) RM(0,5) (32,1,32) RM(1,5) (32,6,16) RM(2,5) (32,16,8) RM(3,5) (32,26,4) RM(4,5) (32,31,2) RM(5,5) (32,32,1) u, the left half, from RM(r, m-1) v, from RM(r-1, m-1), gives u + v base case: the repetition code RM(0,m) or all words RM(m,m)
Figure 2. The recursion as a lattice. Each inner code is built from u in RM(r, m-1) and v in RM(r-1, m-1), and the shaded base cases are the repetition codes and the full spaces.

This is the (u∣u+v)(u \mid u + v) construction of Modifying and Combining Codes, due to Plotkin [3], applied over and over. The same 2-by-2 pattern, which sends a pair (u,v)(u, v) to (u,u⊕v)(u, u \oplus v), is the kernel from which Channel Polarization, in the Part Polar Codes, builds polar codes.

05.Minimum Distance

The weights already seen hint at the answer. The repetition code of length 8 has distance 8, the code RM(1,3)\mathrm{RM}(1, 3) has nonzero words of weight 4 and 8 only, and the even-weight code has distance 2. The distance halves each time the order goes up by one.

Proof. Induction on mm. The base cases are the two ends of every row. For r=0r = 0 the code is the repetition code, with d=2md = 2^m, and for r=mr = m it is the whole space, with d=1=20d = 1 = 2^0. These settle m=1m = 1 entirely. For m≥2m \ge 2 and 1≤r≤m−11 \le r \le m - 1, Equation 7 builds the code from RM(r,m−1)\mathrm{RM}(r, m-1) and RM(r−1,m−1)\mathrm{RM}(r-1, m-1), whose distances are 2m−1−r2^{m-1-r} and 2m−r2^{m-r} by the induction hypothesis. The theorem on the (u∣u+v)(u \mid u + v) construction in Modifying and Combining Codes gives the distance as the smaller of twice the first and once the second, so d=min⁡(2⋅2m−1−r, 2m−r)=2m−rd = \min\left(2 \cdot 2^{m-1-r},\ 2^{m-r}\right) = 2^{m-r}. ■\blacksquare

The monomial x1x2⋯xrx_1 x_2 \cdots x_r shows the bound in one word. It is 1 exactly where its rr variables are 1, which happens at 2m−r2^{m-r} points. By the rule of Distance, Detection and Correction, a code of distance 2m−r2^{m-r} with r<mr \lt m corrects up to 2m−r−1−12^{m-r-1} - 1 errors, which is 1 for RM(1,3)\mathrm{RM}(1, 3) and RM(2,4)\mathrm{RM}(2, 4), 3 for RM(1,4)\mathrm{RM}(1, 4), RM(2,5)\mathrm{RM}(2, 5) and RM(3,6)\mathrm{RM}(3, 6), and 7 for the Mariner code RM(1,5)\mathrm{RM}(1, 5). The script lists every word of the 18 codes up to length 128 with at most 11 information bits, and the 65,536 words of RM(2,5)\mathrm{RM}(2, 5), and finds these distances in all of them. It gets the weights of RM(3,5)\mathrm{RM}(3, 5) and RM(4,5)\mathrm{RM}(4, 5) from those of RM(1,5)\mathrm{RM}(1, 5) and RM(0,5)\mathrm{RM}(0, 5), their duals by Equation 9, through the MacWilliams identity of Weight Distributions and Undetected Errors. Table 4 collects the parameters of the codes this chapter uses most.

Table 4. Parameters (n, k, d) of some Reed–Muller codes

Codennkkdd
RM(1,3)\mathrm{RM}(1, 3)844
RM(1,4)\mathrm{RM}(1, 4)1658
RM(2,4)\mathrm{RM}(2, 4)16114
RM(1,5)\mathrm{RM}(1, 5)32616
RM(2,5)\mathrm{RM}(2, 5)32168
RM(3,5)\mathrm{RM}(3, 5)32264
RM(4,5)\mathrm{RM}(4, 5)32312
RM(1,7)\mathrm{RM}(1, 7)128864
RM(2,7)\mathrm{RM}(2, 7)1282932

Source: reproduced by ch26_reed_muller_codes.py.

06.First-Order Codes and Their Weights

Every nonzero word of RM(1,3)\mathrm{RM}(1, 3) in Table 2 other than 11111111 has weight exactly 4. A simple counting fact is behind this.

Proof. Pick an ii with ai=1a_i = 1 and pair each point with the point that differs from it only in xix_i. Every term of ℓ\ell is the same at the two points except aixia_i x_i, so ℓ\ell takes different values on them. Each of the 2m−12^{m-1} pairs therefore holds exactly one point where ℓ=1\ell = 1. ■\blacksquare

Proof. The constants 0 and 1 give the first two words. The other 2m+1−22^{m+1} - 2 polynomials have some ai=1a_i = 1 with i≥1i \ge 1, and the lemma gives each one weight 2m−12^{m-1}. ■\blacksquare

For m=3,4,5m = 3, 4, 5 that is 14 words of weight 4, 30 of weight 8 and 62 of weight 16, and for m=6m = 6 it is 126 words of weight 32. The script counts all four distributions directly. The words with a0=0a_0 = 0, with position 0 deleted, have as generator the rows x1,…,xmx_1, \ldots, x_m at the points 1 to 2m−12^m - 1, whose columns are every nonzero mm-bit number. That is the counting-order parity-check matrix of the Hamming code, so these words form its dual, and the constant weight generalizes the theorem in Linear Codes that every nonzero word of the dual of the (7,4)(7, 4) code has weight 4.

07.Duality

The dimensions in Table 3 pair up. In each row, kk for order rr and kk for order m−r−1m - r - 1 add to 2m2^m, as in 5+11=165 + 11 = 16 for m=4m = 4. That is the signature of a code and its dual.

Proof. Take ff of degree at most rr and gg of degree at most m−r−1m - r - 1. The inner product of their words counts, modulo 2, the points where both are 1, which is the weight of the word of fgfg. The product has degree at most m−1m - 1, so its word lies in RM(m−1,m)\mathrm{RM}(m-1, m), which has only even weights, and the inner product is 0. So RM(m−r−1,m)⊆RM(r,m)⊥\mathrm{RM}(m - r - 1, m) \subseteq \mathrm{RM}(r, m)^{\perp}. The dimensions are ∑i≤r(mi)\sum_{i \le r} \binom{m}{i} and ∑i≤m−r−1(mi)=∑i≥r+1(mi)\sum_{i \le m - r - 1} \binom{m}{i} = \sum_{i \ge r + 1} \binom{m}{i}, which add to 2m2^m. By the theorem in Vector Spaces over Finite Fields that a code and its dual fill the length, the dual has dimension 2m−k2^m - k, the same as the subspace inside it, so the two are equal. ■\blacksquare

Proof. By Equation 9, RM(m−2,m)\mathrm{RM}(m-2, m) is the dual of RM(1,m)\mathrm{RM}(1, m), whose generator matrix has a 1 above the bits of jj in column jj. Hamming Codes and Perfect Codes built the extended Hamming code from exactly this matrix, the counting-order parity-check matrix with an overall parity row on top and the parity position at 0. For m=3m = 3, the order m−2m - 2 equals 1. ■\blacksquare

The script puts all 16 words of RM(1,3)\mathrm{RM}(1, 3) and all 2048 words of RM(2,4)\mathrm{RM}(2, 4) through both checks of the extended Hamming code, even overall parity and a zero syndrome, and the equal dimensions do the rest. So RM(2,4)\mathrm{RM}(2, 4) is the (16,11,4)(16, 11, 4) extended Hamming code, and RM(1,3)\mathrm{RM}(1, 3) is the extended (8,4,4)(8, 4, 4) code whose decoder Hamming Codes and Perfect Codes built to correct one error and detect two. The dual of the Mariner code is RM(3,5)\mathrm{RM}(3, 5), a (32,26,4)(32, 26, 4) code.

08.Reed's Majority-Logic Decoder

Syndrome Decoding and the Standard Array would decode RM(1,3)\mathrm{RM}(1, 3) with a table of 16 coset leaders. Reed found something better, a decoder that reads each coefficient off the received word by voting. The idea is clearest on a small case.

Table 5. Check sums of Reed's decoder for y = 11000111 in RM(1,3)

CoefficientPairs of pointsSumsVote
a1a_10 and 1, 2 and 3, 4 and 5, 6 and 700100
a2a_20 and 2, 1 and 3, 4 and 6, 5 and 711101
a3a_30 and 4, 1 and 5, 2 and 6, 3 and 710111

Source: reproduced by ch26_reed_muller_codes.py.

Figure 3 shows the pairs as the edges of a cube. The points are its corners, the pairs for aia_i are the four edges parallel to axis ii, and an error at one corner touches only one edge in each direction.

The eight points of RM(1,3) drawn as the corners of a cube, numbered 0 to 7, with x1 to the right, x2 into the page and x3 upward. For each coefficient a1, a2 and a3 the four edges parallel to that axis are highlighted. The two received bits at the ends of an edge add to an estimate of that coefficient, and the four edges are disjoint, so a single error changes at most one of the four estimates. check sums for a1 edges along x1 0 1 2 3 4 5 6 7 sums of y at 01, 23, 45, 67 check sums for a2 edges along x2 0 1 2 3 4 5 6 7 sums of y at 02, 13, 46, 57 check sums for a3 edges along x3 0 1 2 3 4 5 6 7 sums of y at 04, 15, 26, 37 each sum covers its own two points, so one error spoils at most one of the four
Figure 3. The check sums of RM(1,3) as edges of a cube. Each coefficient is estimated by the four edges parallel to its axis, and a single error at one corner spoils at most one of the four.

For higher orders the edges become larger faces. A subcube for a set SS of ss variables is the set of 2s2^s points where the variables outside SS are held at a fixed pattern bb and the variables in SS run free. For S={1,2}S = \{1, 2\} in four variables, the subcubes are the points 0 to 3, 4 to 7, 8 to 11 and 12 to 15. There are 2m−s2^{m-s} of them, and they are disjoint and cover every point.

Proof. The monomial xTx_T is 1 at a point of QQ when every variable in TT is 1. A variable of TT outside SS is fixed on QQ, so it must be 1 in the pattern bb, and the variables of SS outside TT are free. The number of points of QQ where xT=1x_T = 1 is therefore ∏i∈T∖Sbi⋅2∣S∖T∣\prod_{i \in T \setminus S} b_i \cdot 2^{\lvert S \setminus T \rvert}, which is odd only if S∖TS \setminus T is empty, that is, S⊆TS \subseteq T. With ∣T∣≤∣S∣\lvert T \rvert \le \lvert S \rvert that forces T=ST = S, and then the count is 1. ■\blacksquare

So for a codeword of degree at most ss with errors ee, every subcube QQ for an ss-set SS gives

⨁p∈Qy(p)=aS⊕⨁p∈Qe(p).\bigoplus_{p \in Q} y(p) = a_S \oplus \bigoplus_{p \in Q} e(p) .
(10)

The script checks the lemma on all 3,880 combinations of mm from 1 to 5, set, subcube and monomial. Reed's decoder for RM(r,m)\mathrm{RM}(r, m) now runs in stages from degree rr down to 0. At stage ss, each monomial xSx_S of degree ss gets 2m−s2^{m-s} disjoint check sums, each over a subcube of 2s2^s points, and the majority of those sums gives aSa_S. The decided degree-ss part is then removed from yy, leaving a word of degree at most s−1s - 1 plus the same errors, and the next stage begins. The last stage takes the majority of all 2m2^m remaining bits.

Table 6. Degree-2 check sums of Reed's decoder for RM(2,4), with an error at position 10

MonomialSubcubesSumsVote
x1x2x_1 x_2{0,1,2,3}\{0, 1, 2, 3\}, {4,5,6,7}\{4, 5, 6, 7\}, {8,9,10,11}\{8, 9, 10, 11\}, {12,13,14,15}\{12, 13, 14, 15\}11011
x1x3x_1 x_3{0,1,4,5}\{0, 1, 4, 5\}, {2,3,6,7}\{2, 3, 6, 7\}, {8,9,12,13}\{8, 9, 12, 13\}, {10,11,14,15}\{10, 11, 14, 15\}00010
x1x4x_1 x_4{0,1,8,9}\{0, 1, 8, 9\}, {2,3,10,11}\{2, 3, 10, 11\}, {4,5,12,13}\{4, 5, 12, 13\}, {6,7,14,15}\{6, 7, 14, 15\}01000
x2x3x_2 x_3{0,2,4,6}\{0, 2, 4, 6\}, {1,3,5,7}\{1, 3, 5, 7\}, {8,10,12,14}\{8, 10, 12, 14\}, {9,11,13,15}\{9, 11, 13, 15\}11011
x2x4x_2 x_4{0,2,8,10}\{0, 2, 8, 10\}, {1,3,9,11}\{1, 3, 9, 11\}, {4,6,12,14}\{4, 6, 12, 14\}, {5,7,13,15}\{5, 7, 13, 15\}10000
x3x4x_3 x_4{0,4,8,12}\{0, 4, 8, 12\}, {1,5,9,13}\{1, 5, 9, 13\}, {2,6,10,14}\{2, 6, 10, 14\}, {3,7,11,15}\{3, 7, 11, 15\}11011

Source: reproduced by ch26_reed_muller_codes.py.

Proof. Suppose t≤2m−r−1−1t \le 2^{m-r-1} - 1 errors and that every stage above ss decided correctly. Then the word entering stage ss is a codeword of degree at most ss plus the original errors, and Equation 10 holds for every check sum. The 2m−s2^{m-s} subcubes for one monomial are disjoint, so each error spoils at most one sum, and at most tt of the 2m−s2^{m-s} votes are wrong. Since s≤rs \le r, the bound t≤2m−r−1−1<2m−s/2t \le 2^{m-r-1} - 1 \lt 2^{m-s} / 2 leaves a strict majority correct, so stage ss decides correctly too. The stage with the fewest votes, 2m−r2^{m-r}, is s=rs = r, and that is where the bound binds. By induction every stage is correct, down to the final vote over all 2m2^m bits. ■\blacksquare

Two decisions remain about how the decoder behaves when it cannot win. When a vote ties, which can happen because every vote count is even, the decoder stops and reports a failure rather than guess. And the outcome must not depend on which codeword was sent, or no test on one codeword would say anything about the rest.

Proof. At stage ss, write csc_s and ese_s for the parts of the current word coming from cc and from ee. Each check sum of cs⊕esc_s \oplus e_s is the coefficient aSa_S of cc XORed with the same sum taken on ese_s. Flipping every input of a vote by the same bit flips its result and preserves a tie, so the decision on c⊕ec \oplus e is aSa_S XORed with the decision on ee alone. Removing the decided part therefore leaves cs−1⊕es−1c_{s-1} \oplus e_{s-1}, with es−1e_{s-1} exactly what decoding ee alone would leave. At the end the decoded coefficients are those of cc plus those decoded from ee. ■\blacksquare

The lemma means a pattern can be tested on the zero codeword alone. Table 7 lists what the script ran. For RM(1,3)\mathrm{RM}(1, 3), RM(1,4)\mathrm{RM}(1, 4) and RM(2,4)\mathrm{RM}(2, 4) it decoded every correctable pattern added to every codeword. For RM(1,5)\mathrm{RM}(1, 5) it decoded all 4,514,873 patterns of weight 0 to 7 on the zero codeword, 3,365,856 of them of weight 7, and then checked the lemma itself on 801 distinct spread patterns of weight up to 9 against all 64 codewords. The 192 that fail on the zero word, 96 by a tie and 96 by a wrong codeword, fail the same way on every codeword, and the other 609 succeed on every one.

Table 7. Exhaustive runs of Reed's decoder

CodeError patternsDecodingsWrong
RM(1,3)\mathrm{RM}(1, 3), all codewords, weight 0 to 191440
RM(1,4)\mathrm{RM}(1, 4), all codewords, weight 0 to 369722,3040
RM(2,4)\mathrm{RM}(2, 4), all codewords, weight 0 to 11734,8160
RM(1,5)\mathrm{RM}(1, 5), zero codeword, weight 0 to 74,514,8734,514,8730

Source: reproduced by ch26_reed_muller_codes.py.

Reed's check sums are the first of a large family of majority-logic decoders, and Majority-Logic and Finite-Geometry Codes builds codes around them.

09.The Fast Hadamard Transform Decoder

Reed's decoder stops at half the minimum distance. A maximum-likelihood decoder, which by Channels, Signals and Likelihoods picks the nearest codeword on a binary symmetric channel, does better on heavier patterns, and for RM(1,m)\mathrm{RM}(1, m) it costs far less than comparing against all 2m+12^{m+1} codewords one at a time. The trick is to change the alphabet. Map each bit bb to (−1)b(-1)^b, so 0 becomes +1+1 and 1 becomes −1-1, as in Channels, Signals and Likelihoods. Then XOR becomes multiplication, and two words agree in a position exactly when the product of their signs there is +1+1.

The bits of ww name a linear part. With wiw_i the bit of ww in place ii, the number w⋅jw \cdot j is the value of w1x1+⋯+wmxmw_1 x_1 + \cdots + w_m x_m at point jj.

Proof. The codeword's sign at point jj is (−1)a0(−1)w⋅j(-1)^{a_0} (-1)^{w \cdot j}, so the sum of the products of its signs with YY is (−1)a0Tw(-1)^{a_0} T_w. Each agreement adds 1 to that sum and each disagreement subtracts 1, so the sum equals A−(2m−A)=2A−2mA - (2^m - A) = 2A - 2^m. Solving gives Equation 12. Agreement is largest when (−1)a0Tw(-1)^{a_0} T_w is largest, which means the largest ∣Tw∣\lvert T_w \rvert with the sign of (−1)a0(-1)^{a_0} matching that of TwT_w. ■\blacksquare

Computing each TwT_w separately takes 2m−12^m - 1 additions, so all of them take 2m(2m−1)2^m (2^m - 1), roughly 2m⋅2m2^m \cdot 2^m. The signs (−1)w⋅j(-1)^{w \cdot j} form a matrix with a structure that removes most of that work. For m=2m = 2, the rows for w=0,1,2,3w = 0, 1, 2, 3 are (1,1,1,1)(1, 1, 1, 1), (1,−1,1,−1)(1, -1, 1, -1), (1,1,−1,−1)(1, 1, -1, -1) and (1,−1,−1,1)(1, -1, -1, 1), and the bottom-right 2-by-2 block is the negative of the others.

Proof. Induction on mm, with H2H_2 itself as the case m=1m = 1. Split ww and jj into their top bits wmw_m, jmj_m and the rest, w′w' and j′j'. Then (−1)w⋅j=(−1)wmjm(−1)w′⋅j′(-1)^{w \cdot j} = (-1)^{w_m j_m} (-1)^{w' \cdot j'}. The top bit selects the block, and the factor (−1)wmjm(-1)^{w_m j_m} is −1-1 only for the bottom-right block, while the second factor is the entry of H2m−1H_{2^{m-1}} by the induction hypothesis. That is Equation 13. ■\blacksquare

The script confirms H4=H2⊗H2H_4 = H_2 \otimes H_2, H8=H2⊗H4H_8 = H_2 \otimes H_4 and H32=H2⊗H16H_{32} = H_2 \otimes H_{16} entry by entry. Splitting YY into its halves Y′Y' and Y′′Y'', the blocks of Equation 13 say that the first half of TT is H2m−1(Y′+Y′′)H_{2^{m-1}}(Y' + Y'') and the second half is H2m−1(Y′−Y′′)H_{2^{m-1}}(Y' - Y''). This is the same (u∣u⊕v)(u \mid u \oplus v) split as the code itself, now in arithmetic.

Proof. Forming Y′+Y′′Y' + Y'' and Y′−Y′′Y' - Y'' takes 2m2^m operations, and then two transforms of half the size follow, so N(m)=2m+2N(m−1)N(m) = 2^m + 2 N(m-1), with N(1)=2N(1) = 2 for the single pair Y0+Y1Y_0 + Y_1, Y0−Y1Y_0 - Y_1. Then N(1)=1⋅21N(1) = 1 \cdot 2^1, and if N(m−1)=(m−1)2m−1N(m-1) = (m-1) 2^{m-1}, then N(m)=2m+(m−1)2m=m2mN(m) = 2^m + (m-1) 2^m = m 2^m. ■\blacksquare

Table 8. Operations to compute all 2^m correlations, fast against direct

mmFast, m2mm 2^mDirect, 2m(2m−1)2^m (2^m - 1)
2812
32456
464240
5160992
1010,2401,047,552

Source: reproduced by ch26_reed_muller_codes.py.

Table 8 sets the two counts side by side for a few values of mm. At m=10m = 10 the fast transform is 102.3 times cheaper, and Figure 4 shows the gap widening with mm.

Additions needed to correlate a received word with every first-order pattern, direct against fast, for m from 2 to 10 number of variables m, code length 2^m additions and subtractions 1 10 100 1,000 10,000 100,000 1,000,000 10,000,000 2 3 4 5 6 7 8 9 10 1,047,552 10,240 direct correlation, 2^m (2^m - 1) fast Hadamard transform, m 2^m
Figure 4. Additions needed to correlate a received word with every first-order pattern, directly and with the fast Hadamard transform. Data: computed by ch26_charts.py in the companion repository.

Unrolled, the halving becomes mm stages. Stage 1 pairs positions 2m−12^{m-1} apart, stage 2 pairs positions 2m−22^{m-2} apart, and so on down to neighbors. Each pair passes through a butterfly that writes the sum into the upper position and the difference into the lower, so each stage has 2m−12^{m-1} butterflies and m=3m = 3 needs 12. Figure 5 draws them for the received word of Reed's example, and Table 9 lists every intermediate value.

The fast Hadamard transform for m = 3 as three stages of four butterflies. Each butterfly takes two values, an upper input from row j and a lower input from row j plus h, and sends their sum to row j and their difference to row j plus h, with h equal to 4, 2 and 1 in the three stages. The numbers are those of the worked example: the received word 11000111 becomes the signs Y on the left, the small numbers after each stage are its outputs, and the right column lists the correlations T0 to T7. The largest magnitude is T6 = -6. input Y stage 1 j with j+4 stage 2 j with j+2 stage 3 j with j+1 output T Y0 = -1 Y1 = -1 Y2 = 1 Y3 = 1 Y4 = 1 Y5 = -1 Y6 = -1 Y7 = -1 + 0 + -2 + 0 + 0 - -2 - 0 - 2 - 2 + 0 + -2 - 0 - -2 + 0 + 2 - -4 - -2 + T0 = -2 - T1 = 2 + T2 = -2 - T3 = 2 + T4 = 2 - T5 = -2 + T6 = -6 - T7 = -2 + upper input plus lower - upper input minus lower T6 = -6 has the largest magnitude
Figure 5. The fast Hadamard transform for m = 3. Each butterfly sends the sum of its inputs up and their difference down, and the numbers are those of the received word 11000111.

Table 9. The fast Hadamard transform of y = 11000111, stage by stage

Step01234567
Signs YY−1-1−1-1111111−1-1−1-1−1-1
Stage 1, pairs 4 apart00−2-20000−2-2002222
Stage 2, pairs 2 apart00−2-200−2-20022−4-4−2-2
Stage 3, the correlations TT−2-222−2-22222−2-2−6-6−2-2

Source: reproduced by ch26_reed_muller_codes.py.

The largest magnitude is T6=−6T_6 = -6. Position 6 is binary 110, so w1=0w_1 = 0, w2=1w_2 = 1 and w3=1w_3 = 1, and the negative sign gives a0=1a_0 = 1. The decoded word is that of 1+x2+x31 + x_2 + x_3, the codeword sent, with agreement (8+6)/2=7(8 + 6)/2 = 7 by Equation 12. The script confirms that the transform matches direct correlation on all 256 words of length 8. How many errors can this decoder always survive?

Proof. The sent codeword agrees with yy in 2m−t2^m - t positions, so Equation 12 gives (−1)a0Tw∗=2(2m−t)−2m=2m−2t(-1)^{a_0} T_{w^*} = 2(2^m - t) - 2^m = 2^m - 2t. For w≠w∗w \ne w^*, the codeword c′c' of w1x1+⋯+wmxmw_1 x_1 + \cdots + w_m x_m differs from the sent one in a nonconstant first-order word, which has weight 2m−12^{m-1} by the lemma on half the points. Changing tt bits moves the distance from yy to c′c' by at most tt, so it lies between 2m−1−t2^{m-1} - t and 2m−1+t2^{m-1} + t, and the agreement AA lies in the same range. Then Equation 12 gives ∣Tw∣=∣2A−2m∣≤2t\lvert T_w \rvert = \lvert 2A - 2^m \rvert \le 2t. When t≤2m−2−1t \le 2^{m-2} - 1, the correct magnitude 2m−2t2^m - 2t exceeds 2t2t, because 4t<2m4t \lt 2^m. ■\blacksquare

Table 10. The 32 correlations of the Mariner example with seven errors

Patterns wwCorrelations TwT_w
0 to 710,−2,−2,2,−2,2,2,610, -2, -2, 2, -2, 2, 2, 6
8 to 156,2,2,−2,2,−18,−2,−66, 2, 2, -2, 2, -18, -2, -6
16 to 232,−2,−10,2,6,2,−6,−102, -2, -10, 2, 6, 2, -6, -10
24 to 31−2,2,−6,−2,−6,−2,6,−6-2, 2, -6, -2, -6, -2, 6, -6

Source: reproduced by ch26_reed_muller_codes.py.

The radius 2m−2−12^{m-2} - 1 equals Reed's radius for r=1r = 1, so on paper the two decoders promise the same. The difference lies beyond the radius, where the transform still returns a nearest codeword while Reed's decoder may stop on a tie. Nothing in Equation 11 needs the YjY_j to be ±1\pm 1, either. A receiver that keeps the analog value of each bit can feed those values straight into the same butterflies, and Soft-Decision Decoding of Block Codes, in the Part Soft Decisions and Concatenation, shows what that gains.

10.The Mariner Code Revisited

The Mariner code is RM(1,5)\mathrm{RM}(1, 5), a (32,6,16)(32, 6, 16) code of rate 6/32=0.18756/32 = 0.1875, sending 6 data bits in each 32-bit codeword. Its minimum distance 16 corrects up to 7 errors, so a word is decoded wrong only when 8 or more of its 32 bits flip, and on a binary symmetric channel with crossover probability pp that happens with probability

Pw=∑j=832(32j)pj(1−p)32−j.P_w = \sum_{j=8}^{32} \binom{32}{j} p^j (1 - p)^{32 - j} .
(15)

At p=0.05p = 0.05 that is 0.000139, against 0.2649 for the same 6 bits sent bare, the figure Case Study: Codes in the Wild compared with five-fold repetition. The link carried 16,200 bits per second [4], and the structure of this chapter is what made decoding at that rate practical. A syndrome table for the code would need 2262^{26} cosets. Reed's decoder needs five votes of 16 check sums and one vote of 32 bits, and the fast transform needs 160 additions and subtractions and a search for the largest of 32 magnitudes.

11.Hardware for Encoding and Decoding

The encoder is the easiest circuit in the chapter. Codeword bit jj is a0a_0 plus the coefficients of the monomials that are 1 at point jj, so a parallel encoder is one XOR tree per output bit. For RM(1,3)\mathrm{RM}(1, 3), bit jj needs as many two-input XOR gates as jj has 1 bits, 12 in all. Counting the same way, one gate fewer than the number of allowed monomials that are 1 at the point, gives 80 for RM(1,5)\mathrm{RM}(1, 5) and 56 for RM(2,4)\mathrm{RM}(2, 4). A serial encoder trades gates for time. A 3-bit counter steps through the points, three AND gates form a1x1a_1 x_1, a2x2a_2 x_2 and a3x3a_3 x_3, and three XOR gates add them to a0a_0, one codeword bit per clock, as Figure 6 shows.

A serial encoder for RM(1,3). A 3-bit counter steps through the points j = 0 to 7 and presents the bits x1, x2 and x3 of each point. Three AND gates form a1 x1, a2 x2 and a3 x3, and a tree of three XOR gates adds them to a0, so one codeword bit c(j) leaves on each clock. 3-bit counter j = 0 to 7 clk x1 a1 x2 a2 x3 a3 a0 c(j) one bit per clock c(j) = a0 + a1 x1 + a2 x2 + a3 x3 at the point j = (x3 x2 x1)
Figure 6. A serial encoder for RM(1,3). A counter supplies the point, three AND gates select the coefficients, and three XOR gates produce one codeword bit per clock.

Reed's decoder maps onto XOR trees and majority gates. Each check sum over 2s2^s points is an XOR tree of 2s−12^s - 1 gates, and each vote is a majority gate over 2m−s2^{m-s} sums. For RM(1,3)\mathrm{RM}(1, 3) that means three checks of four XOR gates each, three majority gates of 4 inputs, a block of 12 XOR gates that removes a1x1+a2x2+a3x3a_1 x_1 + a_2 x_2 + a_3 x_3 from the received word, and one majority gate of 8 inputs for a0a_0. Figure 7 shows one check in gates and the whole decoder as blocks. A majority gate has one output, so on a 2 to 2 tie it still returns 0 or 1, and the circuit as drawn hands back a codeword where the algorithm would stop. Reporting the failure takes a tie detector on each vote and an OR gate that joins their flags, and the figure draws neither. The top-degree check sums cost 80 XOR gates for RM(1,5)\mathrm{RM}(1, 5), which also needs five majority gates of 16 inputs and one of 32, and 72 for RM(2,4)\mathrm{RM}(2, 4).

Reed's decoder for RM(1,3) in gates. On the left, the check for a1: four XOR gates add the received bits in the pairs 0 and 1, 2 and 3, 4 and 5, 6 and 7, and a majority gate over the four sums gives a1. On the right, the whole decoder as blocks: three such checks give a1, a2 and a3, a block of XOR gates removes a1 x1 + a2 x2 + a3 x3 from the received word, and a majority over the eight remaining bits gives a0. A note under the majority gate says that a 2 to 2 tie is reported only by an extra tie detector, which is not drawn. the a1 check, gate by gate y0 y1 y2 y3 y4 y5 y6 y7 y0+y1 y2+y3 y4+y5 y6+y7 MAJ of 4 a1 a 2 to 2 tie is reported only by an extra detector the whole decoder, block by block y 8 a1 check a1 a2 check a2 a3 check a3 a1, a2, a3 12 XOR, 3 MAJ of 4 remove a1x1+a2x2+a3x3 XOR gates only y' MAJ of 8 a0
Figure 7. Reed's decoder for RM(1,3). One check is drawn in gates on the left, and the whole decoder as blocks on the right.

The fast transform decoder in Figure 8 is an array of butterflies followed by a max-finder. The sign map turns each bit into a 2-bit two's-complement number, 0 into 01 and 1 into 11. After stage ss the values lie between −2s-2^s and 2s2^s, which takes s+2s + 2 bits, so the width grows by one bit per stage, from 3 to 5 bits for m=3m = 3 and from 3 to 7 bits for m=5m = 5. A butterfly at stage ss first sign-extends its two inputs of s+1s + 1 bits to s+2s + 2 bits by copying the top bit. It then feeds them to an adder and a subtracter of s+2s + 2 full-adder cells each, the subtracter being an adder fed the inverted second input and a carry-in of 1, and it drops the carry out of the top cell. Keeping s+1s + 1 cells and taking that carry as the new bit fails at once, because 1+(−1)1 + (-1) is 01+1101 + 11, which gives 00 with a carry of 1, and the 3-bit word 100 reads as −4-4. Stage ss has 2m2^m adders and subtracters, so m=3m = 3 uses 24 of them built from 8⋅(3+4+5)=968 \cdot (3 + 4 + 5) = 96 cells, and m=5m = 5 uses 160 built from 32⋅(3+4+5+6+7)=80032 \cdot (3 + 4 + 5 + 6 + 7) = 800 cells. The script builds this array cell by cell and matches the exact transform on all 256 words of length 8, the 64 Mariner codewords and the seven-error word of Table 10. The max-finder is a tree of comparators on the magnitudes, 7 in 3 levels for m=3m = 3 and 31 in 5 levels for m=5m = 5, carrying the index and sign of the winner. The largest possible magnitude is 2m2^m, which is 8 in 4 bits for m=3m = 3 and 32 in 6 bits for m=5m = 5. Table 11 gathers the counts of this section for both codes.

A fast Hadamard transform decoder for the (32,6) code as blocks. The 32 received bits enter a sign map that turns 0 into +1 and 1 into -1. Five butterfly stages follow, pairing rows 16, 8, 4, 2 and 1 apart, each with 16 butterflies, and their outputs grow from 3 to 7 bits. A magnitude block takes the size and sign of each of the 32 correlations, and a max-finder of 31 comparators in 5 levels keeps the index and sign of the largest. The index gives a1 to a5 and the sign gives a0. butterfly array, 5 stages of 16 butterflies, 160 adders and subtracters y 32 sign map 0 to +1 1 to -1 stage 1 h = 16 out 3 bits stage 2 h = 8 out 4 bits stage 3 h = 4 out 5 bits stage 4 h = 2 out 6 bits stage 5 h = 1 out 7 bits T0 to T31 size and sign 32 sizes of 6 bits 32 sign bits max-finder 31 comparators in 5 levels keeps the index and the sign index w, 5 bits: a1 to a5 sign of Tw: a0 a butterfly sends a + b to row j and a - b to row j + h
Figure 8. A fast Hadamard transform decoder for the (32,6) code. The butterfly array grows one bit per stage, and the max-finder turns the winning index and sign into the six data bits.

Table 11. Gate and operation counts for the circuits of this section

CircuitRM(1,3)\mathrm{RM}(1, 3)RM(1,5)\mathrm{RM}(1, 5)
Parallel encoder, two-input XOR gates1280
Reed decoder, XOR gates in the top-degree check sums1280
Reed decoder, majority gates3 of 4 inputs, 1 of 85 of 16 inputs, 1 of 32
Reed decoder, XOR gates removing the degree-1 part1280
Fast transform, butterflies1280
Fast transform, adders and subtracters24160
Fast transform, full-adder cells96800
Fast transform, stage widths in bits3, 4, 53, 4, 5, 6, 7
Max-finder, comparators and levels7 in 331 in 5

Source: reproduced by ch26_reed_muller_codes.py.

12.Looking Ahead

Reed–Muller codes trade rate for distance in a strict pattern, and at long lengths that trade is poor. The first-order codes keep half the length as distance but carry only m+1m + 1 bits, and the high-order codes keep their rate while the distance falls to a few bits. Bounds on Codes asks how far any code can push the trade between nn, kk and dd, which places this family, and the Hamming and Golay codes before it, against hard limits.

Two threads continue elsewhere. Reed's check sums are majority-logic decoding at its simplest, and finite geometries give larger codes with the same kind of decoder. The fast transform works on soft values unchanged, which matters once a receiver stops deciding bits before it decodes. A full treatment of the family, with its automorphisms and weight enumerators, is in [5].

13.Worked Examples

Table 12. The fast Hadamard transform of y = 0111011000011011, stage by stage

StepPositions 0 to 15
Signs YY1,−1,−1,−1,1,−1,−1,1,1,1,1,−1,−1,1,−1,−11, -1, -1, -1, 1, -1, -1, 1, 1, 1, 1, -1, -1, 1, -1, -1
Stage 1, pairs 8 apart2,0,0,−2,0,0,−2,0,0,−2,−2,0,2,−2,0,22, 0, 0, -2, 0, 0, -2, 0, 0, -2, -2, 0, 2, -2, 0, 2
Stage 2, pairs 4 apart2,0,−2,−2,2,0,2,−2,2,−4,−2,2,−2,0,−2,−22, 0, -2, -2, 2, 0, 2, -2, 2, -4, -2, 2, -2, 0, -2, -2
Stage 3, pairs 2 apart0,−2,4,2,4,−2,0,2,0,−2,4,−6,−4,−2,0,20, -2, 4, 2, 4, -2, 0, 2, 0, -2, 4, -6, -4, -2, 0, 2
Stage 4, the correlations TT−2,2,6,2,2,6,2,−2,−2,2,−2,10,−6,−2,2,−2-2, 2, 6, 2, 2, 6, 2, -2, -2, 2, -2, 10, -6, -2, 2, -2

Source: reproduced by ch26_reed_muller_codes.py.

14.Exercises

References

  1. [1]Muller, David E. (1954). “Application of Boolean Algebra to Switching Circuit Design and to Error Detection.” Transactions of the IRE Professional Group on Electronic Computers, EC-3(3), pp. 6–12. doi:10.1109/IREPGELC.1954.6499441
  2. [2]Reed, Irving S. (1954). “A Class of Multiple-Error-Correcting Codes and the Decoding Scheme.” Transactions of the IRE Professional Group on Information Theory, 4(4), pp. 38–49. doi:10.1109/TIT.1954.1057465
  3. [3]Plotkin, Morris (1960). “Binary Codes with Specified Minimum Distance.” IRE Transactions on Information Theory, 6(4), pp. 445–450. doi:10.1109/TIT.1960.1057584
  4. [4]Tausworthe, Robert C. and Easterling, Mahlon F. and Spear, A. J. (1969). “A High-Rate Telemetry System for the Mariner Mars 1969 Mission.” JPL Technical Report 32-1354 (NASA-CR-100550), Jet Propulsion Laboratory. https://ntrs.nasa.gov/citations/19690012788
  5. [5]MacWilliams, F. Jessie and Sloane, Neil J. A. (1977). “The Theory of Error-Correcting Codes.” North-Holland. doi:10.1016/S0924-6509(08)X7030-8

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes