Perfect codes in the discrete simplex

Abstract

© 2013, Springer Science+Business Media New York. We study the problem of existence of (nontrivial) perfect codes in the discrete n-simplex Δnℓ ≔ {(x0,...,xn): xi ∈ ℤ+, ∑i xi = ℓ} under ℓ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 Δ1ℓ exist for any ℓ ≥ 2e + 1, the 2-simplex Δ2ℓ admits an e-perfect code if and only if ℓ = 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.