ISRO EC 2023 Q.22: solution and answer

ISRO 2023 · ECQ.22 · 1 mark · MCQ

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?

ISRO EC 2023 question 22: A radix-2 butterfly signal flow graph with two inputs on the left (top and bottom nodes) and two outputs on the right. — Figure from the ISRO EC 2023 paper. It is part of the question.

(A)
m = 3,4
(B)
m = 4,5
(C)
m = 3,4,5
(D)
m = 2,4,5

Answer and solution

ANSWER

The butterfly with $W_{N}^{6}$ occurs in stages $m = 4, 5$ , which is option (B).

Official answer: BSource: ISRO's revised and final answer key of 16 February 2024

In a radix-2 decimation-in-time FFT of size $N = 32$ , stage $m$ combines sub-DFTs of length $2^{m}$ , so its butterflies use twiddle factors $W_{2^{m}}^{k}$ with $k = 0, 1, \dots, 2^{m - 1} - 1$ .
Since $W_{2^{m}}^{k} = W_{32}^{k \cdot 2^{5 - m}}$ , the twiddle exponents of $W_{32}$ used in stage $m$ are the multiples of $2^{5 - m}$ that are less than $16$ .
The butterfly in the figure has the twiddle $W_{N}^{6} = W_{32}^{6}$ , so we look for the stages whose exponent set contains $6$ .
Stage 1 uses only $W_{32}^{0}$ . Stage 2 uses $W_{32}^{0}, W_{32}^{8}$ . Stage 3 uses $W_{32}^{0}, W_{32}^{4}, W_{32}^{8}, W_{32}^{12}$ . None of these contains $6$ .
Stage 4 uses $W_{32}^{0}, W_{32}^{2}, W_{32}^{4}, \dots, W_{32}^{14}$ , which contains $W_{32}^{6} = W_{16}^{3}$ (here $k = 3 < 8$ ).
Stage 5 uses $W_{32}^{0}, W_{32}^{1}, \dots, W_{32}^{15}$ , which contains $W_{32}^{6}$ .
Hence a butterfly with $W_{N}^{6}$ appears only in stages $m = 4, 5$ .

KEY IDEA

Stage $m$ of a radix-2 DIT FFT uses $W_{2^{m}}^{k} = W_{N}^{k N / 2^{m}}$ for $k < 2^{m - 1}$ , so its $W_{N}$ exponents are multiples of $N / 2^{m}$ below $N /2$ . A given exponent appears only in the stages where it is such a multiple.

WATCH OUT FOR

Assuming every stage uses all the twiddles $W_{N}^{0}, \dots, W_{N}^{N /2 - 1}$ . Early stages use only a few widely spaced ones, so an exponent like $6$ (odd multiple of $2$ ) cannot appear before stage 4.

From the ISRO EC 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 3 ISRO DTFT & DFT questions, with notes

More ISRO DTFT & DFT questions

ISRO EC 2023 Q.20 · MCQ · 1 markGiven a real sequence and 8 point DFT output are X(0) = 5, X(1) = 1 + j, X(2) = 3 + j, X(3) = 2 + 3j.