KIAM Main page Web Library  •  Publication Search  Русский 
Publication

, 2001
Publisher:
IEEE Trans. Inform. Theory, vol.47, no. 1, 2-22, 2001
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
Source text:
  (PS)