GATE 2024 IN Q.25: solution and answer

GATE 2024 · INQ.25 · 1 mark · NAT

The number of complex multiplications required for computing a 16-point DFT using the decimation-in-time radix-2 FFT is __________ (in integer).

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

A 16-point radix-2 DIT FFT needs $\frac{N}{2} lo g_{2} N = 8 \times 4 = 32$ complex multiplications.

Official answer: 32Source: Official answer key, GATE 2024 IN (IISc Bengaluru)

Number of stages (radix-2 FFT). $N = 16 = 2^{4}$ , so the DIT FFT has $lo g_{2} N = 4$ stages.
Butterflies per stage. Each stage combines the $N$ points in pairs, so there are $\frac{N}{2} = 8$ butterflies per stage.
Cost of one DIT butterfly. The butterfly computes $A^{'} = A + W_{N}^{k} B$ and $B^{'} = A - W_{N}^{k} B$ . The product $W_{N}^{k} B$ is formed once and used in both outputs, so each butterfly needs 1 complex multiplication and 2 complex additions. (The standard count treats every twiddle-factor product as one complex multiplication, even when $W_{N}^{k}$ is $1$ or $- j$ .)
Total multiplications. $Complex multiplications = \frac{N}{2} lo g_{2} N = 8 \times 4 = 32$
Check against the direct DFT. Computing the DFT directly needs $N^{2} = 256$ complex multiplications, so the FFT cuts the count by a factor of $256/32 = 8$ . The FFT's complex additions number $N lo g_{2} N = 64$ .

KEY IDEA

A radix-2 FFT of length $N = 2^{m}$ has $lo g_{2} N$ stages, each with $N /2$ butterflies. Each DIT butterfly needs one complex multiplication, by the twiddle factor $W_{N}^{k}$ , and two complex additions. That gives $\frac{N}{2} lo g_{2} N$ multiplications and $N lo g_{2} N$ additions in total.

WATCH OUT FOR

There are three usual slips. The first is counting two multiplications per butterfly (one for each output), which gives $N lo g_{2} N = 64$ , but the product $W_{N}^{k} B$ is computed once and shared by both outputs. The second is answering with the direct-DFT count $N^{2} = 256$ . The third is counting only the non-trivial twiddle products, skipping every $W_{N}^{k}$ equal to $1$ or $- j$ . That gives a smaller number, but it is not the standard count the question asks for.

From the GATE 2024 IN paper. Every question of this paper · Download the full paper · All 11 DTFT & DFT questions, with notes

GATE 2024 IN Q.25: solution and answer

Answer and solution

More DTFT & DFT questions