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 t he set are the noisy occurrence times of a periodic event with (perhap s very many) missing measurements. This problem arises in radar pulse repetition interval (PRI) analysis, in bit synchronization in communic ations, and in other scenarios. The proposed algorithms are computatio nally straightforward and converge quickly, A robust version is develo ped that is stable despite the presence of arbitrary outliers. The Euc lidean algorithm approach is justified by a theorem that shows that, f or a set of randomly chosen positive integers, the probability that th ey do not all share a common prime factor approaches one quickly as th e cardinality of the set increases. In the noise-free case, this impli es that the algorithm produces the correct answer with only 10 data sa mples, independent of the percentage of missing measurements, In the c ase of noisy data, simulation results show, for example, good estimati on of the period from 100 data samples with 50% of the measurements mi ssing and 25% of the data samples being arbitrary outliers.