Description
Stub. Define first order (\(r=1\)) and second order.
Rate
Achieves capacity of the binary erasure channel [3].
Parent
Cousins
- Divisible code — An RM\((r,m)\) code is \(2^{\left\lceil m/r\right\rceil-1}\)-divisible, according to McEliece's theorem [4][5].
- 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 weakly self-dual RM codes [6]. 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.
- \(q\)-ary 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 \).
Zoo code information
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]
- S. Kudekar et al., “Reed–Muller Codes Achieve Capacity on Erasure Channels”, IEEE Transactions on Information Theory 63, 4298 (2017). DOI
- [4]
- R. J. McEliece, “On periodic sequences from GF(q)”, Journal of Combinatorial Theory, Series A 10, 80 (1971). DOI
- [5]
- R. J. McEliece, “Weight congruences for p-ary cyclic codes”, Discrete Mathematics 3, 177 (1972). DOI
- [6]
- Sagar Vijay and Liang Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”. 1703.00459
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.