# Simplex code

## Description

Also known as a maximum length feedback shift register code. 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. Its dual code is the \([n,n-k,3]_q\) \(q\)-ary Hamming code. 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\).

## Decoding

Due to the small size, it can be decoded according to maximum likelihood.Some faster decoders for the \(q=2\) case: [1][2]A quantum decoder for the \(q=2\) case: [3].

## Notes

See corresponding MinT database entry [4].

## Parents

- Projective geometry code — Columns of the simplex code's generator matrix are in one-to-one correspondence with elements of a projective space.
- Griesmer code — Simplex codes saturate the Griesmer bound ([5], Exer. 5.1.11).
- Constant-weight code — All non-zero simplex codewords have a constant weight of \(q^{k-1}\).

## Child

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

## Cousins

- Extended GRS code — \(S(2,k)\) is an extended RS code [4].
- Repetition code — \(S(2,1)\) reduces to the repetition code.
- \(q\)-ary Hamming code — Hamming and simplex codes are dual to each other.
- 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 ([6], pg. 31).

## References

- [1]
- R. R. Green, "A serial orthogonal decoder," JPL Space Programs Summary, vol. 37–39-IV, pp. 247–253, 1966.
- [2]
- 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
- [3]
- 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
- [4]
- 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
- [5]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016). DOI
- [6]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.

## Zoo code information

## Cite as:

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