Fast Computing Position of Maximum of Circulant Convolution
Journal
Digital Signal Processing: A Review Journal
Journal Volume
83
Pages
83-97
Date Issued
2018
Author(s)
Abstract
Computing the position of maximum of circulant convolution has been used for many applications in image and signal processing, and it usually is time-critical. Given the signal length N and the template size K, the conventional procedure requires O(KN) operations. With K≫logN, this has been speeded by Fast Fourier Transform (FFT) with computation cost O(NlogN). This paper proposes a fast but heuristic scheme, returning only the position of maximum of convolution instead of the whole sequence after convolution. The main idea is to alias both the signal and template into lower dimensional space with the same dimension M being smaller than N and K, respectively. Thus, the computation cost is reduced to O(N+MlogM) operations with M=Ω(N), where M is the only user-defined parameter and plays the trade-off between the computation cost and successfully returning the position of the maximum. To guide how to decide M, we show that the sufficient condition of successfully returning the position of the maximum depends on the relationship between the maximum convolution and remaining convolution results based on three different cases, i.e., K≤M, K>M with M exactly dividing N or not exactly dividing N. We further show how the probability of success can be analyzed if both the signal and template are random. Simulations validate the proposed scheme is fast and efficient, and they support the theoretical results. A case study with synchronization in global positioning system (GPS) is taken as a case study to demonstrate the applicability of our method. © 2018 Elsevier Inc.
Subjects
Aliasing; Circulant matrix; Convolution; Cross-correlation; Time delay estimation
SDGs
Other Subjects
Convolution; Economic and social effects; Fast Fourier transforms; Signal processing; Aliasing; Circulant matrix; Cross correlations; Dimensional spaces; Heuristic schemes; Probability of success; Time delay estimation; User-defined parameters; Global positioning system
Type
journal article