# Linear convolution of a 100 sample time series and a 20 tap filter in the frequency domain

I came across this question on an internship application. For context, I'm three years into my bachelor's for electrical engineering right now. I have learned continuous and discreet convolutions, so I feel like I should know how to answer this question.

I have never heard of "20 tap filter". Is that just a FIR filter with 20 coefficients?

Here's my attempt:

If I was to use something like MATLAB, I would let t = 100 time series and h = 20 tap filter transfer function. Then zero pad both to the correct length to prevent circular convolution. Correct length = (length of x) + (length of h)-1.

Then, Linear convolution= invFFT[FFT{t} * FFT{h)]

Is that a good and proper answer?

• Welcome to SE.SP! The tap question is answered here
– Peter K.
Commented May 17 at 11:32

I have never heard of "20 tap filter". Is that just a FIR filter with 20 coefficients?

yes. (some functions for filtering make it a bit confusing what is the number of coefficients and what is the order of the system, which is one less, but you're not doing that here.)

Is that a good and proper answer?

For a signal length of 100: Sounds like it!

If you want to know how FIR filters are applied in discrete frequency domain to infinitely long series $$x$$, look up the overlap-add and overlap-save methods of fast convolution.

• Thank you for the clarification, Marcus! I will loop into overlap-add and overlap-save methods for my curiosity. Commented May 17 at 20:55

So the linear convolution correct length is as you say: $$N_t + N_h - 1$$ where $$N_t$$ is the length of $$t$$ (e.g. 100) and $$N_h$$ is the length of $$h$$ (e.g. 20).

This equation: $${\tt FFT}^{-1} \left [ {\tt FFT}[t] {\tt FFT}[h] \right]$$ is a little problematic because $${\tt FFT}[\cdot]$$ usually implies taking the FFT of the argument with the FFT length being the same length as the argument. For example, $${\tt FFT}[t]$$ would take an FFT length of 100.

That's a problem because $${\tt FFT}[t]$$ and $${\tt FFT}[h]$$ are of different lengths, and we really want the output to be of the same length as the linear convolution.

To get that length and to avoid "time domain aliasing", both FFTs must be zero-padded to length $$N_t + N_h -1$$.

• Indeed, I'm glad you're spelling that out. I just read "correct length" in the question and mentally implied that, but that can go pretty wrong :) Commented May 17 at 11:42
• Thank you very much for the detailed explanation! Commented May 17 at 20:55