Computational Complexity FFT V/S Direct Computation

COMPUTATIONAL COMPLEXITY FFT V/S DIRECT COMPUTATION

For Radix-2 algorithm value of N is given as N= 2^V

Hence value of v is calculated as

V= log10 N / log10 ² = log₂ N

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 N² multiplication operation & N² – N addition operations.

MEMORY REQUIREMENTS AND IN PLACE COMPUTATION

From 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.

Thus for 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).