Universally optimal \(q\)-ary code[17] 

Description

A binary or \(q\)-ary code that (weakly) minimizes all completely monotonic potentials on binary space [7].

All codes that obtain a linear programming (LP) bound by Delsarte [8] are universally optimal [7]. Such codes are called LP universally optimal or extremal. However, not all universally optimal codes attain the Delsarte LP bound. See [9; Table 12.1] ([7; Table 1]) for a list of (LP) universally optimal codes. See [9; Sec. 12.4] for further discussion.

All codes that attain the Levenshtein bound [14], which estimates the solution to Delsarte's linear program, are universally optimal [5]; see [9; Thm. 12.3.23]. However, not all universally optimal codes attain the Levenshtein bound.

Parents

Children

Cousins

  • Golay code — The Golay code and several of its extended, shortened, and punctured versions are LP universally optimal codes [7].
  • Hadamard code — Several punctured versions of Hadamard codes are LP universally optimal codes [7].
  • Extended Hamming code — Several extended Hamming codes are LP universally optimal codes [7].
  • Kerdock code — Kerdock codes are asymptotically universally optimal [10; Exam. 12.3.25].
  • Constant-weight code — See [3; Table 8.4] for constant-weight universally optimal \(q\)-ary codes.
  • Ternary Golay code — The ternary Golay code and several of its extended, shortened, and punctured versions are LP universally optimal codes [7].
  • Ovoid code — Several shortened and punctured versions of the ovoid code are LP universally optimal codes [7].

References

[1]
V. I. Levenshtein. Bounds for packings of metric spaces and some of their applications. Problemy Kibernet, 40 (1983), 43-110.
[2]
V. I. Levenshtein, “Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces”, IEEE Transactions on Information Theory 41, 1303 (1995) DOI
[3]
V. I. Levenshtein, “Designs as maximum codes in polynomial metric spaces”, Acta Applicandae Mathematicae 29, 1 (1992) DOI
[4]
V. I. Levenshtein, “Universal bounds for codes and designs,” in Handbook of Coding Theory 1, eds. V. S. Pless and W. C. Huffman. Amsterdam: Elsevier, 1998, pp.499-648.
[5]
P. G. Boyvalenkov et al., “Energy bounds for codes and designs in Hamming spaces”, Designs, Codes and Cryptography 82, 411 (2016) DOI
[6]
A. Askikhmin, A. Barg, and S. Litsyn, “Estimates of the distance distribution of codes and designs”, IEEE Transactions on Information Theory 47, 1050 (2001) DOI
[7]
H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
[8]
P. Delsarte, “Bounds for unrestricted codes, by linear programming,” Philips Research Reports, vol. 27, pp. 272–289, 1972
[9]
P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[10]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: univ_opt_q-ary

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

Cite as:

“Universally optimal \(q\)-ary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/univ_opt_q-ary

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/universally_optimal/univ_opt_q-ary.yml.