Reed–Muller code
Encyclopedia
Reed–Muller codes are a family of linear
Linear code
In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although Turbo codes can be seen as a hybrid of these two types. Linear codes allow for...

 error-correcting codes used in communications. Reed–Muller codes belong to the classes of locally testable code
Locally testable code
In theoretical computer science, a locally testable code is an error correcting code for which membership can be tested by a non-adaptive property testing algorithm. That is, locally testable codes have an efficient probabilistic algorithm that, based on its random bits, non-adaptively looks at few...

s and locally decodable codes, which is why they are useful in the design of probabilistically checkable proofs in computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

. They are named after their discoverers, Irving S. Reed
Irving S. Reed
Irving Stoy Reed is a mathematician and engineer. He is best known for co-inventing a class of algebraic error-correcting and error-detecting codes known as Reed-Solomon codes in collaboration with Gustave Solomon...

 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 Hadamard code
Hadamard code
The Hadamard code is an error-correcting code that is used for error detection and correction when transmitting messages over very noisy or unreliable channels....

, the Walsh–Hadamard code
Walsh code
In coding theory, the Walsh–Hadamard code, named after the American mathematician Joseph Leonard Walsh and the French mathematician Jacques Hadamard, is an example of a linear code over a binary alphabet that maps messages of length n to codewords of length 2^n...

, and the Reed–Solomon code
Reed–Solomon error correction
In coding theory, Reed–Solomon codes are non-binary cyclic error-correcting codes invented by Irving S. Reed and Gustave Solomon. They described a systematic way of building codes that could detect and correct multiple random symbol errors...

.

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

RM(0, r) codes are repetition codes of length n = 2 r, rate and minimum distance dmin = n.

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

RM(r − 1, r) codes are parity check codes of length n = 2 r.

RM(r − 2, r) codes are the family of extended Hamming codes of length n = 2 r with minimum distance dmin = 4.

Construction

A generating matrix for a Reed–Muller code of length n = 2d can be constructed like this. Let us write:


Note that each member of the set X is a point in . 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 , and the operation is the usual multiplication in the field .

is a d-dimensional vector space over the field , so it is possible to write



We define in n-dimensional space the following vectors with length n: v0 = (1, 1, 1, 1, 1, 1, 1, 1) and


where the Hi are hyperplanes in (with dimension d −1):


The Reed–Muller RM(d, r) code of order r and length n = 2d is the code generated by v0 and the wedge products of up to r of the vi (where by convention a wedge product of fewer than one vector is the identity for the operation).

Example 1

Let r = 3. Then n = 8, and


and


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


or more explicitly by the rows of the matrix

Example 2

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

or more explicitly by the rows of the matrix:

Properties

The following properties hold:

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

2 The RM (d, r) code has rank
Linear code
In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although Turbo codes can be seen as a hybrid of these two types. Linear codes allow for...



3 RM (d, r) = RM (d − 1, r) | RM (d − 1, r − 1) where '|' denotes the bar product of two codes.

4 RM (d, r) has minimum Hamming weight
Hamming weight
The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string of bits, this is the number of 1's in the string...

 2dr.

Proof

1
There are


such vectors and has dimension n so it is sufficient to check that the n vectors span; equivalently it is sufficient to check that RM(d, d) = .

Let x be an element of X and define


Then

Expansion via the distributivity of the wedge product gives . Then since the vectors span we have RM(d, d) = .


2
By 1, all such wedge products must be linearly independent, so the rank of RM(d, r) must simply be the number of such vectors.


3
Omitted.


4
By induction.

The RM(d, 0) code is the repetition code of length n =2d and weight n = 2d−0 = 2d−0. By 1 RM(d, d) = and has weight 1 = 20 = 2dd.

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 < d and if
i) RM(d − 1, r) has weight 2d−1−r
ii) RM(d-1,r-1) has weight 2d−1−(r−1) = 2dr

then the bar product has weight


Alternative construction

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 = 2 m, 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 field

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 code
Locally testable code
In theoretical computer science, a locally testable code is an error correcting code for which membership can be tested by a non-adaptive property testing algorithm. That is, locally testable codes have an efficient probabilistic algorithm that, based on its random bits, non-adaptively looks at few...

s and locally decodable codes.

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 codes

The table below lists the RM(rm) codes of lengths up to 32.
RM(m,m)
()
universe codes
RM(5,5)
(32,32,1)
RM(4,4)
(16,16,1)
RM(m − 1, m)
()
SPC
Parity bit
A parity bit is a bit that is added to ensure that the number of bits with the value one in a set of bits is even or odd. Parity bits are used as the simplest form of error detecting code....

 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)
()
ext. Hamming code
Hamming code
In telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming-code invented by Richard Hamming in 1950. Hamming codes can detect up to two and correct up to one bit errors. By contrast, the simple parity code cannot correct errors, and can detect only...

s
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,)
RM(0,2)
(4,1,4)
RM(1,4)
(16,5,8)
RM(-1,1)
(2,0,)
RM(0,3)
(8,1,8)
RM(1,5)
(32,6,16)
RM(-1,2)
(4,0,)
RM(0,4)
(16,1,16)
RM(1,m)
()
biorthogonal codes
RM(−1,3)
(8,0,)
RM(0,5)
(32,1,32)
RM(−1,4)
(16,0,)
RM(0,m)
()
repetition code
Repetition code
In coding theory, the repetition code is one of the most basic error-correcting codes. In order to transmit a message over a noisy channel that may corrupt the transmission in a few places, the idea of the repetition code is to just repeat the message several times. The hope is that the channel...

s
RM(−1,5)
(32,0,)
RM(-1,m)
()
trivial codes

Decoding RM codes

RM(r, m) codes can be decoded using the 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.

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK