Reed–Muller codes are error-correcting codes 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.
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 bits, where 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.
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.
A block code can have one or more encoding functions that map messages to codewords . The Reed–Muller code RM(r, m) 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 r. Every multilinear polynomial over the finite field with two elements can be written as follows:
The are the variables of the polynomial, and the values are the coefficients of the polynomial. Since there are exactly coefficients, the message consists of values that can be used as these coefficients.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
The beginning of 21st century provided us with many answers about how to reach the channel capacity. Polarization and spatial coupling are two techniques for achieving the capacity of binary memoryles
We strengthen the results from a recent work by the second author, achieving bounds on the weight distribution of binary linear codes that are successful under block-MAP (as well as bit-MAP) decoding
ASSOC COMPUTING MACHINERY2021
,
The recently introduced polar codes constitute a breakthrough in coding theory due to their capacity-achieving property. This goes hand in hand with a quasilinear construction, encoding, and successiv