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 ?

  • $\begingroup$ 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. $\endgroup$ – robert bristow-johnson Jan 17 '14 at 15:41
  • 6
    $\begingroup$ 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. $\endgroup$ – Jim Clay Jan 17 '14 at 16:03
  • $\begingroup$ 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 ? $\endgroup$ – Arnaud Jan 18 '14 at 11:19
  • $\begingroup$ 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 ? $\endgroup$ – Arnaud Jan 18 '14 at 11:21
  • $\begingroup$ @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. $\endgroup$ – robert bristow-johnson Jan 19 '14 at 17:24

If you have a data sequence that is larger than the size of data window used in each FFT, then you will need to use an algorithm such as overlap-add or save. The size of the FFT should be equal to or larger than the sum of the data window plus the impulse response of your filter (your windowed Sinc). The size of your windowed Sinc will be related to your desired filter transition width and frequency.

| improve this answer | |
  • $\begingroup$ Thx hotpaw2 : I will perform only one FFT at a time. WE have a track of data, we will choose a segment of N (1024/2048/4096 pts) data and perform FFT, Filtering, IFFT. You say that the size of the FFT is >= size of data+filter impulse response. I don't understand, which FFT ? My data one, my filter one, I'm lost on this one. The resulting FFT ? $\endgroup$ – Arnaud Jan 18 '14 at 11:31
  • $\begingroup$ See the first part of my answer. Say with a N=4096 FFT you can use a spacing of the segments of L=2048, an overlap of D=1024, that is, in each FFT you take L+D=3072 samples from the signal, and a filter length of F=1024. $\endgroup$ – Lutz Lehmann Jan 18 '14 at 11:36
  • $\begingroup$ @Arnaud: For which FFT size, please read about and study the overlap-add or overlap-save fast convolution algorithms. There are too many important small details to post here. $\endgroup$ – hotpaw2 Jan 18 '14 at 17:08

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$.

The combination of filtering and downsampling can be factored into steps in the so-called lifting scheme. For short filters like those of the discrete wavelet transform, this is faster than overlap-add. Using the idea of the Remez-algorithm, relatively short wavelet transforms with good frequency separation can be constructed.

| improve this answer | |
  • $\begingroup$ Thx LutzL : I will look into wavelets transforms but considering the time already spent on FFT I have almost reached my goal, I just need a couple of last advice on how to properly apply my filter FFT on my data FFT. I have already found information about wavelets tranform on the net but wasn't sure if it's the good way to go for my "low frequency elimination problem". $\endgroup$ – Arnaud Jan 18 '14 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.