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 codewords with only 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 , and , 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 . They have eight settings, called points, and each point gets a number by reading its bits as a binary number with as the least significant bit and as the most significant,
Point 3 is therefore and point 6 is . Listing a function's values at points 0 through 7 in order gives an 8-bit word. The variable is 1 at the odd points, so its word is 01010101. The variable gives 00110011, 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 is the AND of the first two, 00010001. Figure 1 lists all eight products.
Now add words with XOR. The function has the word , of weight 4. Each sum with coefficients in 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, , and as rows,
Column of is a 1 on top of the three bits of . This code is . Adding the three products of two variables as rows gives a code of dimension 7, and adding 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 , so no power ever needs to appear, and has the same truth table as . Coefficients live in , so . A polynomial here is therefore a sum of distinct monomials, each a product of distinct variables, and variables have exactly 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 , is , whose word is .
The two-variable example generalizes. For a point , the factor equals 1 when and 0 otherwise, so the product
is 1 at and 0 at every other point.
Proof. Expanding Equation 2 and replacing each by turns into a Boolean polynomial. Any function satisfies , because both sides agree at every point, so every word of length is the truth table of some polynomial and the map from polynomials to words is onto. There are polynomials, one for each subset of the monomials, and 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 independent vectors in a space of dimension form a basis.
Reading the polynomial back from a truth table is the next job. Write for the point whose coordinates are 1 exactly at the positions in , so is point 3.
Proof. The monomial is 1 at exactly when , so . Substituting, the right side of Equation 3 is . A fixed appears once for each with , and there are such , since each element of outside may join or not. That count is odd only when , so every other coefficient cancels in pairs and the sum is .
The formula runs as a network of stages. Stage replaces the value at every point with by its XOR with the value at the point lower, the same point with cleared. After all stages, position holds the XOR over every point reached by clearing some of the 1 bits of , which is Equation 3. Each stage costs XORs, so the transform costs , which is 12 at . Table 1 runs it on the word of .
Table 1. The Möbius transform of the truth table of x3 + x1x2, one stage per variable
| Step | Positions 0 to 7 |
|---|---|
| Truth table | 00011110 |
| After the stage | 00011011 |
| After the stage | 00011001 |
| After the stage | 00011000 |
Source: reproduced by ch26_reed_muller_codes.py.
The two 1s sit at positions 3 and 4. Position 3 is the subset and position 4 is , so the polynomial is , as it should be. Run in the other direction, the relation 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 forces the number of to be at most that of , 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 . Each row fixes , and the two columns give and , which are complements of each other.
Table 2. The sixteen codewords of RM(1,3)
| Linear part | |||
|---|---|---|---|
| 000 | 00000000 | 11111111 | |
| 100 | 01010101 | 10101010 | |
| 010 | 00110011 | 11001100 | |
| 110 | 01100110 | 10011001 | |
| 001 | 00001111 | 11110000 | |
| 101 | 01011010 | 10100101 | |
| 011 | 00111100 | 11000011 | |
| 111 | 01101001 | 10010110 |
Source: reproduced by ch26_reed_muller_codes.py.
Proof. The monomials of degree at most are part of the basis of the theorem on monomials, so their truth tables are independent and span . The dimension is the number of such monomials, which is the number of subsets of with at most elements.
Table 3. Dimension k of RM(r,m) for r = 0 to m
| for | ||
|---|---|---|
| 1 | 2 | 1, 2 |
| 2 | 4 | 1, 3, 4 |
| 3 | 8 | 1, 4, 7, 8 |
| 4 | 16 | 1, 5, 11, 15, 16 |
| 5 | 32 | 1, 6, 16, 26, 31, 32 |
| 6 | 64 | 1, 7, 22, 42, 57, 63, 64 |
| 7 | 128 | 1, 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 is , the entries for and , 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 , the dimension is , so the code is the whole space. For , the monomial is 1 at the points where every variable in is 1, an even number when . Since , a sum of even-weight words has even weight, so every codeword has even weight. The code's dimension is , the same as the even-weight code's, and a subspace of the same dimension is the whole space.
For the four codes are , , and , with the minimum distances proved two sections ahead.
04.The Recursive Structure
Take with . On the first eight points and reduces to , whose 3-variable word is . On the last eight points , so is plus 1, and its word there is with , the word of the constant 1. The codeword is , of weight 8. Every polynomial splits this way.
Proof. Collect the monomials of that contain and factor it out. What remains is , and the cofactor is , which lost one variable and so has degree at most . The split is unique because the monomials are a basis. By Equation 1, the first points have and list the points of variables in order, so there and the word is . The last points have and repeat the same order, so there and the word is with . Every pair with the stated degrees arises, so every pair does.
In matrix form, with the generator matrix,
For the top block repeats the four rows of twice, and the bottom block adds one row, , the word of . The count of rows also explains the Pascal pattern, . Figure 2 draws the recursion as a lattice in which every code is fed by two codes of half its length.
This is the construction of Modifying and Combining Codes, due to Plotkin [3], applied over and over. The same 2-by-2 pattern, which sends a pair to , 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 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 . The base cases are the two ends of every row. For the code is the repetition code, with , and for it is the whole space, with . These settle entirely. For and , Equation 7 builds the code from and , whose distances are and by the induction hypothesis. The theorem on the construction in Modifying and Combining Codes gives the distance as the smaller of twice the first and once the second, so .
The monomial shows the bound in one word. It is 1 exactly where its variables are 1, which happens at points. By the rule of Distance, Detection and Correction, a code of distance with corrects up to errors, which is 1 for and , 3 for , and , and 7 for the Mariner code . 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 , and finds these distances in all of them. It gets the weights of and from those of and , 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
| Code | |||
|---|---|---|---|
| 8 | 4 | 4 | |
| 16 | 5 | 8 | |
| 16 | 11 | 4 | |
| 32 | 6 | 16 | |
| 32 | 16 | 8 | |
| 32 | 26 | 4 | |
| 32 | 31 | 2 | |
| 128 | 8 | 64 | |
| 128 | 29 | 32 |
Source: reproduced by ch26_reed_muller_codes.py.
06.First-Order Codes and Their Weights
Every nonzero word of in Table 2 other than 11111111 has weight exactly 4. A simple counting fact is behind this.
Proof. Pick an with and pair each point with the point that differs from it only in . Every term of is the same at the two points except , so takes different values on them. Each of the pairs therefore holds exactly one point where .
Proof. The constants 0 and 1 give the first two words. The other polynomials have some with , and the lemma gives each one weight .
For that is 14 words of weight 4, 30 of weight 8 and 62 of weight 16, and for it is 126 words of weight 32. The script counts all four distributions directly. The words with , with position 0 deleted, have as generator the rows at the points 1 to , whose columns are every nonzero -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 code has weight 4.
07.Duality
The dimensions in Table 3 pair up. In each row, for order and for order add to , as in for . That is the signature of a code and its dual.
Proof. Take of degree at most and of degree at most . The inner product of their words counts, modulo 2, the points where both are 1, which is the weight of the word of . The product has degree at most , so its word lies in , which has only even weights, and the inner product is 0. So . The dimensions are and , which add to . By the theorem in Vector Spaces over Finite Fields that a code and its dual fill the length, the dual has dimension , the same as the subspace inside it, so the two are equal.
Proof. By Equation 9, is the dual of , whose generator matrix has a 1 above the bits of in column . 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 , the order equals 1.
The script puts all 16 words of and all 2048 words of through both checks of the extended Hamming code, even overall parity and a zero syndrome, and the equal dimensions do the rest. So is the extended Hamming code, and is the extended code whose decoder Hamming Codes and Perfect Codes built to correct one error and detect two. The dual of the Mariner code is , a code.
08.Reed's Majority-Logic Decoder
Syndrome Decoding and the Standard Array would decode 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)
| Coefficient | Pairs of points | Sums | Vote |
|---|---|---|---|
| 0 and 1, 2 and 3, 4 and 5, 6 and 7 | 0010 | 0 | |
| 0 and 2, 1 and 3, 4 and 6, 5 and 7 | 1110 | 1 | |
| 0 and 4, 1 and 5, 2 and 6, 3 and 7 | 1011 | 1 |
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 are the four edges parallel to axis , and an error at one corner touches only one edge in each direction.
For higher orders the edges become larger faces. A subcube for a set of variables is the set of points where the variables outside are held at a fixed pattern and the variables in run free. For in four variables, the subcubes are the points 0 to 3, 4 to 7, 8 to 11 and 12 to 15. There are of them, and they are disjoint and cover every point.
Proof. The monomial is 1 at a point of when every variable in is 1. A variable of outside is fixed on , so it must be 1 in the pattern , and the variables of outside are free. The number of points of where is therefore , which is odd only if is empty, that is, . With that forces , and then the count is 1.
So for a codeword of degree at most with errors , every subcube for an -set gives
The script checks the lemma on all 3,880 combinations of from 1 to 5, set, subcube and monomial. Reed's decoder for now runs in stages from degree down to 0. At stage , each monomial of degree gets disjoint check sums, each over a subcube of points, and the majority of those sums gives . The decided degree- part is then removed from , leaving a word of degree at most plus the same errors, and the next stage begins. The last stage takes the majority of all remaining bits.
Table 6. Degree-2 check sums of Reed's decoder for RM(2,4), with an error at position 10
| Monomial | Subcubes | Sums | Vote |
|---|---|---|---|
| , , , | 1101 | 1 | |
| , , , | 0001 | 0 | |
| , , , | 0100 | 0 | |
| , , , | 1101 | 1 | |
| , , , | 1000 | 0 | |
| , , , | 1101 | 1 |
Source: reproduced by ch26_reed_muller_codes.py.
Proof. Suppose errors and that every stage above decided correctly. Then the word entering stage is a codeword of degree at most plus the original errors, and Equation 10 holds for every check sum. The subcubes for one monomial are disjoint, so each error spoils at most one sum, and at most of the votes are wrong. Since , the bound leaves a strict majority correct, so stage decides correctly too. The stage with the fewest votes, , is , and that is where the bound binds. By induction every stage is correct, down to the final vote over all bits.
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 , write and for the parts of the current word coming from and from . Each check sum of is the coefficient of XORed with the same sum taken on . Flipping every input of a vote by the same bit flips its result and preserves a tie, so the decision on is XORed with the decision on alone. Removing the decided part therefore leaves , with exactly what decoding alone would leave. At the end the decoded coefficients are those of plus those decoded from .
The lemma means a pattern can be tested on the zero codeword alone. Table 7 lists what the script ran. For , and it decoded every correctable pattern added to every codeword. For 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
| Code | Error patterns | Decodings | Wrong |
|---|---|---|---|
| , all codewords, weight 0 to 1 | 9 | 144 | 0 |
| , all codewords, weight 0 to 3 | 697 | 22,304 | 0 |
| , all codewords, weight 0 to 1 | 17 | 34,816 | 0 |
| , zero codeword, weight 0 to 7 | 4,514,873 | 4,514,873 | 0 |
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 it costs far less than comparing against all codewords one at a time. The trick is to change the alphabet. Map each bit to , so 0 becomes and 1 becomes , 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 .
The bits of name a linear part. With the bit of in place , the number is the value of at point .
Proof. The codeword's sign at point is , so the sum of the products of its signs with is . Each agreement adds 1 to that sum and each disagreement subtracts 1, so the sum equals . Solving gives Equation 12. Agreement is largest when is largest, which means the largest with the sign of matching that of .
Computing each separately takes additions, so all of them take , roughly . The signs form a matrix with a structure that removes most of that work. For , the rows for are , , and , and the bottom-right 2-by-2 block is the negative of the others.
Proof. Induction on , with itself as the case . Split and into their top bits , and the rest, and . Then . The top bit selects the block, and the factor is only for the bottom-right block, while the second factor is the entry of by the induction hypothesis. That is Equation 13.
The script confirms , and entry by entry. Splitting into its halves and , the blocks of Equation 13 say that the first half of is and the second half is . This is the same split as the code itself, now in arithmetic.
Proof. Forming and takes operations, and then two transforms of half the size follow, so , with for the single pair , . Then , and if , then .
Table 8. Operations to compute all 2^m correlations, fast against direct
| Fast, | Direct, | |
|---|---|---|
| 2 | 8 | 12 |
| 3 | 24 | 56 |
| 4 | 64 | 240 |
| 5 | 160 | 992 |
| 10 | 10,240 | 1,047,552 |
Source: reproduced by ch26_reed_muller_codes.py.
Table 8 sets the two counts side by side for a few values of . At the fast transform is 102.3 times cheaper, and Figure 4 shows the gap widening with .
Unrolled, the halving becomes stages. Stage 1 pairs positions apart, stage 2 pairs positions 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 butterflies and needs 12. Figure 5 draws them for the received word of Reed's example, and Table 9 lists every intermediate value.
Table 9. The fast Hadamard transform of y = 11000111, stage by stage
| Step | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| Signs | ||||||||
| Stage 1, pairs 4 apart | ||||||||
| Stage 2, pairs 2 apart | ||||||||
| Stage 3, the correlations |
Source: reproduced by ch26_reed_muller_codes.py.
The largest magnitude is . Position 6 is binary 110, so , and , and the negative sign gives . The decoded word is that of , the codeword sent, with agreement 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 in positions, so Equation 12 gives . For , the codeword of differs from the sent one in a nonconstant first-order word, which has weight by the lemma on half the points. Changing bits moves the distance from to by at most , so it lies between and , and the agreement lies in the same range. Then Equation 12 gives . When , the correct magnitude exceeds , because .
Table 10. The 32 correlations of the Mariner example with seven errors
| Patterns | Correlations |
|---|---|
| 0 to 7 | |
| 8 to 15 | |
| 16 to 23 | |
| 24 to 31 |
Source: reproduced by ch26_reed_muller_codes.py.
The radius equals Reed's radius for , 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 to be , 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 , a code of rate , 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 that happens with probability
At 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 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 is plus the coefficients of the monomials that are 1 at point , so a parallel encoder is one XOR tree per output bit. For , bit needs as many two-input XOR gates as 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 and 56 for . A serial encoder trades gates for time. A 3-bit counter steps through the points, three AND gates form , and , and three XOR gates add them to , one codeword bit per clock, as Figure 6 shows.
Reed's decoder maps onto XOR trees and majority gates. Each check sum over points is an XOR tree of gates, and each vote is a majority gate over sums. For that means three checks of four XOR gates each, three majority gates of 4 inputs, a block of 12 XOR gates that removes from the received word, and one majority gate of 8 inputs for . 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 , which also needs five majority gates of 16 inputs and one of 32, and 72 for .
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 the values lie between and , which takes bits, so the width grows by one bit per stage, from 3 to 5 bits for and from 3 to 7 bits for . A butterfly at stage first sign-extends its two inputs of bits to bits by copying the top bit. It then feeds them to an adder and a subtracter of 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 cells and taking that carry as the new bit fails at once, because is , which gives 00 with a carry of 1, and the 3-bit word 100 reads as . Stage has adders and subtracters, so uses 24 of them built from cells, and uses 160 built from 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 and 31 in 5 levels for , carrying the index and sign of the winner. The largest possible magnitude is , which is 8 in 4 bits for and 32 in 6 bits for . Table 11 gathers the counts of this section for both codes.
Table 11. Gate and operation counts for the circuits of this section
| Circuit | ||
|---|---|---|
| Parallel encoder, two-input XOR gates | 12 | 80 |
| Reed decoder, XOR gates in the top-degree check sums | 12 | 80 |
| Reed decoder, majority gates | 3 of 4 inputs, 1 of 8 | 5 of 16 inputs, 1 of 32 |
| Reed decoder, XOR gates removing the degree-1 part | 12 | 80 |
| Fast transform, butterflies | 12 | 80 |
| Fast transform, adders and subtracters | 24 | 160 |
| Fast transform, full-adder cells | 96 | 800 |
| Fast transform, stage widths in bits | 3, 4, 5 | 3, 4, 5, 6, 7 |
| Max-finder, comparators and levels | 7 in 3 | 31 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 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 , and , 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
| Step | Positions 0 to 15 |
|---|---|
| Signs | |
| Stage 1, pairs 8 apart | |
| Stage 2, pairs 4 apart | |
| Stage 3, pairs 2 apart | |
| Stage 4, the correlations |
Source: reproduced by ch26_reed_muller_codes.py.
14.Exercises
References
- [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]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]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]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]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.