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.

reconstruction, sequences, optimization, algorithms, graphs, the error metric, combinatorial and probabilistic channels, repeated transmission, reducible reconstructors, asymptotic behavior.

Mathematical problems and theory of numerical methods