Forum: Ruby Time domain to frequency domain with FFT from GSL

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
2ec38e324983babdd5c926c56f9e0c80?d=identicon&s=25 Alex Polite (Guest)
on 2006-06-02 07:13
(Received via mailing list)
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?
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2006-06-02 07:44
(Received via mailing list)
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
2d3ec3a83b4f8784d6853564fa0d2e77?d=identicon&s=25 Dido Sevilla (Guest)
on 2006-06-02 12:18
(Received via mailing list)
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.
2ec38e324983babdd5c926c56f9e0c80?d=identicon&s=25 Alex Polite (Guest)
on 2006-06-02 20:06
(Received via mailing list)
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.
2ec38e324983babdd5c926c56f9e0c80?d=identicon&s=25 Alex Polite (Guest)
on 2006-06-02 20:06
(Received via mailing list)
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
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2006-06-02 21:49
(Received via mailing list)
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...
3bb23e7770680ea44a2d79e6d10daaed?d=identicon&s=25 M. Edward (Ed) Borasky (Guest)
on 2006-06-03 05:25
(Received via mailing list)
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
2ec38e324983babdd5c926c56f9e0c80?d=identicon&s=25 Alex Polite (Guest)
on 2006-06-03 22:28
(Received via mailing list)
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
This topic is locked and can not be replied to.