Reed-Muller (RM) code[1][2]

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

Internal code ID: reed_muller

Your contribution is welcome!

on github.com (edit & pull request)

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} }
Permanent link:
https://errorcorrectionzoo.org/c/reed_muller

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.