Topic: Networks, Signals and Systems
The butterfly in fig. is taken from radix 2 decimation in time FFT with $N=32$. Assume that the five stages of the signal flow graph are indexed by $m=1,2,3,4,5$, where 5 is the last stage. Which of the five stages has butterflies of this form? (Image shows twiddle factor $W_{N}^{6}$)
- A. $m=3,4$
- B. $m=4,5$
- C. $m=3,4,5$
- D. $m=2,4,5$
Answer: B. $m=4,5$
Explanation: In an N-point Radix-2 Decimation-In-Time (DIT) FFT, the twiddle factors at stage $m$ are of the form $W_N^k$, where $k$ is an integer multiple of $N / 2^m$. Here, $N = 32$, and the given twiddle factor is $W_{32}^6$. The index $k = 6$ must be a multiple of $32 / 2^m = 2^{5-m}$.
For $m=3$, the step is $32/8 = 4$. Multiples are $0, 4, 8, 12\dots$ (6 is not a multiple).
For $m=4$, the step is $32/16 = 2$. Multiples are $0, 2, 4, 6, 8\dots$ (6 is a valid multiple).
For $m=5$, the step is $32/32 = 1$. Multiples are $0, 1, 2, 3, 4, 5, 6\dots$ (6 is a valid multiple).
Thus, the twiddle factor $W_{32}^6$ can appear in stages $m=4$ and $m=5$.