\(q\)-ary simplex code

\(q\)-ary simplex code[1,2]

Also known as \(q\)-ary maximum-length feedback-shift-register code.

Description

An \([n,m,q^{m-1}]_q\) 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.

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 [3], with parameters \([[\frac{q^m-q^u}{q-1},m,q^{m-1}-q^{u-1}]]_q\) for \(u \leq m-1\) [4].

Decoding

Permutation decoder [5] and MacDonald [6] codes.

Notes

See corresponding MinT database entry [7].

Parents

Incidence-matrix projective code — Columns of a simplex code's generator matrix correspond to one-dimensional subspaces of \(GF(q)^n\).
Griesmer code — Simplex codes saturate the Griesmer bound ([8], Exer. 5.1.11).
Constant-weight code — All non-zero simplex codewords have a constant weight of \(q^{m-1}\).
Universally optimal \(q\)-ary code — Simplex codes and their punctured versions are LP universally optimal codes [9].

Children

\([2^m-1,m,2^{m-1}]\) simplex code — \(q\)-ary simplex codes reduce to simplex codes for \(q=2\).
Tetracode — The tetracode is equivalent to \(S(3,2)\).

Cousins

\(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}\) [4].

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]: J. E. MacDonald, “Design Methods for Maximum Minimum-Distance Error-Correcting Codes”, IBM Journal of Research and Development 4, 43 (1960) DOI
[4]: A. Patel, “Maximal&lt;tex&gt;q&lt;/tex&gt;-nary linear codes with large minimum distance (Corresp.)”, IEEE Transactions on Information Theory 21, 106 (1975) DOI
[5]: W. Fish et al., “Partial permutation decoding for simplex codes”, Advances in Mathematics of Communications 6, 505 (2012) DOI
[6]: J. D. Key and P. Seneviratne, “Partial permutation decoding for MacDonald codes”, Applicable Algebra in Engineering, Communication and Computing 27, 399 (2016) DOI
[7]: 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://mint.sbg.ac.at/desc_CSimplex.html
[8]: J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
[9]: 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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/projective/q-ary_simplex.yml.