↑ arvau

Wikipedia / Reed–Muller code

Reed–Muller codes are error-correcting codes that are used in wireless communications applications, particularly in deep-space communication. In cryptography, duplicated Reed–Muller codes are concatenated with shortened Reed–Solomon codes in the Hamming Quasi-Cyclic (HQC) key encapsulation mechanism selected by NIST for standardization as an alternative quantum-resistant algorithm. 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. For example, they have been shown to asymptotically achieve Shannon capacity on symmetric memoryless channels.

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 holds, the RM(r,m) code produces a codeword consisting of 2m bits.

Reed–Muller codes are named after David E. Muller, 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 codes and locally decodable codes.

Encoder

A block code. The ReedMuller code has message length and block length. 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 in m

follows from Lagrange interpolation is a linear map. Thus the ReedMuller code is a linear code.

Example

For the code , the parameters are as follows:

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.

included.

appears once.

times for each fixed valuations of the other variables. If there is no error, all those sums should be equal 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.

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

Example

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 start by searching for monomial of degree 2.

  • . In the code this is: 1101 1110 0001 0110. The first sum is 1 (odd number of 1).

  • . In the code this is: 1101 1110 0001 0110. The second sum is 1.

  • . In the code this is: 1101 1110 0001 0110. The third sum is 1.

  • . In the code this is: 1101 1110 0001 0110. The third sum is 0 (even number of 1).

is 1.

is 0001000100010001, the new code is 1100 1111 0000 0111

  • 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.

  • 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.

  • 1100 1111 0000 0111. Sum is 1

  • 1100 1111 0000 0111. Sum is 1

  • 1100 1111 0000 0111. Sum is 1

  • 1100 1111 0000 0111. Sum is 0

is 0000 0011 0000 0011, current code is now 1100 1100 0000 0100.

  • 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

is 0000 0000 0011 0011, current code is now 1100 1100 0011 0111.

  • 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.

  • 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

  • 1100 1100 0011 0111. Sum is 0

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

  • 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

is 0011 0011 0011 0011, current code is now 1111 1111 0000 0100.

and the current code become 1111 1111 1111 1011.

and the corresponding initial word 1 1010 010101

Generalization to larger alphabets via low-degree polynomials

, it is possible to extend the definition of Reed.

Description using a generator matrix

A generator matrix for a ReedMuller code of length can be constructed as follows. Let us write the set of all m-dimensional binary vectors as:

We define in N the indicator vectors

by:

, the binary operation

referred to as the wedge product (not to be confused with the wedge product (N.

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

We define in N and

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

The generator matrix

The ReedMuller 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, (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, as the rows of the generator matrix, where .

Example 1

Let m = 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 m of the vi.

  2. The RM(r, m) code has rank

  3. where '|' denotes the bar product of two codes.

  4. has minimum Hamming weight 2m r.

The full distribution of codeword weights is more complicated than the minimum-distance formula. Tadao Kasami and Nobuki Tokura studied the weight structure of Reed–Muller codes, including low-weight codewords beyond the minimum weight.

Proof

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. RM(m, m) code. RM(). 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 . 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 are self-dual.

Special cases of Reed–Muller codes

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

All and alphabet size 2 are displayed here, annotated with the standard [n,k,d] coding theory notation for block codes. The code -code, that is, it is a linear code over a binary alphabet, has block length, message length (or dimension) , and minimum distance.

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

References

Further reading

  • Chapter 4.

  • Chapter 4.5.