Open main menu

Wikipedia β

Reed–Muller codes are a family of linear error-correcting codes used in communications. Reed–Muller codes belong to the classes of locally testable codes and locally decodable codes, which is why they are useful in the design of probabilistically checkable proofs in computational complexity theory. They are named after Irving S. Reed and David E. Muller. Muller discovered the codes, and Reed proposed the majority logic decoding for the first time. Special cases of Reed–Muller codes include the Walsh–Hadamard code and the Reed–Solomon code.

Reed-Muller code RM(r,m)
Named after Irving S. Reed and David E. Muller
Type Linear block code
Block length
Message length
Alphabet size
Notation -code

Reed–Muller codes are listed as RM(rm), where r is the order of the code, 0 ≤ rm, and m determines the block length N = 2m. RM codes are related to binary functions on the field GF(2m) over the elements {0, 1}.



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


We define in N-dimensional space   the indicator vectors


on subsets   by:


together with, also in  , the binary operation


referred to as the wedge product (this wedge product is not to be confused with the wedge product defined in exterior algebra). Here,   and   are points in   (N-dimensional binary vectors), and the operation   is the usual multiplication in the field  .

  is an m-dimensional vector space over the field  , so it is possible to write


We define in N-dimensional space   the following vectors with length   and


where 1 ≤ i ≤ m and the Hi are hyperplanes in   (with dimension m −1):


Building a generator matrixEdit

The Reed–Muller RM(r, m) code of order r and length N = 2m is the code generated by v0 and the wedge products of up to r of the vi, 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  , as the rows of the generator matrix, where 1 ≤ ikm.

Example 1Edit

Let m = 3. Then N = 8, and




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


or more explicitly by the rows of the matrix:


Example 2Edit

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


or more explicitly by the rows of the matrix:



The following properties hold:

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

2 The RM (r, m) code has rank


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 2mr.



There are
such vectors and   have dimension N so it is sufficient to check that the N vectors span; equivalently it is sufficient to check that RM(m, m) =  .
Let x be a binary vector of length m, an element of X. Let (x)i denote the ith element of x. Define
where 1 ≤ im.
Expansion via the distributivity of the wedge product gives  . Then since the vectors   span   we have RM(m, m) =  .


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.




By induction.
The RM(0, m) code is the repetition code of length N =2m and weight N = 2m−0 = 2mr. By 1 RM(m, m) =   and has weight 1 = 20 = 2mr.
The article bar product (coding theory) gives a proof that the weight of the bar product of two codes C1 , C2 is given by
If 0 < r < m and if
i) RM(r ,m − 1) has weight 2m−1−r
ii) RM(r-1,m-1) has weight 2m−1−(r−1) = 2mr
then the bar product has weight

Further Properties of Specific Reed-Muller CodesEdit

RM(0, m) codes are repetition codes of length N = 2m, rate   and minimum distance  .

RM(1, m) codes are parity check codes of length N = 2m, rate   and minimum distance  .

RM(m − 1, m) codes are single parity check codes of length N = 2m, rate   and minimum distance  .

RM(m − 2, m) codes are the family of extended Hamming codes of length N = 2m with minimum distance  .[1]

Alternative constructionEdit

A Reed–Muller code RM(r,m) exists for any integers   and  . RM(m, m) is defined as the universe ( ) code. RM(−1,m) is defined as the trivial code ( ). The remaining RM codes may be constructed from these elementary codes using the length-doubling construction


From this construction, RM(r,m) is a binary linear block code (n, k, d) with length n = 2m, dimension   and minimum distance   for  . 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.

Construction based on low-degree polynomials over a finite fieldEdit

There is another, simple way to construct Reed–Muller codes based on low-degree polynomials over a finite field. This construction is particularly suited for their application as locally testable codes and locally decodable codes.[2]

Let   be a finite field and let   and   be positive integers, where   should be thought of as larger than  . We are going to encode messages consisting of   elements of   as codewords of length   as follows: We interpret the message as an  -variate polynomial   of degree at most   with coefficient from  . Such a polynomial has   coefficients. The Reed–Muller encoding of   is the list of the evaluations of   on all  ; the codeword at the position indexed by   has value  .

Table of Reed–Muller codesEdit

The table below lists the RM(rm) codes of lengths up to 32 for alphabet of size 2 annotated with standard coding theory notation for block codes The Reed–Muller code is a  -code, that is, it is a linear code over a binary alphabet, has block length  , message length (or dimension)  , and minimum distance  .

( )
universe codes
RM(m − 1, m)
( )
SPC codes
RM(m − 2, m)
( )
ext. Hamming codes
self-dual codes
(1,0, )
(2,0, )
(4,0, )
( )
Punctured hadamard codes
(8,0, )
(16,0, )
( )
repetition codes
(32,0, )
( )
trivial codes

Decoding RM codesEdit

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.

See alsoEdit


  1. ^ Trellis and Turbo Coding, C. Schlegel & L. Perez, Wiley Interscience, 2004, p149.
  2. ^ Prahladh Harsha et al., Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes), Section 5.2.1.

Further readingsEdit

Research Articles:

  • D. E. Muller. Application of boolean algebra to switching circuit design and to error detection. IRE Transactions on Electronic Computers, 3:6–12, 1954.
  • Irving S. Reed. A class of multiple-error-correcting codes and the decoding scheme. Transactions of the IRE Professional Group on Information Theory, 4:38–49, 1954.


External linksEdit