Reed–Muller code explained

Reed-Muller code RM(r,m)
Namesake:	Irving S. Reed and David E. Muller
Type:	Linear block code
Block Length:	2 ^{m}
Message Length:	k = \sum ^{r} _{i =0} \binom{m}{i}
Rate:	k/ 2 ^{m}
Distance:	2 ^{m-r}
Alphabet Size:	2
Notation:	[ 2 ^{m,k,2} ^{m-r} ] _{2} -code

Reed–Muller codes are error-correcting codes that are used in wireless communications applications, particularly in deep-space communication.^[1] Moreover, the proposed 5G standard^[2] relies on the closely related polar codes^[3] for error correction in the control channel. Due to their favorable theoretical and mathematical properties, Reed–Muller codes have also been extensively studied in theoretical computer science.

Reed–Muller codes generalize the Reed–Solomon codes and the Walsh–Hadamard code. Reed–Muller codes are linear block codes that are locally testable, locally decodable, and list decodable. These properties make them particularly useful in the design of probabilistically checkable proofs.

Traditional Reed–Muller codes are binary codes, which means that messages and codewords are binary strings. When r and m are integers with 0 ≤ r ≤ m, the Reed–Muller code with parameters r and m is denoted as RM(r, m). When asked to encode a message consisting of k bits, where

style k = \sum ^{r} _{i =0} \binom{m}{i} holds, the RM(r, m) code produces a codeword consisting of 2^m bits.

Reed–Muller codes are named after David E. Muller, who discovered the codes in 1954,^[4] and Irving S. Reed, who proposed the first efficient decoding algorithm.^[5]

Description using low-degree polynomials

Reed–Muller codes can be described in several different (but ultimately equivalent) ways. The description that is based on low-degree polynomials is quite elegant and particularly suited for their application as locally testable codes and locally decodable codes.^[6]

Encoder

style k = \sum ^{r} _{i =0} \binom{m}{i} and block length style n =2 ^{m} . One way to define an encoding for this code is based on the evaluation of multilinear polynomials with m variables and total degree at most r. Every multilinear polynomial over the finite field with two elements can be written as follows:$$p\_c(Z\_1,\backslash dots,Z\_m)\; =\; \backslash sum\_\; c\_S\backslash cdot\; \backslash prod\_\; Z\_i\backslash ,.$$The $Z\_1,\backslash dots,Z\_m$ are the variables of the polynomial, and the values $c\_S\backslash in\backslash$ are the coefficients of the polynomial. Note that there are exactly $k=\backslash sum\_^r\; \backslash binom$ coefficients. With this in mind, an input message consists of $k$ values $x\backslash in\backslash ^k$ which are used as these coefficients. In this way, each message $x$ gives rise to a unique polynomial $p\_x$ in m variables. To construct the codeword $C(x)$, the encoder evaluates the polynomial $p\_x$ at all points $Z=(Z\_1,\backslash ldots,Z\_n)\backslash in\backslash ^m$, where the polynomial is taken with multiplication and addition mod 2 $(p\_x(Z)\backslash bmod\; 2)\; \backslash in\; \backslash$. That is, the encoding function is defined via$$C(x)\; =\; \backslash left(p\_x(Z)\backslash bmod\; 2\backslash right)\_\backslash ,.$$

The fact that the codeword

C(x) suffices to uniquely reconstruct x follows from Lagrange interpolation, which states that the coefficients of a polynomial are uniquely determined when sufficiently many evaluation points are given. Since C( 0 ) =0 and C(x + y) = C(x) + C(y) \bmod 2 holds for all messages x,y\in\{ 0 , 1 \} ^{k} , the function C is a linear map. Thus the Reed - Muller code is a linear code.

Example

For the code, the parameters are as follows:

Let $C:\backslash ^\backslash to\backslash ^$ be the encoding function just defined. To encode the string x = 1 1010 010101 of length 11, the encoder first constructs the polynomial $p\_x$ in 4 variables:Then it evaluates this polynomial at all 16 evaluation points (0101 means

Z _{1=0,} Z _{2=1,} Z _{3=0,} Z _{4=1)} :$$p\_x(0000)=\; 1,\backslash ;p\_x(0001)=\; 1,\backslash ;p\_x(0010)=\; 0,\backslash ;p\_x(0011)=\; 1,\backslash ;$$

$$p\_x(0100)=\; 1,\backslash ;p\_x(0101)=\; 1,\backslash ;p\_x(0110)=\; 1,\backslash ;p\_x(0111)=\; 0,\backslash ;$$

$$p\_x(1000)=\; 0,\backslash ;p\_x(1001)=\; 0,\backslash ;p\_x(1010)=\; 0,\backslash ;p\_x(1011)=\; 1,\backslash ;$$

$$p\_x(1100)=\; 0,\backslash ;p\_x(1101)=\; 0,\backslash ;p\_x(1110)=\; 1,\backslash ;p\_x(1111)=\; 0\backslash ,.$$As a result, C(1 1010 010101) = 1101 1110 0001 0010 holds.

Decoder

As was already mentioned, Lagrange interpolation can be used to efficiently retrieve the message from a codeword. However, a decoder needs to work even if the codeword has been corrupted in a few positions, that is, when the received word is different from any codeword. In this case, a local decoding procedure can help.

The algorithm from Reed is based on the following property:you start from the code word, that is a sequence of evaluation points from an unknown polynomial $p\_x$ of $\_2[X\_1,X\_2,...,X\_m]$ of degree at most $r$ that you want to find. The sequence may contains any number of errors up to $2^-1$ included.

If you consider a monomial $\backslash mu$ of the highest degree $d$ in $p\_x$ and sum all the evaluation points of the polynomial where all variables in $\backslash mu$ have the values 0 or 1, and all the other variables have value 0, you get the value of the coefficient (0 or 1) of $\backslash mu$ in $p\_x$ (There are $2^d$ such points). This is due to the fact that all lower monomial divisors of $\backslash mu$ appears an even number of time in the sum, and only $\backslash mu$ appears once.

To take into account the possibility of errors, you can also remark that you can fix the value of other variables to any value. So instead of doing the sum only once for other variables not in $\backslash mu$ with 0 value, you do it $2^$ times for each fixed valuations of the other variables. If there is no error, all those sums should be equals to the value of the coefficient searched. The algorithm consists here to take the majority of the answers as the value searched. If the minority is larger than the maximum number of errors possible, the decoding step fails knowing there are too many errors in the input code.

Once a coefficient is computed, if it's 1, update the code to remove the monomial $\backslash mu$ from the input code and continue to next monomial, in reverse order of their degree.

Example

Let's consider the previous example and start from the code. With $r=2,\; m=4$ we can fix at most 1 error in the code.Consider the input code as 1101 1110 0001 0110 (this is the previous code with one error).

We know the degree of the polynomial $p\_x$ is at most $r=2$, we start by searching for monomial of degree 2.

• $\backslash mu=X\_3X\_4$
  • we start by looking for evaluation points with $X\_1=0,\; X\_2=0,\; X\_3\backslash in\backslash ,\; X\_4\backslash in\backslash$. In the code this is: 1101 1110 0001 0110. The first sum is 1 (odd number of 1).
  • we look for evaluation points with $X\_1=0,\; X\_2=1,\; X\_3\backslash in\backslash ,\; X\_4\backslash in\backslash$. In the code this is: 1101 1110 0001 0110. The second sum is 1.
  • we look for evaluation points with $X\_1=1,\; X\_2=0,\; X\_3\backslash in\backslash ,\; X\_4\backslash in\backslash$. In the code this is: 1101 1110 0001 0110. The third sum is 1.
  • we look for evaluation points with $X\_1=1,\; X\_2=1,\; X\_3\backslash in\backslash ,\; X\_4\backslash in\backslash$. In the code this is: 1101 1110 0001 0110. The third sum is 0 (even number of 1).

The four sums don't agree (so we know there is an error), but the minority report is not larger than the maximum number of error allowed (1), so we take the majority and the coefficient of $\backslash mu$ is 1.

We remove $\backslash mu$ from the code before continue : code : 1101 1110 0001 0110, valuation of $\backslash mu$ is 0001000100010001, the new code is 1100 1111 0000 0111

• $\backslash mu=X\_2X\_4$
  • 1100 1111 0000 0111. Sum is 0
  • 1100 1111 0000 0111. Sum is 0
  • 1100 1111 0000 0111. Sum is 1
  • 1100 1111 0000 0111. Sum is 0

One error detected, coefficient is 0, no change to current code.

• $\backslash mu=X\_1X\_4$
  • 1100 1111 0000 0111. Sum is 0
  • 1100 1111 0000 0111. Sum is 0
  • 1100 1111 0000 0111. Sum is 1
  • 1100 1111 0000 0111. Sum is 0

One error detected, coefficient is 0, no change to current code.

• $\backslash mu=X\_2X\_3$
  • 1100 1111 0000 0111. Sum is 1
  • 1100 1111 0000 0111. Sum is 1
  • 1100 1111 0000 0111. Sum is 1
  • 1100 1111 0000 0111. Sum is 0

One error detected, coefficient is 1, valuation of $\backslash mu$ is 0000 0011 0000 0011, current code is now 1100 1100 0000 0100.

• $\backslash mu=X\_1X\_3$
  • 1100 1100 0000 0100. Sum is 1
  • 1100 1100 0000 0100. Sum is 1
  • 1100 1100 0000 0100. Sum is 1
  • 1100 1100 0000 0100. Sum is 0

One error detected, coefficient is 1, valuation of $\backslash mu$ is 0000 0000 0011 0011, current code is now 1100 1100 0011 0111.

• $\backslash mu=X\_1X\_2$
  • 1100 1100 0011 0111. Sum is 0
  • 1100 1100 0011 0111. Sum is 1
  • 1100 1100 0011 0111. Sum is 0
  • 1100 1100 0011 0111. Sum is 0

One error detected, coefficient is 0, no change to current code.We know now all coefficient of degree 2 for the polynomial, we can start mononials of degree 1. Notice that for each next degree, there are twice as much sums, and each sums is half smaller.

• $\backslash mu=X\_4$
  • 1100 1100 0011 0111. Sum is 0
  • 1100 1100 0011 0111. Sum is 0
  • 1100 1100 0011 0111. Sum is 0
  • 1100 1100 0011 0111. Sum is 0
  • 1100 1100 0011 0111. Sum is 0
  • 1100 1100 0011 0111. Sum is 0
  • 1100 1100 0011 0111. Sum is 1
  • 1100 1100 0011 0111. Sum is 0

One error detected, coefficient is 0, no change to current code.

• $\backslash mu=X\_3$
  • 1100 1100 0011 0111. Sum is 1
  • 1100 1100 0011 0111. Sum is 1
  • 1100 1100 0011 0111. Sum is 1
  • 1100 1100 0011 0111. Sum is 1
  • 1100 1100 0011 0111. Sum is 1
  • 1100 1100 0011 0111. Sum is 1
  • 1100 1100 0011 0111. Sum is 1
  • 1100 1100 0011 0111. Sum is 0

One error detected, coefficient is 1, valuation of $\backslash mu$ is 0011 0011 0011 0011, current code is now 1111 1111 0000 0100.

Then we'll find 0 for $\backslash mu=X\_2$, 1 for $\backslash mu=X\_1$ and the current code become 1111 1111 1111 1011.

For the degree 0, we have 16 sums of only 1 bit. The minority is still of size 1, and we found $p\_x=1+X\_1+X\_3+X\_1X\_3+X\_2X\_3+X\_3X\_4$ and the corresponding initial word 1 1010 010101

Generalization to larger alphabets via low-degree polynomials

Using low-degree polynomials over a finite field

F of size q , it is possible to extend the definition of Reed - Muller codes to alphabets of size q . Let m and d be positive integers, where m should be thought of as larger than d . To encode a message $x\backslash in\backslash mathbb\; F^k$ of width k = style\binom{m+d}{m} , the message is again interpreted as an m -variate polynomial p _{x} of total degree at most d and with coefficient from F . Such a polynomial indeed has style\binom{m+d}{m} coefficients. The Reed–Muller encoding of x is the list of all evaluations of p _{x(a)} over all a\in F ^{m} . Thus the block length is n = q ^{m} .

Description using a generator matrix

A generator matrix for a Reed - Muller code of length can be constructed as follows. Let us write the set of all m-dimensional binary vectors as:

X = F ^{m} _{2} = \{ x _{1,} \ldots, x _{N} \}.

We define in N-dimensional space

F ^{N} _{2} the indicator vectorsI _{A} \in F ^{N} _{2}

on subsets

A \subset X by:\left( I _{A} \right) _{i} = \begin{cases} 1 & if x _{i} \in A \ 0 & otherwise \ \end{cases}

together with, also in

F ^{N} _{2} , the binary operationw \wedge z = (w _{1} ⋅ z _{1,} \ldots , w _{N} ⋅ z _{N} ),

referred to as the wedge product (not to be confused with the wedge product defined in exterior algebra). Here,

w = (w _{1,w} _{2,\ldots,w} _{N)} and z = (z _{1,z} _{2,\ldots,} z _{N)} are points in F ^{N} _{2} (N-dimensional binary vectors), and the operation ⋅ is the usual multiplication in the field F _{2} .F ^{m} _{2} is an m-dimensional vector space over the field F _{2} , so it is possible to write( F ^{m} _{2 )} = \{ (y _{m,} \ldots , y _{1)} \mid y _{i} \in F _{2} \} .

We define in N-dimensional space

F ^{N} _{2} the following vectors with length N: v _{0} = ( 1 , 1 ,\ldots, 1 ) andv _{i} = I _{H _{i}} ,

where 1 ≤ i ≤ m and the H_i are hyperplanes in

( F ^{m} _{2 )} (with dimension):H _{i} = \{ y \in ( F _{2} ) ^{m} \mid y _{i} = 0 \} .

The generator matrix

The Reed - Muller code of order r and length N = 2^m is the code generated by v₀ and the wedge products of up to r of the v_i, (where by convention a wedge product of fewer than one vector is the identity for the operation). In other words, we can build a generator matrix for the code, using vectors and their wedge product permutations up to r at a time

{v _{0,} v _{1,} \ldots, v _{n,} \ldots, (v _{i _{1}} \wedge v _{i _{2}} ), \ldots (v _{i _{1}} \wedge v _{i _{2}} \ldots \wedge v _{i _{r}} )} , as the rows of the generator matrix, where .

Example 1

Let m = 3. Then N = 8, and

X = F ^{3} _{2} = \{ ( 0 , 0 , 0 ), ( 0 , 0 , 1 ), ( 0 , 1 , 0 ) \ldots, ( 1 , 1 , 1 ) \},

and

\begin{align} v _{0} & = ( 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ) \\[ 2 pt] v _{1} & = ( 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 ) \\[ 2 pt] v _{2} & = ( 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 ) \\[ 2 pt] v _{3} & = ( 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 ). \end{align}

The RM(1,3) code is generated by the set

\{ v _{0,} v _{1,} v _{2,} v _{3} \},

or more explicitly by the rows of the matrix:

\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}

Example 2

The RM(2,3) code is generated by the set:

\{ v _{0,} v _{1,} v _{2,} v _{3,} v _{1} \wedge v _{2,} v _{1} \wedge v _{3,} v _{2} \wedge v _{3} \}

or more explicitly by the rows of the matrix:

\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}

Properties

The following properties hold:

1. The set of all possible wedge products of up to m of the v_i form a basis for

F ^{N} _{2} .

1. The RM (r, m) code has rank

\sum ^{r} _{s =0} {m \choose s}.

1. where '|' denotes the bar product of two codes.
2. has minimum Hamming weight 2^{m - r}.

Proof

Decoding RM codes

RM(r, m) codes can be decoded using majority logic decoding. The basic idea of majority logic decoding isto build several checksums for each received code word element. Since each of the different checksums must allhave the same value (i.e. the value of the message word element weight), we can use a majority logic decoding to decipherthe value of the message word element. Once each order of the polynomial is decoded, the received word is modifiedaccordingly by removing the corresponding codewords weighted by the decoded message contributions, up to the present stage.So for a rth order RM code, we have to decode iteratively r+1, times before we arrive at the finalreceived code-word. Also, the values of the message bits are calculated through this scheme; finally we can calculatethe codeword by multiplying the message word (just decoded) with the generator matrix.

One clue if the decoding succeeded, is to have an all-zero modified received word, at the end of (r + 1)-stage decodingthrough the majority logic decoding. This technique was proposed by Irving S. Reed, and is more general when appliedto other finite geometry codes.

Description using a recursive construction

A Reed–Muller code RM(r,m) exists for any integers

m \ge 0 and 0 \le r \le m . RM(m, m) is defined as the universe (2 ^{m,2} ^{m,1} ) code. RM(-1,m) is defined as the trivial code (2 ^{m,0,infty} ). The remaining RM codes may be constructed from these elementary codes using the length-doubling constructionRM (r,m) = \{( u , u + v )\mid u \in RM (r,m -1 ), v \in RM (r -1 ,m -1 )\}.

From this construction, RM(r,m) is a binary linear block code (n, k, d) with length, dimension

k(r,m) = k(r,m -1 ) + k(r -1 ,m -1 ) and minimum distance d = 2 ^{m-r} for r \ge 0 . The dual code to RM(r,m) is RM(m-r-1,m). This shows that repetition and SPC codes are duals, biorthogonal and extended Hamming codes are duals and that codes with are self-dual.

Special cases of Reed - Muller codes

Table of all RM(r,m) codes for m≤5

All codes with

0 \le m\le 5 and alphabet size 2 are displayed here, annotated with the standard [n,k,d] coding theory notation for block codes. The code is a style [ 2 ^{m,k,2} ^{m-r} ] _{2} -code, that is, it is a linear code over a binary alphabet, has block length style 2 ^{m} , message length (or dimension), and minimum distance style 2 ^{m-r} .

0	1	2	3	4	5	m
						(1)	universe codes
					RM(5,5) (32,32,1)
				RM(4,4) (16,16,1)			SPC codes
			RM(3,3) (8,8,1)		RM(4,5) (32,31,2)
		RM(2,2) (4,4,1)		RM(3,4) (16,15,2)			extended Hamming codes
	RM(1,1) (2,2,1)		RM(2,3) (8,7,2)		RM(3,5) (32,26,4)
RM(0,0) (1,1,1)		RM(1,2) (4,3,2)		RM(2,4) (16,11,4)
	RM(0,1) (2,1,2)		RM(1,3) (8,4,4)		RM(2,5) (32,16,8)		self-dual codes
RM(-1,0) (1,0,inf ty )		RM(0,2) (4,1,4)		RM(1,4) (16,5,8)
	RM(−1,1) (2,0,inf ty )		RM(0,3) (8,1,8)		RM(1,5) (32,6,16)
		RM(−1,2) (4,0,inf ty )		RM(0,4) (16,1,16)			punctured Hadamard codes
			RM(-1,3) (8,0,inf ty )		RM(0,5) (32,1,32)
				RM(-1,4) (16,0,inf ty )			repetition codes
					RM(-1,5) (32,0,inf ty )
							trivial codes

Properties of RM(r,m) codes for r≤1 or r≥m-1

{R = \tfrac{ 1 }{N}} and minimum distance d _{min} = N .

• codes are parity check codes of length, rate

R = \tfrac{m +1 }{N} and minimum distance d _{min} = \tfrac{N}{ 2 } .

• codes are single parity check codes of length, rate

R = \tfrac{N -1 }{N} and minimum distance d _{min} = 2 .

• codes are the family of extended Hamming codes of length with minimum distance

d _{min} = 4 .^[7]

Further reading

• Book: Shu Lin . Daniel Costello . Error Control Coding . 2 . 2005 . Pearson . 978-0-13-017973-9 . Chapter 4.
• Book: J.H. van Lint . Introduction to Coding Theory . 2 . . . 86 . 1992 . 978-3-540-54894-2 . registration . Chapter 4.5.

External links

• MIT OpenCourseWare, 6.451 Principles of Digital Communication II, Lecture Notes section 6.4
• GPL Matlab-implementation of RM-codes
• Source GPL Matlab-implementation of RM-codes
• Weiss . E. . Generalized Reed-Muller codes . Information and Control . September 1962 . 5 . 3 . 213–222 . 10.1016/s0019-9958(62)90555-7 . 0019-9958.

Notes and References

1. pdf
2. Web site: 3GPP RAN1 meeting #87 final report. 3GPP. 31 August 2017.
3. Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels - IEEE Journals & Magazine. IEEE Transactions on Information Theory. 55. 7. 3051–3073. en-US. 10.1109/TIT.2009.2021379. 2009. Arikan. Erdal. 11693/11695. 0807.3917. 889822 .
4. Muller. David E.. 1954. Application of Boolean algebra to switching circuit design and to error detection. Transactions of the I.R.E. Professional Group on Electronic Computers. en-US. EC-3. 3. 6–12. 10.1109/irepgelc.1954.6499441. 2168-1740.
5. Reed. Irving S.. 1954. A class of multiple-error-correcting codes and the decoding scheme. Transactions of the IRE Professional Group on Information Theory. en-US. 4. 4. 38–49. 10.1109/tit.1954.1057465. 2168-2690. 10338.dmlcz/143797. free.
6. Prahladh Harsha et al., Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes), Section 5.2.1.
7. Trellis and Turbo Coding, C. Schlegel & L. Perez, Wiley Interscience, 2004, p149.