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 bits, where k = ∑ i = 0 r ( m i ) {\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}} 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 can have one or more encoding functions C : { 0 , 1 } k → { 0 , 1 } n {\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}} that map messages x ∈ { 0 , 1 } k {\textstyle x\in \{0,1\}^{k}} to codewords C ( x ) ∈ { 0 , 1 } n {\textstyle C(x)\in \{0,1\}^{n}} . The Reed–Muller code RM(r, m) has message length k = ∑ i = 0 r ( m i ) {\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}} and block length n = 2 m {\displaystyle \textstyle n=2^{m}} . 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:
p c ( Z 1 , … , Z m ) = ∑ S ⊆ { 1 , … , m } | S | ≤ r c S ⋅ ∏ i ∈ S Z i . {\displaystyle p_{c}(Z_{1},\dots ,Z_{m})=\sum _{\underset {|S|\leq r}{S\subseteq \{1,\dots ,m\}}}c_{S}\cdot \prod _{i\in S}Z_{i}\,.}
… excerpt ends here. Continue reading the full article.
