Forums

FFTW question about larger output array than input

Started by nobby_trussin July 21, 2006
Hi,

I am using FFTW to obtain freq values from an input signal. The input and
output arrays are the same size. However, I need more precision (i need to
detect frequencies which aren't whole numbers) therefore as i understand it
i need a larger output array than my input one.

i am using FFTW 3's real-to-real fftw_plan_r2r_1d function as follows: 
fftw_plan_r2r_1d (numSamples, in, out, FFTW_R2HC, FFTW_FORWARD); 

The fftw manual states that when using this function the input and output
arrays must be of the same size so i am assuming i should use a different
function. I have read the documentation for the other functions but none
seem to really match my requirements or mention anything about this. Has
anyone come across anything like this before?

Any suggestions are most welcome

Thank you

Dan


nobby_trussin wrote:

> I am using FFTW to obtain freq values from an input signal. The input and > output arrays are the same size. However, I need more precision (i need to > detect frequencies which aren't whole numbers) therefore as i understand it > i need a larger output array than my input one.
> i am using FFTW 3's real-to-real fftw_plan_r2r_1d function as follows: > fftw_plan_r2r_1d (numSamples, in, out, FFTW_R2HC, FFTW_FORWARD);
> The fftw manual states that when using this function the input and output > arrays must be of the same size so i am assuming i should use a different > function. I have read the documentation for the other functions but none > seem to really match my requirements or mention anything about this. Has > anyone come across anything like this before?
Traditionally and FFT of N real values gave N complex values as the transform, with N/2 independent real values and N/2 independent imaginary values. With N degrees of freedom for input, you shouldn't expect more than N real values as output. The real-to-real transform gives you the N result values as a real array, saving half the storage that would otherwise be required. Note that FFT, and the Fourier transform in general, assume a periodic function. Only frequencies that are an integer multiple of the inverse of the transform length (in time or space) are allowed. If you are careful, you can zero pad the input and get interpolated output spectra. No more information is available, but it might look nicer. -- glen
glen herrmannsfeldt wrote:
> Note that FFT ... assume a periodic > function. Only frequencies that are an integer multiple of the inverse > of the transform length (in time or space) are allowed. If you are > careful, you can zero pad the input and get interpolated output spectra.
You contradict yourself. Either the original function was composed only of periodic sinusoids of integer multiple frequencies, and there is nothing to interpolate. Or there is something you wish to interpolate (possible aliased frequency spectra), thus any assumptions that the FFT operated on a window of a signal that was strictly periodic in that window width, or that the signal was composed of only integer multiple frequencies related to the FFT aperature size, are inconsistant with your desired results. IMHO. YMMV. -- http://www.nicholson.com/rhn
Ron N. wrote:
> glen herrmannsfeldt wrote: >> Note that FFT ... assume a periodic >> function. Only frequencies that are an integer multiple of the inverse >> of the transform length (in time or space) are allowed. If you are >> careful, you can zero pad the input and get interpolated output spectra. > > You contradict yourself. Either the original function was composed > only of periodic sinusoids of integer multiple frequencies, and > there is nothing to interpolate. Or there is something you wish > to interpolate (possible aliased frequency spectra), thus any > assumptions that the FFT operated on a window of a signal that was > strictly periodic in that window width, or that the signal was > composed of only integer multiple frequencies related to the > FFT aperature size, are inconsistant with your desired results.
Ron, I suspect that you misunderstood. The mathematics of the Fourier transform allow only frequencies that are integer multiples of the inverse of the transform length to appear in the output, the nature of the original signal notwithstanding. To get more output frequencies, you need a longer transform. If the extra length of the transform comes from actual data, the extra output frequencies are also real data. If the extra length of the transform comes from zero padding, then the extra output data are mere interpolations and could have been derived from the shorter output alone. I think that's what Glen said, and it's the gist what I said a few days ago (only Glen said it better). Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Jerry Avins wrote:
> Ron N. wrote: > > glen herrmannsfeldt wrote: > >> Note that FFT ... assume a periodic > >> function. Only frequencies that are an integer multiple of the inverse > >> of the transform length (in time or space) are allowed. If you are > >> careful, you can zero pad the input and get interpolated output spectra. > > > > You contradict yourself. Either the original function was composed > > only of periodic sinusoids of integer multiple frequencies, and > > there is nothing to interpolate. Or there is something you wish > > to interpolate (possible aliased frequency spectra), thus any > > assumptions that the FFT operated on a window of a signal that was > > strictly periodic in that window width, or that the signal was > > composed of only integer multiple frequencies related to the > > FFT aperature size, are inconsistant with your desired results. > > Ron, > > I suspect that you misunderstood. The mathematics of the Fourier > transform allow only frequencies that are integer multiples of the > inverse of the transform length to appear in the output, the nature of > the original signal notwithstanding.
But frequencies that are not integer multiples do appear in the output, in aliased form of course (sampled offset sinc's), due to the windowing required to do an FFT perhaps.
> To get more output frequencies, you > need a longer transform. If the extra length of the transform comes from > actual data, the extra output frequencies are also real data. If the > extra length of the transform comes from zero padding, then the extra > output data are mere interpolations and could have been derived from the > shorter output alone.
The extra output data would have no meaning if you really regard only integer multiples frequencies as existing in the original tranform, and no data has been added. Only because of the assumption that non-integer frequencies are hidden in aliasing does interpolating (parabolic, sinc, or zero-padding) make any sense. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
Ron N. wrote:
> Jerry Avins wrote: >> Ron N. wrote: >>> glen herrmannsfeldt wrote: >>>> Note that FFT ... assume a periodic >>>> function. Only frequencies that are an integer multiple of the inverse >>>> of the transform length (in time or space) are allowed. If you are >>>> careful, you can zero pad the input and get interpolated output spectra. >>> You contradict yourself. Either the original function was composed >>> only of periodic sinusoids of integer multiple frequencies, and >>> there is nothing to interpolate. Or there is something you wish >>> to interpolate (possible aliased frequency spectra), thus any >>> assumptions that the FFT operated on a window of a signal that was >>> strictly periodic in that window width, or that the signal was >>> composed of only integer multiple frequencies related to the >>> FFT aperature size, are inconsistant with your desired results. >> Ron, >> >> I suspect that you misunderstood. The mathematics of the Fourier >> transform allow only frequencies that are integer multiples of the >> inverse of the transform length to appear in the output, the nature of >> the original signal notwithstanding. > > But frequencies that are not integer multiples do appear in the > output, in aliased form of course (sampled offset sinc's), due to > the windowing required to do an FFT perhaps.
It is better to say that they affect the output, but they don't appear /per se/ in the output.
>> To get more output frequencies, you >> need a longer transform. If the extra length of the transform comes from >> actual data, the extra output frequencies are also real data. If the >> extra length of the transform comes from zero padding, then the extra >> output data are mere interpolations and could have been derived from the >> shorter output alone. > > The extra output data would have no meaning if you really > regard only integer multiples frequencies as existing in the > original tranform, and no data has been added. Only because > of the assumption that non-integer frequencies are hidden in > aliasing does interpolating (parabolic, sinc, or zero-padding) > make any sense.
Where else are they? Every meaningful datum in the original represents a known. The output can be calculated from them with trig and algebra. (But not easily. That is what make anything but samples regularly spaced in time nearly intractible.) What remains true of any method is that only N unknowns can be determined from N knowns -- it takes N data to solve N equations and get N results. You can interpolate if you like with a draftsman's batten (spline) and produce a continuous curve, but no new information is added. Put differently, if P points suffice to produce kP points by interpolation, all the information is in the original P. Were you to send me only those, I could interpolate between them myself. -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Ron N. wrote:
> Jerry Avins wrote: >> Ron N. wrote: >>> glen herrmannsfeldt wrote: >>>> Note that FFT ... assume a periodic >>>> function. Only frequencies that are an integer multiple of the inverse >>>> of the transform length (in time or space) are allowed. If you are >>>> careful, you can zero pad the input and get interpolated output spectra. >>> You contradict yourself. Either the original function was composed >>> only of periodic sinusoids of integer multiple frequencies, and >>> there is nothing to interpolate. Or there is something you wish >>> to interpolate (possible aliased frequency spectra), thus any >>> assumptions that the FFT operated on a window of a signal that was >>> strictly periodic in that window width, or that the signal was >>> composed of only integer multiple frequencies related to the >>> FFT aperature size, are inconsistant with your desired results. >> Ron, >> >> I suspect that you misunderstood. The mathematics of the Fourier >> transform allow only frequencies that are integer multiples of the >> inverse of the transform length to appear in the output, the nature of >> the original signal notwithstanding. > > But frequencies that are not integer multiples do appear in the > output, in aliased form of course (sampled offset sinc's), due to > the windowing required to do an FFT perhaps.
It is better to say that they affect the output, but they don't appear /per se/ in the output.
>> To get more output frequencies, you >> need a longer transform. If the extra length of the transform comes from >> actual data, the extra output frequencies are also real data. If the >> extra length of the transform comes from zero padding, then the extra >> output data are mere interpolations and could have been derived from the >> shorter output alone. > > The extra output data would have no meaning if you really > regard only integer multiples frequencies as existing in the > original tranform, and no data has been added. Only because > of the assumption that non-integer frequencies are hidden in > aliasing does interpolating (parabolic, sinc, or zero-padding) > make any sense. >
Where else are they? Every meaningful datum in the original represents a known. The output can be calculated from them with trig and algebra. (But not easily. That is what make anything but regularly spaced samples nearly intractible.) What remains true of any method is that only N unknowns can be determined from N knowns -- it takes N data to solve N equations and get N results. You can interpolate if you like with a draftsman's batten (spline) and produce a continuous curve, but no new information is added. Put differently, if P points suffice to produce kP points by interpolation, all the information is in the original P. Were you to send me only those, I could interpolate between them myself. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Jerry Avins wrote:
> Ron N. wrote: > > Jerry Avins wrote: > >> Ron N. wrote: > >>> glen herrmannsfeldt wrote: > >>>> Note that FFT ... assume a periodic > >>>> function. Only frequencies that are an integer multiple of the inverse > >>>> of the transform length (in time or space) are allowed. If you are > >>>> careful, you can zero pad the input and get interpolated output spectra. > >>> You contradict yourself. Either the original function was composed > >>> only of periodic sinusoids of integer multiple frequencies, and > >>> there is nothing to interpolate. Or there is something you wish > >>> to interpolate (possible aliased frequency spectra), thus any > >>> assumptions that the FFT operated on a window of a signal that was > >>> strictly periodic in that window width, or that the signal was > >>> composed of only integer multiple frequencies related to the > >>> FFT aperature size, are inconsistant with your desired results. > >> Ron, > >> > >> I suspect that you misunderstood. The mathematics of the Fourier > >> transform allow only frequencies that are integer multiples of the > >> inverse of the transform length to appear in the output, the nature of > >> the original signal notwithstanding. > > > > But frequencies that are not integer multiples do appear in the > > output, in aliased form of course (sampled offset sinc's), due to > > the windowing required to do an FFT perhaps. > > It is better to say that they affect the output, but they don't appear > /per se/ in the output. > > >> To get more output frequencies, you > >> need a longer transform. If the extra length of the transform comes from > >> actual data, the extra output frequencies are also real data. If the > >> extra length of the transform comes from zero padding, then the extra > >> output data are mere interpolations and could have been derived from the > >> shorter output alone. > > > > The extra output data would have no meaning if you really > > regard only integer multiples frequencies as existing in the > > original tranform, and no data has been added. Only because > > of the assumption that non-integer frequencies are hidden in > > aliasing does interpolating (parabolic, sinc, or zero-padding) > > make any sense. > > Where else are they? Every meaningful datum in the original represents a > known. The output can be calculated from them with trig and algebra. > (But not easily. That is what make anything but samples regularly spaced > in time nearly intractible.) What remains true of any method is that > only N unknowns can be determined from N knowns -- it takes N data to > solve N equations and get N results.
But the problem is that the questions asked of the results of FFT operators are often underconstrained. The questions here are often not about the spectrum of just the window given to the FFT, with perhaps discontinuities at the end-points, but the spectra of some phenomena which has an existance outside the window given to the FFT. In those cases, one might look for the most probable result of N+M unknowns (spectra produced by the data plus some unknown but assumed more locally "continuous" or otherwise behaved data just beyond the window) given only N data points inside the FFT aperature. That's usually the case when you assume that some interpolated sinusoid is more interesting than the odds that something generated that same result using a whole distribution of only integral frequency oscillators that just happened to look like an aliasing. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
Ron N. wrote:

> Jerry Avins wrote:
(snip, someone wrote)
>>>The extra output data would have no meaning if you really >>>regard only integer multiples frequencies as existing in the >>>original tranform, and no data has been added. Only because >>>of the assumption that non-integer frequencies are hidden in >>>aliasing does interpolating (parabolic, sinc, or zero-padding) >>>make any sense.
>>Where else are they? Every meaningful datum in the original represents a >>known. The output can be calculated from them with trig and algebra. >>(But not easily. That is what make anything but samples regularly spaced >>in time nearly intractible.) What remains true of any method is that >>only N unknowns can be determined from N knowns -- it takes N data to >>solve N equations and get N results.
> But the problem is that the questions asked of the results > of FFT operators are often underconstrained. The questions > here are often not about the spectrum of just the window given > to the FFT, with perhaps discontinuities at the end-points, but > the spectra of some phenomena which has an existance > outside the window given to the FFT.
Say I buy a CD of a concert. I would not expect to be able to use any kind of transform to extract the concert before or after the one on the recording. I could write the equations that could be solved for the signal for that concert, but I wouldn't expect a good solution.
> In those cases, one might > look for the most probable result of N+M unknowns (spectra > produced by the data plus some unknown but assumed more > locally "continuous" or otherwise behaved data just beyond the > window) given only N data points inside the FFT aperature.
It might be that you could get a few more sample points on each end, but that doesn't really help much. The DCT boundary conditions make a little more sense sometimes. DCT assumes the derivative is zero at the ends. -- glen
glen herrmannsfeldt wrote:
> Say I buy a CD of a concert. I would not expect to be able to use > any kind of transform to extract the concert before or after the one > on the recording. I could write the equations that could be solved > for the signal for that concert, but I wouldn't expect a good solution.
I'm just guessing, but I assume the OP:
> I am using FFTW to obtain freq values from an audio signal.
is interested in "freq values" from FFTW aperatures shorter than an entire CD. You might better say that the FFTW might be the wrong tool to produce anything like "freq values", buts it's often good enough if one just assumes that the more mathematically elegant results are wrong, and uses a nearby hammer on them or the operator (some form of interpolation or zero-padding) to produce a non-bin frequency as a more likely candidate for the desired "freq value" result. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M