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.
- 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)\)).
- \([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 [8] 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 [8].
- Quantum divisible code — Quantum divisible codes can be constructed out of first-order RM\((1,m)\) codes [9].
- \([[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]
- A. M. Steane, “Simple quantum error-correcting codes”, Physical Review A 54, 4741 (1996) arXiv:quant-ph/9605021 DOI
- [9]
- J. Hu, Q. Liang, and R. Calderbank, “Divisible Codes for Quantum Computation”, (2022) arXiv:2204.13176
Page edit log
- Victor V. Albert (2024-04-26) — most recent
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