https://scholars.lib.ntu.edu.tw/handle/123456789/428079
標題: | Fast Computing Position of Maximum of Circulant Convolution | 作者: | Sung-Hsien Hsieh Chun-Shien Lu SOO-CHANG PEI |
關鍵字: | Aliasing; Circulant matrix; Convolution; Cross-correlation; Time delay estimation | 公開日期: | 2018 | 卷: | 83 | 起(迄)頁: | 83-97 | 來源出版物: | Digital Signal Processing: A Review Journal | 摘要: | 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. |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/428079 https://www.scopus.com/inward/record.uri?eid=2-s2.0-85052479185&doi=10.1016%2fj.dsp.2018.08.009&partnerID=40&md5=3d4abfd108de4a86c71f2d506a0472ff |
ISSN: | 10512004 | DOI: | 10.1016/j.dsp.2018.08.009 | SDG/關鍵字: | 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 |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。