Visual
Hub intro
Digital Signal Processing builds directly on signals and systems but requires comfort with discrete-time mathematics, the DFT, and filter design methods. This hub begins with DFT properties and circular convolution at the beginner level, moves to FIR and IIR filter design techniques at the intermediate level, and ends with GATE-style problems involving filter specifications, DFT symmetry, and overlap-add implementation at the advanced level.
Difficulty levels
BeginnerIntermediateAdvanced
Practice sets
Beginner: DFT Basics and Discrete-Time Fundamentals
BeginnerWrite the definition of the N-point DFT of a sequence x[n].
Answer: X[k] = sum from n=0 to N-1 of x[n] × W_N^(nk), where W_N = e^(-j2π/N). The inverse DFT is x[n] = (1/N) × sum from k=0 to N-1 of X[k] × W_N^(-nk).
The DFT analyses a finite-length sequence in the frequency domain at N uniformly spaced frequencies ω_k = 2πk/N. The twiddle factor W_N = e^(-j2π/N) is a complex rotation. The IDFT reconstructs the time-domain sequence from its DFT coefficients. The DFT assumes the sequence is periodic with period N; this is why the DFT of a finite non-periodic sequence may exhibit spectral leakage.
What is the computational complexity of the direct DFT computation for an N-point sequence, and how does the FFT reduce this?
Answer: Direct DFT: O(N²) complex multiplications and additions. FFT (Cooley-Tukey radix-2): O(N log2 N). For N=1024: direct DFT needs ~10^6 operations; FFT needs ~10240.
The DFT of N points requires N² complex multiplications (each of N output values X[k] requires N multiplications). The radix-2 FFT exploits symmetry and periodicity of the twiddle factor to decompose the N-point DFT into log2(N) stages, each requiring N/2 butterfly operations, giving N/2 × log2(N) complex multiplications. For N=1024, FFT reduces the count from 10^6 to 5120 multiplications, a reduction by a factor of approximately N/log2(N) ≈ 100.
State the circular shift property of the DFT: if X[k] = DFT{x[n]}, what is the DFT of x[(n-m) mod N]?
Answer: DFT{x[(n-m) mod N]} = W_N^(mk) × X[k] = e^(-j2πmk/N) × X[k].
A circular shift of the sequence by m samples corresponds to multiplication of its DFT by the complex exponential e^(-j2πmk/N). This is the discrete-time counterpart of the time-shift property of the Fourier transform. The modulo N operation reflects the periodicity of the DFT. The magnitude |X[k]| is unchanged; only the phase is modified by -2πmk/N.
What is the difference between linear convolution and circular convolution? Under what condition do they produce the same result?
Answer: Linear convolution of x[n] (length M) and h[n] (length N) produces a sequence of length M+N-1. Circular convolution of length L produces a length-L periodic sequence. They agree when L ≥ M+N-1 (i.e. the circular length is at least as long as the linear convolution output).
In circular convolution, the indices wrap around modulo L. If L < M+N-1, the circular convolution is a time-aliased version of the linear convolution (the tails wrap and add to the beginning). Choosing L = M+N-1 or larger (typically the next power of 2 for FFT efficiency) ensures the circular result matches the linear result. This is the basis for fast convolution using the FFT.
Define the frequency resolution of an N-point DFT applied to a sequence sampled at rate fs.
Answer: Frequency resolution Δf = fs/N Hz. Finer resolution requires either a longer data record or a higher sampling rate.
The N-point DFT produces N frequency bins spaced at intervals of Δf = fs/N. For example, if fs = 8000 Hz and N = 512, Δf = 8000/512 = 15.625 Hz per bin. To resolve two frequency components separated by Δf Hz, at least N = fs/Δf points are needed. Increasing N by zero-padding does not improve true frequency resolution (it interpolates existing spectral values) but increasing the data record length does.
Intermediate: Filter Design and Spectral Analysis
IntermediateDesign a 5-tap FIR low-pass filter using a rectangular window with cutoff frequency ωc = π/4 rad/sample. Write the ideal impulse response and the windowed coefficients.
Answer: hd[n] = sin(ωc(n-M/2)) / (π(n-M/2)) for n ≠ M/2, and hd[M/2] = ωc/π. For M=4 (5 taps, M/2=2): hd[2]=0.25, hd[1]=hd[3]=sin(π/4×1)/π = 0.2251, hd[0]=hd[4]=sin(π/4×2)/(2π) = sin(π/2)/(2π) = 1/(2π) ≈ 0.1592.
The ideal low-pass FIR filter impulse response is a sinc function centred at n=M/2 (for a causal filter of length M+1). With ωc=π/4 and M=4: h[0]=h[4]=sin(π/4×2)/(2π)=sin(π/2)/(2π)=1/(2π)≈0.159. h[1]=h[3]=sin(π/4×1)/(π×1)=sin(π/4)/π=(√2/2)/π≈0.225. h[2]=ωc/π=(π/4)/π=0.25. The rectangular window passes the coefficients unchanged; better windows (Hamming, Hanning) reduce sidelobe levels at the cost of wider transition bandwidth.
An IIR filter has system function H(z) = 1/(1 - 0.8z^(-1)). Write its difference equation and determine whether it is FIR or IIR.
Answer: Difference equation: y[n] = 0.8y[n-1] + x[n]. This is an IIR filter because the output depends on past output values, leading to an infinite-duration impulse response.
From H(z) = Y(z)/X(z) = 1/(1-0.8z^(-1)): Y(z) = 0.8z^(-1)Y(z) + X(z). Taking the inverse z-transform: y[n] = 0.8y[n-1] + x[n]. The impulse response h[n] = (0.8)^n u[n], which decays but is nonzero for all n ≥ 0, hence IIR. FIR filters have no feedback; their difference equations contain only x[n-k] terms and the impulse response has finite duration.
Explain the frequency transformation used to convert a low-pass prototype filter to a high-pass digital filter.
Answer: Replace z^(-1) by -z^(-1) in the low-pass filter transfer function H_LP(z). This maps ω → π - ω, converting the low-pass frequency response to high-pass.
The spectral transformation z^(-1) → -z^(-1) corresponds to multiplying n by (-1)^n in the time domain, which modulates the spectrum by e^(jπn) = (-1)^n, shifting all frequencies by π. So DC (ω=0) maps to the Nyquist frequency (ω=π) and vice versa, turning a low-pass filter into a high-pass filter. Bandpass and bandstop transformations involve more complex substitutions for z^(-1).
An 8-point DFT of a real sequence x[n] is computed. X[0] = 4, X[1] = 1-j2. Using the conjugate symmetry property of the DFT, find X[7] and X[4].
Answer: X[7] = X*[N-7] = X*[1] = (1-j2)* = 1+j2. X[4] = X*[N-4] = X*[4], so X[4] must be real.
For a real sequence x[n], the DFT satisfies X[k] = X*[N-k] (conjugate symmetry). Therefore X[7] = X*[8-7] = X*[1] = (1-j2)* = 1+j2. For X[4]: X[4] = X*[8-4] = X*[4], meaning X[4] equals its own complex conjugate, so X[4] must be real. Similarly X[0] must be real (it is the sum of all samples). These symmetry properties reduce the computation: for a real N-point sequence, only N/2+1 DFT values need to be computed.
Describe the overlap-add method for filtering a long input sequence using a short FIR filter.
Answer: Divide the input into non-overlapping blocks of length L. Compute the linear convolution (via FFT) of each block with the filter h[n] of length M. Each output block has length L+M-1. Add the overlapping portions (the last M-1 samples of one output block overlap with the first M-1 of the next). Concatenate to form the output.
The overlap-add method exploits the FFT for efficient block convolution. Block size L is chosen for FFT efficiency: FFT length = L+M-1 (rounded up to next power of 2). Each block requires one FFT of the input segment, one FFT of the filter (computed once), one pointwise multiplication, and one IFFT. The overlap region of length M-1 at the end of each block must be added to the start of the next processed block. This method avoids storing the entire long input in memory.
Advanced: GATE-Style Problems
AdvancedCompute the 4-point DFT of x[n] = {1, 1, 1, 1} directly from the definition.
Answer: X[0] = 4, X[1] = 0, X[2] = 0, X[3] = 0.
X[k] = sum_{n=0}^{3} x[n] × e^(-j2πkn/4) = sum_{n=0}^{3} 1 × e^(-jπkn/2). For k=0: X[0] = 1+1+1+1 = 4. For k=1: X[1] = e^0 + e^(-jπ/2) + e^(-jπ) + e^(-j3π/2) = 1 + (-j) + (-1) + j = 0. For k=2: X[2] = 1 + e^(-jπ) + e^(-j2π) + e^(-j3π) = 1-1+1-1 = 0. For k=3: X[3] = 1 + e^(-j3π/2) + e^(-j3π) + e^(-j9π/2) = 1+j+(-1)+(-j) = 0. The DFT of a constant (DC) sequence has energy only at k=0.
An FIR filter has the transfer function H(z) = 1 + 2z^(-1) + z^(-2). Is this filter linear phase? Find the group delay.
Answer: Yes, the filter is linear phase because the coefficients are symmetric: h[0]=1, h[1]=2, h[2]=1. Group delay = M/2 = 2/2 = 1 sample.
A causal FIR filter of length M+1 has linear phase if its coefficients satisfy h[n] = h[M-n] (symmetric) or h[n] = -h[M-n] (antisymmetric). Here M=2: h[0]=1, h[1]=2, h[2]=1. h[0]=h[2]=1 (symmetric). Linear phase means the phase response is φ(ω) = -ωM/2, corresponding to a constant group delay of M/2 = 1 sample for all frequencies. Linear phase is a key advantage of FIR filters over IIR filters, particularly for data transmission.
A digital Butterworth low-pass filter is designed using the bilinear transformation from an analogue prototype with cutoff at Ωc = 1 rad/s. If the digital cutoff is at ωd = π/4 rad/sample and the sampling period T = 1 s, find the pre-warped analogue frequency.
Answer: Ωa = (2/T) × tan(ωd/2) = 2 × tan(π/8) = 2 × 0.4142 ≈ 0.828 rad/s.
The bilinear transformation maps s = (2/T)×(z-1)/(z+1). This introduces frequency warping: the digital frequency ωd maps to the analogue frequency Ωa = (2/T)×tan(ωd/2). For the filter to have the correct digital cutoff ωd = π/4, design the analogue prototype with cutoff at Ωa = 2×tan(π/8). tan(π/8) = tan(22.5°) = √2 - 1 ≈ 0.4142. So Ωa = 2 × 0.4142 ≈ 0.828 rad/s. Design the Butterworth prototype with this cutoff, then apply the bilinear transformation to obtain the digital filter.
An N-point DFT has X[k] as its output. If the input is shifted circularly by N/2 positions to give x[(n-N/2) mod N], express the new DFT in terms of X[k].
Answer: DFT{x[(n-N/2) mod N]} = e^(-j2π(N/2)k/N) × X[k] = e^(-jπk) × X[k] = (-1)^k × X[k].
Using the circular shift property: DFT{x[(n-m) mod N]} = W_N^(mk) × X[k] = e^(-j2πmk/N) × X[k]. With m = N/2: e^(-j2π(N/2)k/N) = e^(-jπk) = (e^(-jπ))^k = (-1)^k. So every alternate DFT coefficient is negated. Even-indexed X[k] remain unchanged; odd-indexed X[k] are multiplied by -1. This is the discrete-time equivalent of modulating by e^(jπn) = (-1)^n in the time domain, which shifts the spectrum by π.
A causal IIR filter has poles at z = 0.5 and z = -0.5j. Is the filter stable? If so, what is the ROC of H(z)?
Answer: Both poles are inside the unit circle: |0.5| = 0.5 < 1 and |-0.5j| = 0.5 < 1. The filter is stable. ROC: |z| > 0.5 (for causal filter, ROC is outside the outermost pole).
For a causal discrete-time system, stability requires all poles to lie strictly inside the unit circle |z| = 1. Here both poles have magnitude 0.5, which is inside the unit circle. The ROC of a causal system is |z| > max(|pole magnitudes|) = 0.5. Since the ROC includes the unit circle (|z|=1 > 0.5), the system is BIBO stable. If any pole were on or outside the unit circle, the causal system would be unstable.
Lab exercises
- Compute and plot the 8-point DFT of a sinusoidal sequence in MATLAB and verify the spectral peaks at the correct frequency bins: /labs/dft-sinusoid-matlab-lab
- Design and implement a 21-tap FIR low-pass filter using the Hamming window and plot its frequency response: /labs/fir-hamming-window-design-lab
- Apply the overlap-add method to filter a 1000-sample sequence using a 10-tap FIR filter and verify against direct convolution: /labs/overlap-add-fir-filtering-lab
Revision checklist
- Can you compute the 4-point DFT of a simple sequence by hand using the definition?
- Do you know when circular convolution gives the same result as linear convolution?
- Can you identify whether a given FIR filter has linear phase from its coefficient symmetry?
- Do you know the pre-warping formula for the bilinear transformation and why it is needed?
- Can you determine the stability of a digital filter from its pole locations relative to the unit circle?