On Multiple Deletion Codes

Landjev, Ivan; Haralambiev, Kristiyan

Serdica Journal of Computing (2007)

  • Volume: 1, Issue: 1, page 13-26
  • ISSN: 1312-6555

Abstract

top
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.

How to cite

top

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 -

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.