Reed–Muller code

[1] Moreover, the proposed 5G standard[2] relies on the closely related polar codes[3] for error correction in the control channel.

These properties make them particularly useful in the design of probabilistically checkable proofs.

holds, the RM(r, m) code produces a codeword consisting of 2m bits.

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.

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:

follows from Lagrange interpolation, which states that the coefficients of a polynomial are uniquely determined when sufficiently many evaluation points are given.

As was already mentioned, Lagrange interpolation can be used to efficiently retrieve the message from a codeword.

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

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

from the input code and continue to next monomial, in reverse order of their degree.

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

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

and the corresponding initial word 1 1010 010101 Using low-degree polynomials over a finite field

, it is possible to extend the definition of Reed–Muller codes to alphabets of size

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

(with dimension m − 1): 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

Then N = 8, and and The RM(1,3) code is generated by the set or more explicitly by the rows of the matrix: The RM(2,3) code is generated by the set: or more explicitly by the rows of the matrix: The following properties hold: such vectors and

The basic idea of majority logic decoding is to build several checksums for each received code 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.

This technique was proposed by Irving S. Reed, and is more general when applied to other finite geometry codes.

-code, that is, it is a linear code over a binary alphabet, has block length