Discrete Fourier Transform / General Science and Electronics / Forums

Forums

4hv.org :: Forums :: General Science and Electronics

« Previous topic | Next topic »

Discrete Fourier Transform

1 2 next

Move Thread

LAN_403

AndrewM

Sat Nov 04 2006, 07:29AM

Registered Member #49 Joined: Thu Feb 09 2006, 04:05AM
Location: Bigass Pile of Penguins
Posts: 362

So I'm feeling pretty dumb right now; I've been out of school for mere months and I've already lost my edge:

I'm doing some DFT in visual basic; borrowed code, not mine. What I want to do is use my FT as a sort of curve fit; I'd like to be able to extrapolate a function based on the fourier coefficients that I find for the given data.

My problem is... I don't remember what to do with these coefficients. I keep confusing myself with which indexes represent the time and frequency domain (not to mention all my programmatic indexes for good measure).

Can anyone straighten me out?

WaveRider

Sat Nov 04 2006, 09:30AM

Registered Member #29 Joined: Fri Feb 03 2006, 09:00AM
Location: Hasselt, Belgium
Posts: 500

Hi Andrew,

The coefficients are the weights for the complex exponentials..

f(x) = Sum(c_n * exp(2*pi*I*n*x/N))
(this may be off by a constant scaling factor.. Check a text on the exact scaling.. I'm recounting this off the top of my head..)

N = # of FT bins
I = sqrt(-1)
c_n = coefficient n

Your function can be recovered by computing the sum of the complex exponentials (this is the inverse DFT..which the inverse FFT will perform very rapidly)..
remember that the "negative" frequency coefficients appear for n>N/2..

Hope this helps..
Bill

AndrewM

Sat Nov 04 2006, 05:30PM

Registered Member #49 Joined: Thu Feb 09 2006, 04:05AM
Location: Bigass Pile of Penguins
Posts: 362

Yes, that helps... just a little more though if you please

c_n is the complex coefficient? I'm doing this in vb which balks at imaginary numbers, so my coefficients are stored in two arrays, one for the real half and one for ther imaginary half. I'm not sure how to produce that sum without being able to define /i/

Also, N is the number of FT bins... what does that mean? If I feed my DFT function an array j data points, it will produce a set (real and imaginary) of coefficients also with j members. Is N= j?

Carbon_Rod

Sat Nov 04 2006, 09:09PM

Registered Member #65 Joined: Thu Feb 09 2006, 06:43AM
Location:
Posts: 1155

FFT/DFT can get somewhat impractical if writing time critical code. Often, even though companies like Analog Devices offer products that support both real and unreal variables for some sensor front-end chips. However, most programmers only utilize the estimated real solution thatâ€™s auto generated as the code is simpler to implement.

VB is kind of a bad language as it does not support operator overloading to create new operations or custom variable types like C based languages. However, VB does allow OLE, media support, and simplified network connectivity. Many people tend to write DLLs (including GPL dedicated math libraries) for the math in C++ and import the functions into VB.

Likewise, small utility programs (often in C, Java, VB) will often simply connect with a network or system resource provided by Mathematica (see zip file) or Maple etc.

Cheers,

]1162674549_65_FT17586_mathematica_vb.zip[/file]

Bjørn

Sat Nov 04 2006, 10:34PM

Registered Member #27 Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058

The HvWiki might be of some help

Use the real transform unless you need the complex one.

Mathworld explains how to use complex numbers using normal floatingpoint math (at least some of the operations)

Simon

Sun Nov 05 2006, 05:23AM

Registered Member #32 Joined: Sat Feb 04 2006, 08:58AM
Location: Australia
Posts: 549

Andrew wrote ...

c_n is the complex coefficient? I'm doing this in vb which balks at imaginary numbers, so my coefficients are stored in two arrays, one for the real half and one for ther imaginary half. I'm not sure how to produce that sum without being able to define /i/

If you're too lazy to study complex numbers again, the summation is incredibly simple. Sum all the real parts in the real array to get the real part of whole sum. The imaginary part of the sum is simply the sum of all the imaginary parts.

wrote ...

Also, N is the number of FT bins... what does that mean? If I feed my DFT function an array j data points, it will produce a set (real and imaginary) of coefficients also with j members. Is N= j?

Yes, that's what N traditionally is.

Carbon Rod: I guess you're right but VB is hardly the first thing that comes to mind when designing time critical code, either.

Andrew, could you tell us more about your problem? You're trying to use the FT for extrapolation? I have a funny feeling about that since, theoretically, the DFT works as if the data you're transforming is periodic. In other words, if you use the DFT for extrapolation, you'd just as well take the data you've got and repeat it like a looped tape.

That's my first thought, anyway.

AndrewM

Sun Nov 05 2006, 06:14AM

Registered Member #49 Joined: Thu Feb 09 2006, 04:05AM
Location: Bigass Pile of Penguins
Posts: 362

Simon: The plan is to check IF the data is periodic by computing the DFT for a given (large) set of the data and the extrapolating to view the correlation (if any) with the rest of the data... I see what you mean about looping the data I've got, but what if I only have 1/3 of a period? I'm hoping the DFT will allow me to reconstruct the rest...

now that you put it to me, I can't actually recall if the FT behaves as I'd like it to... Shit. Someone know so I don't have to generate data sets just to check out how it behaves?

I haven't digested the rest of the info in this thread yet, but thanks guys, ill keep you posted.

Dr. Slack

Sun Nov 05 2006, 08:19AM

Registered Member #72 Joined: Thu Feb 09 2006, 08:29AM
Location: UK St. Albans
Posts: 1659

What exactly are you trying to do? DFT may not be the best way to approach it, especially if not sure what you're doing.

Quote <sort of curve fit ... Extrapolate a function, based on FT coefficients that you find for the given data>

Are you extrapolating a function, or a data series? Are the data measurements, or samples from a process, are they noisy, is there a well-defined underlying model? Is the curve fit to the best curves over the interval of the data, to what order, with what base - complex exponentials direct from the DFT, or polynominals, or Tcheby polynominals? People very rarely lose an eye doing interpolation, but extrapolation is all set up to end in tears.

Steve Conner

Sun Nov 05 2006, 11:42AM

Registered Member #30 Joined: Fri Feb 03 2006, 10:52AM
Location: Glasgow, Scotland
Posts: 6706

The DFT/FFT starts by assuming the data is periodic. So I don't think you'll have much luck using it to tell if something's periodic or not. I'm not too sure exactly what the problem is you're trying to solve, but my gut feeling is that autocorrelation might be more useful to you than FFTs. I see Neil is kind of hinting at Kalman filtering too.

Simon

Mon Nov 06 2006, 12:00AM

Registered Member #32 Joined: Sat Feb 04 2006, 08:58AM
Location: Australia
Posts: 549

Andrew wrote ...

Simon: The plan is to check IF the data is periodic by computing the DFT for a given (large) set of the data and the extrapolating to view the correlation (if any) with the rest of the data... I see what you mean about looping the data I've got, but what if I only have 1/3 of a period? I'm hoping the DFT will allow me to reconstruct the rest...

I'm not sure you quite see what I mean about looping.

The DFT won't allow you to reconstruct the rest. Looping isn't some bright idea, it's theoretically inherent in the DFT. If you use the DFT to extrapolate, you'll get looping.

I'm afraid there's no way around it. If you want to test if something is periodic, you have to collect data for long enough to see it repeat, unless you have some specific knowledge for the application.

Once you have a few periods worth of data there are plenty of ways to find the periods and I'd probably base an algorithm on the FFT. Autocorrelation can be done with an FFT (FFT: O(nlogn), autocorrelation: O(n^2)) and if you do an FFT, that should be good enough to see periodicity by itself.

1 2 next

Moderator(s): Chris Russell, Noelle, Alex, Tesladownunder, Dave Marshall, Dave Billington, Bjørn, Steve Conner, Wolfram, Kizmo, Mads Barnkob