Home /
Expert Answers /
Computer Science /
the-radix-2-butterfly-is-an-atomic-computation-in-dft-engines-the-equation-and-the-diagram-looks-as-pa188
(Solved): The Radix-2 butterfly is an atomic computation in DFT engines. The equation and the diagram looks as ...
The Radix-2 butterfly is an atomic computation in DFT engines. The equation and the
diagram looks as the below.
a radix-2 decimation-in-time FFT algorithm on n=2^(P) inputs with respect to a
primitive n-th root of unity \omega _(n)^(k)=e^(-(2rik)/(n)) relies on O(nlog_(2)n) butterflies of the form:
{[y_(0)=x_(0)+x_(1)\omega _(n)^(k)],[y_(1)=x_(0)-x_(1)\omega _(n)^(k)]}
A. Create a 'data flow graph' i.e, a task graph of how you would arrive at the solution of
the expression after evaluating the terms in the right order.
B. How many multipliers, adders, subtractors are needed.
C. If the multiplier takes 3 clock cycles, and adder & subtractor takes 1 clock cycles.
What would be the #clock cycles for the complete expression to be evaluated.
D. Mention the schedule (time taken) at each level of the graph.
Hints and Basic assumptions:
Keep it simple. Optimization and operator sharing is not expected.
The problem is not to provide a solution to the Digital Fourier Transform (DFT), but to
create the "data flow graph" of the equation which is used repeatedly in carrying out the
DFT.