|
This article is cited in 3 scientific papers (total 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$.
Received: 28.12.1989
Citation:
V. I. Levenshtein, “Perfect codes in the metric of deletions and insertions”, Diskr. Mat., 3:1 (1991), 3–20; Discrete Math. Appl., 2:3 (1992), 241–258
Linking options:
https://www.mathnet.ru/eng/dm771 https://www.mathnet.ru/eng/dm/v3/i1/p3
|
Statistics & downloads: |
Abstract page: | 848 | Full-text PDF : | 402 | First page: | 1 |
|