RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1991 Volume 3, Issue 1, Pages 3–20 (Mi dm771)

This article is cited in 3 papers

Perfect codes in the metric of deletions and insertions

V. I. Levenshtein


Abstract: We consider a problem of packing and covering a metric space $B^n_q$ that consists of $q$-ary words of length $n$ and is provided with a metric of deletions and insertions. For any $n=1,2,\dots $ we present partitions of the space $B^n_2$ and the set of permutations $S_n$ $(S_n\subset B^n_n)$ into perfect codes with correction of individual deletions. In connection with a problem of constructing ordered codes with correction of $s$ deletions we formulate a problem of constructing ordered Steiner systems and give a solution of this problem for certain values of the parameters. We construct codes complete in $B^n_q$ with correction of individual deletions for $n=3$ and any $q$, and also for $n=4$ and any even $q$. We find the asymptotic behavior of the maximum cardinality of the code in $B^n_q$ with correction of individual deletions as $q/n\to\infty$.

UDC: 519.72, 519.1

Received: 28.12.1989


 English version:
Discrete Mathematics and Applications, 1992, 2:3, 241–258

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025