Re: DFT Function

David C. Ullrich wrote:
On Fri, 14 Nov 2008 08:22:04 -0500, David Bernier
<david250@xxxxxxxxxxxx> wrote:

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 ?

I'm not sure exactly what you're asking (because for example
if we're talking about periodic functions then the FT is not
"continuous", the FT is the sequence of Fourier coefficients).


Of course, Z/(nZ) is not ordered, and I hadn't realized
that when I asked the question. So, now I don't see a
natural ordering for the DFT coefficients with
abelian group Z/(nZ).

So "connecting close-by points of the DFT" could be
a dubious idea at best.

David Bernier


It can't be hard to see what the DFT coefficients from N sample
points have to do with the actual Fourier coefficients... Say
f is continuous with period 2pi. Define the Fourier
coefficients

[i] c[n] = 1/2pi int_0^2pi f(t) exp(-int) dt.

And define the DFT coefficients with N sample points

[ii] c_N[k] = 1/N sum_{j=1}^N f(2pi j/N) exp(-2pi i jk/N).

(Ok, the domain of the DFT is "Z mod N", not Z. So the real
formula would be

[iii] c_N[k mod N] = 1/N sum_{j=1}^N f(2pi j/N) exp(-2pi i jk/N),

taking "k mod N" to mean the coset k + NZ in Z/N;
"k mod N" may make more sense to some readers). But
instead of taking the domain of the DFT to be Z/N
let's say that the DFT coefficients are an ordinary sequence
of period N; then they're given by [ii].)

Huh - [ii] is just a Riemann sum. If f is continuous with period
2pi then c_N[k] -> c_k as N tends to infinity.

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

Thanks,

David Bernier

David C. Ullrich
.

Relevant Pages

  • Re: real exact pruned DFT?
    ... coefficients are scattered b) I need my solution to be ... rounding) to the DFT. ... First, by "exact algorithm", the original poster certainly means ...
    (comp.dsp)
  • Re: Autocorrelation matrix of a long sequence
    ... Convolution by DFT is circular, ... Time-reversing in time domain is not sufficient to ... (save some scaling coefficients), can alternatively be ...
    (comp.dsp)
  • Re: Autocorrelation matrix of a long sequence
    ... to zero-pad before computing the DFT. ... zero-pad further, to the next power of 2. ... handle wrap-around effects from circular convolution, ... (save some scaling coefficients), can alternatively be ...
    (comp.dsp)
  • Re: The inherent periodicity of the Discrete Fourier Transform
    ... then calculate an N point DFT, the coefficients of the N point DFT ... signal match the inherent periodicity of the N point DFT ... Consider Nyquist sampling of signals with finite and ...
    (comp.dsp)
  • Re: Series of tetrated terms
    ... Like David said, your question is meaningless. ... coefficients such that the series converges _to_ exp. ... 2-cycle and the odd-height of the power-tower terms will be close to the ...
    (sci.math)