Optimal Ternary Codes with Weight $w$ and Distance $2w-2$ in ${\ell }_1$-Metric

Abstract

The study of constant-weight codes in ${\ell }_1$-metric was motivated by the duplication-correcting problem for data storage in live DNA. It is interesting to determine the maximum size of a code given the length $n$, weight $w$, minimum distance $d$ and the alphabet size $q$. In this paper, based on graph decompositions, we determine the maximum size of ternary codes with constant weight $w$ and distance $2w-2$ for all sufficiently large length $n$. Previously, this was known only for a very sparse family $n$ of density $4/w(w-1)$.

13 pages, 1 figure