Fast Fourier Transform in Real Time

[olbert]

I guess this is programming and physics all combined into one but hopefully I can get some help anyway.

I am doing some signal analysis of real-time streaming sensor data. I would like to do a DFFT on the data in real time as it streams in. So far pretty easy, however, there are a number of issues that make it more complicated - not the least of which is that I haven't dealt with FFT's since university.

Firstly I only want to do a transform on the most recent block of data, ie, I only want to know the frequencies from the last 10 seconds. Any data older than that is already out of date and useless.

Speed is a major issue as I want the spectrum of the data to be always up to date. Every new sample that comes in I want a new spectrum.

I was hoping that there was a function that calculate the transform one sample at a time and also remove a sample once it's too old. So in other words, in my program call the function 'FFT = FFT_Add_New_Sample(newSample);' and then call the function 'FFT = FFT_Remove_Old_Sample(oldSample);' once a sample becomes to old.

The idea would be that the whole FFT would not be recalculated with every new sample, just modified speedily with the new data coming in and old data going out.

I have no idea if this is even mathematically possible but if it was, it would be a great help!

 

[K^2]

I wouldn't use FFT for this, except maybe for the first block of samples. Once you have a DFT of N elements, you can compute contribution from the 1st element, and subtract it from each component of DFT. You can then shift samples back, which will be rotation by 2nPi/N in complex plane, and and add a new Nth sample by computing its contribution for each component. Of course, it's easier to do this for each component at a time, so your overall operation of removing an old sample and adding a new one is just order O(N), which is probably not too bad for real time, depending on your sample rate and value of N.

 

[AlephZero]

You haven't told us the most important thing: what is the sampling rate and how many samples are in the "10 seconds" of data for your FFT.

If you are taking 1 sample per second doing this is trivial. For 1 million samples per second it's impossible.

Another question is how you are going to use with each set up updated frequencies, and whether you really need an update for every sample, or whether an update every n samples is good enough (where n might be smaller than the number of samples in each FFT, but not 1)

 

[olbert]

At the moment, the data is coming in at 120Hz, and there is a possibility I might want to do it on multiple 120Hz streams of data.

It should be possible to perform the calculation on every few samples or a summary of a few sample rather than every single new sample.

The problem is that this isn't the only calculation I will be doing, I am doing a bunch of things concurrently, so that even if I can do what I want to with the FFT in a reasonable time, it might still be too much.

In other words, I am looking towards speed rather than accuracy (though clearly there has to be some level of accuracy to be useful).

 

[olbert]

Ok, so here is my summation:

Do the DFT properly once to get the sequence X. Then modify each element of X using the following formula:

X_k,t+1 = X_k,t e^-i2Pi(k/N) - x_t-tN + x_t+1 e^-i2Pi(k/N)

Where:
- X is the spectrum of x.
- N is the number of elements in both X and x (and also in the time period t_N)
- t is the time instant that this occurs.
- t+1 is the next time instant that a new element is received from the sensor.
- X_k is the k^th element of the sequence X.

Is this correct? Is this a reasonable approach? Am I reinventing the wheel?

 

[AlephZero]

You could do something like that, but it takes O(n) operations for each new data point where n is the length of the FFT.

But doing a completely new DFT only takes O(n log n) operations, so you aren't saving much.

You are also ingnoring windowing. If you don't use a windowing function your DFT will contain a lot of "noise", becuse effectively you are taking a set of data samples and sticking an infinite number of copies end to end to make a periodic function, but ignoring the fact that the arbitrary end points don't "match up" properly. If you include a simple window (e.g. Hanning or Hamming) the FFT data will look nicer, but trying to add and remove one sample at a time is more complicated.

I would consider just doing a new DFT every "k" samples, where k is the smallest number you can use depending on your computer. For your low sampling rate k won't be very big, and it might even be 1.

 

[the_emi_guy]

Are you constrained to using a desktop computer?

 

[marcusl]

120Hz? Forget the fancy talk. That's so slow that you can even do this in Matlab on a PC and still keep up in real time!

10 seconds of data have 1200 samples, and you have 8.3 ms to take the transform before the next sample arrives. A 2048 point FFT takes an average of 35 us to compute in Matlab on my PC, even with Outlook, Excel, Firefox and everything else running in the background. (I just tried it.)

 

[AlephZero]

10 seconds of data have 1200 samples

For some reason I mis-remembered the OP as saying 10 minutes of data not 10 seconds - which would make it a bit more challenging, but not obviously impossible.