|
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 Bnq that consists of q-ary words of length n and is provided with a metric of deletions and insertions. For any n=1,2,… we present partitions of the space Bn2 and the set of permutations Sn (Sn⊂Bnn) 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 Bnq 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 Bnq with correction of individual deletions as q/n→∞.
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: | 913 | Full-text PDF : | 430 | References: | 1 | First page: | 1 |
|