Skip to content

spacekitcat/cooley-tukey-fast-fourier-transform

Repository files navigation

In-place Cooley-Tukey FFT implementation

This is a toy FFT implementation. Numpy has a fantastic production quality implementation

Note: Source code is here, sorry about all the boiler plate, I used some project generator and shouldn't have!

Fourier transforms are really cool and I want to learn the maths and concepts behind it all. This continues from fourier-exp-01, a small C program that performs a temporal to frequency domain transform. This is a port of the C program, Python seems to have a better selection of libraries for parsing wave files, drawing graphs and doing maths.

This project includes a Python implementation of the Discrete Fourier Transform (DFT) in the C project above, it also contains an implementation of the Cooley-Tukey Fast Fourier Transform (FFT). The key differences between this project and the earlier C project is that this one uses Python's built in support for complex numbers, it also uses the correct divisor in the argument for the complex exponent operation (which expands cis(x)).

Building

git clone github.com/spacekitcat/<repository-name>
cd <repository-name>
python setup.py develop
python src/cooley-tukey-fast-fourier-transform-implentation/fft.py resources/440hz.wav

The graph below shows the frequency graph for an input wave file made up of a single 440hz sine wave.

A graph with the frequencies from 0hz to 20050hz plotted along the x-axis (the frequency domain) and the magnitude plotted along the y-axis (the amplitude or magnitude, i.e. the contribution this frequency makes to the signal). The graph spikes at 440hz, showing 440hz as the dominant frequency

The graph below shows the frequency graph for an input wave file made up of a 500hz and a 1200hz sine wave.

A graph with the frequencies from 0hz to 20050hz plotted along the x-axis (the frequency domain) and the magnitude plotted along the y-axis (the amplitude or magnitude, i.e. the contribution this frequency makes to the signal). The graph spikes at 500hz and 1200hz, showing 500hz and 1200hz as the dominant frequencies

Learning Material

Fourier Series (Dover Books on Mathematics) - Georgi P. Tolstov

Wikipedia: Cooley–Tukey FFT algorithm

About

Toy implementation of the Cooley-Tukey Fast Fourier Transform (FFT) with a comparison to the Numpy FFT and a DFT

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages