-
-
Save lukicdarkoo/3f0d056e9244784f8b4a to your computer and use it in GitHub Desktop.
| #include "FFT.h" | |
| void fft(int *x_in, | |
| std::complex<double> *x_out, | |
| int N) { | |
| // Make copy of array and apply window | |
| for (int i = 0; i < N; i++) { | |
| x_out[i] = std::complex<double>(x_in[i], 0); | |
| x_out[i] *= 1; // Window | |
| } | |
| // Start recursion | |
| fft_rec(x_out, N); | |
| } | |
| void fft_rec(std::complex<double> *x, int N) { | |
| // Check if it is splitted enough | |
| if (N <= 1) { | |
| return; | |
| } | |
| // Split even and odd | |
| std::complex<double> odd[N/2]; | |
| std::complex<double> even[N/2]; | |
| for (int i = 0; i < N / 2; i++) { | |
| even[i] = x[i*2]; | |
| odd[i] = x[i*2+1]; | |
| } | |
| // Split on tasks | |
| fft_rec(even, N/2); | |
| fft_rec(odd, N/2); | |
| // Calculate DFT | |
| for (int k = 0; k < N / 2; k++) { | |
| std::complex<double> t = exp(std::complex<double>(0, -2 * M_PI * k / N)) * odd[k]; | |
| x[k] = even[k] + t; | |
| x[N / 2 + k] = even[k] - t; | |
| } | |
| } |
| /* --------------------------------------------------------------------------- | |
| ** Basic implementation of Cooley-Tukey FFT algorithm in C++ | |
| ** | |
| ** Author: Darko Lukic <[email protected]> | |
| ** -------------------------------------------------------------------------*/ | |
| #ifndef FFT_h | |
| #define FFT_h | |
| #include <cmath> | |
| #include <complex> | |
| extern void fft(int *x_in, | |
| std::complex<double> *x_out, | |
| int N); | |
| void fft_rec(std::complex<double> *x, int N); | |
| #endif |
This is a great implementation. No weird data types and building stuff with cmake, just basic, working code.
This is pretty good, but is it actually Cooley-Tukey FFT algorithm? I am looking for a non-recursive FFT algotithm...
It won't give you proper results in case if you want to do some signal processing with it, since, for example, fft of [1, 2, 3] and same signal padded with zero to nearest power of 2 give you completely different results. So i still wondering how to deal with it.
It won't give you proper results in case if you want to do some signal processing with it, since, for example, fft of [1, 2, 3] and same signal padded with zero to nearest power of 2 give you completely different results. So i still wondering how to deal with it.
I think that's just the nature of the algorithm mathematically speaking in order for FFT to work properly you need your number of samples to be a power of two.
amazing