Reed–Muller 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 code RM(r,m)
Named after	Irving S. Reed and David E. Muller
Classification
Type	Linear block code
Block length	${\displaystyle 2^{m}}$
Message length	${\displaystyle k=\sum _{i=0}^{r}{\binom {m}{i}}}$
Rate	${\displaystyle k/2^{m}}$
Distance	${\displaystyle 2^{m-r}}$
Alphabet size	${\displaystyle 2}$
Notation	${\displaystyle [2^{m},k,2^{m-r}]_{2}}$-code

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 ${\displaystyle \textstyle k=\sum _{i=0}^{r}{\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

A block code can have one or more encoding functions ${\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$ that map messages ${\textstyle x\in \{0,1\}^{k}}$ to codewords ${\textstyle C(x)\in \{0,1\}^{n}}$. The Reed–Muller code RM(r, m) has message length ${\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}$ and block length ${\displaystyle \textstyle 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 r. Every multilinear polynomial over the finite field with two elements can be written as follows:

$${\displaystyle p_{c}(Z_{1},\dots ,Z_{m})=\sum _{\underset {|S|\leq r}{S\subseteq \{1,\dots ,m\}}}c_{S}\cdot \prod _{i\in S}Z_{i}\,.}$$

The ${\textstyle Z_{1},\dots ,Z_{m}}$ are the variables of the polynomial, and the values ${\textstyle c_{S}\in \{0,1\}}$ are the coefficients of the polynomial. Since there are exactly ${\textstyle k}$ coefficients, the message ${\textstyle x\in \{0,1\}^{k}}$ consists of ${\textstyle k}$ values that can be used as these coefficients. In this way, each message ${\textstyle x}$ gives rise to a unique polynomial ${\textstyle p_{x}}$ in m variables. To construct the codeword ${\textstyle C(x)}$, the encoder evaluates ${\textstyle p_{x}}$ at all evaluation points ${\textstyle a\in \{0,1\}^{m}}$, where it interprets the sum as addition modulo two in order to obtain a bit ${\textstyle (p_{x}(a){\bmod {2}})\in \{0,1\}}$. That is, the encoding function is defined via

$${\displaystyle C(x)=\left(p_{x}(a){\bmod {2}}\right)_{a\in \{0,1\}^{m}}\,.}$$

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

Example

For the code RM(2, 4), the parameters are as follows:

${\textstyle {\begin{aligned}r&=2\\m&=4\\k&=\textstyle {\binom {4}{2}}+{\binom {4}{1}}+{\binom {4}{0}}=6+4+1=11\\n&=2^{m}=16\\\end{aligned}}}$

Let ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ be the encoding function just defined. To encode the string x = 1 1010 010101 of length 11, the encoder first constructs the polynomial ${\textstyle p_{x}}$ in 4 variables:

$${\displaystyle {\begin{aligned}p_{x}(Z_{1},Z_{2},Z_{3},Z_{4})&=1+(1\cdot Z_{1}+0\cdot Z_{2}+1\cdot Z_{3}+0\cdot Z_{4})+(0\cdot Z_{1}Z_{2}+1\cdot Z_{1}Z_{3}+0\cdot Z_{1}Z_{4}+1\cdot Z_{2}Z_{3}+0\cdot Z_{2}Z_{4}+1\cdot Z_{3}Z_{4})\\&=1+Z_{1}+Z_{3}+Z_{1}Z_{3}+Z_{2}Z_{3}+Z_{3}Z_{4}\end{aligned}}}$$

Then it evaluates this polynomial at all 16 evaluation points:

$${\displaystyle p_{x}(0000)=1,\;p_{x}(0001)=1,\;p_{x}(0010)=1,\;p_{x}(0011)=1,\;p_{x}(0100)=1,\;p_{x}(0101)=0,\;p_{x}(0110)=1,\;p_{x}(0111)=0,\;p_{x}(1000)=0,\;p_{x}(1001)=1,\;p_{x}(1010)=0,\;p_{x}(1011)=1,\;p_{x}(1100)=0,\;p_{x}(1101)=0,\;p_{x}(1110)=0,\;p_{x}(1111)=0\,.}$$

As a result, C(1 1010 010101) = 1111 1010 0101 0000 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.

Generalization to larger alphabets via low-degree polynomials

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

Description using a generator matrix

A generator matrix for a Reed–Muller code RM(r, m) of length N = 2^m can be constructed as follows. Let us write the set of all m-dimensional binary vectors as:

${\displaystyle X=\mathbb {F} _{2}^{m}=\{x_{1},\ldots ,x_{N}\}.}$

We define in N-dimensional space ${\displaystyle \mathbb {F} _{2}^{N}}$ the indicator vectors

${\displaystyle \mathbb {I} _{A}\in \mathbb {F} _{2}^{N}}$

on subsets ${\displaystyle A\subset X}$ by:

${\displaystyle \left(\mathbb {I} _{A}\right)_{i}={\begin{cases}1&{\mbox{ if }}x_{i}\in A\\0&{\mbox{ otherwise}}\\\end{cases}}}$

together with, also in ${\displaystyle \mathbb {F} _{2}^{N}}$, the binary operation

${\displaystyle w\wedge z=(w_{1}\cdot z_{1},\ldots ,w_{N}\cdot z_{N}),}$

referred to as the wedge product (not to be confused with the wedge product defined in exterior algebra). Here, ${\displaystyle w=(w_{1},w_{2},\ldots ,w_{N})}$ and ${\displaystyle z=(z_{1},z_{2},\ldots ,z_{N})}$ are points in ${\displaystyle \mathbb {F} _{2}^{N}}$ (N-dimensional binary vectors), and the operation ${\displaystyle \cdot }$ is the usual multiplication in the field ${\displaystyle \mathbb {F} _{2}}$.

${\displaystyle \mathbb {F} _{2}^{m}}$ is an m-dimensional vector space over the field ${\displaystyle \mathbb {F} _{2}}$, so it is possible to write

${\displaystyle (\mathbb {F} _{2})^{m}=\{(y_{m},\ldots ,y_{1})\mid y_{i}\in \mathbb {F} _{2}\}.}$

We define in N-dimensional space ${\displaystyle \mathbb {F} _{2}^{N}}$ the following vectors with length ${\displaystyle N:v_{0}=(1,1,\ldots ,1)}$ and

${\displaystyle v_{i}=\mathbb {I} _{H_{i}},}$

where 1 ≤ i ≤ m and the H_i are hyperplanes in ${\displaystyle (\mathbb {F} _{2})^{m}}$ (with dimension m − 1):

${\displaystyle H_{i}=\{y\in (\mathbb {F} _{2})^{m}\mid y_{i}=0\}.}$

The generator matrix

The Reed–Muller RM(r, m) 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, 1 ≤ i ≤ m (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 RM(r, m) code, using vectors and their wedge product permutations up to r at a time ${\displaystyle {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 1 ≤ i_k ≤ m.

Example 1

Let m = 3. Then N = 8, and

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

and

${\displaystyle {\begin{aligned}v_{0}&=(1,1,1,1,1,1,1,1)\\[2pt]v_{1}&=(1,0,1,0,1,0,1,0)\\[2pt]v_{2}&=(1,1,0,0,1,1,0,0)\\[2pt]v_{3}&=(1,1,1,1,0,0,0,0).\end{aligned}}}$

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

${\displaystyle \{v_{0},v_{1},v_{2},v_{3}\},\,}$

or more explicitly by the rows of the matrix:

${\displaystyle {\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:

${\displaystyle \{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:

${\displaystyle {\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 ${\displaystyle \mathbb {F} _{2}^{N}}$.
2. The RM (r, m) code has rank

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

3. RM (r, m) = RM (r, m − 1) | RM (r − 1, m − 1) where '|' denotes the bar product of two codes.
4. RM (r, m) has minimum Hamming weight 2^{m − r}.

Proof

1. There are

   ${\displaystyle \sum _{s=0}^{m}{m \choose s}=2^{m}=N}$

   such vectors and ${\displaystyle \mathbb {F} _{2}^{N}}$ have dimension N so it is sufficient to check that the N vectors span; equivalently it is sufficient to check that ${\displaystyle \mathrm {RM} (m,m)=\mathbb {F} _{2}^{N}}$.

   Let x be a binary vector of length m, an element of X. Let (x)_i denote the i^th element of x. Define

   ${\displaystyle y_{i}={\begin{cases}v_{i}&{\text{ if }}(x)_{i}=0\\v_{0}+v_{i}&{\text{ if }}(x)_{i}=1\\\end{cases}}}$

   where 1 ≤ i ≤m.

   Then ${\displaystyle \mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}}$

   Expansion via the distributivity of the wedge product gives ${\displaystyle \mathbb {I} _{\{x\}}\in \mathrm {RM} (m,m)}$. Then since the vectors ${\displaystyle \{\mathbb {I} _{\{x\}}\mid x\in X\}}$ span ${\displaystyle \mathbb {F} _{2}^{N}}$ we have ${\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}}$.
2. By 1, all such wedge products must be linearly independent, so the rank of RM(r, m) must simply be the number of such vectors.
3. Omitted.
4. By induction.

   The RM(0, m) code is the repetition code of length N =2^m and weight N = 2^m−0 = 2^m−r. By 1 ${\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}}$ and has weight 1 = 2⁰ = 2^m−r.

   The article bar product (coding theory) gives a proof that the weight of the bar product of two codes C₁ , C₂ is given by

   ${\displaystyle \min\{2w(C_{1}),w(C_{2})\}}$

   If 0 < r < m and if

   1. RM(r,m − 1) has weight 2^m−1−r
   2. RM(r − 1,m − 1) has weight 2^{m−1−(r−1)} = 2^m−r

   then the bar product has weight

   ${\displaystyle \min\{2\times 2^{m-1-r},2^{m-r}\}=2^{m-r}.}$

Decoding RM codes

RM(r, m) codes can be decoded using majority logic decoding. The basic idea of majority logic decoding is to build several checksums for each received code word element. Since each of the different checksums must all have the same value (i.e. the value of the message word element weight), we can use a majority logic decoding to decipher the value of the message word element. Once each order of the polynomial is decoded, the received word is modified accordingly 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 final received code-word. Also, the values of the message bits are calculated through this scheme; finally we can calculate the 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 decoding through the majority logic decoding. This technique was proposed by Irving S. Reed, and is more general when applied to other finite geometry codes.

Description using a recursive construction

A Reed–Muller code RM(r,m) exists for any integers ${\displaystyle m\geq 0}$ and ${\displaystyle 0\leq r\leq m}$. RM(m, m) is defined as the universe (${\displaystyle 2^{m},2^{m},1}$) code. RM(−1,m) is defined as the trivial code (${\displaystyle 2^{m},0,\infty }$). The remaining RM codes may be constructed from these elementary codes using the length-doubling construction

${\displaystyle \mathrm {RM} (r,m)=\{(\mathbf {u} ,\mathbf {u} +\mathbf {v} )\mid \mathbf {u} \in \mathrm {RM} (r,m-1),\mathbf {v} \in \mathrm {RM} (r-1,m-1)\}.}$

From this construction, RM(r,m) is a binary linear block code (n, k, d) with length n = 2^m, dimension ${\displaystyle k(r,m)=k(r,m-1)+k(r-1,m-1)}$ and minimum distance ${\displaystyle d=2^{m-r}}$ for ${\displaystyle r\geq 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 k = n/2 are self-dual.

Special cases of Reed–Muller codes

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

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

						RM(m,m) (2^m, 2^m, 1)	universe codes
					RM(5,5) (32,32,1)
				RM(4,4) (16,16,1)		RM(m − 1, m) (2^m, 2^m−1, 2)	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)		RM(m − 2, m) (2^m, 2^m−m−1, 4)	ext. 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,${\displaystyle \infty }$)		RM(0,2) (4,1,4)		RM(1,4) (16,5,8)
	RM(−1,1) (2,0,${\displaystyle \infty }$)		RM(0,3) (8,1,8)		RM(1,5) (32,6,16)
		RM(−1,2) (4,0,${\displaystyle \infty }$)		RM(0,4) (16,1,16)		RM(1,m) (2^m, m+1, 2^m−1)	Punctured hadamard codes
			RM(−1,3) (8,0,${\displaystyle \infty }$)		RM(0,5) (32,1,32)
				RM(−1,4) (16,0,${\displaystyle \infty }$)		RM(0,m) (2^m, 1, 2^m)	repetition codes
					RM(−1,5) (32,0,${\displaystyle \infty }$)
						RM(−1,m) (2^m, 0, ∞)	trivial codes

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

• RM(0, m) codes are repetition codes of length N = 2^m, rate ${\displaystyle {R={\tfrac {1}{N}}}}$ and minimum distance ${\displaystyle d_{\min }=N}$.
• RM(1, m) codes are parity check codes of length N = 2^m, rate ${\displaystyle R={\tfrac {m+1}{N}}}$ and minimum distance ${\displaystyle d_{\min }={\tfrac {N}{2}}}$.
• RM(m − 1, m) codes are single parity check codes of length N = 2^m, rate ${\displaystyle R={\tfrac {N-1}{N}}}$ and minimum distance ${\displaystyle d_{\min }=2}$.
• RM(m − 2, m) codes are the family of extended Hamming codes of length N = 2^m with minimum distance ${\displaystyle d_{\min }=4}$.[7]

References

1. Massey, James L. (1992), "Deep-space communications and coding: A marriage made in heaven", Advanced Methods for Satellite and Deep Space Communications, Lecture Notes in Control and Information Sciences, 182, Springer-Verlag, pp. 1–17, CiteSeerX 10.1.1.36.4265, doi:10.1007/bfb0036046, ISBN 978-3540558514pdf
2. "3GPP RAN1 meeting #87 final report". 3GPP. Retrieved 31 August 2017.
3. Arikan, Erdal (2009). "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. arXiv:0807.3917. doi:10.1109/TIT.2009.2021379. hdl:11693/11695.
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. EC-3 (3): 6–12. doi:10.1109/irepgelc.1954.6499441. ISSN 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. 4 (4): 38–49. doi:10.1109/tit.1954.1057465. hdl:10338.dmlcz/143797. ISSN 2168-2690.
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.

Further reading

• Shu Lin; Daniel Costello (2005). Error Control Coding (2 ed.). Pearson. ISBN 978-0-13-017973-9. Chapter 4.
• J.H. van Lint (1992). Introduction to Coding Theory. GTM. 86 (2 ed.). Springer-Verlag. ISBN 978-3-540-54894-2. 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. (September 1962). "Generalized Reed-Muller codes". Information and Control. 5 (3): 213–222. doi:10.1016/s0019-9958(62)90555-7. ISSN 0019-9958.