FFT-optimointimenetelmät
Kehrä Halme · Aaltodoc (Aalto University) · 2026
Discrete Fourier transform (DFT) is widely used in various applications, such as signal processing and communication systems. However, direct calculation of DFT has a high computational complexity of (2) operations. In an effort to reduce computational complexity, an algorithm known as the fast Fourier transform (FFT) was introduced. Calculating the DFT via FFT reduces the computational complexity significantly, from (2) operations to ( log ) operations. Since the introduction of FFT in the 1960’s, multiple variants of the FFT have been introduced to improve design aspects, such as computational efficiency, memory usage, latency and power consumption. The main objective of this thesis is to provide an overview of the FFT and its variants, as well as examine, which hardware parameters each variant optimize. Algorithms surveyed include Cooley-Tukey FFT, Winograd Fourier transform algorithm (WFTA), split-radix, mixed radix and prime factor algorithm. Additionally, a brief overview of three broad architecture categories is provided. The thesis was conducted as a literature survey. According to prior studies, the Cooley-Tukey FFT algorithm appears to be the most commonly used FFT algorithm. Cooley-Tukey FFT reduces the computational complexity of the DFT. Additionally, the reuse of butterfly units allows for better area efficiency. Split-radix FFT requires the least arithmetic operations out of the power-of-two FFT variants. Meaning that out of the power-of-two variants, it is the most power efficient. Mixed-radix provides more flexibility on the choice of N, while retaining a relatively low computational complexity. Winograd Fourier transform algorithm and prime factor algorithm do not require a multiplication by the twiddle factor, making them more area efficient.