COMPUTATIONAL COMPLEXITY FFT V/S DIRECT COMPUTATION
For Radix-2 algorithm value of N is
given as N= 2V
Hence value of v is calculated as
V= log10 N / log10 2 =
Thus if value of N is 8 then the
value of v=3. Thus three stages of decimation. Total number of butterflies will
be Nv/2 = 12.
If value of N is 16 then the value
of v=4. Thus four stages of decimation. Total number of butterflies will be
Nv/2 = 32.
Each butterfly operation takes two
addition and one multiplication operations. Direct computation requires N2
multiplication operation & N2 – N addition operations.
MEMORY REQUIREMENTS AND IN PLACE COMPUTATION
values a and b new values A and B are computed. Once A and B are computed,
there is no need to store a and b. Thus same memory locations can be used to
store A and B where a and b were stored hence called as In place computation.
The advantage of in place computation is that it reduces memory requirement.
computation of one butterfly, four memory locations are required for storing
two complex numbers A and B. In every stage there are N/2 butterflies hence
total 2N memory locations are required. 2N locations are required for each
stage. Since stages are computed successively these memory locations can be
shared. In every stage N/2 twiddle factors are required hence maximum storage
requirements of N point DFT will be (2N + N/2).