Reed–Muller code
   HOME

TheInfoList



OR:

Reed–Muller codes are
error-correcting code In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
s that are used in wireless communications applications, particularly in deep-space communication. Moreover, the proposed 5G standard relies on the closely related polar codes 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 Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...
. Reed–Muller codes generalize the Reed–Solomon codes and the
Walsh–Hadamard code The Hadamard code is an error-correcting code named after Jacques Hadamard that is used for error detection and correction when transmitting messages over very noisy or unreliable channels. In 1971, the code was used to transmit photos of Mar ...
. 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 proof In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm i ...
s. 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 \textstyle k=\sum_^r \binom holds, the RM(''r'', ''m'') code produces a codeword consisting of 2''m'' bits. Reed–Muller codes are named after
David E. Muller David Eugene Muller (November 2, 1924 – April 27, 2008) was an American mathematician and computer scientist. He was a professor of mathematics and computer science at the University of Illinois (1953–92), after which he became an emeritu ...
, who discovered the codes in 1954, and Irving S. Reed, who proposed the first efficient decoding algorithm.


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 code A locally testable code is a type of error-correcting code for which it can be determined if a string is a word in that code by looking at a small (frequently constant) number of bits of the string. In some situations, it is useful to know if the ...
s and
locally decodable code In mathematics, a mathematical object is said to satisfy a property locally, if the property is satisfied on some limited, immediate portions of the object (e.g., on some ''sufficiently small'' or ''arbitrarily small'' neighborhoods of points). P ...
s.


Encoder

A
block code In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definit ...
can have one or more encoding functions C:\^k\to\^ that map messages x\in\^k to codewords C(x)\in\^ . The Reed–Muller code has message length \textstyle k=\sum_^r \binom and block length \textstyle n=2^m. One way to define an encoding for this code is based on the evaluation of
multilinear polynomial In algebra, a multilinear polynomial is a multivariate polynomial that is linear (meaning affine) in each of its variables separately, but not necessarily simultaneously. It is a polynomial in which no variable occurs to a power of 2 or higher; tha ...
s with ''m'' variables and
total degree In mathematics, the degree of a polynomial is the highest of the degrees of the polynomial's monomials (individual terms) with non-zero coefficients. The degree of a term is the sum of the exponents of the variables that appear in it, and thus i ...
''r''. Every multilinear polynomial over the
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
with two elements can be written as follows: p_c(Z_1,\dots,Z_m) = \sum_ c_S\cdot \prod_ Z_i\,. The Z_1,\dots,Z_m are the variables of the polynomial, and the values c_S\in\ are the coefficients of the polynomial. Since there are exactly k coefficients, the message x\in\^k consists of k values that can be 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 p_x at all evaluation points a\in\^m , where it interprets the sum as addition modulo two in order to obtain a bit (p_x(a)\bmod 2) \in \. That is, the encoding function is defined viaC(x) = \left(p_x(a)\bmod 2\right)_\,. The fact that the codeword C(x) suffices to uniquely reconstruct x follows from
Lagrange interpolation In numerical analysis, the Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of data. Given a data set of coordinate pairs (x_j, y_j) with 0 \leq j \leq k, the x_j are called ''nodes'' an ...
, 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\^k, the function C is a
linear map In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a Map (mathematics), mapping V \to W between two vect ...
. Thus the Reed–Muller code is a
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 ...
.


Example

For the code , the parameters are as follows: \begin r&=2\\ m&=4\\ k&=\textstyle\binom+\binom+\binom= 6+4+1=11\\ n&=2^m=16\\ \end Let C:\^\to\^ 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:\begin 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_1Z_3 + 0\cdot Z_1Z_4 + 1\cdot Z_2Z_3 + 0\cdot Z_2Z_4+ 1\cdot Z_3Z_4)\\ &=1+Z_1+Z_3+Z_1Z_3+Z_2Z_3+Z_3Z_4 \endThen 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,\; p_x(0001)= 1,\; p_x(0010)= 0,\; p_x(0011)= 1,\; p_x(0100)= 1,\; p_x(0101)= 1,\; p_x(0110)= 1,\; p_x(0111)= 0,\; p_x(1000)= 0,\; p_x(1001)= 0,\; p_x(1010)= 0,\; p_x(1011)= 1,\; p_x(1100)= 0,\; p_x(1101)= 0,\; p_x(1110)= 1,\; p_x(1111)= 0\,.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 _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 \mu of the highest degree d in p_x and sum all the evaluation points of the polynomial where all variables in \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 \mu in p_x (There are 2^d such points). This is due to the fact that all lower monomial divisors of \mu appears an even number of time in the sum, and only \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 \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 much errors in the input code. Once a coefficient is computed, if it's 1, update the code to remove the monomial \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. * \mu=X_3X_4 ** we start by looking for evaluation points with X_1=0, X_2=0, X_3\in\, X_4\in\. 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\in\, X_4\in\. 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\in\, X_4\in\. 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\in\, X_4\in\. 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 \mu is 1. We remove \mu from the code before continue :
 code : 1101 1110 0001 0110, valuation of \mu is 0001000100010001, the new code is 1100 1111 0000 0111 * \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. * \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. * \mu=X_2X_3 ** 1100 1111 0000 0111. Sum is 1 ** 100 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 \mu is 0000 0011 0000 0011, current code is now 1100 1100 0000 0100. * \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 \mu is 0000 0000 0011 0011, current code is now 1100 1100 0011 0111. * \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. * \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 0 ** 1100 1100 0011 0111. Sum is 1 One error detected, coefficient is 0, no change to current code. * \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 \mu is 0011 0011 0011 0011, current code is now 1111 1111 0000 0100. Then we'll find 0 for \mu=X_2 , 1 for \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_1X3+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 \mathbb 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\in\mathbb F^k of width k=\textstyle\binom, the message is again interpreted as an m-variate polynomial p_x of total degree at most d and with coefficient from \mathbb F. Such a polynomial indeed has \textstyle\binom coefficients. The Reed–Muller encoding of x is the list of all evaluations of p_x(a) over all a\in\mathbb F^m. Thus the block length is n=q^m.


Description using a generator matrix

A
generator matrix In coding theory, a generator matrix is a matrix whose rows form a basis for a linear code. The codewords are all of the linear combinations of the rows of this matrix, that is, the linear code is the row space of its generator matrix. Terminol ...
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 = \mathbb_2^m = \. We define in ''N''-dimensional space \mathbb_2^N the
indicator vector In mathematics, the indicator vector or characteristic vector or incidence vector of a subset ''T'' of a Set (mathematics), set ''S'' is the vector x_T := (x_s)_ such that x_s = 1 if s \in T and x_s = 0 if s \notin T. If ''S'' is countable set, cou ...
s :\mathbb_A \in \mathbb_2^N on subsets A \subset X by: :\left( \mathbb_A \right)_i = \begin 1 & \mbox x_i \in A \\ 0 & \mbox \\ \end together with, also in \mathbb_2^N, the binary operation : 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 A wedge is a triangular shaped tool, and is a portable inclined plane, and one of the six simple machines. It can be used to separate two objects or portions of an object, lift up an object, or hold an object in place. It functions by converti ...
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 \mathbb_2^N (''N''-dimensional binary vectors), and the operation \cdot is the usual multiplication in the field \mathbb_2. \mathbb_2^m is an ''m''-dimensional vector space over the field \mathbb_2, so it is possible to write (\mathbb_2)^m = \ . We define in ''N''-dimensional space \mathbb_2^N the following vectors with length N: v_0 = (1,1,\ldots,1) and : v_i = \mathbb_ , where 1 ≤ i ≤ ''m'' and the ''H''''i'' are
hyperplane In geometry, a hyperplane is a subspace whose dimension is one less than that of its ''ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyper ...
s in (\mathbb_2)^m (with dimension ): :H_i = \ .


The generator matrix

The Reed–Muller code of order ''r'' and length ''N'' = 2''m'' is the code generated by ''v''0 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 , as the rows of the generator matrix, where .


Example 1

Let ''m'' = 3. Then ''N'' = 8, and : X = \mathbb_2^3 = \, and : \begin v_0 & = (1,1,1,1,1,1,1,1) \\ ptv_1 & = (1,0,1,0,1,0,1,0) \\ ptv_2 & = (1,1,0,0,1,1,0,0) \\ ptv_3 & = (1,1,1,1,0,0,0,0). \end The RM(1,3) code is generated by the set : \,\, or more explicitly by the rows of the matrix: : \begin 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


Example 2

The RM(2,3) code is generated by the set: : \ or more explicitly by the rows of the matrix: : \begin 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


Properties

The following properties hold: # The set of all possible wedge products of up to ''m'' of the ''v''''i'' form a basis for \mathbb_2^N. # The RM (''r'', ''m'') code has
rank Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as: Level or position in a hierarchical organization * Academic rank * Diplomatic rank * Hierarchy * H ...
#: \sum_^r . # where ', ' denotes the bar product of two codes. # has minimum
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 o ...
2''m'' − ''r''.


Proof


Decoding RM codes

RM(''r'', ''m'') codes can be decoded using
majority logic decoding In error detection and correction, majority logic decoding is a method to decode repetition codes, based on the assumption that the largest number of occurrences of a symbol was the transmitted symbol. Theory In a binary alphabet made of 0,1, if a ...
. 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 ''r''th 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 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 construction :\mathrm(r,m) = \. From this construction, RM(''r,m'') is a binary
linear block code In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definit ...
(''n'', ''k'', ''d'') with length , dimension k(r,m)=k(r,m-1)+k(r-1,m-1) and minimum distance d = 2^ for r \ge 0. The
dual code In coding theory, the dual code of a linear code :C\subset\mathbb_q^n is the linear code defined by :C^\perp = \ where :\langle x, c \rangle = \sum_^n x_i c_i is a scalar product. In linear algebra terms, the dual code is the annihilator ...
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 m\le 5 and alphabet size 2 are displayed here, annotated with the standard ,k,d coding theory notation for
block code In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definit ...
s. The code is a \textstyle ^m,k,2^2-code, that is, it is a
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 ...
over a binary alphabet, has block length \textstyle 2^m, message length (or dimension) , and minimum distance \textstyle 2^.


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

* codes are
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 mess ...
s of length , rate and minimum distance d_\min = N. * codes are parity check codes of length , rate R=\tfrac and minimum distance d_\min = \tfrac. * codes are single parity check codes of length , rate R=\tfrac and minimum distance d_\min = 2. * codes are the family of extended Hamming codes of length with minimum distance d_\min = 4.Trellis and Turbo Coding, C. Schlegel & L. Perez, Wiley Interscience, 2004, p149.


References


Further reading

* Chapter 4. * Chapter 4.5.


External links


MIT OpenCourseWare
6.451 Principles of Digital Communication II, Lecture Notes section 6.4


Source GPL Matlab-implementation of RM-codes
* {{DEFAULTSORT:Reed-Muller code Error detection and correction Coding theory Theoretical computer science