[Jump to code hierarchy]

Reed-Muller (RM) code[1–3]

Description

Member of the RM\((r,m)\) family of linear binary codes derived from multivariate polynomials. The code parameters are \([2^m,\sum_{j=0}^{r} {m \choose j},2^{m-r}]\), where \(r\) is the order of the code satisfying \(0\leq r\leq m\). First-order RM codes are also called biorthogonal codes, while \(m\)th order RM codes are also called universe codes. Punctured RM codes RM\(^*(r,m)\) are obtained from RM codes by deleting one coordinate from each codeword.

Generator matrices of RM codes are constructed using the \((u|u+v)\) construction by starting from the \(2^m\)-dimensional matrix \(F^{(m)}=\left(\begin{smallmatrix}1 & 0\\ 1 & 1 \end{smallmatrix}\right)^{\otimes m}\), labeling its rows top-to-bottom from \(0\) to \(2^m-1\), converting the labels to binary strings of length \(m\), and deleting all rows whose labels have a Hamming weight less than \(m-r\). The recursive nature of the tensor product in the matrix \(F^{(m)}\) implies that RM\((r,m)\) is a subcode of RM\((r+1,m)\).

Another way to generate RM codewords is to list all outcomes of all polynomials of \(m\) binary variables of degree at most \(r\) [4] (see also Ch. 13 of Ref. [5]).

The automorphism code of the RM\((r,m)\) (RM\(^*(r,m)\)) code is \(GA_{m}(\mathbb{F}_2)\) (\(GL_{m}(\mathbb{F}_2)\)) for \(1 \leq r \leq m-2\) [5].

Protection

The Schwartz-Zippel Lemma provides a distance lower bound on RM codes and extended the degree mantra from RS codes. There is a relation between RM code performance against correlated generalizations of multiple-access channels (MACs) and quantum RM code performance against Pauli channels [6].

Rate

Achieves capacity of the binary erasure channel [7,8], the binary memoryless symmetric (BMS) channel under bitwise maximum-a-posteriori decoding [9] (see also Ref. [10]), and the binary symmetric channel (BSC), solving a long-standing conjecture [11].

Decoding

Reed decoder with \(r+1\)-step majority decoding corrects \(\frac{1}{2}(2^{m-r}-1)\) errors [1] (see also Ch. 13 of Ref. [5]).Sequential code-reduction decoding [12].Matrix factorization can be used to decode an RM\((n,n-3)\) code [13]; see [14].

Realizations

Deep-space communication [15,16].

Notes

See [17][5; Chs. 13-15] for details of RM codes and their variants.Review on theory and algorithms of RM codes [4].

Cousins

  • Binary BCH code— RM\(^*(r,m)\) codes are equivalent to subcodes of BCH codes of designed distance \(2^{m-r}-1\), while RM\((r,m)\) are subcodes of extended BCH codes of the same designed distance [5; Ch. 13].
  • Dual linear code— The codes RM\((r,m)\) and RM\((m-r-1,m)\) are dual to each other, with the case \(m = 2r+1\) being self dual.
  • Self-dual linear code— The codes RM\((r,m)\) and RM\((m-r-1,m)\) are dual to each other, with the case \(m = 2r+1\) being self dual.
  • Binary duadic code— Certain punctured RM codes, such as RM\(^*(2,5)\) [18; Table 6.2] and codes of order \((m-1)/2\) for odd \(m\) [19], are duadic.
  • Cyclic linear binary code— Punctured RM codes are cyclic ([5], Ch. 13, Thm. 11), making RM codes extended cyclic codes. RM codes with nonzero evaluation points are cyclic [20][21; pg. 52].
  • Binary linear LTC— RM codes can be LTCs in the low- [22,23] and high-error [24] regimes; see also [25].
  • Qubit code— Optimizing T gates in a qubit circuit that uses CNOT and T gates is equivalent to decoding a particular RM code [26].
  • Orthogonal array (OA)— RM codes are related to orthogonal arrays [27; Exam. 10.57].
  • Barnes-Wall (BW) lattice— BW lattices are lattice analogues of RM codes in that both can be constructed recursively via a \(|u|u+v|\) construction [28,29].
  • \(\Lambda_{16}\) Barnes-Wall lattice— The RM\((1,4)\) code can be used to obtain the \(\Lambda_{16}\) Barnes-Wall lattice [30; Exam. 10.7.2].
  • Combinatorial design— Fixed-weight RM codewords of weight less than \(2^m\) support combinatorial 3-designs [31; Exam. 5.2.7].
  • Preparata code— A Preparata code can be written as a union of a linear subcode \(\mathcal{C}\) of RM\((m-2,m)\) and the \(2^{m-1}-1\) representatives of coset formed by \(\mathcal{C}\) in RM\((m-2,m)\). The coset representatives are given by \(|1|x^j|0|x^{j}\theta_{1}|\), where \(1\leq j \leq 2^{m-1}-1\). \(\mathcal{C}\) comprises of codewords of the form \(|g(1)|g(x)(1+\theta_{1})|f(1)+g(1)|g(x)(1+\theta_{1})+f(x)(1+\theta_{1}+\theta_{3})|\), where \(f(x)\) and \(g(x)\) are arbitrary, and where \(\theta_{1}\) and \(\theta_{3}\) denote the primitive idempotents corresponding to cyclotomic cosets \(C_1\) and \(C_3\) respectively.
  • Delsarte-Goethals (DG) code— The code DG\((m,r)\) is a subcode of the second-order Reed-Muller code RM\((2,m)\), and equals RM\((2,m)\) at \(r=1\) [5; pg. 461]. The code is the union of certain cosets of the first-order RM\((1,m)\) code in RM\((2,m)\) that are specified by bilinear forms [32].
  • Kerdock code— Kerdock code is a subcode of a second-order RM Code [5; pg. 457]. It consists of a number of cosets of RM\((2,m)\) created by quotienting with first-order RM\((1,m)\) codes.
  • Hadamard code— The \([2^m,m+1,2^{m-1}]\) augmented Hadamard code is the first-order RM code (a.k.a. RM\((1,m)\)). The \([2^m-1,m,2^{m-1}]\) shortened Hadamard code is the simplex code (a.k.a. RM\(^*(1,m)\)). Rows of a Hadamard matrix forming a Prometheus orthonormal set (PONS) are codewords of a coset of RM\((1,m)\) in RM\((2,m)\) [33].
  • \([2^m-1,m,2^{m-1}]\) simplex code— Simplex are equivalent to RM\(^*(1,m)\).
  • \([2^r-1,2^r-r-1,3]\) Hamming code— Binary Hamming codes are equivalent to RM\(^*(r-2,r)\).
  • Polar code— The generator matrices of RM and polar codes are different submatrices of Kronecker products of Hadamard matrices [34,35]. There are families interpolating between the two codes [36].
  • \(C_{m,r}\) code— The \(C_{m,r}\) code is generated by \(\textnormal{RM}(r,m) + 2\textnormal{RM}(m-r-1,m)\) for \(3r \leq m-1\) [37].
  • Quaternary RM (QRM) code— The mod-two reduction of the QRM\((r,m)\) code is the RM\((r,m)\) code [38; Thm. 19].
  • ZRM code— The ZRM code is generated by \(\textnormal{RM}(r-1,m-1) + 2\textnormal{RM}(r,m-1)\) [38; Thm. 7]. The image of the ZRM\((r,m-1)\) code under the Gray map is the RM\((r,m)\) code [38; Thm. 7].
  • Klemm code— The Klemm code at \(m=4\) is generated by \(\textnormal{RM}(0,4) + 2\textnormal{RM}(3,4)\) [39].
  • RM Majorana code— RM Majorana codes are constructed from self-orthogonal RM codes.
  • Quantum Reed-Muller (RM) code— Quantum RM codes are constructed from RM codes via the CSS construction. There is a relation between RM code performance against correlated generalizations of multiple-access channels (MACs) and quantum RM code performance against Pauli channels [6].

Member of code lists

Primary Hierarchy

Classical Domain
Binary Kingdom
Binary codeECC
Binary group-orbit codeECC
Linear binary codeLinear \(q\)-ary Linear code over \(\mathbb{Z}_q\) ECC
Coxeter code
Parents
Coxeter code
An RM\((r,m)\) code is spanned by indicators of all subcubes of dimension \(m-r\) in the \(m\)-dimensional cube (this is a redundant generating set [40]), i.e., by the cosets of rank-\((m-r)\) subgroups of \(\mathbb{Z}_2^m\). For a finite Coxeter group \(W\) with \(m\) generators, the Coxeter code \(C_W(r)\) of order \(r\) with \(-1 \leq r \leq m\) is similarly spanned by indicators of all the cosets of rank-\((m-r)\) parabolic subgroups of \(W\).
\((u|u+v)\)-construction codeECC
All RM codes can be constructed via the \((u|u+v)\) construction [5; Ch. 13].
Generalized RM (GRM) codeEvaluation Linear \(q\)-ary LCC LRC Distributed-storage LDC ECC
Binary GRM codes are RM codes.
Hyperbolic evaluation codeEvaluation Linear \(q\)-ary ECC
RM codes are special cases of hyperbolic evaluation codes [41; Thm. 3 proof].
Divisible codeLinear \(q\)-ary ECC
An RM\((r,m)\) code is \(2^{\left\lceil m/r\right\rceil-1}\)-divisible, according to McEliece’s theorem [42,43].
Group-algebra codeLinear \(q\)-ary ECC
RM codes are group-algebra codes [44,45][46; Exam. 16.4.11]. Consider a binary vector space of dimension \( m \). Under addition, this forms a finite group with \( 2^m \) elements known as an elementary Abelian 2-group – the direct product of \( m \) two-element cyclic groups \( \mathbb{Z}_2 \times \dots \times \mathbb{Z}_2 \). Denote this group by \( G_m \). Let \( J \) be the Jacobson radical of the group algebra \( \mathbb{F}_2 G_m \). RM\((r,m)\) codes correspond to the ideal \( J^{m-r} \). The length of the code is \( |G_m| = 2^m \), the distance is \( 2^{m-r} \), and the dimension is \( \sum_{i=0}^r {m \choose i} \). A similar construction exists for choices of a prime \( p\neq 2 \).
Reed-Muller (RM) code
Children
\([2^m,m+1,2^{m-1}]\) First-order RM code
First-order RM codes are RM\((1,m)\) codes.
Repetition code
Repetition codes are RM\((0,m)\) codes.
\([2^m,2^m-m-1,4]\) Extended Hamming code
Extended Hamming codes are RM\((m-2,m)\) codes.
\([n,n-1,2]\) Single parity-check (SPC) code
SPCs are RM\((m-1,m)\) codes.

References

[1]
D. E. Muller, “Application of Boolean algebra to switching circuit design and to error detection”, Transactions of the I.R.E. Professional Group on Electronic Computers EC-3, 6 (1954) DOI
[2]
I. Reed, “A class of multiple-error-correcting codes and the decoding scheme”, Transactions of the IRE Professional Group on Information Theory 4, 38 (1954) DOI
[3]
N. Mitani, On the transmission of numbers in a sequential computer, delivered at the National Convention of the Inst. of Elect. Engineers of Japan, November 1951.
[4]
E. Abbe, A. Shpilka, and M. Ye, “Reed-Muller Codes: Theory and Algorithms”, (2020) arXiv:2002.03317
[5]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[6]
D. Abdelhadi, C. Sandon, E. Abbe, and R. Urbanke, “Reed-Muller Codes for Quantum Pauli and Multiple Access Channels”, (2025) arXiv:2506.08651
[7]
S. Kumar and H. D. Pfister, “Reed-Muller Codes Achieve Capacity on Erasure Channels”, (2015) arXiv:1505.05123
[8]
S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. Şaşoğlu, and R. Urbanke, “Reed-Muller Codes Achieve Capacity on Erasure Channels”, (2016) arXiv:1601.04689
[9]
G. Reeves and H. D. Pfister, “Reed–Muller Codes on BMS Channels Achieve Vanishing Bit-Error Probability for all Rates Below Capacity”, IEEE Transactions on Information Theory 70, 920 (2024) arXiv:2110.14631 DOI
[10]
E. Abbe, A. Shpilka, and A. Wigderson, “Reed-Muller codes for random erasures and errors”, (2014) arXiv:1411.4590
[11]
E. Abbe and C. Sandon, “A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels”, (2023) arXiv:2304.02509
[12]
L. Rudolph and C. Hartmann, “Decoding by sequential code reduction”, IEEE Transactions on Information Theory 19, 549 (1973) DOI
[13]
G. Seroussi and A. Lempel, “Factorization of Symmetric Matrices and Trace-Orthogonal Bases in Finite Fields”, SIAM Journal on Computing 9, 758 (1980) DOI
[14]
E. T. Campbell and M. Howard, “Unified framework for magic state distillation and multiqubit gate synthesis with reduced resource cost”, Physical Review A 95, (2017) arXiv:1606.01904 DOI
[15]
J. L. Massey, “Deep-space communications and coding: A marriage made in heaven”, Lecture Notes in Control and Information Sciences 1 DOI
[16]
E.C. Posner, Combinatorial Structures in Planetary Reconnaissance in Error Correcting Codes, ed. H.B. Mann, Wiley, NY 1968.
[17]
E. F. Assmus and J. D. Key, Designs and Their Codes (Cambridge University Press, 1992) DOI
[18]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[19]
H. Liu, C. Li, and C. Ding, “Five infinite families of binary cyclic codes and their related codes with good parameters”, (2023) arXiv:2301.06446
[20]
M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
[21]
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
[22]
N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron, “Testing Reed–Muller Codes”, IEEE Transactions on Information Theory 51, 4032 (2005) DOI
[23]
T. Kaufman and D. Ron, “Testing Polynomials over General Fields”, SIAM Journal on Computing 36, 779 (2006) DOI
[24]
A. Samorodnitsky, “Low-degree tests at large distances”, (2006) arXiv:math/0604353
[25]
A. Bhattacharyya, S. Kopparty, G. Schoenebeck, M. Sudan, and D. Zuckerman, “Optimal Testing of Reed-Muller Codes”, (2010) arXiv:0910.0641
[26]
M. Amy and M. Mosca, “T-Count Optimization and Reed–Muller Codes”, IEEE Transactions on Information Theory 65, 4771 (2019) arXiv:1601.07363 DOI
[27]
Combinatorial Designs (Springer-Verlag, 2004) DOI
[28]
E. L. Cusack, “Error control codes for QAM signalling”, Electronics Letters 20, 62 (1984) DOI
[29]
G. D. Forney, “Coset codes. I. Introduction and geometrical classification”, IEEE Transactions on Information Theory 34, 1123 (1988) DOI
[30]
T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
[31]
V. D. Tonchev, “Codes and designs.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[32]
P. Delsarte and J. M. Goethals, “Alternating bilinear forms over GF(q)”, Journal of Combinatorial Theory, Series A 19, 26 (1975) DOI
[33]
M. An, J. Byrnes, W. Moran, B. Saffari, H. S. Shapiro, and R. Tolimieri, “Pons, Reed-Muller Codes, and Group Algebras”, NATO Science Series II: Mathematics, Physics and Chemistry 155 DOI
[34]
E. Arikan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels”, IEEE Transactions on Information Theory 55, 3051 (2009) arXiv:0807.3917 DOI
[35]
E. Arikan, “A survey of reed-muller codes from polar coding perspective”, IEEE Information Theory Workshop 2010 (ITW 2010) 1 (2010) DOI
[36]
M. Mondelli, S. H. Hassani, and R. Urbanke, “From Polar to Reed-Muller Codes: a Technique to Improve the Finite-Length Performance”, (2014) arXiv:1401.3127
[37]
S. T. Dougherty, P. Gaborit, M. Harada, A. Munemasa, and P. Sole, “Type IV self-dual codes over rings”, IEEE Transactions on Information Theory 45, 2345 (1999) DOI
[38]
A. R. Hammons Jr., P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Solé, “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
[39]
A. Bonnecaze, P. Sole, C. Bachoc, and B. Mourrain, “Type II codes over Z/sub 4/”, IEEE Transactions on Information Theory 43, 969 (1997) DOI
[40]
A. Barg, N. J. Coble, D. Hangleiter, and C. Kang, “Geometric structure and transversal logic of quantum Reed-Muller codes”, (2024) arXiv:2410.07595
[41]
O. Geil and T. Høholdt, “On Hyperbolic Codes”, Lecture Notes in Computer Science 159 (2001) DOI
[42]
R. J. McEliece, “On periodic sequences from GF(q)”, Journal of Combinatorial Theory, Series A 10, 80 (1971) DOI
[43]
R. J. McEliece, “Weight congruences for p-ary cyclic codes”, Discrete Mathematics 3, 177 (1972) DOI
[44]
S. D. Berman, “On the theory of group codes”, Cybernetics 3, 25 (1969) DOI
[45]
Charpin, Pascale. Codes idéaux de certaines algèbres modulaires. Diss. 1982.
[46]
W. Willems, “Codes in Group Algebras.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: reed_muller

Cite as:
“Reed-Muller (RM) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/reed_muller
BibTeX:
@incollection{eczoo_reed_muller, title={Reed-Muller (RM) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/reed_muller} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/reed_muller

Cite as:

“Reed-Muller (RM) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/reed_muller

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/reed_muller/reed_muller.yml.