Home | | Discrete Time Systems and Signal Processing | Computational Complexity FFT V/S Direct Computation

# Computational Complexity FFT V/S Direct 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.

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 = log2 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 N2 multiplication operation & N2 – 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).

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Digital Signal Processing : Frequency Transformations : Computational Complexity FFT V/S Direct Computation |