On Multiple Deletion Codes

Landjev, Ivan, and Haralambiev, Kristiyan. "On Multiple Deletion Codes." Serdica Journal of Computing 1.1 (2007): 13-26. <http://eudml.org/doc/11409>.

@article{Landjev2007,
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.},
author = {Landjev, Ivan, Haralambiev, Kristiyan},
journal = {Serdica Journal of Computing},
keywords = {Insertion/Deletion Codes; Varshamov-Tennengolts Codes; Multiple Insertion/Deletion Codes; insertion/deletion codes; Varshamov-Tennengolts codes; multiple insertion/ deletion codes},
language = {eng},
number = {1},
pages = {13-26},
publisher = {Institute of Mathematics and Informatics Bulgarian Academy of Sciences},
title = {On Multiple Deletion Codes},
url = {http://eudml.org/doc/11409},
volume = {1},
year = {2007},
}

TY - JOUR
AU - Landjev, Ivan
AU - Haralambiev, Kristiyan
TI - On Multiple Deletion Codes
JO - Serdica Journal of Computing
PY - 2007
PB - Institute of Mathematics and Informatics Bulgarian Academy of Sciences
VL - 1
IS - 1
SP - 13
EP - 26
AB - 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.
LA - eng
KW - Insertion/Deletion Codes; Varshamov-Tennengolts Codes; Multiple Insertion/Deletion Codes; insertion/deletion codes; Varshamov-Tennengolts codes; multiple insertion/ deletion codes
UR - http://eudml.org/doc/11409
ER -