Reed-Muller (RM) code

Reed-Muller (RM) code[1][2][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\). Punctured RM codes RM\(^*(r,m)\) are obtained from RM codes by deleting one or more coordinates 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]).

Rate

Achieves capacity of the binary erasure channel [6] and of the binary memoryless symmetric (BMS) channel under bitwise maximum-a-posteriori decoding [7].

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 [8].First-order (\(r=1\)) RM codes admit specialized decoders [9].

Realizations

Deep-space communication, including the Mariner 9 spacecraft [10][9].

Notes

See Chs. 13-15 of Ref. [5] for details of RM codes and their variants.See Ref. [11] for the weight distribution of the \(2^{26}\) cosets of the \((32,6)\) first-order RM code, obtained in part by hand computation.

Parents

Polynomial evaluation code — RM codes are multivariate polynomial evaluation codes with \(\cal X\) being the entire \(m\)-dimensional affine binary space ([12], pgs. 44-46; [13][14]).
Linear binary code
Quaternary code over \(\mathbb{Z}_4\) — RM codes are images of ring-linear quaternary codes under the Gray map ([15], Sec. 6.3).
Divisible code — An RM\((r,m)\) code is \(2^{\left\lceil m/r\right\rceil-1}\)-divisible, according to McEliece's theorem [16][17].
Group code — 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 \).

Child

Hamming code — Hamming codes are equivalent to RM\(^*(m-2,m)\).

Cousins

Binary BCH code — RM\((r,m)\) codes are subcodes of BCH codes of designed distance \(2^{m-r}-1\) ([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. [18], 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 ([12], pg. 52).
Parity-check code — RM\((m-1,m)\) are parity-check codes.
Binary linear LTC — RM codes can be LTCs in the low- [19][20] and high-error [21] regimes.
Generalized RM (GRM) code
Hadamard code — For any Hamming code \([2^m,2^m-m-1,3]\), the dual Hadamard code, when augmented with a bit that is always 0, gives the RM\((1,m)\) code. In general, RM\((1,m)\) is related to the duals of the Hamming code, and when RM\((1,m)\) is self-dual, it is directly related to the Hamming code.
Majorana stabilizer code — Majorana stabilizer codes can be constructed by self-orthogonal RM codes [22]. 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.
Polar code — RM codes rely on the same generator matrix, but place message bits in different coordinates.
Quantum Reed-Muller code
Quantum divisible code — Quantum divisible codes can be constructed out of first-order RM codes.
Simplex code — Binary simplex codes can be constructed from the generator matrix of RM\((1,k)\) by removing first the all-ones row, and then the all-zero column. Punctured RM codes and simplex codes are interconvertible via expurgation and augmentation ([5], pg. 31).

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]: Emmanuel Abbe, Amir Shpilka, and Min Ye, “Reed-Muller Codes: Theory and Algorithms”. 2002.03317
[5]: F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[6]: S. Kudekar et al., “Reed–Muller Codes Achieve Capacity on Erasure Channels”, IEEE Transactions on Information Theory 63, 4298 (2017). DOI
[7]: Galen Reeves and Henry D. Pfister, “Reed-Muller Codes Achieve Capacity on BMS Channels”. 2110.14631
[8]: L. Rudolph and C. Hartmann, “Decoding by sequential code reduction”, IEEE Transactions on Information Theory 19, 549 (1973). DOI
[9]: E.C. Posner, Combinatorial Structures in Planetary Reconnaissance in Error Correcting Codes, ed. H.B. Mann, Wiley, NY 1968.
[10]: J. L. Massey, “Deep-space communications and coding: A marriage made in heaven”, Advanced Methods for Satellite and Deep Space Communications 1. DOI
[11]: E. Berlekamp and L. Welch, “Weight distributions of the cosets of the (32,6) Reed-Muller code”, IEEE Transactions on Information Theory 18, 203 (1972). DOI
[12]: M. A. Tsfasman and S. G. Vlăduţ, Algebraic-geometric Codes (Springer Netherlands, 1991). DOI
[13]: S. G. Vléduts and Y. I. Manin, “Linear codes and modular curves”, Journal of Soviet Mathematics 30, 2611 (1985). DOI
[14]: T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[15]: W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021). DOI
[16]: R. J. McEliece, “On periodic sequences from GF(q)”, Journal of Combinatorial Theory, Series A 10, 80 (1971). DOI
[17]: R. J. McEliece, “Weight congruences for p-ary cyclic codes”, Discrete Mathematics 3, 177 (1972). DOI
[18]: W. C. Huffman and V. Pless, Fundamentals of Error-correcting Codes (Cambridge University Press, 2003). DOI
[19]: N. Alon et al., “Testing Reed–Muller Codes”, IEEE Transactions on Information Theory 51, 4032 (2005). DOI
[20]: T. Kaufman and D. Ron, “Testing Polynomials over General Fields”, SIAM Journal on Computing 36, 779 (2006). DOI
[21]: Alex Samorodnitsky, “Low-degree tests at large distances”. math/0604353
[22]: Sagar Vijay and Liang Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”. 1703.00459

Page edit log

Victor V. Albert (2022-07-28) — most recent
Anqi Gong (2022-07-28)
Victor V. Albert (2021-11-04)

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/tree/main/codes/classical/bits/reed_muller.yml.