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?

on 2006-06-02 07:13

on 2006-06-02 07:44

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 2006-06-02 12:18

On 6/2/06, Alex Polite <notmyprivateemail@gmail.com> 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 2006-06-02 20:06

```
On 6/2/06, Dido Sevilla <dido.sevilla@gmail.com> wrote:
> library somewhere.
Thanks. Seems like it's available at my local library. I'll pick it up
later today.
```

on 2006-06-02 20:06

On 6/2/06, Adam Shelly <adam.shelly@gmail.com> 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

on 2006-06-02 21:49

On 6/2/06, Alex Polite <notmyprivateemail@gmail.com> 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 2006-06-03 05:25

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. :) 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 Polite 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 http://linuxcapacityplanning.com

on 2006-06-03 22:28

On 6/2/06, Adam Shelly <adam.shelly@gmail.com> 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