Web Library  •  Publication Searh Publication

 Article, 2001 Publisher: IEEE Trans. Inform. Theory, vol.47, no. 1, 2-22 Authors: Levenshtein V.I. Efficient reconstruction of seguences Abstract: In this paper we introduce and solve some new problems of effective reconstruction of an unknown sequence of a fixed length with the help of its patterns which are distorted by errors of a given type. These patterns can be considered as output sequences for multiple transmission of this sequence over a combinatorial channel with a maximum permissible number of single errors or over a discrete probabilistic channel. The efficiency of recognition is understood in the sense of minimizing the number N of erroneous patterns which are sufficient to reconstruct exactly any unknown sequence or reconstruct it with a preset accuracy and/or with a given probability. This also includes the existence of simple reconstruction algorithms. Complete solutions for combinatorial channels with some types of errors of essential interest in coding theory, namely: substitutions, transpositions, deletions and insertions of symbols are given. For these cases simple reconstruction algorithms based on majority and threshold principles and their non-trivial combination are found. In general, for combinatorial channels the considered problem is reduced to a new problem of reconstructing a vertex of an arbitrary graph with the help of the minimum number of vertices in its metrical ball of a given radius. A certain sufficient condition for solution of this problem is presented. For a discrete memoryless channel asymptotic behavior of the minimum number of repeated transmissions which are sufficient to reconstruct any sequence of length n within the Hamming distance d with error probability ε is found when d/n and ε tends to 0 as n → ∞ . A similar result for the continuous channel with discrete time and additive Gaussian noise is also obtained. Keywords: reconstruction, sequences, optimization, algorithms, graphs, the error metric, combinatorial and probabilistic channels, repeated transmission, reducible reconstructors, asymptotic behavior. Publication language: english,  pages: 20 Research direction: Mathematical problems and theory of numerical methods English source text: List of publications citation: Export link to publication in format:   RIS    BibTeX About authors: Levenshtein V. I.,  KIAM RAS