Perfect Codes in the Discrete Simplex

We study the problem of existence of (nontrivial) perfect codes in the discrete $n$-simplex $Δ_{\ell}^n := \left\{ \begin{pmatrix} x_0, \ldots, x_n \end{pmatrix} : x_i \in \mathbb{Z}_{+}, \sum_i x_i = \ell \right\}$ under $\ell_1$ metric. The problem is motivated by the so-called multiset codes, which have recently been introduced by the authors as appropriate constructs for error correction in the permutation channels. It is shown that $e$-perfect codes in the $1$-simplex $Δ_{\ell}^1$ exist for any $\ell \geq 2e + 1$, the $2$-simplex $Δ_{\ell}^2$ admits an $e$-perfect code if and only if $\ell = 3e + 1$, while there are no perfect codes in higher-dimensional simplices. In other words, perfect multiset codes exist only over binary and ternary alphabets.

No reviews yet.

No comments yet.