This project presents a recursive Python implementation of the Radix-2 Fast Fourier Transform (FFT) algorithm in obtaining the discrete fourier transform (DFT) of a discrete set of data points whose count follows any power of 2.
It also provides several examples on analyzing the frequency information and composition of given periodic and non-periodic signals (e.g. square waves, exponential decay), verifying the properties of the DFT in relation to the Nyquist-Shannon theorem and continuous fourier transform (CFT), and the application of FFT to polynomial multiplication and function convolution.
This project also discusses the mathematical theories (e.g. frequency detection, inner product interpretation, matrix interpretation, polynomial evaluation) behind the FFT algorithm and program results through algebraic derivations and visualizations in the complex plane.
Based on the results of this program, the high efficiency and versatility of the radix-2 FFT algorithm in transforming data between the physical and frequency domains enables it to be utilized in applications such as signal processing and mathematical analysis.