Time domain to frequency domain with FFT from GSL

Ruby
1

Howdy.

I need to do some Fast Fourier Transforms for an audio project I’m
working on. Problem is I don’t know shit about math :wink:

Reading a dozen online tutorials on FFT tells me that the FFT of a
vector of real time domain data of size N should yield a vector of
frequency domain data of size N/2.

So I try out the different FFT functions in GSL, but the ones that
accept a vector of real data of size N also return a vector of size N.

What’s the deal here?

2

The items after N/2 are the “negative frequencies” Some mathematician
can
tell you what that means, but in practical terms, they are a mirror
image of
the first half (at least for audio signals).
If all you are trying to do is display (or extract information about)
the
spectrum, you can throw the 2nd half of the vector away.

-Adam

3

On 6/2/06, Alex P. [email protected] wrote:

Howdy.

I need to do some Fast Fourier Transforms for an audio project I’m
working on. Problem is I don’t know shit about math :wink:

This is a big problem. If you at the very least have an elementary
calculus background, I would recommend you try to read Richard W.
Hamming’s book “Digital Filters” (ISBN: 0132128950). It covers all of
the basics you need to know about digital signal processing and it’s
written in a more friendly style than most math books I’ve seen. It
explains what the discrete Fourier transform actually computes (I’m
not sure if this is entirely clear to you…), how to use windowing
functions, what is meant by frequency aliasing, what negative
frequencies are, and why it’s not such a good idea to zero pad the
data you feed into your FFT routine, among other things. Find it in a
library somewhere.

4

On 6/2/06, Dido S. [email protected] wrote:

library somewhere.
Thanks. Seems like it’s available at my local library. I’ll pick it up
later today.

5

On 6/2/06, Adam S. [email protected] wrote:

The items after N/2 are the “negative frequencies” Some mathematician can
tell you what that means, but in practical terms, they are a mirror image of
the first half (at least for audio signals).
If all you are trying to do is display (or extract information about) the
spectrum, you can throw the 2nd half of the vector away.

OK, so say I’m using the ruby wrapper round FFTW3.

na is my time domain data. Then I can get my freq domain data by this:

FFTW3.fft(na, -1).real[0…na.length/2-1]

Right?

alex

6

A Fast Fourier transform comes in four flavors:

  1. Forward Real to Complex
  2. Forward Complex to Complex
  3. Inverse Complex to Complex
  4. Inverse Complex to Real

You started with a real array of length N in the time domain and did
flavor 1. That gave you a complex array of length N/2, which occupies
the same number of memory locations as the real array of length N.
There’s also a “trick” … one of the “complex” numbers, usually the
first one in the output array, isn’t really a complex number but two
real numbers – the real part is one of them and the imaginary part is
the other one.

There are lots and lots of web sites that explain the Fast Fourier
Transform. I worked for Floating Point Systems in a past life, and still
see this stuff in my dreams sometimes. :slight_smile: But, given an “audio project”,
an FFT is a pretty low-level tool – a means to an end. It would help is
we knew what that end was.

Alex P. wrote:

accept a vector of real data of size N also return a vector of size N.

What’s the deal here?

–
M. Edward (Ed) Borasky

7

On 6/2/06, Alex P. [email protected] wrote:

OK, so say I’m using the ruby wrapper round FFTW3.

na is my time domain data. Then I can get my freq domain data by this:

FFTW3.fft(na, -1).real[0…na.length/2-1]

Right?

What do you want to do with the result? FFTW3.fft(na, -1) gives you
an array of complex numbers. You probably can’t just throw away the
imaginary part.

For example, I just used FFTW in a C application to plot the spectrum
of a signal.

I plotted something equivalent to
n = na.length
fd = FFTW3.fft(na, -1)
plotdata = fd.real.zip(fd.imag).map {|re, im|
r = re/n; i = im/n;
Math::sqrt(rr + ii)
}

I’m lucky enough to have a math genius in the office to consult for
these things. The book Dido recommended may be your next best bet…

8

On 6/2/06, Adam S. [email protected] wrote:

What do you want to do with the result? FFTW3.fft(na, -1) gives you
an array of complex numbers. You probably can’t just throw away the
imaginary part.

One of the tutorials I read said you could do just that. But, hey,
what do I know.

alex