Real Fast Fourier Transform (FFT) in Qt

Mr.Floppy

At goocreations:
Don't be sorry! It's all good :)

I have embedded your code from gitHub directly to my project and it works!
I will get back to the library when I am done testing.

For now I have another, more mathematical question:

As far as I can tell, each index in the fft-array represents one frequency, that fits completely into the window I am watching.
For example 10hz in a 1 second window will result in a sharp imaginary Peak at index (FFT_SIZE/2 + 10).

What if my window is 1 second long and my frequency is 10.25Hz.
Is it possible to generate a sharp peak for that, too?
Sorry that I can't explain it better, but I have attached a picture where I have done a "frequency sweep" from 10Hz to 11Hz.

"frequency_sweep.png":http://i.imgur.com/85jCQO4.png

The spectrum is the output of the forwardTransformation, rescaled like this:
@result = 2 * sqrt(real_part ^ 2 + imaginary_part ^ 2) / FFT_SIZE@

10Hz and 11Hz give sharp peaks, anything in between is not humanly readable.

Can I "up the resolution" from 1Hz to, let's say 0.25Hz, so that every spectrum in the picture would show just one peak?
Or is that mathematically impossible / absurd?

Again, sorry, I am mighty confused right now and don't exactly know what I am talking about ;)

My final goal is to look at a window of 1 second and to get sharp peaks for tenths of a Hz...

At kumararajas:
Sorry for being so vague, but that is basically all the code that mattered.
I started a new QWidgets Project, added the one line I have posted to the .pro file, loaded goocreations' headers into the project and tried to create a QFourierTransformer object in the MainWindow constructor.
I will get back to that as soon as I have figured out a bunch of other stuff ;)

Mr.Floppy

At goocreations:
Don't be sorry! It's all good :)

I have embedded your code from gitHub directly to my project and it works!
I will get back to the library when I am done testing.

For now I have another, more mathematical question:

As far as I can tell, each index in the fft-array represents one frequency, that fits completely into the window I am watching.
For example 10hz in a 1 second window will result in a sharp imaginary Peak at index (FFT_SIZE/2 + 10).

What if my window is 1 second long and my frequency is 10.25Hz.
Is it possible to generate a sharp peak for that, too?
Sorry that I can't explain it better, but I have attached a picture where I have done a "frequency sweep" from 10Hz to 11Hz.

"frequency_sweep.png":http://i.imgur.com/85jCQO4.png

The spectrum is the output of the forwardTransformation, rescaled like this:
@result = 2 * sqrt(real_part ^ 2 + imaginary_part ^ 2) / FFT_SIZE@

10Hz and 11Hz give sharp peaks, anything in between is not humanly readable.

Can I "up the resolution" from 1Hz to, let's say 0.25Hz, so that every spectrum in the picture would show just one peak?
Or is that mathematically impossible / absurd?

Again, sorry, I am mighty confused right now and don't exactly know what I am talking about ;)

My final goal is to look at a window of 1 second and to get sharp peaks for tenths of a Hz...

At kumararajas:
Sorry for being so vague, but that is basically all the code that mattered.
I started a new QWidgets Project, added the one line I have posted to the .pro file, loaded goocreations' headers into the project and tried to create a QFourierTransformer object in the MainWindow constructor.
I will get back to that as soon as I have figured out a bunch of other stuff ;)

goocreations

Yeah, you are right, I don't completely understand what you are looking for. As far as I understand, you want to change the resolution of your output frequencies, is that right? You can achieve that by:

Change the resolution of your time-domain inputs. A smaller window of samples will result in a lower resolution in the frequency spectrum. A larger window is equal to higher resolution frequencies. That means you either have to change your input duration of 1s or change the sample rate. If you want to keep 1s at 10 Hz for some reason, I would go with option two.
Ignore the time-domain and simply "resample" the frequencies. There are many ways to do this, just google for "resampling". An easy way to get half the resolution, is to simply average the neighboring frequencies. To increase the resolution, simply add frequencies in between, by taking the average of the left and right frequency. If you upsample using this technique, you will loose information/accuracy and I would rather go with a well-known algorithm that can do that accurately.

Hope I understood you correctly.

goocreations

Yeah, you are right, I don't completely understand what you are looking for. As far as I understand, you want to change the resolution of your output frequencies, is that right? You can achieve that by:

Change the resolution of your time-domain inputs. A smaller window of samples will result in a lower resolution in the frequency spectrum. A larger window is equal to higher resolution frequencies. That means you either have to change your input duration of 1s or change the sample rate. If you want to keep 1s at 10 Hz for some reason, I would go with option two.
Ignore the time-domain and simply "resample" the frequencies. There are many ways to do this, just google for "resampling". An easy way to get half the resolution, is to simply average the neighboring frequencies. To increase the resolution, simply add frequencies in between, by taking the average of the left and right frequency. If you upsample using this technique, you will loose information/accuracy and I would rather go with a well-known algorithm that can do that accurately.

Hope I understood you correctly.

Mr.Floppy

Thanks for the quick response!

I think you understood correctly.
I will look into option 2, but what do you mean by "change the sample rate" in option 1?

Let's say, I have an analogue signal that contains valuable information between 0 and 2 Hz. The sampling frequency of the a/d converter is 100Hz.

To transform roughly one second of this signal, I have to set my FFT_SIZE to 128 and the output array will contain level information between 0 and 128Hz. That's because the input and output array have to be the same size... correct?

If I increase the a/d sampling frequency to 1kHz, my FFT_SIZE would have to be 1024 and the output array will contain level information between 0 and 1024Hz... at least that's what I think.

I COULD increase my sampling window to 10 seconds, but I don't want to ;)

What I want is the output array to contain level information between 0 and 2Hz divided by FFT_SIZE... so maybe resampling is the way to go... I will google the s*** out of that!

Mr.Floppy

Thanks for the quick response!

I think you understood correctly.
I will look into option 2, but what do you mean by "change the sample rate" in option 1?

Let's say, I have an analogue signal that contains valuable information between 0 and 2 Hz. The sampling frequency of the a/d converter is 100Hz.

To transform roughly one second of this signal, I have to set my FFT_SIZE to 128 and the output array will contain level information between 0 and 128Hz. That's because the input and output array have to be the same size... correct?

If I increase the a/d sampling frequency to 1kHz, my FFT_SIZE would have to be 1024 and the output array will contain level information between 0 and 1024Hz... at least that's what I think.

I COULD increase my sampling window to 10 seconds, but I don't want to ;)

What I want is the output array to contain level information between 0 and 2Hz divided by FFT_SIZE... so maybe resampling is the way to go... I will google the s*** out of that!

goocreations

Ahh, understand. You will need a resampling or interpolation algorithm. An easy way would be to simply use "linear interpolation":http://en.wikipedia.org/wiki/Linear_interpolation and interpolate the frequencies between 0 and 2 Hz. However, this is only an approximation of the frequencies. This is not a problem if you don't need accurate frequencies. However, if you need a good resolution of the frequencies between 0 and 2 Hz, you either need to increase the sample rate or increase the sample window size.

There are other more accurate approximations besides linear interpolation. You can use higher degree "polynomials":http://en.wikipedia.org/wiki/Polynomial_interpolation, "Fourier polynomials ":http://en.wikipedia.org/wiki/Trigonometric_interpolation, or even an "AR model":http://en.wikipedia.org/wiki/Autoregressive_model. However, you have to use a linear least squares fit to estimate the coefficients of these polynomials/models, which on the other hand requires you to implement more code. Luckley for you, I've already implemented it with Qt classes, here "headers":https://github.com/visore/Visore/tree/master/code/essentials/headers/vimatrix and here "source":https://github.com/visore/Visore/tree/master/code/essentials/sources/vimatrix. You can use the ViMatrix and ViVector classes (mathematical matrices and vectors) and the ViSystemSolver to solve the polynomials as described in the Wikipedia articles. Use the function "solve" to estimate the polynomial coefficients.

I've published an "conference paper":ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6776913 about a couple of interpolation algorithms on the time-domain of audio signals, but it will work perfectly for your frequency problem as well. I sadly can only give you the IEEExplore link, and because of copyright issues can't give you the pdf "publicly".

Or as I already said, if the accuracy/resolution is not that important, simply use linear interpolation. Very easy to calculate.

goocreations

Ahh, understand. You will need a resampling or interpolation algorithm. An easy way would be to simply use "linear interpolation":http://en.wikipedia.org/wiki/Linear_interpolation and interpolate the frequencies between 0 and 2 Hz. However, this is only an approximation of the frequencies. This is not a problem if you don't need accurate frequencies. However, if you need a good resolution of the frequencies between 0 and 2 Hz, you either need to increase the sample rate or increase the sample window size.

There are other more accurate approximations besides linear interpolation. You can use higher degree "polynomials":http://en.wikipedia.org/wiki/Polynomial_interpolation, "Fourier polynomials ":http://en.wikipedia.org/wiki/Trigonometric_interpolation, or even an "AR model":http://en.wikipedia.org/wiki/Autoregressive_model. However, you have to use a linear least squares fit to estimate the coefficients of these polynomials/models, which on the other hand requires you to implement more code. Luckley for you, I've already implemented it with Qt classes, here "headers":https://github.com/visore/Visore/tree/master/code/essentials/headers/vimatrix and here "source":https://github.com/visore/Visore/tree/master/code/essentials/sources/vimatrix. You can use the ViMatrix and ViVector classes (mathematical matrices and vectors) and the ViSystemSolver to solve the polynomials as described in the Wikipedia articles. Use the function "solve" to estimate the polynomial coefficients.

I've published an "conference paper":ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6776913 about a couple of interpolation algorithms on the time-domain of audio signals, but it will work perfectly for your frequency problem as well. I sadly can only give you the IEEExplore link, and because of copyright issues can't give you the pdf "publicly".

Or as I already said, if the accuracy/resolution is not that important, simply use linear interpolation. Very easy to calculate.

Mr.Floppy

Thanks for the kind support!

I have done a little research and testing about interpolation and found, that upsampling my signal with cubic splines works pretty well for me!

Now I have another mathematical question.
Is it possible, to convolute two non periodic signals by multiplying their FFTs?

Below I have linked two pictures.
The first one is the convolution of two sine waves, the second one is the convolution of two gaussian bells.

The FFT-size is 1024, and the graphs from top to bottom are read:

Signal1
Signal2
FFT1 (from Signal1)
FFT2 (from Signal2)
FFT1 * FFT2
inverse transformation of FFT1*FFT2

Periodic: http://i.imgur.com/skNcBK1.png
Non Periodic: http://i.imgur.com/EJYcKTn.png

As you can see, the sine waves convolute just fine. The gaussian bells however do not.

So the question remains:
Is there a way to convolute non periodic signals using your qRealFourier class?

Thank you,

schmaunz

Mr.Floppy