Low-complexity hopping DFT design based on a compact recursive structure

A novel hopping discrete Fourier transform (DFT) algorithm and its architecture design for efficiently computing time-frequency spectra are presented. Since the sliding process is adopted sample by sample, the spectral bin output data rate is the same as the input data rate. Under the conditions of an M-sample complex input sequence (M = 256), and N-point recursive DFT computation (N = 64) for time hop L (L = 4), the proposed method has the following advantages: (i) the computational complexity of Proposed-I requires only four complex additions and four complex multiplications for each frequency bin, after the first spectral component has been finally calculated; (ii) Proposed-II utilises a re-timing scheme to greatly shorten and balance the critical path; (iii) Proposed-II is less computationally complex than Wang et al.'s method, as the numbers of multiplication and addition operations in the proposed algorithm are 768 and 1024, representing reductions of 50 and 20%, respectively. In addition, the number of coefficients can be reduced by 50% compared with Park et al.'s method. In the FPGA implementation, the proposed design can be operated at 47.26 MHz. It is thus more suitable for use with real-time analytic applications of time-frequency spectra.