Bounds and Constructions for Multi-Symbol Duplication Error Correcting Codes
pith:ELXX3GQK Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{ELXX3GQK}
Prints a linked pith:ELXX3GQK badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
In this paper, we study codes correcting $t$ duplications of $\ell$ consecutive symbols. These errors are known as tandem duplication errors, where a sequence of symbols is repeated and inserted directly after its original occurrence. Using sphere packing arguments, we derive non-asymptotic upper bounds on the cardinality of codes that correct such errors for any choice of parameters. Based on the fact that a code correcting insertions of $t$ zero-blocks can be used to correct $t$ tandem duplications, we construct codes for tandem duplication errors. We compare the cardinalities of these codes with their sphere packing upper bounds. Finally, we discuss the asymptotic behavior of the derived codes and bounds, which yields insights about the tandem duplication channel.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Central Limit Theorem for Mutation Systems
A central limit theorem is established for stochastic fluctuations of empirical k-tuple frequencies in mutation systems, with an explicit limiting covariance matrix derived via spectral projection and martingale methods.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.