From 6b0a499024166602128c586e73604461828c792a Mon Sep 17 00:00:00 2001
From: FreeArtMan <dos21h@gmail.com>
Date: Wed, 25 Aug 2021 09:52:04 +0100
Subject: Update fft implementation

---
 md/writeup/naive_fft_implementation_in_c.md | 18 +++++++++++++++---
 1 file changed, 15 insertions(+), 3 deletions(-)

(limited to 'md/writeup')

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
-- 
cgit v1.2.3