Perfect Codes in the Discrete Simplex

Abstract

We study the problem of existence of (nontrivial) perfect codes in the discrete $n$-simplex ${\Delta }_{\ell }^n:=\left\{\left(\begin{array}{c}{x}_0,\dots ,x_n\end{array}\right):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 ${\Delta }_{\ell }^1$ exist for any $\ell \ge 2e+1$, the $2$-simplex ${\Delta }_{\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.

15 pages (single-column), 5 figures. Minor revisions made. Accepted for publication in Designs, Codes and Cryptography

Cited by in corpus (5)

• Codes in the Space of Multisets---Coding for Permutation Channels with Impairments
• Coding Theorems for Noisy Permutation Channels
• Capacity of Noisy Permutation Channels
• Permutation Capacity Region of Adder Multiple-Access Channels
• Gilbert-Varshamov Bound for Codes in $L_1$ Metric using Multivariate Analytic Combinatorics