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

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?

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

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

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.

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.

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

A Fast Fourier transform comes in four flavors:

- Forward Real to Complex
- Forward Complex to Complex
- Inverse Complex to Complex
- 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. 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

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(r*r + i*i)

}

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…

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