Alternative names: Shortened Hadamard code, RM\(^*(1,m)\) code, Maximum-length feedback-shift-register code.
Description
A member of the equidistant code family that is dual to the \([2^m-1,2^m-m-1,3]\) Hamming family. The columns of its generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(m-1,2)\), with each column being a chosen representative of the corresponding element. Simplex codes saturate the Plotkin bound and hence have nonzero codewords all of the same weight, \(2^{m-1}\) [3; Th. 11(a)]. The codewords form a \((2^m,2^m+1)\) simplex spherical code under the antipodal mapping.
A punctured simplex code is known as a MacDonald code [4], with parameters \([2^m-2^u,m,2^{m-1}-2^{u-1}]\) for \(u \leq m-1\) [5].
The automorphism group of the code is \(GL_{m}(\mathbb{F}_2)\) [3].
Protection
Simplex codes saturate the Plotkin bound [3; pg. 43].Cousins
- Linear binary code— Linear binary codes cannot be constant weight, but can have nonzero codewords with constant weight. All such codes are equidistant, and Bonisoli’s theorem states that any equidistant linear binary code is a direct sum of simplex codes [9] (see also Refs. [10,11]).
- \([2^r-1,2^r-r-1,3]\) Hamming code— Hamming and simplex codes are dual to each other.
- Dual linear code— Hamming and simplex codes are dual to each other.
- Simplex spherical code— Binary simplex codes map to \((2^m,2^m+1)\) simplex spherical codes under the antipodal mapping [12; Sec. 6.5.2][13; pg. 18]. In other words, simplex (simplex spherical) codes form simplices in Hamming (Euclidean) space.
- \([2^m,m+1,2^{m-1}]\) First-order RM code— First-order RM codes and simplex codes are interconvertible via shortening and lengthening [3; pg. 31]. Punctured first-order RM codes and simplex codes are interconvertible via expurgation and augmentation [3; pg. 31].
- Constant-weight code— Linear binary codes cannot be constant weight, but can have nonzero codewords with constant weight. All such codes are equidistant, and Bonisoli’s theorem states that any equidistant linear binary code is a direct sum of simplex codes [9] (see also Refs. [10,11]).
- Reed-Muller (RM) code— Simplex are equivalent to RM\(^*(1,m)\).
- Simplex integer-based code— Codewords of simplex integer-based codes are restricted to lie in a discrete simplex.
- \([2^r-1, 2r ]\) Gold code— Simplex codes are used to make gold codes. The dual of a Gold code is the intersection of the duals of the simplex codes used to construct it [14].
- Hadamard code— The \([2^m-1,m,2^{m-1}]\) shortened Hadamard code is the simplex code (a.k.a. RM\(^*(1,m)\)).
- \([[2^r-1, 2^r-2r-1, 3]]\) quantum Hamming code— Quantum Hamming codes result from applying the CSS construction to Hamming codes and their duals the simplex codes.
- Subsystem Hypergraph Product Simplex (SHYPS) code— SHYPS code gauge generator matrices are constructed from hypergraph products of simplex codes [15].
Member of code lists
- \(q\)-ary linear codes
- Binary linear codes
- Classical codes
- Classical codes with notable decoders
- Combinatorial designs
- Constant-weight codes
- Cyclic codes
- Evaluation codes
- Locally correctable codes
- Locally decodable codes
- Locally recoverable codes
- MDS codes and friends
- Orthogonal arrays and friends
- Projective codes
- Universally optimal codes
Primary Hierarchy
Parents
Simplex codes can be realized as maximal-length feedback-shift-register codes, and are therefore cyclic [3; pgs. 89 and 216].
Simplex codewords form a 2-design [3; pg. 166].
\(q\)-ary simplex codeGRM Evaluation MDS Projective geometry Linear \(q\)-ary OA LCC LRC Distributed-storage LDC Universally optimal ECC \(t\)-design
\(q\)-ary simplex codes reduce to simplex codes for \(q=2\).
\([2^m-1,m,2^{m-1}]\) simplex code
Children
References
- [1]
- R. A. FISHER, “THE THEORY OF CONFOUNDING IN FACTORIAL EXPERIMENTS IN RELATION TO THE THEORY OF GROUPS”, Annals of Eugenics 11, 341 (1941) DOI
- [2]
- C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 379 (1948) DOI
- [3]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [4]
- J. E. MacDonald, “Design Methods for Maximum Minimum-Distance Error-Correcting Codes”, IBM Journal of Research and Development 4, 43 (1960) DOI
- [5]
- A. Patel, “Maximalq-nary linear codes with large minimum distance (Corresp.)”, IEEE Transactions on Information Theory 21, 106 (1975) DOI
- [6]
- R. R. Green, “A serial orthogonal decoder,” JPL Space Programs Summary, vol. 37–39-IV, pp. 247–253, 1966.
- [7]
- A. Ashikhmin and S. Litsyn, “Simple MAP decoding of first order Reed-Muller and Hamming codes”, Proceedings 2003 IEEE Information Theory Workshop (Cat. No.03EX674) 18 DOI
- [8]
- A. Barg and S. Zhou, “A quantum decoding algorithm for the simplex code”, in Proceedings of the 36th Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, 23–25 September 1998 (UIUC 1998) 359–365
- [9]
- Bonisoli, Arrigo. “Every equidistant linear code is a sequence of dual Hamming codes.” Ars Combinatoria 18 (1984): 181-186.
- [10]
- A. E.F. Jr. and H. F. Mattson, “Error-correcting codes: An axiomatic approach”, Information and Control 6, 315 (1963) DOI
- [11]
- E. Weiss, “Linear Codes of Constant Weight”, SIAM Journal on Applied Mathematics 14, 106 (1966) DOI
- [12]
- Forney, G. D. (2003). 6.451 Principles of Digital Communication II, Spring 2003.
- [13]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
- [14]
- M. des Noes, V. Savin, J. M. Brossier, and L. Ros, “Iterative decoding of Gold sequences”, 2015 IEEE International Conference on Communications (ICC) 4840 (2015) DOI
- [15]
- A. J. Malcolm et al., “Computing Efficiently in QLDPC Codes”, (2025) arXiv:2502.07150
Page edit log
- Victor V. Albert (2022-08-09) — most recent
- Yi-Ting (Rick) Tu (2022-03-28)
Cite as:
“\([2^m-1,m,2^{m-1}]\) simplex code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/simplex