Reed–Muller code
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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).…
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 \textstyle k=\sum_{i=0}^r \binom{m}{i} holds, the RM(r, m) code produces a codeword consisting of 2 m 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. A block code can have one or more encoding functions C:\{0,1\}^k\to\{0,1\}^{n} that map messages x\in\{0,1\}^k to codewords C(x)\in\{0,1\}^{n} . The Reed–Muller code has message length \textstyle k=\sum_{i=0}^r \binom{m}{i} and block length \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,\dots,Z_m) = \sum_{\underset codes are repetition codes of length , rate {R=\tfrac{1}{N}} and minimum distance d_\min = N . codes are parity check codes of length , rate R=\tfrac{m+1}{N} and minimum distance d_\min = \tfrac{N}{2} . codes are single parity check codes of length , rate R=\tfrac{N-1}{N} and minimum distance d_\min = 2 . codes are the family of extended Hamming codes of length with minimum distance d_\min = 4 .
External links
MIT OpenCourseWare, 6.451 Principles of Digital Communication II, Lecture Notes section 6.4 GPL Matlab-implementation of RM-codes Source GPL Matlab-implementation of RM-codes
Text derived from https://en.wikipedia.org/w/index.php?oldid=1368949473 under CC BY-SA 4.0; modifications have been made.