domain of a discrete fourier transform

365 Views Asked by At

The task at hand is to plot a discrete Fourier transform of a function $f(x)$ defined at each element of an array of size $2N$.

The 1D Fourier transform can be approximated as a sum over discrete values:

$F(u) = \frac{1}{2N}\sum_{x=-N}^{N-1} \left(f(x) e ^ {-\frac{\pi i x u}{N}}\right)$

I'm confused by a few elements here.

What should the domain of $F(u)$ be? When I perform the DFT I find that $F(u)$ is periodic with period 2N, with vertical lines of symmetry at integer multiples of $N$. This is far from what I expect, given what I see when I google DFTs of the kinds of functions I'm trying. Whatever function I try, I always seem to get plots of a similar form to this. enter image description here. (Don't worry, I'm not here for debugging - if it's wrong just say and I'll go down the debugging avenue myself). The plot is for $N=250$ and with $f(x) = 1$ for $-6<x<5$ and $0$ otherwise.

On a similar note, does it make sense to plot ANY frequency, or should I only be plotting integer multiples of some 'fundamental frequency'? What would this fundamental frequency be?

I'm happy to provide any further details or plots if necessary. Thanks for any help!

1

There are 1 best solutions below

3
On BEST ANSWER

You must be carefull as the mathematics of DFT are not the same as for the fourier transform as an integral. However the fourier transform of the rectangular function is $sinc(x)$, which what you are showing here(altougth is the absolute value here). However because the DFT takes limited points, the first consecuence is that the DFT is periodic, as: \begin{eqnarray} F(u+2N) &=&\frac{1}{2N}\sum_{x=-N}^{N-1}f(x)e^{-πix(u+2N)/N} \\ &=& \frac{1}{2N}\sum_{x=-N}^{N-1}f(x)e^{-πix(u)/N}e^{-πix(2N)/N} \end{eqnarray} And as x takes values 0,1,2... 2N , $e^{-πix(2N)/N}=e^{-2\pi i x}=1$ meaning that $F(u+2N)=F(u)$ in your definition. This also means that F(-u)=F(2N-u), so that plotting $u=0..2N$ is most of the times enougth.

On another note, usually the DFT as defined in MATLAB and many other codes, for example, goes from u=1:N, or u=0:N-1, not 2N, but that relies more on your definition, is not that important.