Alternative names: 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\). The family is self-orthogonal for \(m \geq 3\) [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)\) [2].
Decoding
First-order RM codes admit specialized decoders, such as the Fast Hadamard Transform decoder [3].Realizations
The \([32, 6, 16]\) RM\((1,5)\) code was used for the 1971 Mariner 9 spacecraft [4].Notes
See Ref. [5] for the weight distribution of the \(2^{26}\) cosets of the \([32,6]\) first-order RM code.Cousins
- Biorthogonal spherical code— Each first-order RM code maps to a \((2^m,2^{m+1})\) biorthogonal spherical code under the antipodal mapping [6][7; Sec. 6.4][8; 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)\)). Rows of a Hadamard matrix forming a Prometheus orthonormal set (PONS) are codewords of a coset of RM\((1,m)\) in RM\((2,m)\) [9].
- \([2^m-1,m,2^{m-1}]\) simplex code— First-order RM codes and simplex codes are interconvertible via shortening and lengthening [2; pg. 31]. Punctured first-order RM codes and simplex codes are interconvertible via expurgation and augmentation [2; 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 [2; 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^{m-1},2^{m-1}-m-1,4]]_{f}\) Hamming Majorana code— A Hamming Majorana code is constructed from a first-order RM code (whose dual is the extended Hamming code).
- \([[2^r, 2^r-r-2, 3]]\) Gottesman code— Gottesman codes can be obtained from a modified CSS construction [10] 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 [10].
- Quantum divisible code— Quantum divisible codes can be constructed out of first-order RM\((1,m)\) codes [11].
- \([[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.
Primary Hierarchy
Parents
\([2^m,m+1,2^{m-1}]\) First-order RM code
Children
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.
References
- [1]
- M. Shi, S. Li, T. Helleseth, and J.-L. Kim, “Binary self-orthogonal codes which meet the Griesmer bound or have optimal minimum distances”, (2023) arXiv:2303.16729
- [2]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [3]
- E.C. Posner, Combinatorial Structures in Planetary Reconnaissance in Error Correcting Codes, ed. H.B. Mann, Wiley, NY 1968.
- [4]
- E. Arikan, “A survey of reed-muller codes from polar coding perspective”, IEEE Information Theory Workshop 2010 (ITW 2010) 1 (2010) DOI
- [5]
- 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
- [6]
- G. D. Forney and G. Ungerboeck, “Modulation and coding for linear Gaussian channels”, IEEE Transactions on Information Theory 44, 2384 (1998) DOI
- [7]
- Forney, G. D. (2003). 6.451 Principles of Digital Communication II, Spring 2003.
- [8]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
- [9]
- 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
- [10]
- A. M. Steane, “Simple quantum error-correcting codes”, Physical Review A 54, 4741 (1996) arXiv:quant-ph/9605021 DOI
- [11]
- 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