Home | | **Discrete Time Systems and Signal Processing** | 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= 2^{V}

Hence value of v is calculated as

V= log10 N / log10 ^{2} =
log_{2} 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^{2}
multiplication operation & N^{2} – 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 |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.