Datapath-regular implementation and scaled technique for N=3×2m DFTs

Discrete Fourier transform (DFT) is used widely in almost all fields of science and engineering, and is generally calculated using the fast Fourier transform (FFT) algorithm. In this paper, we present a fast algorithm for efficiently computing a DFT of size 3×2m. The proposed algorithm decomposes the DFT, obtaining one length-2m unscaled sub-DFT and two length-2m sub-DFTs scaled by constant real numbers. For efficiently computing the scaled sub-DFTs, the constant real factors are attached to twiddle factors, combining them into new twiddle factors. By using this approach, the number of real multiplications is reduced compared with existing algorithms. To obtain regular datapath, a novel implementation method is presented aiming at the implementation of the proposed algorithm and making its datapath regular like the radix-2 FFT algorithm. The method can be applied to other algorithms with L-shape butterfly. Experimental result shows that, the proposed algorithm consumes less processing time than the existing algorithms for all scale DFTs, and than FFTW, a C subroutine library of FFTs, just for small scale DFTs.