Domain of a discrete fourier transform

[Jezza]

Homework Statement

The (computing) task at hand is to take a function f(x) defined at 2N discrete points, and use the Discrete Fourier Transform (DFT) to produce F(u), a plot of the amplitudes of the frequencies required to produce f(x). I have an array for each function holding the value of each function at each value of x.

I have 2 questions:
1) Does it make sense to talk of a continuous frequency space when we start with a discrete real space? i.e. Can I let u take any value or should it only take values corresponding to functions with integral periods?
2) What should the domain of F(u) be?

Homework Equations

The 1D Fourier transform of a function f(x) can be approximated as a sum over discrete values:
<br /> F(u) = \frac{1}{2N} \sum_{x=-N}^{N-1} f(x) e ^{\frac{\pi i x u}{N}}<br />

The Attempt at a Solution

[/B]
Allow me to explain my intuition on what's going on, and please put me right on it if I'm wrong!

If we choose to plot f(x) on a continuous x axis, then due to the discrete, array, representation of it, we will see vertical discontinuities, or steps, between each successive value of the function. Each step will be an arbitrary constant width \delta which would be decided at the plotting stage.

As such, when we use the Fourier transform, we find the amplitudes of the square waves of each frequency which make up the original function f(x). Because f(x) is only defined over a space of 2N points, we can say that the maximum period of any function is 2N\delta in the continuous space, or 2N in the discrete space. To say that a wave has a frequency \nu is to say it has a period \frac{2N\delta}{\nu} in the continuous space, or \frac{2N}{\nu} in the discrete space.


Now my attempts at answers:

1) Upon plotting F(u) with a continuous u I see no discontinuities, so I suppose then it does make sense, but then I'm really not sure. My hesitation is because an arbitrary real-valued u would not generally be exactly representable in the discrete space, and would have to represented by the nearest one that is.2) I have a few thoughts on this:

a) The maximum frequency representable in the discrete space is N. My logic is that the maximum frequency square wave on a discrete space is of the following form:
{..., a, 0, a, 0, a, 0, a, 0, ...}
where a is the wave's amplitude. A higher frequency would have to have adjacent 'a's and '0's, and would therefore be indistinguishable from a lower frequency in the discrete space. The conclusion is that the domain should be [0:N]

b) I have tried a few plots of F(u). I've tried with f(x) = 1 for -6&lt;x&lt;5 and 0 otherwise. I see that the plot is periodic with period 2N and with vertical axes of symmetry at integer multiples of N. This seems to support my conclusion in (a). I attach one of my plots of |F(u)| for this f(x). This was plotted with N=250 with (effectively) continuous u.

c) If the inclusion of non-integral frequencies that are not representable on the discrete space is allowed, then this renders my argument in (a) irrelevant, because we're not worrying about whether the frequency can be represented on the discrete space.

Thank you to anyone who takes the time to read this. I hope I've made my thoughts clear and explained what I mean well enough!

 

[olivermsun]

If we choose to plot f(x) on a continuous x axis, then due to the discrete, array, representation of it, we will see vertical discontinuities, or steps, between each successive value of the function. Each step will be an arbitrary constant width \delta which would be decided at the plotting stage.

As such, when we use the Fourier transform, we find the amplitudes of the square waves of each frequency which make up the original function f(x). Because f(x) is only defined over a space of 2N points, we can say that the maximum period of any function is 2N\delta in the continuous space, or 2N in the discrete space. To say that a wave has a frequency \nu is to say it has a period \frac{2N\delta}{\nu} in the continuous space, or \frac{2N}{\nu} in the discrete space.

Your intuition with the minimum "gaps" between function values is sort of along the right track...

However, keep in mind that the "step" width \delta is, as you said, an arbitrary feature of your plotting convention. The function is only defined at exact points; there are no steps or sums of square waves. In fact, you can see from the (discrete) Fourier transform formula that $F(u)$ finds the weights of sinusoidal functions whose sum can be used to reconstruct $f(x)$ on the $2N$ points on which it is defined.

 

[Jezza]

Your intuition with the minimum "gaps" between function values is sort of along the right track...

However, keep in mind that the "step" width \delta is, as you said, an arbitrary feature of your plotting convention. The function is only defined at exact points; there are no steps or sums of square waves. In fact, you can see from the (discrete) Fourier transform formula that $F(u)$ finds the weights of sinusoidal functions whose sum can be used to reconstruct $f(x)$ on the $2N$ points on which it is defined.

Thank you for this. I was very tired when I wrote the post, and sleeping on it I also realized this myself!

I suppose then, we don't need to worry about representing a given frequency on the discrete grid, and so any frequency can sensibly be plotted. The question of a suitable domain still remains. The periodic nature of F(u) surely means that no particular section of it is more important than another, but then I obviously can't plot an infinite domain. The fact that F(u) doesn't decrease in magnitude with increasing u as a general trend is making me think I've made a mistake.

 

[olivermsun]

The question of a suitable domain still remains. The periodic nature of F(u) surely means that no particular section of it is more important than another, but then I obviously can't plot an infinite domain. The fact that F(u) doesn't decrease in magnitude with increasing u as a general trend is making me think I've made a mistake.

That's no mistake. Periodic sampling of f(x) has made F(u) periodic as you've discovered!

 

[Jezza]

Thank you! So finally, should I be considering a continuous u, or a discrete u? If discrete then what should the step size be?

My thoughts are that it should be discrete, and the step size should be 1/2, this being because the so-called fundamental period of the system is 2*2N; twice the length of the discrete space. Since the sum has a factor of 1/(2N) in the exponential to account for the size of the space, and the fundamental frequency would be 1/(4N), we're left with the factor 1/2. Discrete, because typically a Fourier transform plots only integer multiples of the fundamental frequency.

 

[olivermsun]

Right, the "discrete Fourier transform" is defined for discrete $u$ (the frequency is defined at samples of the continuous function which you plotted ).

Note however that your function $F(u)$ in the frequency domain looks to be periodic with fundamental period 2N (not 2*2N).

So what are you defining as the step size? Do you mean the difference between adjacent $u$'s or between the actual frequencies (are they cyclic or radian?) that appear in the exponential, or what?

 

[Jezza]

After a bit more research, I've found that the DFT should be thought of as a unitary matrix that maps a vector from the real basis to the sine basis. This makes sense to me I think. From this I conclude that u\in\mathbb{Z}\in[0:2N[.