Modifications of the Euclidean Algorithm for Isolating Periodicities from a Sparse Set of Noisy Measurements
Casey, Stephen D.
Sadler, Brian M.
MetadataShow full item record
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 10 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 100 data samples with 50 percent of the measurements missing and 25 percent of the data samples being arbitrary outliers.