WSEAS Transactions on Mathematics
Print ISSN: 1109-2769 , E-ISSN: 2224-2880
Volume 21, 2022
Codes in the q-ary Lee Hypercube
Authors: , ,
Abstract: Let $$Fq ={\left\{ 0, 1, . . . , q − 1\right\} }$$ be an alphabet of size $$ q$$ so that $$F^{n}_{q}$$ is the q-ary hypercube of dimension $$ n $$.
Let $$x = (x1, . . . , xn)$$ and $$y = (y1, . . . , yn)$$ be two elements in $$F^{n}_{q}$$. The Lee distance between $$ x $$ and $$ y $$ is equal to $$ \sum_{i=1}^n min(|xi − yi|, q − |xi − yi|).$$ Let $$ C \subseteq F^{n}_{q}$$; $$ C $$ is called a code. Given an integer radius $$ r \geqslant1,$$ 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 F^{n}_{q}$$ 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 $$ F^{n}_{q} \setminus 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 $$F^{n}_{q}$$ 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 {\left\{4, 5, 6\right\}}, $$ 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.
Search Articles
Keywords: Dominating codes, Covering codes, Locating-dominating codes, Identifying codes, Hamming distance, Lee distance, q-ary hypercube, Graph theory, Combinatorial optimization, Heuristics
Pages: 173-186
DOI: 10.37394/23206.2022.21.24