A Top-Down Design Methodology for Approximate Fast Fourier Transform (FFT) Design

The fast Fourier transform (FFT) is a crucial algorithm in digital communication and sensor signal processing, making it an essential component of computer systems. Recently, with the popularity of human perception-related tasks, the requirements of full precision and exactness are not always necessary for FFT-based applications. Unlike many prior work that deploy approximate arithmetic circuits from bottom-up to build the complex FFT, we propose a top-down design methodology for approximate FFT design to fully exploit the error-tolerance nature of the FFT algorithm. Our approach consists of error modeling, approximation optimization, and design implementation. Experimental results on both simulation and RTL implementation show that the proposed approximate FFT can achieve up to 52% area-delay product improvement and 23% energy saving when compared to a conventional exact FFT design. When compared to other approximate FFT designs, the proposed design is found to cover almost 2 times wider precision range with higher energy efficiency. When the proposed design is applied to an audio classification system, the resulting loss in accuracy is around 1%, further demonstrating the practical potential of this approach.