From 8f85479f511d67389b89e5df5a992234f9ec926b Mon Sep 17 00:00:00 2001 From: FreeArtMan Date: Thu, 26 Aug 2021 07:54:57 +0100 Subject: Add more words to naitve fft --- md/writeup/naive_fft_implementation_in_c.md | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) diff --git a/md/writeup/naive_fft_implementation_in_c.md b/md/writeup/naive_fft_implementation_in_c.md index 80c1ea6..e5729ee 100644 --- a/md/writeup/naive_fft_implementation_in_c.md +++ b/md/writeup/naive_fft_implementation_in_c.md @@ -84,7 +84,9 @@ DFT speed is $$ O(N^2)$$ and FFT becomes as $$ O(N\log N) $$ -#### Shuffling arrays +#### Shuffling data + +Rearranging data before running FFT ```c void ffti_shuffle_1(double *x_i, double *x_q, uint64_t n) { @@ -134,7 +136,7 @@ void ffti_shuffle_1(double *x_i, double *x_q, uint64_t n) { ``` -#### Implementation +#### FFT Implementation ```c void fft_1(double *x_i, double *x_q, uint64_t n, uint64_t inv) { @@ -191,9 +193,10 @@ void fft_1(double *x_i, double *x_q, uint64_t n, uint64_t inv) { ``` - ## Octave verification code +Quick verification of FFT and DFT with octave code + ```matlab data1 = [1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0] res1 = fft(data1) -- cgit v1.2.3