Error-Free Communication in the Presence of Duplication Errors
Kovačević, Mladen
arXiv, Tome 2019 (2019) no. 0, / Harvested from
This paper is concerned with the problem of error-free communication over the i.i.d. duplication channel which acts on a transmitted sequence $ x_1 \cdots x_n $ by inserting a random number of copies of each symbol $ x_i $ next to the original symbol. The random variables representing the numbers of inserted copies at each position $ i $ are independent and take values in $ \{0, 1, \ldots, r\} $, where $ r $ is a fixed parameter. A more general model in which blocks of $ \ell $ consecutive symbols are being duplicated, and which is inspired by DNA-based data storage systems wherein the stored molecules are subject to tandem-duplication mutations, is also analyzed. A construction of optimal codes correcting all patterns of errors of this type is described, and the zero-error capacity of the duplication channel---the largest rate at which information can be transmitted through it in an error-free manner---is determined for each $ \ell $ and $ r $.
Publié le : 2019-02-17
Classification:  Computer Science - Information Theory,  Computer Science - Discrete Mathematics,  94A24, 94B25, 94B50
@article{1902.06275,
     author = {Kova\v cevi\'c, Mladen},
     title = {Error-Free Communication in the Presence of Duplication Errors},
     journal = {arXiv},
     volume = {2019},
     number = {0},
     year = {2019},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1902.06275}
}
Kovačević, Mladen. Error-Free Communication in the Presence of Duplication Errors. arXiv, Tome 2019 (2019) no. 0, . http://gdmltest.u-ga.fr/item/1902.06275/