BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2007 >
Volume 1 Number 1 >

Please use this identifier to cite or link to this item:

Title: On Multiple Deletion Codes
Authors: Landjev, Ivan
Haralambiev, Kristiyan
Keywords: Insertion/Deletion Codes
Varshamov-Tennengolts Codes
Multiple Insertion/Deletion Codes
Issue Date: 2007
Publisher: Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation: Serdica Journal of Computing, Vol. 1, No 1, (2007), 13p-26p
Abstract: 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.
ISSN: 1312-6555
Appears in Collections:Volume 1 Number 1

Files in This Item:

File Description SizeFormat
sjc005-vol1-num1-2007.pdf146.81 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License