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

Rate

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

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 [11].Matrix factorization can be used to decode an RM\((n,n-3)\) code [12]; see [13].

Realizations

Deep-space communication [14,15].

Notes

See [16][5; Chs. 13-15] for details of RM codes and their variants.

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.
  • Binary duadic code— Certain punctured RM codes such as RM\(^*(2,5)\) are duadic; see Ref. [17], Table 6.2.
  • 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 [18][19; pg. 52].
  • Binary linear LTC— RM codes can be LTCs in the low- [20,21] and high-error [22] regimes; see also [23].
  • Qubit code— Optimizing T gates in a qubit circuit that uses CNOT and T gates is equivalent to decoding a particular RM code [24].
  • Orthogonal array (OA)— RM codes are related to orthogonal arrays [25; 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 [26,27]. Unions of certain RM codes yield self-dual quaternary codes over \(\mathbb{Z}_4\) that then give rise to certain BW lattices [28,29].
  • \(BW_{32}\) Barnes-Wall lattice— The union of RM\((1,5)\) and 2RM\((3,5)\) codes yields a Type II self-dual linear code over \(\mathbb{Z}_4\) that then gives rise to the \(B_{32}\) Barnes-Wall lattice via Construction \(A_4\) [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].
  • 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)\) [32].
  • \([2^r-1,2^r-r-1,3]\) Hamming code— Binary Hamming codes are equivalent to RM\(^*(r-2,r)\).
  • 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 [33].
  • 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.
  • Polar code— The generator matrices of RM and polar codes are different submatrices of Kronecker products of Hadamard matrices; see Ref. [34]. There are families interpolating between the two codes [35].
  • Quaternary RM (QRM) code— The image of the QRM\((r,m)\) code under the Gray map is the RM\((r,m)\) code [36; Thm. 19][37; Sec. 6.3]. Unions of certain RM codes yield self-dual quaternary codes over \(\mathbb{Z}_4\) that then give rise to certain BW lattices [28,29].
  • Majorana stabilizer code— Majorana stabilizer codes can be constructed by self-orthogonal RM codes [38]. These codes have the additional property that the global fermion parity is fixed in the codespace. In this family of codes, logical measurements are reduced to parity measurements of some subset of Majorana fermions in the code.
  • Quantum Reed-Muller code

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
Parents
Linear binary code
\((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 [39; 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 [40,41].
Group-algebra codeLinear \(q\)-ary ECC
RM codes are group-algebra codes [42,43][44; 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 \), where \(\mathbb{F}_2=GF(2)\). 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
Repetition code
RM\((0,m)\) are repetition codes.
\([2^m,m+1,2^{m-1}]\) First-order RM code
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]
S. Kumar and H. D. Pfister, “Reed-Muller Codes Achieve Capacity on Erasure Channels”, (2015) arXiv:1505.05123
[7]
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
[8]
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
[9]
E. Abbe, A. Shpilka, and A. Wigderson, “Reed-Muller codes for random erasures and errors”, (2014) arXiv:1411.4590
[10]
E. Abbe and C. Sandon, “A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels”, (2023) arXiv:2304.02509
[11]
L. Rudolph and C. Hartmann, “Decoding by sequential code reduction”, IEEE Transactions on Information Theory 19, 549 (1973) DOI
[12]
G. Seroussi and A. Lempel, “Factorization of Symmetric Matrices and Trace-Orthogonal Bases in Finite Fields”, SIAM Journal on Computing 9, 758 (1980) DOI
[13]
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
[14]
J. L. Massey, “Deep-space communications and coding: A marriage made in heaven”, Lecture Notes in Control and Information Sciences 1 DOI
[15]
E.C. Posner, Combinatorial Structures in Planetary Reconnaissance in Error Correcting Codes, ed. H.B. Mann, Wiley, NY 1968.
[16]
E. F. Assmus and J. D. Key, Designs and Their Codes (Cambridge University Press, 1992) DOI
[17]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[18]
M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
[19]
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
[20]
N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron, “Testing Reed–Muller Codes”, IEEE Transactions on Information Theory 51, 4032 (2005) DOI
[21]
T. Kaufman and D. Ron, “Testing Polynomials over General Fields”, SIAM Journal on Computing 36, 779 (2006) DOI
[22]
A. Samorodnitsky, “Low-degree tests at large distances”, (2006) arXiv:math/0604353
[23]
A. Bhattacharyya, S. Kopparty, G. Schoenebeck, M. Sudan, and D. Zuckerman, “Optimal Testing of Reed-Muller Codes”, (2010) arXiv:0910.0641
[24]
M. Amy and M. Mosca, “T-Count Optimization and Reed–Muller Codes”, IEEE Transactions on Information Theory 65, 4771 (2019) arXiv:1601.07363 DOI
[25]
Combinatorial Designs (Springer-Verlag, 2004) DOI
[26]
E. L. Cusack, “Error control codes for QAM signalling”, Electronics Letters 20, 62 (1984) DOI
[27]
G. D. Forney, “Coset codes. I. Introduction and geometrical classification”, IEEE Transactions on Information Theory 34, 1123 (1988) DOI
[28]
P. Sole, "Generalized theta functions for lattice vector quantization", in Coding and Quantization, DIMACS Series in Dr,crete Mathenulies and Theoretical Computer Science, vol. 14. Providence, RH: American Math. Soc., 1993, pp. 27-32.
[29]
A. Bonnecaze, P. Sole, and A. R. Calderbank, “Quaternary quadratic residue codes and unimodular lattices”, IEEE Transactions on Information Theory 41, 366 (1995) 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]
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
[33]
P. Delsarte and J. M. Goethals, “Alternating bilinear forms over GF(q)”, Journal of Combinatorial Theory, Series A 19, 26 (1975) DOI
[34]
E. Arikan, “A survey of reed-muller codes from polar coding perspective”, IEEE Information Theory Workshop 2010 (ITW 2010) (2010) DOI
[35]
M. Mondelli, S. H. Hassani, and R. L. Urbanke, “From Polar to Reed-Muller Codes: A Technique to Improve the Finite-Length Performance”, IEEE Transactions on Communications 62, 3084 (2014) DOI
[36]
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
[37]
S. T. Dougherty, "Codes over rings." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[38]
S. Vijay and L. Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”, (2017) arXiv:1703.00459
[39]
O. Geil and T. Høholdt, “On Hyperbolic Codes”, Lecture Notes in Computer Science 159 (2001) DOI
[40]
R. J. McEliece, “On periodic sequences from GF(q)”, Journal of Combinatorial Theory, Series A 10, 80 (1971) DOI
[41]
R. J. McEliece, “Weight congruences for p-ary cyclic codes”, Discrete Mathematics 3, 177 (1972) DOI
[42]
S. D. Berman, “On the theory of group codes”, Cybernetics 3, 25 (1969) DOI
[43]
Charpin, Pascale. Codes idéaux de certaines algèbres modulaires. Diss. 1982.
[44]
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.