Modifications of the Euclidean Algorithm for Isolating Periodicities from a Sparse Set of Noisy Measurements.

摘要

Modifications of the Euclidean algorithm are presented for determining the period from a sparse set of noisy measurements. The elements of the set are the noisy occurrence times of a periodic event with (perhaps very many) missing measurements. This problem arises in radar pulse repetition interval (PRI) analysis, in bit synchronization in communications, and other scenarios. The proposed algorithms are computationally straightforward and converge quickly. A robust version is developed that is stable despite the presence of arbitrary outliers. The Euclidean algorithm approach is justified by a theorem which shows that, for a set of randomly chosen positive integers, the probability that they do not all share a common prime factor approaches one quickly as the cardinality of the set increases. In the noise-free case this implies convergence with only ten data samples, independent of the percentage of missing measurements. In the case of noisy data simulation results show, for example, good estimation of the period from one hundred data samples with fifty percent of the measurements missing and twenty five percent of the data samples being arbitrary outliers.