Alternative names: \(q\)-ary maximum-length feedback-shift-register code.
Description
An \([n,m,q^{m-1}]_q\) equidistant projective code with \(n=\frac{q^m-1}{q-1}\), denoted as \(S(q,m)\). The columns of the generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(m-1,q)\), with each column being a chosen representative of the corresponding element. All nonzero simplex codewords have a constant weight of \(q^{m-1}\) [3,4].
The dual of a \(q\)-ary simplex code is the \([n,n-m,3]_q\) \(q\)-ary Hamming code. A punctured simplex code is known as a \(q\)-ary MacDonald code [5], with parameters \([\frac{q^m-q^u}{q-1},m,q^{m-1}-q^{u-1}]_q\) for \(u \leq m-1\) [6].
Notes
See corresponding MinT database entry [9].Cousins
- Linear \(q\)-ary code— Linear \(q\)-ary 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 code is a direct sum of \(q\)-ary simplex codes [10] (see also Refs. [3,4]).
- Constant-weight block code— Linear \(q\)-ary 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 code is a direct sum of \(q\)-ary simplex codes [10] (see also Refs. [3,4]).
- \(q\)-ary Hamming code— \(q\)-ary Hamming and \(q\)-ary simplex codes are dual to each other.
- Dual linear code— \(q\)-ary Hamming and \(q\)-ary simplex codes are dual to each other.
- Two-weight code— \(q\)-ary MacDonald codes are the unique two-weight codes with weights \(q^{m-1}-q^{m-1}\) and \(q^{m-1}\) [6].
Primary Hierarchy
Parents
Columns of a simplex code’s generator matrix correspond to one-dimensional subspaces of \(\mathbb{F}_q^n\).
Simplex codes saturate the Griesmer bound ([11], Exer. 5.1.11).
Simplex codes and their punctured versions are LP universally optimal codes [12].
\(q\)-ary simplex code
Children
\(q\)-ary simplex codes reduce to simplex codes for \(q=2\).
The tetracode is equivalent to \(S(3,2)\).
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]
- A. E.F. Jr. and H. F. Mattson, “Error-correcting codes: An axiomatic approach”, Information and Control 6, 315 (1963) DOI
- [4]
- E. Weiss, “Linear Codes of Constant Weight”, SIAM Journal on Applied Mathematics 14, 106 (1966) DOI
- [5]
- J. E. MacDonald, “Design Methods for Maximum Minimum-Distance Error-Correcting Codes”, IBM Journal of Research and Development 4, 43 (1960) DOI
- [6]
- A. Patel, “Maximalq-nary linear codes with large minimum distance (Corresp.)”, IEEE Transactions on Information Theory 21, 106 (1975) DOI
- [7]
- W. Fish, J. D. Key, and E. Mwambene, “Partial permutation decoding for simplex codes”, Advances in Mathematics of Communications 6, 505 (2012) DOI
- [8]
- J. D. Key and P. Seneviratne, “Partial permutation decoding for MacDonald codes”, Applicable Algebra in Engineering, Communication and Computing 27, 399 (2016) DOI
- [9]
- Rudolf Schürer and Wolfgang Ch. Schmid. “Simplex Code.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. https://web.archive.org/web/20240420202309/https://mint.sbg.ac.at/desc_CSimplex.html
- [10]
- Bonisoli, Arrigo. “Every equidistant linear code is a sequence of dual Hamming codes.” Ars Combinatoria 18 (1984): 181-186.
- [11]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [12]
- H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
Page edit log
- Victor V. Albert (2022-04-26) — most recent
Cite as:
“\(q\)-ary simplex code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/q-ary_simplex