Codes in the q-ary Lee Hypercube
WSEAS (World Scientific and Engineering Academy and Society)
Transactions on Mathematics, Vol. 21, pp. 173-186, 2022.
Irène CHARON (*), Olivier HUDRY (*), Antoine LOBSTEIN (**)
(*) Institut polytechnique de Paris, Télécom Paris, 91123 Palaiseau
(**) Laboratoire Interdisciplinaire des Sciences du Numérique (UMR 9015), CNRS, Université Paris-Saclay, 91400 Orsay
Abstract. Let Fq = {0, 1, ... , q - 1} be an alphabet of size q, so that Fqn is the q-ary hypercube of dimension n. Let x = (x1, ..., xn) and y = (y1, ... , yn) be two elements in Fqn. The Lee distance between x and y is equal to Σi=1n min(|xi - yi|, q - |xi - yi|). Let C ⊆ Fqn; C is called a code. Given an integer radius r >0, we consider three types of codes with respect to the Lee distance: an r-dominating code C (also called an r-covering code) is such that any element x in Fqn is within distance r from at least one codeword c in C (then c r-dominates x); an r-locating-dominating code C is (i) r-dominating and (ii) such that any two vertices x, y in Fqn∖C are r-dominated by distinct sets of codewords; an r-identifying code C is (i) r-dominating and (ii) such that any two vertices x, y in Fqn are r-dominated by distinct sets of codewords. We look for minimum such codes. For the above three types of codes, we give tables of upper bounds on their smallest cardinalities, for alphabet size q in {4,5,6}, dimension n up to 7, and radius r up to 5. These bounds are obtained mainly by using different heuristics (greedy, descent, noising). We conclude with conjectures and open problems.