On Multiple Deletion Codes
DOI:
https://doi.org/10.55630/sjc.2007.1.13-26Keywords:
Insertion/Deletion Codes, Varshamov-Tennengolts Codes, Multiple Insertion/Deletion CodesAbstract
In 1965 Levenshtein introduced the deletion correcting codes and found an asymptotically optimal family of 1-deletion correcting codes. During the years there has been a little or no research on t-deletion correcting codes for larger values of t. In this paper, we consider the problem of finding the maximal cardinality L2(n;t) of a binary t-deletion correcting code of length n. We construct an infinite family of binary t-deletion correcting codes. By computer search, we construct t-deletion codes for t = 2;3;4;5 with lengths n ≤ 30. Some of these codes improve on earlier results by Hirschberg-Fereira and Swart-Fereira. Finally, we prove a recursive upper bound on L2(n;t) which is asymptotically worse than the best known bounds, but gives better estimates for small values of n.
References
Ginzburg B. D. A number-theoretic function with an application in the theory of coding. Problemy Kibernetiki 19 (1967), 249–252 (in Russian); English translation: Systems Theory Research 19 (1970), 255–259.
Helberg A. S. J., H. C. Fereira. On multiple insertion/deletion correcting codes. IEEE Trans. Inf. Theory 48 (2002), 305–308.
Hirschberg D. S., M. Reigner. Tight bounds on the number of string subsequences. J. of Disc. Algorithms 1 (2000), 123–132.
Levenshtein V. Binary codes capable of correcting deletions, insertions and reversals. Dokl. Akad. Nauk SSSR 163 (1965), 845–848 (in Russian); English translation: Soviet Phys.-Dokl. 10 (1966), 707–710.
Levenshtein V. On perfect codes in the insertion/deletion metric. Diskr. Mat. 3 (1991), 3–20. (in Russian); English translation: Discrete Math. and Applications 2 (1992), 241–258.
Levenshtein V. Efficient reconstruction of sequences
from their subsequences or supersequences. J. Comb. Theory Ser. A 93 (2001), 310–332.
Levenshtein V. Bounds for insertion-deletion-correcting codes. IEEE Int Symp. on Inf. Theory 2002, Lausanne, Switzerland.
Martirosyan S. Single-error correcting close packed and perfect codes. In: Proc. of the 1st INTAS Int. Seminar on Coding Theory and Combinatorics, Thakhadzor, Armenia, 1996, 90–115.
Sloane N. J. A. On single-deletion-correcting codes. In:
Codes and Designs, Ohio State University, May 2000 (Ray-Chaudhuri Festschrift), (eds K. T. Arasu, A. Seress), Walter de Gruyter, Berlin, 2002, 273–291.
Swart T. G., H. C. Fereira. A note on double insertion/deletion correcting codes. IEEE Trans. Inf Theory 49 (2003), 269–272.
Tolhuizen L. Upper bounds on the size of insertion/deletion-correcting codes. Proc. of the 8th Workshop on ACCT, Tsarskoe Selo, Russia, 2002, 242–246.
Varshamov R. R. On an arithmetic function with an application in the theory of coding. Dokl. Akad. Nauk SSSR 161 (1965), 540–543 (in Russian).
Varshamov R. R., G. M. Tenengolts. Codes which correct a single asymmetric error. Avtomatika i Telemehanika 26, No 2, (1965), 288–292 (in Russian); English translation: Automation and remote control 26 (1965), 286–290.
