Optimal detection of a~recurring tuple of reference fragments in a~quasi-periodic sequence

A. V. Kel'manov ; L. V. Mikhailova ; S. A. Khamidullin

Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 11 (2008) no. 3, pp. 311-327

Résumé

The a posteriori (off-line) approach to solving the problem of maximum-likelihood detection of a recurring tuple containing reference fragments in a numerical quasi-periodic sequence is studied. The case is analyzed, where (1) the total number of fragments in a sequence is unknown; (2) the index of a sequence term corresponding to the beginning of a fragment is a deterministic (not random) value; (3) a sequence distorted by an additive uncorrelated Gaussian noise is available for observation. It is shown that the problem under consideration is reduced to testing a set of simple hypotheses about the mean of a random Gaussian vector. The cardinality of this totality exponentially grows as the vector dimension (i.e., the length of a sequence understudy) increases. It is established that the search for a maximum-likelihood hypothesis is equivalent to finding the arguments which yield a maximum for an auxiliary objective function. It is shown that maximizing this objective function is reduced to solving a special optimization problem. It is proven that this special problem is a polynomial-solvable one. The exact algorithm for solving this problem is substantiated, which underlies the algorithm for the optimal (maximum-likelihood) detection of the recurring tuple. The kernel of this algorithm is the algorithm for solution of a special (basic) optimization problem. The results of numerical simulation are presented.