[DSP] radix-2 DIT and DIF algorithms

by JJ91
Tags: algorithms, radix2
JJ91 is offline
Nov20-12, 02:57 PM
P: 41
1. The problem statement, all variables and given/known data


I literally can't see difference between DIT and DIF algorithms. Would be kind enough to explain a difference between two algorithms ?

Both algorithms have the same number of multiplications and additions for given signal:
[itex]\frac{N}{2}[/itex]log[itex]_{2}[/itex](N) - No. of Multiplications
Nlog[itex]_{2}[/itex](N) - No. of additions

Decimation in Time:

Decimation in Frequency:

3. The attempt at a solution
By looking into butterfly diagrams of both it can be seen that DIT starts from operation on pair of inputs ending on single multiplication at the last stage of FFT where is DIF starts from individual inputs computation ending on computation of pair of inputs.

In practice, what does that mean? How does that affect system?
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language

Register to reply

Related Discussions
probabilistic algorithms vs. deterministic algorithms Linear & Abstract Algebra 0
Is there an easy way to find the radix r? Electrical Engineering 4
Radix r Set Theory, Logic, Probability, Statistics 12