A LOW-COMPLEXITY RECURSIVE ALGORITHM AND COMPACT HARDWARE DESIGN FOR SLIDING DISCRETE FOURIER TRANSFORM

Shin-Chi Lai ； Chia-Chun Tsai

《電機工程學刊》 23卷2期 (2016/04) Pp. 73-81

https://doi.org/10.6329/CIEE.2016.2.05

並列摘要

This paper proposes a novel sliding discrete Fourier transform (DFT) algorithm and architecture design for efficient computation of time-frequency spectrum information. Since the sliding process is handled sample by sample, the spectral bin output data rate can be same as the input data rate. Under the conditions of M-sample real input sequence (M=256) and N-point recursive DFT computation (N=64), the advantages of the proposed method are summarized as follows: 1) Proposed-I requires less computational complexity than Krzysztof Duda’s method. The number of multiplication operations of the proposed algorithm is 44,864 and achieves an 80.35% reduction. In addition, 54.91% of addition operations are reduced. 2) For computing each frequency bin, Proposed-I only requires 4addition and 2 multiplication operations after the first spectral component has been finally calculated; 3) Proposed-II utilizes three registers and a re-timing scheme to effectively shorten and balance the critical path of the proposed design. Moreover, the number of coefficients is reduced by 75% compared to Krzysztof Duda's method. For FPGA implementation, the proposed design can be operated at 43.5 MHz processing rate, which can easily meet the requirements of real-time applications. Therefore, this approach is suitable for real-time analysis of time-frequency spectrum in the future.

並列關鍵字

Discrete Fourier transform (DFT) ； Recursive DFT (RDFT) ； Sliding DFT (SDFT)