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

Shin Chi Lai, Sheau Fang Lei, Chia Lin Chang, Chen Chieh Lin, Ching Hsing Luo

Research output: Contribution to journalArticlepeer-review

27 Citations (Scopus)

Abstract

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 μm2, 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.

Original languageEnglish
Pages (from-to)921-925
Number of pages5
JournalIEEE Transactions on Circuits and Systems II: Express Briefs
Volume56
Issue number12
DOIs
Publication statusPublished - 2009 Dec 1

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Low computational complexity, low power, and low area design for the implementation of recursive DFT and IDFT algorithms'. Together they form a unique fingerprint.

Cite this