# FFT calculation of an N-tap FIR filter

I have the following question:

a) For an N-tap FIR filter, sketch the direct form realization. How many multipliers per sample? You may choose 8.

b) For an FFT calculation of an N-tap filter sketch the realization. (N=8, FFT size is 256)

The answer to a) is given here, and I think 8 multipliers are needed per sample, assuming an 8-tap filter.

With respect to b) I am confused. I don't know how to form a realization of the FFT of a filter. Could somebody help me out with b). Thanks!

## 1 Answer

hint only, since this is homework and you could get a lot out of this!

The mathematical operation a filter performs between filter impulse response and signal is called __________(1). When we process both filter and signal with an FFT (which is just a fast implementation of __________(2)), then that operation on the originals is equivalent to __________(3) after the (2).

To do (3) on both (2)'ed vectors, these vectors need to be of the same __________(4), here 256. Often, the signal itself is longer than 256 - (length of filter). This is a problem, because (1) under the (2) is not __________(5) as the filtering operation normally is, but __________(6) due to the periodic nature of the (2).

To alleviate this, a segmented approach is chosen.

• (1) Convolution, (2) Discrete fourier transform, (3) Multiplication, (4) size/length, (5) finite, (6) infinite. Are my answers correct? Thanks for just not giving me the answer but adding this little puzzle! Jan 18, 2021 at 22:15
• (5) and (6): I meant: acyclic and cyclic, respectively, but I think you've got it. Jan 18, 2021 at 23:35
• I was thinking; I am still a little confused, because the problem is asking for the realization. What would that look like? Sorry for coming back, but I was thinking through, and it's not clear to me yet. Jan 28, 2021 at 4:08
• well if you want a cyclic convolution, your block diagram "explains itself": input FFT, filter FFT, multiplication, IFFT. For the acyclic, go and look for "segmented convolution", and especially "overlap-add" methods. Jan 28, 2021 at 8:31