\([2^m,m+1,2^{m-1}]\) First-order RM code 

Also known as Biorthogonal code, RM\((1,m)\) code, Augmented Hadamard code.

Description

A member of the family of first-order RM codes. Its codewords are the rows of the \(2^m\)-dimensional Hadamard matrix \(H\) and its negation \(-H\) with the mapping \(+1\to 0\) and \(-1\to 1\). They form a \((2^m,2^{m+1})\) biorthogonal spherical code under the antipodal mapping.

The automorphism group of the code is \(GA_{m}(\mathbb{F}_{2})\) [1].

Decoding

First-order RM codes admit specialized decoders, such as the Fast Hadamard Transform decoder [2].

Realizations

The \([32, 6, 16]\) RM\((1,5)\) code was used for the 1971 Mariner 9 spacecraft [3].

Notes

See Ref. [4] for the weight distribution of the \(2^{26}\) cosets of the \([32,6]\) first-order RM code.

Parent

Child

  • \([8,4,4]\) extended Hamming code — The \([8,4,4]\) extended Hamming code is a first-order RM code because it is self-dual and first-order RM codes are dual to extended Hamming codes.

Cousins

  • Biorthogonal spherical code — Each first-order RM code maps to a \((2^m,2^{m+1})\) biorthogonal spherical code under the antipodal mapping [5][6; Sec. 6.4][7; pg. 19]. In other words, first-order RM (biorthogonal spherical) codes form orthoplexes in Hamming (Euclidean) space.
  • Dual polytope code — Orthoplexes and hypercubes are dual to each other.
  • 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)\)). Rows of a Hadamard matrix forming a Prometheus orthonormal set (PONS) are codewords of a coset of RM\((1,m)\) in RM\((2,m)\) [8].
  • \([2^m-1,m,2^{m-1}]\) simplex code — First-order RM codes and simplex codes are interconvertible via shortening and lengthening [1; pg. 31]. Punctured first-order RM codes and simplex codes are interconvertible via expurgation and augmentation [1; pg. 31].
  • \([2^r,2^r-r-1,4]\) Extended Hamming code — Extended Hamming and first-order RM codes are dual to each other.
  • Kerdock code — Kerdock code is a subcode of a second-order RM Code [1; pg. 457]. It consists of a number of cosets of RM\((2,m)\) created by quotienting with first-order RM\((1,m)\) codes.
  • Levenshtein code — First-order RM codes and Levenshtein codes are both constructed using Hadamard matrices.
  • \([[2^r, 2^r-r-2, 3]]\) Gottesman code — Gottesman codes can be obtained from a modified CSS construction [9] with a \([2^r,r+1,2^{r-1}] = C_2^{\perp}\) first-order RM code and a \([2^r,2^r-1,2] = C_1\) even-weight code [9].
  • Quantum divisible code — Quantum divisible codes can be constructed out of first-order RM\((1,m)\) codes [10].
  • \([[2^r-1,1,3]]\) simplex code — The \([[2^r-1,1,3]]\) simplex code is constructed with a punctured first-order RM code and its even subcode.

References

[1]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[2]
E.C. Posner, Combinatorial Structures in Planetary Reconnaissance in Error Correcting Codes, ed. H.B. Mann, Wiley, NY 1968.
[3]
E. Arikan, “A survey of reed-muller codes from polar coding perspective”, IEEE Information Theory Workshop 2010 (ITW 2010) (2010) DOI
[4]
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
[5]
G. D. Forney and G. Ungerboeck, “Modulation and coding for linear Gaussian channels”, IEEE Transactions on Information Theory 44, 2384 (1998) DOI
[6]
Forney, G. D. (2003). 6.451 Principles of Digital Communication II, Spring 2003.
[7]
T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
[8]
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
[9]
A. M. Steane, “Simple quantum error-correcting codes”, Physical Review A 54, 4741 (1996) arXiv:quant-ph/9605021 DOI
[10]
J. Hu, Q. Liang, and R. Calderbank, “Divisible Codes for Quantum Computation”, (2022) arXiv:2204.13176
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: biorthogonal

Cite as:
“\([2^m,m+1,2^{m-1}]\) First-order RM code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/biorthogonal
BibTeX:
@incollection{eczoo_biorthogonal, title={\([2^m,m+1,2^{m-1}]\) First-order RM code}, booktitle={The Error Correction Zoo}, year={2024}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/biorthogonal} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/biorthogonal

Cite as:

“\([2^m,m+1,2^{m-1}]\) First-order RM code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/biorthogonal

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