# Filter size vs. FFT size and Overlap add

### First of all I would like to say that :

1. I'm new to DSP and in a "learning curve" hence the "basicness" of my questions.
2. I've read as many posts/articles as possible on the internet but still need "guidance".
3. I'm french hence the bad formulation sometimes.

### My mission/data context :

Performing data analysis on real data sets (oil-rig data). Sometimes data collected on the rig present low frequency component due to rig movements. Data are collected every 5 seconds so the sampling rate is 0.2 Hz. The size of the data to be analysed will be 1024/2048/4096 points let's call it N is this post. My mission is to perform a filtering on these data to eliminate the low frequency component. This is not a real time application. The range of data to be analysed will be chosen and then the analysis performed.

### Chosen approach :

Process these data with a FFT, filtering the FFT and perform an IFFT to obtain and clean(er) set of data. Basically the lowest frequency found in the FFT is to be eliminated. Many users suggested me to use the overlap-add method to obtain the desired result. First I was thinking of just zeroing low frequency related bins in my FFT but my readings on the subject suggested to rather use a high pass filtering (with spectral inverted windowed-sinc).

Designing this filter and applying it is what I post here for because it turned out to be way more difficult than expected.

### Questions :

Do I have to use the overlap-add method considering that my application is not a real time one ?

For what I have understood I need to design a high pass filter kernel with a spectral inverted sinc function. Then I have to perform a FFT on my filter kernel and multiply points by points my filter FFT(1) coefficients with my data FFT(2) coefficient before performing a IFFT on the resulting FFT. Am I correct on this one ?

1. According to my readings I can obtain a spectral inverted sinc function by inverting (-sin(x)/x) it and adding 1 to the center of symmetry. I am right, do you guys confirm ? Do I add 1 on the one center point only ?

2. What is the right size to choose for my filter kernel ? Is it the same size N as my data ? As I have to multiply my FFT(1) with my FFT(2) I would think that I have to choose the same size but I'm probably wrong on this one and the overlap add method may be the answer.

3. The kernel filter designing is tricky, I don't know where to place the central lobe of my spectral inverted sinc, in 0, on a specific offset in the time domain ?

• there's a lot to your question, and i don't have time to go through it all. no, you need not overlap-add if the size of your data fits nicely into the FFT. you might want to window and zero-pad it. maybe not. remember that the FFT essentially periodically extends whatever data set passed to it. so you might need to worry about the edges. – robert bristow-johnson Jan 17 '14 at 15:41
• Unless you need to squeak out every drop of performance that you can, I would highly recommend not filtering using FFT's. Filter in the time domain. For shorter filters this is actually more computationally efficient than filtering with FFT's anyways. – Jim Clay Jan 17 '14 at 16:03
• Thx Robert : What do you mean by "the size of the data fits in the FFT". For now, I choose let's say 2048 points of data and perform an FFT, as my data is Real I obtain an Hermitian symetric FFT of 1024 usefull complex points. What must I window or pad ? – Arnaud Jan 18 '14 at 11:19
• Thx Jim : Do you have any hints on how to filter in the time domain ? (something I haven't wrapped my mind around at the moment) Any good links on the subject ? – Arnaud Jan 18 '14 at 11:21
• @Arnaud, i cannot think of a simpler way to put it. if your 2048 data points fit into the 2048-point DFT, there is no issue of breaking up the data to make it fit and overlapping the results of multiple uses of the DFT. now, if you are putting 2048 non-zero samples into a 2048-point DFT, you must keep in mind the discontinuity that exists between $x[2047]$ and $x[0]$ because of the inherent periodic extension done by the DFT. FYI, the "FFT" is an efficient method to compute the DFT. all of the mathematical properties of the DFT apply. – robert bristow-johnson Jan 19 '14 at 17:24

To do the computation of overlap-add: You divide the signal into segments starting at indices $kL$ using an overlap of size $D$, that is, between kL and kL+D there is a cross-fade adding to 1 of the segment $(k-1)$ and segment $k$. Applying a filter of finite length is equivalent to polynomial multiplication. The windowed $k$th segment of length $L+D$ and the filter of length $F$ result in a filtered segment of length $L+D+F-1$. This is the size that has to fit in the dyadic FFT-length $N$. After zeropadding, FFT, multiplication with the FFT of the filter and iFFT the filtered segment is added in its full length $N$ to the output signal starting at positon $kL$.