Alternative names: Multiset code.
Description
An integer-based code over the \(\ell_1\) metric whose codewords are restricted to lie in a discrete simplex.
Discrete simplex: The discrete simplex \(\Delta_{q,N}\) of dimension \(q-1\) and discretization \(N\) is the set of length-\(q\) non-negative integer strings whose coordinates add up to \(N\), \begin{align} \Delta_{q,N}=\left\{ \mathbf{n}\in\mathbb{Z}_{\geq 0}^{q}\,|\,\sum_j n_j =N\right\}~. \tag*{(1)}\end{align} The number of points in a discrete simplex is \begin{align} |\Delta_{q,N}|=\binom{N+q-1}{q-1}\,. \tag*{(2)}\end{align}
Protection
There is a GV bound for simplex integer-based codes over the \(\ell_1\) metric [4–7]. Existence of certain codes is guaranteed by constructing Sidon sets per the Bose-Chowla theorem [8][2; Thm. 14].Cousins
- DNA storage code— Simplex integer-based codewords are intended to model multisets of DNA molecules [2]. Points in a discrete simplex are in one-to-one correspondence to multisets because their coordinates denote the multiplicity of each element in a given multiset [2].
- Simplex spherical code— Codewords of simplex integer-based codes are restricted to lie in a discrete simplex.
- \([2^m-1,m,2^{m-1}]\) simplex code— Codewords of simplex integer-based codes are restricted to lie in a discrete simplex.
- Permutation-invariant (PI) code— Simplex integer-based codes can be partitioned into qudit PI codewords whose error-correction is guaranteed by the Tverberg theorem [9; Thm. VII.5].
Member of code lists
Primary Hierarchy
Parents
Simplex integer-based code
References
- [1]
- D. J. C. MacKay, J. Sayir, and N. Goldman, “Near-Capacity Codes for Fountain Channels with Insertions, Deletions, and Substitutions, with Applications to DNA Archives,” Unpublished manuscript, 2015.
- [2]
- M. Kovacevic and V. Y. F. Tan, “Codes in the Space of Multisets—Coding for Permutation Channels With Impairments”, IEEE Transactions on Information Theory 64, 5156 (2018) arXiv:1612.08837 DOI
- [3]
- L. Sok, J.-C. Belfiore, P. Sole, and A. Tchamkerten, “Lattice Codes for Deletion and Repetition Channels”, IEEE Transactions on Information Theory 64, 1595 (2018) DOI
- [4]
- V. D. Kolesnik and V. Y. Krachkovsky, “Generating functions and lower bounds on rates for limited error-correcting codes”, IEEE Transactions on Information Theory 37, 778 (1991) DOI
- [5]
- J. Gu and T. Fuja, “A generalized Gilbert-Varshamov bound derived via analysis of a code-search algorithm”, IEEE Transactions on Information Theory 39, 1089 (1993) DOI
- [6]
- L. M. G. M. Tolhuizen, “The generalized Gilbert-Varshamov bound is implied by Turan’s theorem [code construction]”, IEEE Transactions on Information Theory 43, 1605 (1997) DOI
- [7]
- K. Goyal, D. Tu Dao, M. Kovačević, and H. Mao Kiah, “Gilbert–Varshamov Bound for Codes in L₁ Metric Using Multivariate Analytic Combinatorics”, IEEE Transactions on Information Theory 71, 244 (2025) arXiv:2402.14712 DOI
- [8]
- R. C. Bose and S. Chowla, “Theorems in the additive theory of numbers”, Commentarii Mathematici Helvetici 37, 141 (1962) DOI
- [9]
- A. Aydin, V. V. Albert, and A. Barg, “Quantum error correction beyond \(SU(2)\): spin, bosonic, and permutation-invariant codes from convex geometry”, (2025) arXiv:2509.20545
Page edit log
- Victor V. Albert (2025-10-24) — most recent
Cite as:
“Simplex integer-based code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2025. https://errorcorrectionzoo.org/c/simplex_discrete