1. Design of a recursive single-bin DFT algorithm for sparse spectrum analysis
- Author
-
Wei Wang, Wang Kening, Xiongxing Zhang, and Ying Tang
- Subjects
Cooley–Tukey FFT algorithm ,Computer Networks and Communications ,Computer science ,Bluestein's FFT algorithm ,Fast Fourier transform ,02 engineering and technology ,01 natural sciences ,Discrete Fourier transform ,Spectral line ,010309 optics ,Discrete Fourier transform (general) ,Cyclotomic fast Fourier transform ,0103 physical sciences ,0202 electrical engineering, electronic engineering, information engineering ,Digital signal processing ,Butterfly diagram ,business.industry ,Prime-factor FFT algorithm ,Short-time Fourier transform ,020206 networking & telecommunications ,Frequency spectrum ,Split-radix FFT algorithm ,Rader's FFT algorithm ,Bruun's FFT algorithm ,business ,Algorithm ,Software ,Goertzel algorithm ,Twiddle factor - Abstract
Discrete Fourier transform (DFT) is the basic means of spectrum analysis in the field of digital signal processing, and the fast Fourier transform (FFT) has become the most popular algorithm which decreases the computational complexity from quadratical to linearithmic. However, engineers are often challenged to detect a single or just a few of the frequency components. For this kind of sparse spectrum analysis, the FFT no longer has advantage because it always computes all the frequency components. This paper proposes a recursive single-bin DFT (RSB-DFT) algorithm to compute one specific frequency spectrum, whose theoretical derivation is elaborated and implementation steps are given as a flow diagram. A 16-point RSB-DFT calculation example is also given to exhibit computation process of the algorithm. An application example for bioimpedance spectroscopy (BIS) measurement demonstrates that the proposed RSB-DFT algorithm can compute specific single spectral lines accurately. The computation efficiency of the proposed RSB-DFT algorithm is demonstrated as the highest compared with the DFT, FFT, Goertzel algorithm, which means that the RSB-DFT algorithm has the potential to become an alternative and efficient tool for sparse spectrum analysis.
- Published
- 2017