Cross correlation is a general way to estimate time delay of arrival (TDOA), with a computational complexity of O(n log n) using fast Fourier transform. However, since only one spike is required for time delay estimation, complexity can be further reduced. Guided by Chinese Remainder Theorem (CRT), this paper presents a new approach called Co-prime Aliased Sparse FFT (CASFFT) in O(n1-1/d log n) multiplications and O(mn) additions, where m is smooth factor and d is stage number. By adjusting these parameters, it can achieve a balance between runtime and noise robustness. Furthermore, it has clear advantage in parallelism and runtime for a large range of signal-to-noise ratio (SNR) conditions. The accuracy and feasibility of this algorithm is analyzed in theory and verified by experiment.
Bei ZHAO
Hangzhou DianZi University
Chen CHENG
Zhejiang University
Zhenguo MA
Zhejiang University
Feng YU
Zhejiang University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Bei ZHAO, Chen CHENG, Zhenguo MA, Feng YU, "Time Delay Estimation via Co-Prime Aliased Sparse FFT" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 12, pp. 2566-2570, December 2016, doi: 10.1587/transfun.E99.A.2566.
Abstract: Cross correlation is a general way to estimate time delay of arrival (TDOA), with a computational complexity of O(n log n) using fast Fourier transform. However, since only one spike is required for time delay estimation, complexity can be further reduced. Guided by Chinese Remainder Theorem (CRT), this paper presents a new approach called Co-prime Aliased Sparse FFT (CASFFT) in O(n1-1/d log n) multiplications and O(mn) additions, where m is smooth factor and d is stage number. By adjusting these parameters, it can achieve a balance between runtime and noise robustness. Furthermore, it has clear advantage in parallelism and runtime for a large range of signal-to-noise ratio (SNR) conditions. The accuracy and feasibility of this algorithm is analyzed in theory and verified by experiment.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.2566/_p
Copy
@ARTICLE{e99-a_12_2566,
author={Bei ZHAO, Chen CHENG, Zhenguo MA, Feng YU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Time Delay Estimation via Co-Prime Aliased Sparse FFT},
year={2016},
volume={E99-A},
number={12},
pages={2566-2570},
abstract={Cross correlation is a general way to estimate time delay of arrival (TDOA), with a computational complexity of O(n log n) using fast Fourier transform. However, since only one spike is required for time delay estimation, complexity can be further reduced. Guided by Chinese Remainder Theorem (CRT), this paper presents a new approach called Co-prime Aliased Sparse FFT (CASFFT) in O(n1-1/d log n) multiplications and O(mn) additions, where m is smooth factor and d is stage number. By adjusting these parameters, it can achieve a balance between runtime and noise robustness. Furthermore, it has clear advantage in parallelism and runtime for a large range of signal-to-noise ratio (SNR) conditions. The accuracy and feasibility of this algorithm is analyzed in theory and verified by experiment.},
keywords={},
doi={10.1587/transfun.E99.A.2566},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - Time Delay Estimation via Co-Prime Aliased Sparse FFT
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2566
EP - 2570
AU - Bei ZHAO
AU - Chen CHENG
AU - Zhenguo MA
AU - Feng YU
PY - 2016
DO - 10.1587/transfun.E99.A.2566
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2016
AB - Cross correlation is a general way to estimate time delay of arrival (TDOA), with a computational complexity of O(n log n) using fast Fourier transform. However, since only one spike is required for time delay estimation, complexity can be further reduced. Guided by Chinese Remainder Theorem (CRT), this paper presents a new approach called Co-prime Aliased Sparse FFT (CASFFT) in O(n1-1/d log n) multiplications and O(mn) additions, where m is smooth factor and d is stage number. By adjusting these parameters, it can achieve a balance between runtime and noise robustness. Furthermore, it has clear advantage in parallelism and runtime for a large range of signal-to-noise ratio (SNR) conditions. The accuracy and feasibility of this algorithm is analyzed in theory and verified by experiment.
ER -