Simplex code[1,2] 

Also known as Maximum-length feedback-shift-register code.

Description

An \([n,k,q^{k-1}]_q\) projective code with \(n=\frac{q^k-1}{q-1}\), denoted as \(S(q,k)\). The columns of the generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(k-1,q)\), with each column being a chosen representative of the corresponding element. The name of the code comes from the property that, for \(q=2\), the codewords form a \((2^k-1)\)-simplex of constant edge length if the codewords are interpreted as points in \(\mathbb{R}^n\).

The dual of a simple code is the \([n,n-k,3]_q\) \(q\)-ary Hamming code. A punctured simplex code is known as a MacDonald code [3], with parameters \([[\frac{q^k-q^u}{q-1},k,q^{k-1}-q^{u-1}]]_q\) for \(u \leq k-1\) [4].

Decoding

Permutation decoder for simplex [5] and MacDonald [6] codes.Decoders for the \(q=2\) case: [7,8]A quantum decoder for the \(q=2\) case: [9].

Notes

See corresponding MinT database entry [10].

Parents

Child

  • Tetracode — The tetracode is equivalent to \(S(3,2)\).

Cousins

  • Extended GRS code — \(S(2,k)\) is an extended RS code [10].
  • Repetition code — \(S(2,1)\) reduces to the repetition code.
  • \(q\)-ary Hamming code — Hamming and simplex codes are dual to each other.
  • Hadamard code — Binary simplex codes are \([2^m-1,m,2^{m-1}]\) shortened Hadamard codes.
  • Simplex spherical code — Binary simplex codes map to simplex spherical codes under the antipodal mapping [13; Sec. 6.5.2][14; pg. 18]. In other words, simplex (simplex spherical) codes form simplices in Hamming (Euclidean) space.
  • Reed-Muller (RM) code — Binary simplex codes can be constructed from the generator matrix of RM\((1,k)\) by removing first the all-ones row, and then the all-zero column. Punctured RM codes and simplex codes are interconvertible via expurgation and augmentation ([15], pg. 31).
  • Two-weight code — MacDonald codes are the unique two-weight codes with weights \(q^{k-1}-q^{u-1}\) and \(q^{k-1}\) [4].
  • Gold code — Simplex codes are used to make gold codes. The dual of a Gold code is the interesection of the duals of the simplex codes used to construct it [16].

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<tex>q</tex>-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]
R. R. Green, "A serial orthogonal decoder," JPL Space Programs Summary, vol. 37–39-IV, pp. 247–253, 1966.
[8]
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) DOI
[9]
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
[10]
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. http://mint.sbg.ac.at/desc_CSimplex.html
[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
[13]
Forney, G. D. (2003). 6.451 Principles of Digital Communication II, Spring 2003.
[14]
T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
[15]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[16]
M. des Noes et al., “Iterative decoding of Gold sequences”, 2015 IEEE International Conference on Communications (ICC) (2015) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: simplex

Cite as:
“Simplex code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/simplex
BibTeX:
@incollection{eczoo_simplex, title={Simplex code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/simplex} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/simplex

Cite as:

“Simplex code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/simplex

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