Sung-Hsien HsiehChun-Shien LuSOO-CHANG PEI2019-10-242019-10-24201810512004https://scholars.lib.ntu.edu.tw/handle/123456789/428079https://www.scopus.com/inward/record.uri?eid=2-s2.0-85052479185&doi=10.1016%2fj.dsp.2018.08.009&partnerID=40&md5=3d4abfd108de4a86c71f2d506a0472ffComputing 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≫log⁡N, this has been speeded by Fast Fourier Transform (FFT) with computation cost O(Nlog⁡N). 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+Mlog⁡M) 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.Aliasing; Circulant matrix; Convolution; Cross-correlation; Time delay estimation[SDGs]SDG11Convolution; 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 systemjournal article10.1016/j.dsp.2018.08.0092-s2.0-85052479185