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