how does DFT really work?

[bradley1234]

Hi all

Ive read thru the tutorials about the Fourier transform, they are very well written and helpful.

Im trying to learn and understand how some math equation (DFT or FFT) can take a complex signal and figure out the component frequencies and their respective amplitude?

A spectrum analyzer output is a 2D array of frequency and amplitude, so its f, A and #samples or arraysize. the math equations with the unknown squiggly lines dont really explain it all to me. it might as well be Greek.

In the analog world, a complex signal can be mixed with a reference signal and the result measured? is that whats going on with the DFT or FFT in math? does one have to use the equation and step in a sequential reference frequency?

so Ive got a sampled, digitized signal stored in a memory array that represents a complex signal, lets say its in the audio range and the signals Im looking for are in the 1k to 10kHz region.

the sampling rate is 25kHz, and its 1 second worth of data

the math that makes it possible to convert that array of samples into a spectrum analyzer plot is a total mystery to me, would someone please explain it??

THANKS!!

[bradley1234]

Ive been studying this topic, one thing I didnt realize was the concept of complex numbers z = a+bi

somewhere I read that 'a' can be thought of as x along the real x axis, and 'i' times b, the imaginary part? can be thought of as y along the y axis?

so my original question would have been: explain the Fourier transform without referencing complex numbers or specifics of convolution and without using the letter 'e' ?

I had learned of complex numbers in algebra classes, and learned how to solve the questions and pass the tests, but now a couple years later the reality of learning "a complex number does what??" is setting in. thanks to another post in this forum


So far I think the way a DFT works is that for some digitized sample of N points, some math eq is used, and you pick some kind of seed number, look at the results of processing all the points and based on the results change the seed number

so you really do have to kind of send in a known number and factor in all of the points... a flowchart? is there a flowchart somewhere that describes the steps of a DFT? so to write a computer program a person has a flowchart of what to do with the numbers??

does anyone know where to find a block diagram flowchart of how to compute the DFT or FFT? and something in Visual Basic.net or CSharp? or even old original Basic?

An old Basic program with lots of comments explaining how to do the FFT or DFT?

[charan langton]

You can imagine complex numbers in this context as not straight x and y axes by at as sine and cosine waves. Read the first FFT tutorial to see how I go from real to complex.
Charan

[harcoolbabe]

hi, all.. i'm confuse about order and point in fft..
now, if i want to make a 64 point fft does it mean that it has 64 order?

thanks b4...

[bookmaniac]

D DFT workz by electrostatic induction...

[jsolar]

bradley1234, You can look at how the DFT works in a couple of ways. Here are two of them.
he first way is to view the DFT process as a correlation; that is multiplying your real string of data by a sine wave point by point, then adding up those numbers. What happens is that if the input data was made up of just a sine wave of the same frequency as your DFT picket frequency the input will be a positive voltage whenever your DFT frequency is positive. Then whenever your input frequency is a negative voltage the DFT frequency will be negative and the product of two negatives is a positive number. The addumulator will be adding all positive nmbers and thus the result for the magnitude of that picket will grow into a large number. Now for any frequency that is not close to the DFT frequency the product of the two sign waves will not always be positive, thus the times that the product is negative will make the accumulators sum decrease sometimes. On average it may stay fairly close to zero. This is how the energy from other frequencies is screened out from the results intended for the picket frequency of interest.
Now if the frequency input matches the DFT picket frequency you are working on is out of phase then sometimes the accumulator for the sine wave will sometimes have negative numbers added in so the sum will not grow as large, but will not be too close to zero. That is why in addition to a sine wave a cosine wave is also used. It will work out that however small the sine sum goes the cosine sum will be larger such that if you take the pythagorean distance of mag = sqrt( I*I + Q*Q) will always be proportional to the magnitude of the input sie wave if the input signal. I have used the name I to mean In-phase and Q to mean quadrature. This is common practice and makes sense because a sine wave is in quadrature (or 90 degree shift) from a cosine wave. If you know complex number theory then you know that the absolute value of a complex number uses the same pythagorean formula shown above.

A second way to view the operation of a DFT is as a mixer followed by a low pass filter and a detector. Since you mentioned an analog equivalent I thought might relate to your background a little better.

Each DFT frequency will mix the input signal down to DC (and also up to twice the input frequency). All other frequencies will be mixed to something away from DC. The accumlator of the DFT will add up the mixed to DC and detected signal and the output will grow. For all input frequencies far enough away from the DFT frequency the low pass filter operation of the accumulator will filter out (reject) and the output will not stray far from zero.

I hope this helps