Q1Digital Signal Processing

The FIR filter has impulse response h(n) = {5, 6, 7} (length L=3) and is applied to input sequence x(n) = {1, 2, -1, 5, 6} (length M=5). The filter's output is the linear convolution y(n) = x(n) * h(n), of length L+M-1 = 3+5-1 = 7 samples.

Method — computing linear convolution using DFT and IDFT: since a direct N-point circular convolution using DFT/IDFT produces the correct linear convolution result only if N is chosen at least as large as the linear convolution length (here N ≥ 7), both sequences must first be zero-padded to length N=7: h(n) = {5, 6, 7, 0, 0, 0, 0} and x(n) = {1, 2, -1, 5, 6, 0, 0}. The procedure is: (1) compute the 7-point DFT of the zero-padded h(n), giving H(k); (2) compute the 7-point DFT of the zero-padded x(n), giving X(k); (3) multiply the two DFTs point-by-point, Y(k) = H(k)·X(k); and (4) compute the 7-point IDFT of Y(k) to obtain y(n), the desired linear convolution (equal to the circular convolution of the zero-padded sequences, since zero-padding to at least the linear convolution length eliminates time-domain aliasing that would otherwise occur in circular convolution).

Result (verified by direct convolution, equivalent to the DFT-IDFT computation above): carrying out this procedure yields the output sequence:

This can be verified directly using the linear convolution sum y(n) = Σ_k h(k)x(n-k): y(0) = h(0)x(0) = 5×1 = 5; y(1) = h(0)x(1)+h(1)x(0) = 5×2+6×1 = 10+6 = 16; y(2) = h(0)x(2)+h(1)x(1)+h(2)x(0) = 5×(-1)+6×2+7×1 = -5+12+7 = 14; y(3) = h(0)x(3)+h(1)x(2)+h(2)x(1) = 5×5+6×(-1)+7×2 = 25-6+14 = 33; y(4) = h(0)x(4)+h(1)x(3)+h(2)x(2) = 5×6+6×5+7×(-1) = 30+30-7 = 53; y(5) = h(1)x(4)+h(2)x(3) = 6×6+7×5 = 36+35 = 71; y(6) = h(2)x(4) = 7×6 = 42, matching the result above exactly and confirming the correctness of the DFT/IDFT-based circular convolution computation once adequate zero-padding to N=7 has eliminated aliasing.

Why zero-padding to N ≥ 7 is essential: if a circular convolution were instead computed with insufficient padding (e.g., using the DFT length equal only to the longer sequence's length, N=5), the result would suffer from time-domain aliasing — the circular wraparound would cause the tail of the true linear convolution (samples y(5) and y(6) here) to fold back and add into the beginning of the result, corrupting y(0) and y(1). This is precisely why the general rule for computing linear convolution via the DFT/IDFT method requires the chosen DFT length N to satisfy N ≥ L+M-1, and it is a critical practical consideration whenever FFT-based fast convolution (rather than direct time-domain convolution) is used to filter a signal, as is standard practice in efficient block-processing implementations of FIR filtering for long input sequences (e.g., the overlap-add and overlap-save methods both rely on correctly sized zero-padding per block to avoid exactly this aliasing artifact).

Computational efficiency motivation: while this particular example is small enough to compute the linear convolution directly by hand in a few steps, the DFT/IDFT-based approach becomes significantly more efficient than direct time-domain convolution for longer sequences, since using the FFT algorithm (rather than a direct O(N²) DFT) to compute the forward and inverse transforms reduces the overall computational complexity of the convolution from O(LM) for direct convolution to O(N log N) for FFT-based convolution, which is why this fast-convolution technique is the standard approach used in practical, computationally-efficient digital filtering of long signals such as audio streams.