FFTW question about larger output array than input

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