Description
A binary or \(q\)-ary code that (weakly) minimizes all completely monotonic potentials on binary space [7].
All codes that attain the 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 [1–4], 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
- \([2^r-1,2^r-r-1,3]\) Hamming code — Binary Hamming codes and several of their extended, punctured, and shortened versions are LP universally optimal codes [7].
- Conference code — Conference codes are LP universally optimal codes [7].
- Maximum distance separable (MDS) code — MDS codes are LP universally optimal codes [7].
- \(q\)-ary Hamming code — Hamming codes and their punctured and shortened versions are LP universally optimal codes [7].
- \(q\)-ary simplex code — Simplex codes and their punctured versions are LP universally optimal codes [7].
- \(q\)-ary sharp configuration — All \(q\)-ary sharp configurations are universally optimal \(q\)-ary codes [7], but the converse is not true.
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 Hadamard codes are LP universally optimal codes [7].
- \([2^r,2^r-r-1,4]\) 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
- Victor V. Albert (2023-03-05) — most recent
- Alexander Barg (2023-03-05)
- Victor V. Albert (2023-02-24)
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