On Multiple Deletion Codes
Data(s) |
16/09/2009
16/09/2009
2007
|
---|---|
Resumo |
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. |
Identificador |
Serdica Journal of Computing, Vol. 1, No 1, (2007), 13p-26p 1312-6555 |
Idioma(s) |
en_US |
Publicador |
Institute of Mathematics and Informatics Bulgarian Academy of Sciences |
Palavras-Chave | #Insertion/Deletion Codes #Varshamov-Tennengolts Codes #Multiple Insertion/Deletion Codes |
Tipo |
Article |