# Newbie question on FFT

Started by May 19, 2005
```I feel kinda shameful for asking such a newbie question, cuz even
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 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*y
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;
```
```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, y, y,
y, y and y, 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
> 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, y, y,
> y, y and y, 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.

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.
>
> 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  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

 Sun Microsystems "Numerical Computation Guide"

```