Newbie question on FFT

I feel kinda shameful for asking such a newbie question, cuz even
though I read the FFTW manual and other documentation about DFT's,
there is one thing I still don't understand

When doing a r2r transform (with FFTW), how do i interpret the result
array?

I have an array of doubles in input that represent a sound, and in the
output an array of the same type and size, the problem is that I didn't
manage to figure out what the values in the output array match too.

My goal is to make a spectrogram, but i'm quite confused because I
don't know how to get to it using the output array.

"Michel Rouzic" <Michel0528@yahoo.fr> writes:

> When doing a r2r transform (with FFTW), how do i interpret the result
> array?

What's an "r2r transform"?
-- 
Randy Yates
Sony Ericsson Mobile Communications
Research Triangle Park, NC, USA
randy.yates@sonyericsson.com, 919-472-1124

Did you mean Radix 2, are you confused by bit reversal algo ??? Your
FFT is decimation in Time or Frequency ??

If you are using the FFTW_R2HC transform type (a real-input to
halfcomplex-format-output DFT), then if you have N real inputs then the
outputs y[k] are N real outputs where y[0] is the DC amplitude, y[N/2]
is the Nyquist amplitude (for even N), and (y[k], y[N-k]) are the
(real,imag) parts of the k-th frequency output for other k.  This is
described in detail by the manual.

If you want the spectrogram, then you probably want the amplitude
squared ... i.e.

k=0:  y[0]*y[0]
0<k<N/2:  y[k] * y[k] + y[N-k] * y[N-k]
k=N/2: y[N/2]*y[N/2]

where the k-th output corresponds to the frequency k/T where T is your
total sampling time.

Cordially,
Steven G. Johnson

PS. As the FFTW manual says in its introduction, our manual tells you
how to use FFTW but is not an introduction to Fourier transforms or
signal processing.   You should really read a good book on the subject,
e.g. The Fast Fourier Transform and Its Applications by E. O. Brigham
(Prentice-Hall, Englewood Cliffs, NJ, 1988).

Randy Yates wrote:
> What's an "r2r transform"?

(This is just the FFTW interface for all transforms that take N real 
inputs to N real outputs ("r2r" = "real-to-real").  This includes DCTs 
and DSTs, the DHT, and also the DFT of real inputs with output in 
"halfcomplex" format (real parts followed by imaginary parts reverse 
order).  Most likely the original poster is using the last (DFT) case; 
see also my other message.)

oh ok thank you for help.

by the way, when transforming (with FTTW_R2HC or FFTW_DHT) with an
array of any size filled with 0 values, i always have in the output
array (no matter the size of the array) peaks at y[4], y[7], y[13],
y[17], y[23] and y[129], as I expected every value to be flat since i'm
transforming an array filled with 0 values.

Did I do something wrong to always obtain that or is there a meaning to
it?

Thank you for help

"Michel Rouzic" <Michel0528@yahoo.fr> wrote in message 
news:1116535002.291736.290630@o13g2000cwo.googlegroups.com...
> oh ok thank you for help.
>
> by the way, when transforming (with FTTW_R2HC or FFTW_DHT) with an
> array of any size filled with 0 values, i always have in the output
> array (no matter the size of the array) peaks at y[4], y[7], y[13],
> y[17], y[23] and y[129], as I expected every value to be flat since i'm
> transforming an array filled with 0 values.
>
> Did I do something wrong to always obtain that or is there a meaning to
> it?
>

If the inputs are all zero, I would check the scaling (i.e. the magnitude) 
of the outputs and would expect them to be in the noise.  Zero in should 
yield zero out.

Fred 

If the inputs are zero, the outputs should be *exactly* zero.  There is
no "noise", because the results of multiplication and addition by zero
are always exactly representable in floating-point.  So, the poster has
a bug somewhere in his code.

stevenj@alum.mit.edu wrote:
> If the inputs are zero, the outputs should be *exactly* zero.

Are you sure about this? No numerical noise is introduced anywhere?
I sincerely hope you are right, but I don't remember having seen
such claims before.

> There is
> no "noise", because the results of multiplication and addition by
zero
> are always exactly representable in floating-point.  So, the poster
has
> a bug somewhere in his code.

Assuming you are wrong in your first statement, and numerical
noise *is* introduced when multiplying with zeros, there will
come some non-zero garbage with vanishing amplitudes out in the
other end. If so, the OP nees to look at the exponential terms
in the output. If the magnitudes of numbers are on the order of
1e-12 or less, the FFT works but introduces numerical garbage.

Rune

Rune Allnor wrote:
> stevenj@alum.mit.edu wrote:
> > If the inputs are zero, the outputs should be *exactly* zero.
>
> Are you sure about this? No numerical noise is introduced anywhere?
> I sincerely hope you are right, but I don't remember having seen
> such claims before.

I don't know about other standards, but this is stated [1] about IEEE
754 arithmetic:

"
Each of the [...] operations must deliver to its destination the exact
result, unless there is no such result or that result does not fit in
the destination's format. In the latter case, the operation must
minimally modify the exact result according to the rules of prescribed
rounding modes [...] and deliver the result so modified to the
operation's destination.
"

As addition and multiplication of an IEEE 754 value with zero is always
another IEEE 754 value, the result is exact.

Perhaps you are mistaking this with the fact that a standard real FFT
transforms a real symmetric vector into an almost real vector -- the
non-zero imaginary part is due to finite-precision arithmetic errors.

Regards,
Andor

[1] Sun Microsystems "Numerical Computation Guide"