1

If I have the basic Discrete Fourier Transform from a discrete function $x[n]$, like this: $$\displaystyle X[k] = \sum\limits_{n=0}^{N-1} x[n]e^{-j\frac{2\pi}{N}kn} $$

How can I get to the expression for the Fourier Transform:

$$\displaystyle X(j\Omega) = \sum\limits_{n=-\infty}^{+\infty} x[n]e^{-j\Omega n} $$

I understand that it follows when $N\rightarrow \infty$ but When you simply substitute that, you get limits from $0 \mbox{ to } \infty$ instead of $-\infty \mbox{ to } \infty$, which si needed for Fourier Transform.

How can I get around this?

P.S. The function $x$ can be of length $L$, and $N\geq L$, with func $x$ appended with zeros for values of n $L\leq n \leq N-1$, but that isn't so important.

Vidak
  • 322
  • Mathematically, that is the wrong question to ask. A Fourier transform is an algebra homomorphism from the group algebra to continuous functions on the Pontryagin dual. What you have here is two different groups: $\mathbb{Z}_n$ and the integers $\mathbb{Z}$. So to "go from one to the other", you need to relate the two groups. There's no precise way to do that in this case besides some questionable heuristics. – Michael Jun 01 '13 at 09:22

1 Answers1

3

For the Discrete Fourier Transform (DFT) the signal $x[n]$ needs to be of finite length. This is not a very serious restriction because $N$ can of course be chosen arbitrarily large. If the indices are then chosen such that $x[n]$ is zero for $n<0$ and $n\ge N$ then the Fourier Transform of $x[n]$ can be evaluated at discrete frequencies $\Omega_k=\frac{2\pi k}{N}$ using the DFT. A denser frequency grid can be easily computed by zero-padding $x[n]$, i.e. by appending zeros to $x[n]$ and computing the DFT for a larger value of $N$.

EDIT: If we extend $x[n]$ periodically, we have $$ X[k] = \sum\limits_{n=0}^{N-1} x[n]e^{-j\frac{2\pi}{N}kn}= \sum\limits_{n=-N/2}^{N/2-1} x[n]e^{-j\frac{2\pi}{N}kn} $$ for even $N$. Now you can take the limit $N\rightarrow\infty$ if you make sure that the limit exists, i.e. if $\sum_{n=-\infty}^{\infty}|x[n]|$ is finite.

Matt L.
  • 10,636
  • Yes, of course, that I know. However, my question was to derive the expression of the Fourier transform from the expression for the Discrete Foureir Transform, by mathematical transformations and letting N grow to infinity. – Vidak Jun 01 '13 at 08:14
  • OK, see my edited answer. – Matt L. Jun 01 '13 at 09:02
  • Great, that's what I wanted :) thanks! – Vidak Jun 01 '13 at 09:16