Low computational complexity, low power, and low area design for the implementation of recursive DFT and IDFT algorithms

A novel recursive algorithm for discrete Fourier transform (DFT) and its inverse transform (IDFT) is proposed in this brief. It was found that the proposed algorithm and its implementation outperformed other existing recursive algorithms. The proposed algorithm was found to 1) reduce multiplication computations by 50.5% using the symmetric identity of coefficients and a resource-sharing technique and register-splitting scheme; 2) decrease read-only memory sizes by 50% compared with conventional algorithms; 3) reduce the number of multipliers implemented by 80% compared with the latest algorithm; and 4) increase data throughput by 100% per transformation. This design is suitable for communication systems and digital radio mondiale (DRM) systems, such as dual-tone multifrequency detection and coded orthogonal frequency-division- multiplexing modulation. The algorithm was designed and fabricated using a 0.18 μm 1P6M complementary metal-oxide-semiconductor process. The core area is 397 × 388 μm², including the DFT and IDFT modules. For modern applications (voice over packet and DRM), this processor only consumes 2.96 mW at 25 MHz. Furthermore, it can calculate the 212/165/106/288/256/176/112-point DFTs and IDFTs.