A Fast Algorithm Based on SRFFT for Length N = q x 2(m) DFTs

作者：Zheng, Weihua^*; Li, Kenli; Li, Keqin

来源：IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS, 2014, 61(2): 110-114.

DOI：10.1109/TCSII.2013.2291098

• Fast Fourier transform (FFT)
• modified split-radix FFT (MSRFFT)
• radix 2/8 FFT algorithm
• scaled discrete Fourier transform (SDFT)
• split-radix FFT (SRFFT)

In this brief, we present a fast algorithm for computing length-q x 2(m) discrete Fourier transforms (DFT). The algorithm divides a DFT of size-N = q x 2(m) decimation in frequency into one length-N/2 DFT and two length-N/4 DFTs. The length-N/2 sub-DFT is recursively decomposed decimation in frequency, and the two size-N/4 sub-DFTs are transformed into two dimension and the terms with the same rotating factor are arranged in a column. Thus, the scaled DFTs (SDFTs) are obtained, simplifying the real multiplications of the proposed algorithm. A further improvement can be achieved by the application of radix-2/8, modified split-radix FFT (MSRFFT), and Wang's algorithm for computing its length-2(m) and length-q sub-DFTs. Compared with the related algorithms, a substantial reduction of arithmetic complexity and more accurate precision are obtained.

• 出版日期2014-2
• 单位湖南大学