GATE EC · EE · IN

DTFT, DFT and FFT

The DTFT gives the spectrum of a discrete-time signal as a continuous function of digital frequency that repeats every $2 π$ . The DFT is $N$ equally spaced samples of that spectrum, computed from a finite block of data, and the FFT is a fast algorithm that computes exactly the same DFT. The working toolkit is small: a table of standard pairs, a few properties (Parseval, the shifts, the value at $ω = 0$ or $k = 0$ ), circular convolution, DFT symmetry and the FFT operation counts. Fix the conventions first and the algebra stays short.

11 previous-year questions · 11 solved · 5 practice questions

The DTFT: definition, convention and existence

The discrete-time Fourier transform (DTFT) writes a sequence $x [n]$ as a continuum of complex exponentials $e^{j ω n}$ . Convention used throughout these notes: $ω$ is the normalised digital frequency in rad/sample, the transform is written $X (e^{j ω})$ , and the $1/2 π$ sits in the inverse. Some texts write $Ω$ for this same variable, or use $f = ω /2 π$ in cycles/sample; the $f$ form is given below. The notation $X (e^{j ω})$ is a reminder that the DTFT is the bilateral z-transform evaluated on the unit circle, whenever the ROC includes the unit circle.

Because $e^{j (ω + 2 π) n} = e^{j ω n}$ for every integer $n$ , the DTFT is always periodic in $ω$ with period $2 π$ . One period, $- π < ω \leq π$ (or $0 \leq ω < 2 π$ ), carries all the information. Low frequencies sit near $ω = 0$ and near every multiple of $2 π$ ; the highest frequency a sequence can have is $ω = π$ , the sequence $(- 1)^{n}$ . When $x [n] = x_{a} (n T_{s})$ comes from sampling at $F_{s} = 1/ T_{s}$ , a component at analog frequency $F$ (in Hz) appears at $ω = 2 π F / F_{s}$ , read modulo $2 π$ : a component with $∣ F ∣ > F_{s} /2$ lands at the same $ω$ as a lower frequency (aliasing).

DTFT (ANALYSIS EQUATION)

X (e^{j ω}) = n = - \infty \sum \infty x [n] e^{- j ω n}

Bilateral sum over all $n$ , with $ω$ in rad/sample. Defined when the sum converges (see existence below).

INVERSE DTFT (SYNTHESIS EQUATION)

x [n] = \frac{1}{2 π} \int_{- π}^{π} X (e^{j ω}) e^{j ω n} d ω

The integral may be taken over any interval of length $2 π$ . In the $ω$ convention the $1/2 π$ belongs to the inverse.

CYCLES-PER-SAMPLE FORM

X (f) = n = - \infty \sum \infty x [n] e^{- j 2 π f n}, x [n] = \int_{- 1/2}^{1/2} X (f) e^{j 2 π f n} df

The same transform in $f = ω /2 π$ cycles/sample: the period is $1$ instead of $2 π$ and there is no $1/2 π$ in the inverse. For a sampled signal, $f = F / F_{s}$ .

PERIODICITY

X (e^{j (ω + 2 π k)}) = X (e^{j ω}), k any integer

Holds for every sequence. So $ω = 3 π /2$ and $ω = - π /2$ are the same frequency.

LINK TO THE Z-TRANSFORM

X (e^{j ω}) = X (z)_{z = e^{j ω}}

$X (z)$ is the bilateral z-transform. Valid only if the ROC of $X (z)$ contains the unit circle $∣ z ∣ = 1$ . For an LTI system this is the frequency response $H (e^{j ω})$ , which exists as an ordinary function when the system is BIBO stable.

DTFT OF A SAMPLED SIGNAL

x [n] = x_{a} (n T_{s}) \Rightarrow X (e^{j ω}) = F_{s} k = - \infty \sum \infty X_{a} (\frac{( ω - 2 π k ) F _{s}}{2 π})

Here $X_{a} (F) = \int_{- \infty}^{\infty} x_{a} (t) e^{- j 2 π F t} d t$ is the continuous-time Fourier transform of $x_{a} (t)$ , with $F$ in Hz. The DTFT of the samples is the analog spectrum, scaled by $F_{s}$ , with $F$ replaced by $ω F_{s} /2 π$ and repeated every $2 π$ . If $X_{a} (F) = 0$ for $∣ F ∣ \geq F_{s} /2$ the copies do not overlap, and $X (e^{j ω}) = F_{s} X_{a} (ω F_{s} /2 π)$ for $∣ ω ∣ \leq π$ .

Existence. Three cases matter. (i) If $x [n]$ is absolutely summable, the sum converges uniformly to a continuous function of $ω$ ; every stable impulse response is in this class. (ii) If $x [n]$ is only square summable (finite energy), the sum converges in the mean-square sense and $X (e^{j ω})$ may have jumps. The ideal low-pass sequence $sin (ω_{c} n) / (π n)$ is the standard example, and truncating its sum produces the Gibbs overshoot near $ω = \pm ω_{c}$ . (iii) Some sequences that are neither, such as $1$ , $u [n]$ , $e^{j ω_{0} n}$ and $cos (ω_{0} n)$ , have a DTFT only in the generalised sense, with impulses $δ (ω)$ repeated every $2 π$ . Growing sequences such as $2^{n} u [n]$ have no DTFT at all, not even a generalised one; they need the z-transform.

SUFFICIENT CONDITION FOR EXISTENCE

n = - \infty \sum \infty ∣ x [n] ∣ < \infty \Rightarrow ∣ X (e^{j ω}) ∣ \leq n = - \infty \sum \infty ∣ x [n] ∣ < \infty

Absolute summability is sufficient, not necessary: finite-energy sequences such as the sinc sequence also have a DTFT, in the mean-square sense.

VALUES AT SPECIAL POINTS

X (e^{j 0}) = n \sum x [n], X (e^{j π}) = n \sum (- 1)^{n} x [n], x [0] = \frac{1}{2 π} \int_{- π}^{π} X (e^{j ω}) d ω

Put $ω = 0$ or $ω = π$ in the analysis equation, or $n = 0$ in the inverse. These evaluate such sums and integrals without finding $X (e^{j ω})$ at all.

EXAM TIP

Read the limits of a frequency integral. Because $X (e^{j ω})$ is $2 π$ -periodic, $\int_{- π}^{π} X (e^{j ω}) d ω = 2 π x [0]$ , but $\int_{- 2 π}^{2 π} X (e^{j ω}) d ω = 4 π x [0]$ . Count how many periods the integral covers before applying the inverse formula.

Standard DTFT pairs

Learn these pairs in the $ω$ convention. Every entry is periodic with period $2 π$ ; in the impulse entries the sum over $k$ makes that explicit. Sinc convention used here: $sinc (x) = sin (π x) / (π x)$ , so $sinc (0) = 1$ and its zeros are at the non-zero integers.

$x [n]$	$X (e^{j ω})$	Condition / note
$δ [n]$	$1$	All $ω$
$δ [n - n_{0}]$	$e^{- j ω n_{0}}$	Integer $n_{0}$ ; linear phase
$a^{n} u [n]$	$\frac{1}{1 - a e ^{- j ω}}$	$∣ a ∣ < 1$ (right-sided)
$- a^{n} u [- n - 1]$	$\frac{1}{1 - a e ^{- j ω}}$	$∣ a ∣ > 1$ (left-sided)
$n a^{n} u [n]$	$\frac{a e ^{- j ω}}{( 1 - a e ^{- j ω} ) ^{2}}$	$∣ a ∣ < 1$ ; differentiation in frequency
$(n + 1) a^{n} u [n]$	$\frac{1}{( 1 - a e ^{- j ω} ) ^{2}}$	$∣ a ∣ < 1$
$a^{∣ n ∣}$	$\frac{1 - a ^{2}}{1 - 2 a cos ω + a ^{2}}$	Real $a$ , $∣ a ∣ < 1$ ; real and even
$1$ for $∣ n ∣ \leq M$ , else $0$	$\frac{sin ( ( 2 M + 1 ) ω /2 )}{sin ( ω /2 )}$	Length $2 M + 1$ ; real and even; value $2 M + 1$ at $ω = 0$
$1$ for $0 \leq n \leq N - 1$ , else $0$	$e^{- j ω (N - 1) /2} \frac{sin ( N ω /2 )}{sin ( ω /2 )}$	Length $N$ ; the same kernel times a linear phase
$\frac{sin ( ω _{c} n )}{π n}$	$1$ for $∣ ω ∣ \leq ω_{c}$ , $0$ for $ω_{c} < ∣ ω ∣ \leq π$	$0 < ω_{c} < π$ ; ideal low-pass; value $ω_{c} / π$ at $n = 0$
$1$ (all $n$ )	$2 π \sum_{k} δ (ω - 2 π k)$	Generalised
$e^{j ω_{0} n}$	$2 π \sum_{k} δ (ω - ω_{0} - 2 π k)$	Generalised
$cos (ω_{0} n)$	$π \sum_{k} [δ (ω - ω_{0} - 2 π k) + δ (ω + ω_{0} - 2 π k)]$	Generalised
$sin (ω_{0} n)$	$\frac{π}{j} \sum_{k} [δ (ω - ω_{0} - 2 π k) - δ (ω + ω_{0} - 2 π k)]$	Generalised
$u [n]$	$\frac{1}{1 - e ^{- j ω}} + π \sum_{k} δ (ω - 2 π k)$	Generalised; not absolutely summable

RIGHT-SIDED EXPONENTIAL

a^{n} u [n] \leftrightarrow \frac{1}{1 - a e ^{- j ω}}, ∣ a ∣ < 1

For real $a$ the magnitude is $1/ 1 - 2 a cos ω + a^{2}$ . With $0 < a < 1$ it peaks at $1/ (1 - a)$ at $ω = 0$ and falls to $1/ (1 + a)$ at $ω = π$ (low-pass); for $- 1 < a < 0$ the roles swap (high-pass). For $∣ a ∣ \geq 1$ there is no DTFT as an ordinary function.

DIRICHLET KERNEL (LENGTH-N RECTANGULAR PULSE)

n = 0 \sum N - 1 e^{- j ω n} = e^{- j ω (N - 1) /2} \frac{sin ( N ω /2 )}{sin ( ω /2 )}

Value $N$ at $ω = 0$ (as a limit). Zeros at $ω = 2 π m / N$ for integers $m$ that are not multiples of $N$ . The main lobe is $4 π / N$ rad/sample wide, null to null. Unlike the continuous-time sinc, the whole expression is periodic with period $2 π$ . The ratio $sin (N ω /2) / sin (ω /2)$ on its own has period $2 π$ only for odd $N$ ; for even $N$ it changes sign after $2 π$ , and the linear-phase factor changes sign too, so the product is still $2 π$ -periodic.

IDEAL LOW-PASS (SINC) SEQUENCE

h [n] = \frac{sin ( ω _{c} n )}{π n} = \frac{ω _{c}}{π} sinc (\frac{ω _{c} n}{π}) \leftrightarrow H (e^{j ω}) = 1 for ∣ ω ∣ \leq ω_{c}, 0 for ω_{c} < ∣ ω ∣ \leq π

$h [0] = ω_{c} / π$ (as a limit). The sequence is not absolutely summable but is square summable, with energy $\sum_{n} h^{2} [n] = ω_{c} / π$ by Parseval. It is non-causal and infinitely long, so it cannot be realised exactly.

EXAM TIP

Building other ideal filters from the low-pass one. Delaying it to $\frac{sin ( ω _{c} ( n - n _{0} ))}{π ( n - n _{0} )}$ keeps the magnitude and adds the phase $- ω n_{0}$ . A high-pass filter with cutoff $ω_{c}$ is $δ [n] - \frac{sin ( ω _{c} n )}{π n}$ . A band-pass filter passing $ω_{0} - ω_{c} \leq ∣ ω ∣ \leq ω_{0} + ω_{c}$ (with $ω_{c} < ω_{0} < π - ω_{c}$ ) is $2 cos (ω_{0} n) \frac{sin ( ω _{c} n )}{π n}$ , by the modulation property.

EXAM TIP

Check $∣ a ∣ < 1$ before quoting a pair. $a^{n} u [n]$ with $∣ a ∣ \geq 1$ has no ordinary DTFT, and $1/ (1 - a e^{- j ω})$ with $∣ a ∣ > 1$ belongs to the left-sided sequence $- a^{n} u [- n - 1]$ . The borderline case $a = 1$ is $u [n]$ , whose DTFT needs the extra impulse train.

DTFT properties and the frequency response

In the table, $x [n] \leftrightarrow X (e^{j ω})$ and $y [n] \leftrightarrow Y (e^{j ω})$ . Every property can be checked from the analysis equation in one or two lines, which is the safest way to recover a sign under exam pressure.

Property	Sequence	DTFT
Linearity	$a x [n] + b y [n]$	$a X (e^{j ω}) + b Y (e^{j ω})$
Time shift	$x [n - n_{0}]$	$e^{- j ω n_{0}} X (e^{j ω})$
Frequency shift (modulation)	$e^{j ω_{0} n} x [n]$	$X (e^{j (ω - ω_{0})})$
Cosine modulation	$x [n] cos (ω_{0} n)$	$\frac{1}{2} [X (e^{j (ω - ω_{0})}) + X (e^{j (ω + ω_{0})})]$
Time reversal	$x [- n]$	$X (e^{- j ω})$
Conjugation	$x^{*} [n]$	$X^{*} (e^{- j ω})$
Convolution	$x [n] * y [n]$	$X (e^{j ω}) Y (e^{j ω})$
Multiplication	$x [n] y [n]$	$\frac{1}{2 π} \int_{- π}^{π} X (e^{j θ}) Y (e^{j (ω - θ)}) d θ$
Differentiation in frequency	$n x [n]$	$j \frac{d X ( e ^{j ω} )}{d ω}$
First difference	$x [n] - x [n - 1]$	$(1 - e^{- j ω}) X (e^{j ω})$
Accumulation	$\sum_{m = - \infty}^{n} x [m]$	$\frac{X ( e ^{j ω} )}{1 - e ^{- j ω}} + π X (e^{j 0}) \sum_{k} δ (ω - 2 π k)$
Time expansion by $L$	$x [n / L]$ if $L$ divides $n$ , else $0$	$X (e^{j L ω})$
Downsampling by $M$	$x [M n]$	$\frac{1}{M} \sum_{i = 0}^{M - 1} X (e^{j (ω - 2 π i) / M})$
Parseval	$\sum_{n} ∣ x [n] ∣^{2}$	$\frac{1}{2 π} \int_{- π}^{π} ∣ X (e^{j ω}) ∣^{2} d ω$

TIME SHIFT AND FREQUENCY SHIFT

x [n - n_{0}] \leftrightarrow e^{- j ω n_{0}} X (e^{j ω}), e^{j ω_{0} n} x [n] \leftrightarrow X (e^{j (ω - ω_{0})})

A delay of $n_{0}$ samples adds the linear phase $- ω n_{0}$ and leaves $∣ X ∣$ unchanged. Multiplying by $(- 1)^{n} = e^{j π n}$ shifts the spectrum by $π$ , which turns a low-pass sequence into a high-pass one.

TIME REVERSAL AND CONJUGATION

x [- n] \leftrightarrow X (e^{- j ω}), x^{*} [n] \leftrightarrow X^{*} (e^{- j ω})

Combining them: $x^{*} [- n] \leftrightarrow X^{*} (e^{j ω})$ .

SYMMETRY OF A REAL SEQUENCE

x [n] real \Rightarrow X (e^{- j ω}) = X^{*} (e^{j ω})

So $∣ X ∣$ and $Re X$ are even in $ω$ , while $∠ X$ and $Im X$ are odd. A real, even $x [n]$ has a real, even $X$ ; a real, odd $x [n]$ has a purely imaginary, odd $X$ . More generally, for real $x [n]$ the even part $\frac{1}{2} (x [n] + x [- n])$ transforms to $Re X (e^{j ω})$ and the odd part $\frac{1}{2} (x [n] - x [- n])$ to $j Im X (e^{j ω})$ .

CONVOLUTION THEOREM

y [n] = x [n] * h [n] = k = - \infty \sum \infty x [k] h [n - k] \leftrightarrow Y (e^{j ω}) = X (e^{j ω}) H (e^{j ω})

Linear (aperiodic) convolution. This is why the output spectrum of an LTI system is the input spectrum times its frequency response.

MULTIPLICATION (PERIODIC CONVOLUTION)

x [n] y [n] \leftrightarrow \frac{1}{2 π} \int_{- π}^{π} X (e^{j θ}) Y (e^{j (ω - θ)}) d θ

The integral runs over one period only, so this is a periodic convolution. Windowing $x [n]$ by $w [n]$ smears $X$ with the window's kernel, which is the origin of spectral leakage.

DIFFERENTIATION IN FREQUENCY

n x [n] \leftrightarrow j \frac{d X ( e ^{j ω} )}{d ω}, n \sum n x [n] = j \frac{d X ( e ^{j ω} )}{d ω}_{ω = 0}

Useful for $\sum n x [n]$ and, together with Parseval, for $\int_{- π}^{π} ∣ d X / d ω ∣^{2} d ω = 2 π \sum n^{2} ∣ x [n] ∣^{2}$ .

PARSEVAL'S THEOREM

n = - \infty \sum \infty ∣ x [n] ∣^{2} = \frac{1}{2 π} \int_{- π}^{π} ∣ X (e^{j ω}) ∣^{2} d ω

Energy in time equals the energy spread over one period of frequency. The general form is $\sum_{n} x [n] y^{*} [n] = \frac{1}{2 π} \int_{- π}^{π} X (e^{j ω}) Y^{*} (e^{j ω}) d ω$ .

FREQUENCY RESPONSE FROM A DIFFERENCE EQUATION

k = 0 \sum N_{a} a_{k} y [n - k] = k = 0 \sum M_{b} b_{k} x [n - k] \Rightarrow H (e^{j ω}) = \frac{\sum _{k = 0}^{M_{b}} b _{k} e ^{- j ω k}}{\sum _{k = 0}^{N_{a}} a _{k} e ^{- j ω k}}

Take the DTFT of both sides with the time-shift property ( $a_{0} \neq = 0$ ). Valid for a stable system; for a causal system that means all poles of $H (z)$ inside the unit circle.

SINUSOIDAL RESPONSE OF A STABLE LTI SYSTEM

x [n] = A cos (ω_{0} n + ϕ) \Rightarrow y [n] = A ∣ H (e^{j ω_{0}}) ∣ cos (ω_{0} n + ϕ + ∠ H (e^{j ω_{0}}))

For real $h [n]$ and an input applied for all $n$ . Evaluate $H$ at the input frequency in rad/sample; reduce $ω_{0}$ modulo $2 π$ first if it is outside $(- π, π]$ .

EXAM TIP

Take the centre of symmetry out as a delay. A real finite sequence symmetric about $n = n_{0}$ , i.e. $x [n] = x [2 n_{0} - n]$ ( $n_{0}$ may be a half-integer for an even length), has $X (e^{j ω}) = e^{- j ω n_{0}} A (ω)$ with $A (ω)$ real, because each pair of equal samples contributes $2 x [n] e^{- j ω n_{0}} cos (ω (n - n_{0}))$ . The rest is a cosine sum, which removes most of the algebra. The phase is linear, so the group delay $- d ∠ X / d ω$ is $n_{0}$ , apart from the points where $A (ω)$ changes sign and the phase jumps by $π$ .

WORKED EXAMPLE

Let $x [n] = 1, 2, 3, 2, 1$ for $n = - 2, - 1, 0, 1, 2$ and $x [n] = 0$ elsewhere, and let $y [n] = x [n - 2]$ . Find (a) $X (e^{j ω})$ in real form, (b) $X (e^{j 0})$ and $X (e^{j π})$ , (c) $\int_{- π}^{π} ∣ Y (e^{j ω}) ∣^{2} d ω$ , (d) $\int_{- π}^{π} Y (e^{j ω}) e^{j 2 ω} d ω$ , and (e) $\int_{- π}^{π} d X (e^{j ω}) / d ω^{2} d ω$ .

Solution

(a) Pair the symmetric terms: $X (e^{j ω}) = 3 + 2 (e^{j ω} + e^{- j ω}) + (e^{j 2 ω} + e^{- j 2 ω}) = 3 + 4 cos ω + 2 cos 2 ω$ . It is real and even because $x [n]$ is real and even.
(b) $X (e^{j 0}) = \sum x [n] = 1 + 2 + 3 + 2 + 1 = 9$ and $X (e^{j π}) = \sum (- 1)^{n} x [n] = 1 - 2 + 3 - 2 + 1 = 1$ . From (a): $3 + 4 + 2 = 9$ and $3 - 4 + 2 = 1$ .
(c) $Y (e^{j ω}) = e^{- j 2 ω} X (e^{j ω})$ , so $∣ Y ∣ = ∣ X ∣$ ; a delay does not change the energy. By Parseval, $\int_{- π}^{π} ∣ Y ∣^{2} d ω = 2 π \sum ∣ x [n] ∣^{2} = 2 π (1 + 4 + 9 + 4 + 1) = 38 π$ .
(d) This is the inverse DTFT at $n = 2$ without the $1/2 π$ : $\int_{- π}^{π} Y (e^{j ω}) e^{j 2 ω} d ω = 2 π y [2] = 2 π x [0] = 6 π$ .
(e) $d X / d ω$ is the DTFT of $- j n x [n]$ , so by Parseval $\int_{- π}^{π} ∣ d X / d ω ∣^{2} d ω = 2 π \sum n^{2} ∣ x [n] ∣^{2} = 2 π (4 \cdot 1 + 1 \cdot 4 + 0 + 1 \cdot 4 + 4 \cdot 1) = 32 π$ .
Check (e) directly: $d X / d ω = - 4 sin ω - 4 sin 2 ω$ , and $\int_{- π}^{π} (16 sin^{2} ω + 32 sin ω sin 2 ω + 16 sin^{2} 2 ω) d ω = 16 π + 0 + 16 π = 32 π$ .

Answer: (a) $3 + 4 cos ω + 2 cos 2 ω$ ; (b) $9$ and $1$ ; (c) $38 π$ ; (d) $6 π$ ; (e) $32 π$ .

The DFT: definition, sampling the DTFT and the DFT matrix

The DTFT is a continuous function of $ω$ , so a computer cannot store it. The discrete Fourier transform (DFT) takes a finite block of $N$ samples, $x [n]$ for $0 \leq n \leq N - 1$ , and returns $N$ numbers $X [k]$ , $0 \leq k \leq N - 1$ . Convention used throughout these notes: $W_{N} = e^{- j 2 π / N}$ , so the forward DFT carries the negative exponent and the $1/ N$ sits in the inverse, and $(n)_{N}$ means $n$ modulo $N$ , reduced to the range $0$ to $N - 1$ . Both $x [n]$ and $X [k]$ behave as one period of a sequence with period $N$ , so every index is read modulo $N$ .

DFT

X [k] = n = 0 \sum N - 1 x [n] W_{N}^{k n} = n = 0 \sum N - 1 x [n] e^{- j 2 π k n / N}, k = 0, 1, \dots, N - 1

$W_{N} = e^{- j 2 π / N}$ . $X [k]$ is complex in general, even when $x [n]$ is real.

INVERSE DFT (IDFT)

x [n] = \frac{1}{N} k = 0 \sum N - 1 X [k] W_{N}^{- k n} = \frac{1}{N} k = 0 \sum N - 1 X [k] e^{j 2 π k n / N}, n = 0, 1, \dots, N - 1

Some texts put $1/ N$ in both directions (the unitary DFT), and then Parseval has no $1/ N$ . These notes keep $1/ N$ in the inverse only.

DFT AS SAMPLES OF THE DTFT

X [k] = X (e^{j ω})_{ω = 2 π k / N}, k = 0, 1, \dots, N - 1

Exact when $x [n]$ is zero outside $0 \leq n \leq N - 1$ ; a length- $L$ sequence with $L \leq N$ is zero-padded to $N$ . The samples are spaced $2 π / N$ apart over one period $[0, 2 π)$ .

SAMPLING THE DTFT ALIASES IN TIME

IDFT_{N} {X (e^{j 2 π k / N})} = r = - \infty \sum \infty x [n - r N], 0 \leq n \leq N - 1

If $x [n]$ is longer than $N$ (or infinitely long), $N$ samples of its DTFT recover this time-aliased sum, not $x [n]$ . It is the time-domain counterpart of the aliasing caused by sampling a signal too slowly.

DTFT OF A PERIODIC SEQUENCE (DISCRETE FOURIER SERIES)

\tilde{x} [n + N] = \tilde{x} [n] \Rightarrow \tilde{x} [n] = \frac{1}{N} k = 0 \sum N - 1 \tilde{X} [k] e^{j 2 π k n / N} \leftrightarrow \frac{2 π}{N} k = - \infty \sum \infty \tilde{X} [k] δ (ω - \frac{2 π k}{N})

$\tilde{X} [k] = \sum_{n = 0}^{N - 1} \tilde{x} [n] W_{N}^{k n}$ is the $N$ -point DFT of one period, extended periodically in $k$ . A periodic sequence is not summable, so its DTFT is a train of impulses at the bin frequencies $2 π k / N$ . If the Fourier-series coefficients are defined as $a_{k} = \tilde{X} [k] / N$ , the same result reads $2 π \sum_{k} a_{k} δ (ω - 2 π k / N)$ . Check: $\tilde{x} [n] = 1$ gives $\tilde{X} [k] = N$ at multiples of $N$ and $0$ elsewhere, hence $2 π \sum_{k} δ (ω - 2 π k)$ .

FREQUENCY OF BIN K

ω_{k} = \frac{2 π k}{N} rad/sample, F_{k} = \frac{k F _{s}}{N} Hz

For a sequence sampled at $F_{s}$ . Bins $k$ and $N - k$ correspond to $\pm F_{k}$ : for $k > N /2$ , bin $k$ represents the negative frequency $(k - N) F_{s} / N$ . For even $N$ , bin $N /2$ is $F_{s} /2$ .

TWIDDLE-FACTOR IDENTITIES

W_{N}^{N} = 1, W_{N}^{k + N} = W_{N}^{k}, W_{N}^{N /2} = - 1, W_{N}^{k + N /2} = - W_{N}^{k}, W_{N}^{2} = W_{N /2}

The first two hold for every $N$ ; the last three need $N$ even. Periodicity and half-period symmetry of $W_{N}$ are exactly the identities the FFT exploits. For $N = 4$ : $W_{4} = - j$ , $W_{4}^{2} = - 1$ , $W_{4}^{3} = j$ .

DFT MATRICES FOR N = 2 AND N = 4

F_{2} = [11 1 - 1], F_{4} = 1111 1 - j - 1 j 1 - 1 1 - 1 1 j - 1 - j

$X = F_{N} x$ with $[F_{N}]_{k n} = W_{N}^{k n}$ (row $k$ , column $n$ , both counted from $0$ ). $F_{N}$ is symmetric. With $F_{4}$ memorised, a 4-point DFT needs only additions, subtractions and multiplications by $\pm j$ (a swap of real and imaginary parts with a sign change).

INVERSE AND POWERS OF THE DFT MATRIX

F_{N}^{- 1} = \frac{1}{N} F_{N}^{*}, F_{N}^{2} x = N [x [0], x [N - 1], x [N - 2], \dots, x [1]]^{T}, F_{N}^{4} = N^{2} I

$F_{N} F_{N}^{*} = N I$ , so $F_{N} / N$ is unitary. Applying the DFT twice returns the circularly time-reversed sequence $x [(- n)_{N}]$ scaled by $N$ ; four applications return $N^{2} x$ . Hence every eigenvalue of $F_{N}$ is one of $\pm N$ , $\pm j N$ .

EXAM TIP

The double DFT reverses, it does not return. If $X [k]$ is the $N$ -point DFT of $x [n]$ , the DFT of the sequence $X [n]$ is $N x [(- k)_{N}]$ , not $N x [k]$ . For $x [n] = {a, b, c, d}$ it is $4 {a, d, c, b}$ : index $0$ stays in place and the rest reverse.

EXAM TIP

$N$ samples of a DTFT are not always the DFT of the original sequence. If a question gives the DTFT of an infinitely long sequence and asks for the IDFT of $N$ of its samples, add the time-aliased copies. For $a^{n} u [n]$ with $∣ a ∣ < 1$ , the result is $\frac{a ^{n}}{1 - a ^{N}}$ for $0 \leq n \leq N - 1$ .

DFT properties and circular convolution

Because the DFT treats both $x [n]$ and $X [k]$ as one period of a periodic sequence, every shift, reversal and convolution is circular: indices are taken modulo $N$ . In the table all sequences have length $N$ , $x [n] \leftrightarrow X [k]$ , $y [n] \leftrightarrow Y [k]$ , and $⊛$ denotes $N$ -point circular convolution.

Property	Sequence ( $0 \leq n \leq N - 1$ )	$N$ -point DFT
Linearity	$a x [n] + b y [n]$	$a X [k] + b Y [k]$
Circular time shift	$x [(n - m)_{N}]$	$W_{N}^{k m} X [k]$
Circular frequency shift	$W_{N}^{- l n} x [n] = e^{j 2 π l n / N} x [n]$	$X [(k - l)_{N}]$
Circular time reversal	$x [(- n)_{N}]$	$X [(- k)_{N}]$
Conjugation	$x^{*} [n]$	$X^{*} [(- k)_{N}]$
Conjugate and reverse	$x^{*} [(- n)_{N}]$	$X^{*} [k]$
Real part	$Re {x [n]}$	$\frac{1}{2} (X [k] + X^{*} [(- k)_{N}])$
Imaginary part	$j Im {x [n]}$	$\frac{1}{2} (X [k] - X^{*} [(- k)_{N}])$
Duality	$X [n]$	$N x [(- k)_{N}]$
Circular convolution	$x [n] ⊛ y [n]$	$X [k] Y [k]$
Multiplication	$x [n] y [n]$	$\frac{1}{N} X [k] ⊛ Y [k]$
Parseval	$\sum_{n = 0}^{N - 1} ∣ x [n] ∣^{2}$	$\frac{1}{N} \sum_{k = 0}^{N - 1} ∣ X [k] ∣^{2}$

CONJUGATE SYMMETRY FOR A REAL SEQUENCE

x [n] real \Rightarrow X [N - k] = X^{*} [k], ∣ X [N - k] ∣ = ∣ X [k] ∣, ∠ X [N - k] = - ∠ X [k]

For $1 \leq k \leq N - 1$ . So $X [0]$ is real and, for even $N$ , $X [N /2]$ is real. Only $X [0]$ to $X [N /2]$ need computing for even $N$ ( $X [0]$ to $X [(N - 1) /2]$ for odd $N$ ); the rest are conjugates. If $x [n]$ is real and circularly even, $x [n] = x [(N - n)_{N}]$ , then $X [k]$ is real and circularly even; if it is real and circularly odd, $x [n] = - x [(N - n)_{N}]$ , then $X [k]$ is purely imaginary and circularly odd.

CIRCULAR CONVOLUTION

y [n] = x [n] ⊛ h [n] = m = 0 \sum N - 1 x [m] h [(n - m)_{N}], 0 \leq n \leq N - 1 \leftrightarrow Y [k] = X [k] H [k]

Both sequences are treated as length $N$ (zero-padded if shorter). Multiplying two $N$ -point DFTs and inverting always gives the circular convolution, not the linear one.

PARSEVAL'S RELATION FOR THE DFT

n = 0 \sum N - 1 ∣ x [n] ∣^{2} = \frac{1}{N} k = 0 \sum N - 1 ∣ X [k] ∣^{2}, n = 0 \sum N - 1 x [n] y^{*} [n] = \frac{1}{N} k = 0 \sum N - 1 X [k] Y^{*} [k]

With $W_{N} = e^{- j 2 π / N}$ and $1/ N$ in the inverse, the $1/ N$ is on the frequency side. Leaving it out gives an answer $N$ times too large.

VALUES AT K = 0, N = 0 AND N/2

X [0] = n = 0 \sum N - 1 x [n], x [0] = \frac{1}{N} k = 0 \sum N - 1 X [k], X [N /2] = n = 0 \sum N - 1 (- 1)^{n} x [n], x [N /2] = \frac{1}{N} k = 0 \sum N - 1 (- 1)^{k} X [k]

The last two need $N$ even. $X [0]$ is $N$ times the mean of $x [n]$ , and $x [0]$ is the mean of the $X [k]$ .

Circular versus linear convolution. If $x [n]$ has length $N_{1}$ and $h [n]$ has length $N_{2}$ , their linear convolution $y_{l} [n]$ has length $N_{1} + N_{2} - 1$ . For $N \geq max (N_{1}, N_{2})$ , the $N$ -point circular convolution is the linear one wrapped around modulo $N$ : every sample of $y_{l}$ beyond index $N - 1$ is added back onto the start. The two therefore agree exactly when nothing wraps, i.e. when $N \geq N_{1} + N_{2} - 1$ . That is why linear filtering with the DFT (or FFT) needs both sequences zero-padded to at least $N_{1} + N_{2} - 1$ points.

CIRCULAR CONVOLUTION IS ALIASED LINEAR CONVOLUTION

y_{c} [n] = r = - \infty \sum \infty y_{l} [n - r N], 0 \leq n \leq N - 1

Valid whenever $N \geq max (N_{1}, N_{2})$ . For $max (N_{1}, N_{2}) \leq N < N_{1} + N_{2} - 1$ , only the first $N_{1} + N_{2} - 1 - N$ samples can differ from the linear result; samples $n = N_{1} + N_{2} - 1 - N$ to $N - 1$ equal it.

LENGTH NEEDED FOR LINEAR CONVOLUTION BY DFT

N \geq N_{1} + N_{2} - 1

$N_{1}$ and $N_{2}$ are the lengths of the two sequences. For a radix-2 FFT, take the next power of $2$ at or above $N_{1} + N_{2} - 1$ .

Computing an $N$ -point circular convolution by hand (both sequences no longer than $N$ ):

1. Zero-pad both sequences to length $N$ .
2. Compute the ordinary linear convolution $y_{l} [n]$ , of length $N_{1} + N_{2} - 1$ , by the tabular or sliding method.
3. Wrap it: add $y_{l} [N]$ to $y_{l} [0]$ , $y_{l} [N + 1]$ to $y_{l} [1]$ , and so on.
4. Check: $\sum_{n} y_{c} [n] = (\sum_{n} x [n]) (\sum_{n} h [n])$ , because $Y [0] = X [0] H [0]$ .
Alternative. Form the circulant matrix $H_{c}$ whose entry in row $n$ , column $m$ is $h [(n - m)_{N}]$ : its first column is $h [0], h [1], \dots, h [N - 1]$ and each later column is the previous one shifted down by one place circularly. Then $y = H_{c} x$ .

EXAM TIP

Two real DFTs for the price of one. For real $x_{1} [n]$ and $x_{2} [n]$ of length $N$ , form $v [n] = x_{1} [n] + j x_{2} [n]$ and compute one $N$ -point DFT $V [k]$ . Then $X_{1} [k] = \frac{1}{2} (V [k] + V^{*} [(N - k)_{N}])$ and $X_{2} [k] = \frac{1}{2 j} (V [k] - V^{*} [(N - k)_{N}])$ .

EXAM TIP

A circular shift changes only the phase. $∣ X [k] ∣$ is the same for $x [n]$ and $x [(n - m)_{N}]$ . For even $N$ , a circular shift by $N /2$ multiplies $X [k]$ by $W_{N}^{k N /2} = (- 1)^{k}$ .

WORKED EXAMPLE

$x [n] = {1, 2, 0, - 1}$ and $h [n] = {1, - 1, 2}$ , both starting at $n = 0$ . (a) Find the 4-point DFT $X [k]$ and verify Parseval. (b) Find $y_{4} [n]$ , the IDFT of $X [k] H [k]$ with both DFTs 4-point. (c) Find the 5-point circular convolution $y_{5} [n]$ , and the smallest $N$ for which the $N$ -point circular convolution equals the linear convolution.

Solution

(a) With $W_{4} = - j$ : $X [0] = 1 + 2 + 0 - 1 = 2$ ; $X [1] = 1 + 2 (- j) + 0 + (- 1) (j) = 1 - 3 j$ ; $X [2] = 1 - 2 + 0 + 1 = 0$ . Since $x [n]$ is real, $X [3] = X^{*} [1] = 1 + 3 j$ .
Parseval: $\sum ∣ x [n] ∣^{2} = 1 + 4 + 0 + 1 = 6$ , and $\frac{1}{4} (4 + 10 + 0 + 10) = 6$ . The two sides agree.
(b) A product of 4-point DFTs inverts to the 4-point circular convolution. First the linear convolution, of length $4 + 3 - 1 = 6$ : $y_{l} [0] = 1$ , $y_{l} [1] = - 1 + 2 = 1$ , $y_{l} [2] = 2 - 2 + 0 = 0$ , $y_{l} [3] = 4 + 0 - 1 = 3$ , $y_{l} [4] = 0 + 1 = 1$ , $y_{l} [5] = - 2$ . So $y_{l} [n] = {1, 1, 0, 3, 1, - 2}$ ; check: $\sum y_{l} = 4 = (2) (2)$ .
Wrap modulo 4: $y_{4} [0] = y_{l} [0] + y_{l} [4] = 2$ , $y_{4} [1] = y_{l} [1] + y_{l} [5] = - 1$ , $y_{4} [2] = 0$ , $y_{4} [3] = 3$ . So $y_{4} [n] = {2, - 1, 0, 3}$ .
Check through the DFTs: $H [k] = {2, - 1 + j, 4, - 1 - j}$ , so $X [k] H [k] = {4, 2 + 4 j, 0, 2 - 4 j}$ and $y_{4} [0] = \frac{1}{4} (4 + 2 + 4 j + 0 + 2 - 4 j) = 2$ , as found.
(c) Wrap modulo 5: only $y_{l} [5]$ folds, onto $n = 0$ , so $y_{5} [n] = {1 - 2, 1, 0, 3, 1} = {- 1, 1, 0, 3, 1}$ . Samples $n = 1$ to $4$ already equal the linear result, as the rule predicts: $N_{1} + N_{2} - 1 - N = 1$ corrupted sample.
The smallest $N$ with no wrap-around is $N_{1} + N_{2} - 1 = 4 + 3 - 1 = 6$ .

Answer: (a) $X [k] = {2, 1 - 3 j, 0, 1 + 3 j}$ , and both sides of Parseval equal $6$ ; (b) $y_{4} [n] = {2, - 1, 0, 3}$ ; (c) $y_{5} [n] = {- 1, 1, 0, 3, 1}$ , and $N = 6$ .

Frequency resolution, zero padding and block convolution

Two different spacings are easy to confuse. The bin spacing $2 π / N$ (or $F_{s} / N$ Hz) is how finely the DTFT is sampled, and it shrinks when you zero-pad. The resolution is how close two spectral lines can be and still show as two peaks. It is set by the length $L$ of the actual data record: a record of $L$ samples is the signal multiplied by a length- $L$ window, whose Dirichlet kernel (main lobe $4 π / L$ wide) smears every line. Zero padding samples this smeared DTFT more densely, which gives a smoother plot, but it cannot separate lines the window has already merged.

BIN SPACING

Δ ω = \frac{2 π}{N} rad/sample, Δ F = \frac{F _{s}}{N} Hz

$N$ is the DFT length, including any zero padding.

RECORD-LENGTH RESOLUTION (RECTANGULAR WINDOW)

Δ F_{res} \approx \frac{F _{s}}{L} = \frac{1}{L T _{s}} = \frac{1}{T _{0}}

$L$ is the number of genuine data samples and $T_{0} = L T_{s}$ the observation time. This is a rule of thumb, not an exact threshold: the main lobe of the rectangular window is $2 F_{s} / L$ wide null to null, and whether two tones about $F_{s} / L$ apart show as two peaks also depends on their relative phase. Only a longer record improves it. Other windows lower the side lobes at the cost of a wider main lobe.

DFT OF A SINUSOID THAT LANDS EXACTLY ON A BIN

x [n] = A cos (\frac{2 π k _{0} n}{N}), 0 \leq n \leq N - 1 \Rightarrow X [k] = \frac{A N}{2} (δ [k - k_{0}] + δ [k - (N - k_{0})])

For an integer $k_{0}$ with $0 < k_{0} < N /2$ , i.e. a whole number of cycles in the record. Likewise $e^{j 2 π k_{0} n / N}$ gives $N δ [k - k_{0}]$ for integer $0 \leq k_{0} \leq N - 1$ . If the frequency falls between bins, energy spreads into every bin: spectral leakage.

EXAM TIP

Zero padding does not add information. Padding a 64-sample record to 1024 points gives 1024 samples of the same DTFT, and two tones closer than about $F_{s} /64$ still merge. What zero padding does buy: (i) a denser, easier-to-read spectrum; (ii) a length that suits a radix-2 FFT; (iii) the extra length that makes circular convolution equal linear convolution.

Filtering a long signal with the FFT. When the input is very long, or streaming, and the FIR filter $h [n]$ has length $M$ , cut the input into blocks, filter each block with $N$ -point FFTs, and stitch the results together. With $L$ new input samples per block, $N \geq L + M - 1$ . The two standard stitching methods are compared below.

	Overlap-add	Overlap-save
Input blocks	Non-overlapping, $L$ samples each, zero-padded to $N$	Length $N$ , each overlapping the previous block by $M - 1$ samples, so $L = N - M + 1$ new samples
Transform size	$N \geq L + M - 1$ ; $h [n]$ zero-padded to $N$	$N$ (the block length); $h [n]$ zero-padded to $N$
What each block gives	The full linear convolution of the block, $L + M - 1$ samples long	An $N$ -point circular convolution whose first $M - 1$ samples are wrapped (aliased)
Stitching	Add the $M - 1$ overlapping output samples of neighbouring blocks	Discard the first $M - 1$ output samples of each block; keep the last $N - M + 1$ and place them end to end
Start	Nothing special	Put $M - 1$ zeros in front of the first block

The FFT: radix-2 decimation in time and in frequency

A direct $N$ -point DFT computes $N$ outputs, each a sum of $N$ products: $N^{2}$ complex multiplications and $N (N - 1)$ complex additions. The fast Fourier transform (FFT) computes exactly the same $X [k]$ (it is not an approximation) by splitting the DFT into smaller DFTs and reusing $W_{N}^{k + N /2} = - W_{N}^{k}$ . The radix-2 algorithms need $N = 2^{ν}$ ; pad with zeros to the next power of $2$ if necessary. There are $ν = lo g_{2} N$ stages, each made of $N /2$ butterflies.

DECIMATION-IN-TIME (DIT) SPLIT

X [k] = X_{e} [k] + W_{N}^{k} X_{o} [k], X [k + N /2] = X_{e} [k] - W_{N}^{k} X_{o} [k], k = 0, 1, \dots, N /2 - 1

$X_{e} [k]$ and $X_{o} [k]$ are the $N /2$ -point DFTs of the even-indexed samples $x [2 r]$ and the odd-indexed samples $x [2 r + 1]$ . Repeat the split until only 2-point DFTs remain.

DIT BUTTERFLY

A = a + W_{N}^{r} b, B = a - W_{N}^{r} b

The twiddle factor multiplies the lower input before the add and subtract. One complex multiplication and two complex additions per butterfly.

DECIMATION-IN-FREQUENCY (DIF) SPLIT

X [2 r] = n = 0 \sum N /2 - 1 (x [n] + x [n + N /2]) W_{N /2}^{r n}, X [2 r + 1] = n = 0 \sum N /2 - 1 (x [n] - x [n + N /2]) W_{N}^{n} W_{N /2}^{r n}

For $r = 0, 1, \dots, N /2 - 1$ . The first and second halves of the input are combined, and the even- and odd-indexed outputs each come from an $N /2$ -point DFT.

DIF BUTTERFLY

A = a + b, B = (a - b) W_{N}^{n}

The twiddle factor multiplies the difference after the subtraction. Still one complex multiplication and two complex additions.

COST OF A DIRECT DFT

M_{DFT} = N^{2}, A_{DFT} = N (N - 1)

Complex multiplications $M$ and complex additions $A$ : each of the $N$ outputs needs $N$ products and $N - 1$ additions.

COST OF A RADIX-2 FFT

M_{FFT} = \frac{N}{2} lo g_{2} N, A_{FFT} = N lo g_{2} N

$lo g_{2} N$ stages of $N /2$ butterflies. The count includes trivial multiplications by $W_{N}^{0} = 1$ and by $- j$ , which a practical program skips; use the formula as stated unless a question says otherwise. One complex multiplication, done directly as $(a + j b) (c + j d) = (a c - b d) + j (a d + b c)$ , costs 4 real multiplications and 2 real additions.

SPEED-UP IN MULTIPLICATIONS

\frac{N ^{2}}{( N /2 ) lo g _{2} N} = \frac{2 N}{lo g _{2} N}

For example $2 \times 1024/10 = 204.8$ for $N = 1024$ .

$N$	Stages $lo g_{2} N$	Direct: mult. / add.	FFT: mult. / add.	Mult. ratio
$8$	$3$	$64$ / $56$	$12$ / $24$	$5.33$
$16$	$4$	$256$ / $240$	$32$ / $64$	$8$
$256$	$8$	$65536$ / $65280$	$1024$ / $2048$	$64$
$1024$	$10$	$1048576$ / $1047552$	$5120$ / $10240$	$204.8$

	Decimation in time (DIT)	Decimation in frequency (DIF)
Split first	Input samples: even $n$ and odd $n$	Output samples: even $k$ and odd $k$
Input order (in-place form)	Bit-reversed	Natural
Output order (in-place form)	Natural	Bit-reversed
Twiddle factor	Multiplies the lower input before the add and subtract	Multiplies the difference after the add and subtract
Cost	$\frac{N}{2} lo g_{2} N$ mult., $N lo g_{2} N$ add.	The same

Bit reversal and stage structure. Write the index in $ν = lo g_{2} N$ bits and reverse the bits. For $N = 8$ : $1 = 001 \to 100 = 4$ and $3 = 011 \to 110 = 6$ , so the DIT input order is $x [0], x [4], x [2], x [6], x [1], x [5], x [3], x [7]$ . Indices whose bit pattern reads the same both ways ( $0, 2, 5, 7$ for $N = 8$ ) stay in place. In the DIT graph with bit-reversed input, stage $m$ ( $m = 1, \dots, ν$ ) uses the twiddles $W_{2^{m}}^{r}$ , $r = 0, 1, \dots, 2^{m - 1} - 1$ , so the first stage is plain 2-point DFTs with $W_{2}^{0} = 1$ . Each stage can overwrite its inputs with its outputs (in-place computation), so only $N$ complex storage locations are needed.

EXAM TIP

Counting questions. Stages $= lo g_{2} N$ ; butterflies per stage $= N /2$ ; total butterflies $= \frac{N}{2} lo g_{2} N$ , the same as the multiplication count because each butterfly has one multiplication. An $N$ -point IDFT costs the same as a DFT plus a scaling by $1/ N$ : conjugate $X [k]$ , run the forward FFT, conjugate the result and divide by $N$ , since $x [n] = \frac{1}{N} (DFT {X^{*} [k]})^{*}$ .

WORKED EXAMPLE

A signal is sampled at $F_{s} = 8$ kHz and $L = 1000$ samples are recorded. They are zero-padded to $N = 1024$ and a radix-2 FFT is computed. Find (a) the bin spacing; (b) the bin indices of a $1$ kHz component and of its mirror image; (c) the number of stages, butterflies, complex multiplications and complex additions, and the saving over a direct DFT; (d) whether tones at $1000$ Hz and $1005$ Hz can be relied on to appear as two separate peaks.

Solution

(a) $Δ F = F_{s} / N = 8000/1024 = 7.8125$ Hz.
(b) $k = F /Δ F = 1000/7.8125 = 128$ . The signal is real, so the mirror is at $N - k = 1024 - 128 = 896$ , which represents $- 1$ kHz.
(c) $ν = lo g_{2} 1024 = 10$ stages, $N /2 = 512$ butterflies per stage, $5120$ butterflies in all. Complex multiplications $= \frac{N}{2} lo g_{2} N = 512 \times 10 = 5120$ ; complex additions $= N lo g_{2} N = 10240$ .
A direct 1024-point DFT needs $N^{2} = 1048576$ complex multiplications, so the FFT needs $1048 576/5120 = 204.8$ times fewer, which is $2 N / lo g_{2} N$ .
(d) Resolution is set by the record length: $T_{0} = L / F_{s} = 1000/8000 = 0.125$ s, so $Δ F_{res} \approx 1/ T_{0} = 8$ Hz. The tones are only $5$ Hz apart, less than the $8$ Hz half-width of the main lobe, so the two lobes overlap heavily. Depending on the tones' relative phase the spectrum shows one merged peak, or two humps that do not sit at $1000$ Hz and $1005$ Hz; either way the tones are not resolved.
The $7.8125$ Hz bin spacing does not decide this, and padding to $N = 8192$ would not help either. The rule of thumb asks for a record of at least $F_{s} /5 = 1600$ samples ( $0.2$ s), and in practice somewhat more, because at a separation of exactly $F_{s} / L$ some relative phases still merge the two peaks.

Answer: (a) $7.8125$ Hz; (b) $k = 128$ and $k = 896$ ; (c) $10$ stages, $512$ butterflies per stage, $5120$ complex multiplications, $10240$ complex additions, $204.8$ times fewer multiplications than a direct DFT; (d) no: $5$ Hz is below the $\approx 8$ Hz resolution of a $0.125$ s record, whatever the zero padding.

PREVIOUS-YEAR QUESTIONS

11 questions from the EC, EE and IN papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE ECE 2024 · GATE ECE 2023 · GATE ECE 2022 · GATE ECE 2020 · GATE ECE 2018 · GATE EE 2023 · GATE IN 2025 · GATE IN 2024 · GATE IN 2020 · GATE IN 2018

GATE 2025 IN Q.54

GATE 2025 · INQ.54 · 2 marks · NAT

Let $X (e^{j ω})$ represent the discrete time Fourier transform of a 4-length sequence $x [n]$ , where $x [0] = 1$ , $x [1] = 2$ , $x [2] = 2$ , and $x [3] = 4$ . $X (e^{j ω})$ is sampled at $ω_{k} = \frac{2 π k}{3}$ to generate a periodic sequence in $k$ with period 3, where $k$ represents an integer. Let $y [n]$ represent another sequence such that its discrete Fourier transform $Y [k]$ is given as $Y [k] = X (e^{j ω_{k}})$ for $0 \leq k \leq 2$ . The value of $y [0]$ is ______ (in integer).

Answer and solution

GATE 2025 IN Q.54: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 IN Q.54: answer and solution

GATE 2024 EC Q.59

GATE 2024 · ECQ.59 · 2 marks · NAT

The relationship between any N-length sequence $x [n]$ and its corresponding N-point discrete Fourier transform $X [k]$ is defined as

X [k] = F {x [n]} .

Another sequence $y [n]$ is formed as below

y [n] = F {F {F {F {x [n]}}}} .

For the sequence $x [n] = {1, 2, 1, 3}$ , the value of $Y [0]$ is ________.

Answer and solution

GATE 2024 EC Q.59: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 EC Q.59: answer and solution

GATE 2024 IN Q.25

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).

Answer and solution

GATE 2024 IN Q.25: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 IN Q.25: answer and solution

GATE 2024 IN Q.53

GATE 2024 · INQ.53 · 2 marks · NAT

The 4-point DFTs of two sequences $x [n]$ and $y [n]$ are $X [k] = [1, - j, 1, j]$ and $Y [k] = [1, 3 j, 1, - 3 j]$ , respectively. Assuming $z [n]$ represents the 4-point circular convolution of $x [n]$ and $y [n]$ , the value of $z [0]$ is ________ (rounded off to nearest integer).

Note: The DFT of a $N$ -point sequence $x [n]$ is defined as
$X [k] = n = 0 \sum N - 1 x [n] e^{\frac{- j 2 π nk}{N}}$

Answer and solution

GATE 2024 IN Q.53: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 IN Q.53: answer and solution

GATE 2023 EC Q.48

GATE 2023 · ECQ.48 · 2 marks · MCQ

Let an input $x [n]$ having discrete time Fourier transform $X (e^{j Ω}) = 1 - e^{- j Ω} + 2 e^{- 3 j Ω}$ be passed through an LTI system. The frequency response of the LTI system is $H (e^{j Ω}) = 1 - \frac{1}{2} e^{- j 2Ω}$ . The output $y [n]$ of the system is

(A)
$δ [n] + δ [n - 1] - \frac{1}{2} δ [n - 2] - \frac{5}{2} δ [n - 3] + δ [n - 5]$
(B)
$δ [n] - δ [n - 1] - \frac{1}{2} δ [n - 2] - \frac{5}{2} δ [n - 3] + δ [n - 5]$
(C)
$δ [n] - δ [n - 1] - \frac{1}{2} δ [n - 2] + \frac{5}{2} δ [n - 3] - δ [n - 5]$
(D)
$δ [n] + δ [n - 1] + \frac{1}{2} δ [n - 2] + \frac{5}{2} δ [n - 3] + δ [n - 5]$

Answer and solution

GATE 2023 EC Q.48: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 EC Q.48: answer and solution

GATE 2023 EE Q.50

GATE 2023 · EEQ.50 · 2 marks · NAT

The discrete-time Fourier transform of a signal $x [n]$ is $X (Ω) = (1 + cos Ω) e^{- j Ω}$ . Consider that $x_{p} [n]$ is a periodic signal of period $N = 5$ such that

x_{p} [n] = x [n], for n = 0, 1, 2 = 0, for n = 3, 4

Note that $x_{p} [n] = \sum_{k = 0}^{N - 1} a_{k} e^{j \frac{2 π}{N} k n}$ . The magnitude of the Fourier series coefficient $a_{3}$ is ________ (Round off to 3 decimal places).

Answer and solution

GATE 2023 EE Q.50: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 EE Q.50: answer and solution

GATE 2022 EC Q.55

GATE 2022 · ECQ.55 · 2 marks · NAT

For a vector $\overset{x}{ˉ} = [x [0], x [1], \dots, x [7]]$ , the 8-point discrete Fourier transform (DFT) is denoted by $\overset{ˉ}{X} = D F T (\overset{x}{ˉ}) = [X [0], X [1], \dots, X [7]]$ , where

X [k] = n = 0 \sum 7 x [n] exp (- j \frac{2 π}{8} nk) .

Here, $j = - 1$ . If $\overset{x}{ˉ} = [1, 0, 0, 0, 2, 0, 0, 0]$ and $\overset{y}{ˉ} = D F T (D F T (\overset{x}{ˉ}))$ , then the value of $y [0]$ is ________ (rounded off to one decimal place).

Answer and solution

GATE 2022 EC Q.55: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 EC Q.55: answer and solution

GATE 2020 EC Q.29

GATE 2020 · ECQ.29 · 2 marks · MCQ

A finite duration discrete-time signal $x [n]$ is obtained by sampling the continuous-time signal $x (t) = cos (200 π t)$ at sampling instants $t = n /400$ , $n = 0, 1, \dots, 7$ . The 8-point discrete Fourier transform (DFT) of $x [n]$ is defined as

X [k] = n = 0 \sum 7 x [n] e^{- j \frac{π k n}{4}}, k = 0, 1, \dots, 7.

Which one of the following statements is TRUE?

(A)
All $X [k]$ are non-zero.
(B)
Only $X [4]$ is non-zero.
(C)
Only $X [2]$ and $X [6]$ are non-zero.
(D)
Only $X [3]$ and $X [5]$ are non-zero.

Answer and solution

GATE 2020 EC Q.29: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 EC Q.29: answer and solution

GATE 2020 IN Q.48

GATE 2020 · INQ.48 · 2 marks · NAT

Consider the finite sequence $X = (1, 1, 1)$ . The Inverse Discrete Fourier Transform (IDFT) of $X$ is given as $(x (0), x (1), x (2))$ . The value of $x (2)$ is ____

Answer and solution

GATE 2020 IN Q.48: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 IN Q.48: answer and solution

GATE 2018 EC Q.55

GATE 2018 · ECQ.55 · 2 marks · NAT

Let $X [k] = k + 1, 0 \leq k \leq 7$ be 8-point DFT of a sequence $x [n]$ , where $X [k] = \sum_{n = 0}^{N - 1} x [n] e^{- j 2 π nk / N}$ . The value (correct to two decimal places) of $\sum_{n = 0}^{3} x [2 n]$ is ______.

Answer and solution

GATE 2018 EC Q.55: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 EC Q.55: answer and solution

GATE 2018 IN Q.35

GATE 2018 · INQ.35 · 2 marks · MCQ

For the sequence $x [n] = {1, - 1, 1, - 1}$ , with $n = 0, 1, 2, 3$ , the DFT is computed as $X (k) = \sum_{n = 0}^{3} x [n] e^{- j \frac{2 π}{4} nk}$ , for $k = 0, 1, 2, 3$ . The value of $k$ for which $X (k)$ is not zero is

(A)
0
(B)
1
(C)
2
(D)
3

Answer and solution

GATE 2018 IN Q.35: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 IN Q.35: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 11 mark · MCQ

Let $X [k]$ be the 4-point DFT of $x [n] = {2, - 1, 3, 5}$ , $n = 0, 1, 2, 3$ . The 4-point DFT of the sequence $v [n] = X [n]$ , $n = 0, 1, 2, 3$ , is

(A)
${8, - 4, 12, 20}$
(B)
${8, 20, 12, - 4}$
(C)
${2, 5, 3, - 1}$
(D)
${20, 12, - 4, 8}$

Answer and solution

Answer: (B)

Applying the DFT twice gives $N$ times the circularly reversed sequence: $DFT {X [n]} = N x [(- k)_{N}]$ .
$x [(- k)_{4}] = {x [0], x [3], x [2], x [1]} = {2, 5, 3, - 1}$ ; multiplying by $N = 4$ gives ${8, 20, 12, - 4}$ .
Direct check of the first value: $X [k] = {9, - 1 + 6 j, 1, - 1 - 6 j}$ , and its DFT at $k = 0$ is the sum $9 - 1 + 1 - 1 = 8$ .
A leaves out the reversal and C leaves out the factor $N$ .

PRACTICE 22 marks · NAT

$x [n] = {1, 2, 3}$ and $h [n] = {2, 0, - 1, 1}$ , both starting at $n = 0$ . $X [k]$ and $H [k]$ are their 4-point DFTs ( $x [n]$ zero-padded to length 4), and $y [n]$ is the 4-point IDFT of $X [k] H [k]$ . The value of $y [1]$ is ______.

Answer and solution

Answer: $7$ (accepted range $\pm 0.01$ )

The IDFT of a product of 4-point DFTs is the 4-point circular convolution, not the linear one.
Linear convolution, of length $3 + 4 - 1 = 6$ : $y_{l} [n] = {2, 4, 5, - 1, - 1, 3}$ . Check: the sum is $12 = (6) (2)$ .
Wrap modulo 4: $y [1] = y_{l} [1] + y_{l} [5] = 4 + 3 = 7$ .
Direct check: $y [1] = x [0] h [1] + x [1] h [0] + x [2] h [3] + x [3] h [2] = 0 + 4 + 3 + 0 = 7$ . The full result is $y [n] = {1, 7, 5, - 1}$ .

PRACTICE 31 mark · NAT

A real sequence $x [n]$ , $0 \leq n \leq 3$ , has 4-point DFT values $X [0] = 4$ , $X [1] = 2 - 2 j$ and $X [2] = 0$ , with $W_{4} = e^{- j 2 π /4}$ . The value of $\sum_{n = 0}^{3} ∣ x [n] ∣^{2}$ is ______.

Answer and solution

Answer: $8$ (accepted range $\pm 0.01$ )

$x [n]$ is real, so $X [3] = X^{*} [1] = 2 + 2 j$ .
Parseval: $\sum ∣ x [n] ∣^{2} = \frac{1}{4} (16 + 8 + 0 + 8) = 8$ .
Check: the IDFT gives $x [n] = {2, 2, 0, 0}$ , whose energy is $4 + 4 = 8$ .

PRACTICE 42 marks · MSQ

$x [n] = (0.5)^{n} u [n]$ has DTFT $X (e^{j ω})$ , with $ω$ in rad/sample. Which of the following statements is/are correct?

(A)
$X (e^{j π}) = \frac{2}{3}$
(B)
$\frac{1}{2 π} \int_{- π}^{π} ∣ X (e^{j ω}) ∣^{2} d ω = \frac{4}{3}$
(C)
$∣ X (e^{j ω}) ∣$ is largest at $ω = π$
(D)
If $\tilde{x} [n]$ , $0 \leq n \leq 3$ , is the 4-point IDFT of the samples $X (e^{j 2 π k /4})$ , $k = 0, 1, 2, 3$ , then $\tilde{x} [0] = \frac{16}{15}$

Answer and solution

Answer: (A), (B), (D)

A: $X (e^{j ω}) = \frac{1}{1 - 0.5 e ^{- j ω}}$ . At $ω = π$ , $e^{- j π} = - 1$ , so $X (e^{j π}) = 1/1.5 = 2/3$ . Correct.
B: By Parseval the integral equals $\sum_{n \geq 0} (0.5)^{2 n} = \frac{1}{1 - 0.25} = \frac{4}{3}$ . Correct.
C: $∣ X (e^{j ω}) ∣^{2} = \frac{1}{1.25 - cos ω}$ , which is largest at $ω = 0$ (value $4$ , so $∣ X ∣ = 2$ ) and smallest at $ω = π$ . Incorrect.
D: Sampling the DTFT at 4 points aliases in time: $\tilde{x} [n] = \sum_{r} x [n - 4 r]$ . At $n = 0$ the non-zero terms are $x [0], x [4], x [8], \dots$ , so $\tilde{x} [0] = 1 + (0.5)^{4} + (0.5)^{8} + \dots = \frac{1}{1 - 1/16} = \frac{16}{15}$ . Correct.

PRACTICE 52 marks · MSQ

A signal sampled at $F_{s} = 4$ kHz is recorded for $L = 400$ samples. The record is zero-padded to $N = 512$ and a radix-2 decimation-in-time FFT (bit-reversed input, natural-order output) is computed. Which of the following statements is/are correct?

(A)
The DFT bin spacing is $7.8125$ Hz.
(B)
Zero-padding from $400$ to $512$ points allows two tones $5$ Hz apart to be resolved, which a $400$ -point DFT could not do.
(C)
The FFT requires $2304$ complex multiplications, counting trivial ones.
(D)
With the flow-graph inputs numbered $0$ to $511$ , the sample $x [1]$ is applied at input position $256$ .

Answer and solution

Answer: (A), (C), (D)

A: $F_{s} / N = 4000/512 = 7.8125$ Hz. Correct.
B: Resolution depends on the record length, $F_{s} / L = 4000/400 = 10$ Hz, and zero padding does not change it. Incorrect.
C: $\frac{N}{2} lo g_{2} N = 256 \times 9 = 2304$ . Correct.
D: In $ν = 9$ bits, $1 = 000000001$ reverses to $100000000 = 256$ . Correct.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE EC

DTFT, DFT

GATE EE

Applications of Fourier Transform for … discrete time signals

GATE IN

DFT and FFT

Preparing in Kolkata? IAE Academy's course for GATE ECE, GATE EE or GATE IN.