Modifications of the Euclidean algorithm for isolating periodicities from a sparse set of noisy measurements
Authors:
- B.M. SadlerBSB.M. Sadler
- 1 September 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 44 (9) , 2260-2272
Abstract
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 in 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 that 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 that the algorithm produces the correct answer 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% of the measurements missing and 25% of the data samples being arbitrary outliers.Keywords
This publication has 16 references indexed in Scilit:
- Parameter estimation of cyclostationary AM time series with application to missing observationsIEEE Transactions on Signal Processing, 1994
- Nonparametric cyclic-polyspectral analysis of AM signals and processes with missing observationsIEEE Transactions on Information Theory, 1993
- Performance evaluation of zero-crossing-based bit synchronizersIEEE Transactions on Communications, 1989
- Optimal ARMA parameter estimation based on the sample covariances for data with missing observationsIEEE Transactions on Information Theory, 1989
- A zero crossing-based spectrum analyzerIEEE Transactions on Acoustics, Speech, and Signal Processing, 1986
- Number Theory in Science and Communication1986
- Estimating the frequency of a noisy sinusoid by linear regression (Corresp.)IEEE Transactions on Information Theory, 1985
- A Classical Introduction to Modern Number Theory1982
- Spectral Analysis with Randomly Missed Observations: The Binomial CaseThe Annals of Mathematical Statistics, 1965
- Spectral Analysis with Regularly Missed ObservationsThe Annals of Mathematical Statistics, 1962