Reconstruction of Sequences Over Non-Identical Channels

Autor: Eitan Yaakobi, Michal Horovitz
Rok vydání: 2019
Předmět:
Zdroj: ISIT
ISSN: 1557-9654
0018-9448
DOI: 10.1109/tit.2018.2859813
Popis: Motivated by the error behavior in the DNA storage channel, in this paper, we extend the previously studied sequence reconstruction problem by Levenshtein. The reconstruction problem studies the model in which the information is read through multiple noisy channels, and the decoder, which receives all channel estimations, is required to decode the information. For the combinatorial setup, the assumption is that all the channels cause at most some $t$ errors. Levenshtein considered the case in which all the channels have the same behavior, and we generalize this model and assume that the channels are not identical. Thus, different channels may cause different maximum numbers of errors. For example, we assume that there are $N$ channels, which cause at most $t_{1}$ or $t_{2}$ errors, where $t_{1} , and the number of channels with at most $t_{1}$ errors is at least $\lceil pN\rceil $ , for some fixed $0 . If the information codeword belongs to a code with minimum distance $d$ , the problem is then to find the minimum number of channels that guarantees successful decoding in the worst case. A different problem we study in this paper is where the number of channels is fixed, and the question is finding the minimum distance $d$ that provides exact reconstruction. We study these problems and show how to apply them for the cases of substitutions and transpositions.
Databáze: OpenAIRE