Re: DFT Function

David C. Ullrich wrote:
On Thu, 13 Nov 2008 12:06:13 -0800 (PST), Pat <pabrown1975@xxxxxxxxx>
wrote:

On Nov 13, 4:06 am, David C. Ullrich <dullr...@xxxxxxxxxxx> wrote:

It's impossible to say what the problem is. The input to the code
is an array of floats. You say you get the wrong answer with
input cos(5.5 * 6.2831853 * t). That's not an array of floats.
What _are_ you using for input? (Also, what output do you get
and how do you know it's wrong?)
Here is the code that fills the input array:

#define NUM_SAMPLES 256

float x[NUM_SAMPLES];
float fx[NUM_SAMPLES];

for (int i = 0; i < 256; i++)
{
float t = (float)i / NUM_SAMPLES;
x[i] = cosf(5.5f * 2.0f * (float)M_PI * t);
}

full_dft(x, fx, NUM_SAMPLES);

That's more or less what I guessed. The output you get
below is right (except it has remarkably large roundoff error;
I get much more precise results with the crudest possible
Python code!)

Evidently you were expecting a peak around 5.5.
That's simply not how it works - no, the fact that
you're ignoring the sin part is not the explanation,
if you include that you're not going to see a peak
around 5.5 either. Well, you do get something
sort of like that, but it's not nearly as sharp as
what you're going to get with a frequency of 5.

The point is that cos(5.5 t) does not have period
2pi; you're not really taking any sort of FT of
that function, you're only sampling a piece of
a period. (Well, you're sampling 5 and a half
periods, which explains why there's a rough
sort of peak around 5.5.)

In fact cos(5.5(2 pi - t)) = - cos(5.5 2 pi t),
so the actual cosine coefficients of the continuous
function (ass opposed to the discrete sampling
of it) are exactly 0.

When run, the output array (fx) is filled with the following:

0: 0.999978
1: 0.999983
2: 0.999979
3: 0.999979
4: 0.999971
5: 0.999916
6: 1.000051
7: 1.000010
8: 1.000008
9: 1.000000

... and so on; all values of the output array are very close to 1.0.
In contrast, when the input is changed to a frequency of 5.0, the
output array looks like so:

0: 0.000013
1: 0.000013
2: 0.000012
3: 0.000014
4: 0.000022
5: 127.999992
6: 0.000013
7: 0.000002
8: 0.000003
9: 0.000006

... and the rest of the values are very close to 0.0. Just what I
would expect, a large peak at a frequency of 5.

I'm curious what the output would look like (graphically)
with 2048 or 4096 samples instead of 256 samples.
With 2^20 samples, would the graph be of the same outline
shape (by connecting close-by points of the DFT) to
the continuous FT ?

There may be some underlying Poisson kernel or something else
that I don't know about or have forgotten.

Thanks,

David Bernier
.

Relevant Pages

  • Re: DFT Function
    ... Here is the code that fills the input array: ... Evidently you were expecting a peak around 5.5. ... you're sampling 5 and a half ... "Understanding Godel isn't about following his formal proof. ...
    (sci.math)
  • Re: I believe Ive found an Access bug...can anyone confirm?
    ... "david" wrote: ... The from-to array declaration syntax is such an improvement ... IRRCashFlowA = 957.55 ... Dim IngSizeA As Long ...
    (microsoft.public.access.modulesdaovba)
  • Re: Charles container library usage examples
    ... > David, in the past I also played with Charles and instantiated a ... > how I did the instantiations: ... > package Lists_Of_Regexes is ... You can see I ditched the list for a simple array! ...
    (comp.lang.ada)
  • Re: The next number that is not in an array
    ... begun to really dig in to Ruby. ... My first take on this 'quiz' was to initialize a new array with members ... Rails training from David A. Black and Ruby Power and Light: ...
    (comp.lang.ruby)
  • Re: Behaviour of Enumerables reject vs. select mixed into Hash
    ... David said: ... but selecting means creating a new collection" ... new collection as an array, actually the ongoing discussion about this ...
    (comp.lang.ruby)