diff options
Diffstat (limited to 'md/writeup/naive_fft_implementation_in_c.md')
| -rw-r--r-- | md/writeup/naive_fft_implementation_in_c.md | 18 |
1 files changed, 15 insertions, 3 deletions
diff --git a/md/writeup/naive_fft_implementation_in_c.md b/md/writeup/naive_fft_implementation_in_c.md index 6d7293e..80c1ea6 100644 --- a/md/writeup/naive_fft_implementation_in_c.md +++ b/md/writeup/naive_fft_implementation_in_c.md @@ -25,18 +25,23 @@ IOWA FFT source on implementation side. ### DFT +Formula for most simple Discreate Fourier Transformation. Also most slowest one. + +Official DFT formula $$X(k) = F_{D}[x(nT)] = $$ $$ \sum_{n=0}^{N-1} x(nT) e^{-jk\omega nT} , k=0,1,...,N-1 $$ +My wording of DFT algorithm: +Go over data array and sumup multiplication of each "frequency" $$e^{-jk\omega nT}$$ over data array $$x(nT)$$ + + + ```c void dft(double *x_i, double *x_q, int n, int inv) { double Wn,Wk; - //static array - //double Xi[DATA_SIZE],Xq[DATA_SIZE]; - //dynamic array double *Xi, *Xq; double c,s; int i,j; @@ -72,6 +77,13 @@ void dft(double *x_i, double *x_q, int n, int inv) { } ``` ### FFT + +This is more advanced version of Fourier Transformation, with rearrangement of data there is possible to +reduce amount of calculations and that give speed increase. +DFT speed is +$$ O(N^2)$$ +and FFT becomes as $$ O(N\log N) $$ + #### Shuffling arrays ```c |