Reconstruction of Sequences Over Non-Identical Channels
Autor: | Eitan Yaakobi, Michal Horovitz |
---|---|
Rok vydání: | 2019 |
Předmět: |
0301 basic medicine
Computer science Code word 0102 computer and information sciences Data_CODINGANDINFORMATIONTHEORY 02 engineering and technology Library and Information Sciences 01 natural sciences Electronic mail Read through Combinatorics 03 medical and health sciences 0202 electrical engineering electronic engineering information engineering Computer Science::Information Theory Mathematics Noise measurement Minimum distance 020206 networking & telecommunications Computer Science Applications 030104 developmental biology Reconstruction problem 010201 computation theory & mathematics Algorithm Decoding methods Information Systems Communication channel |
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 |
Externí odkaz: |