# Theoretical question on Fast Fourier

I have a question regarding Discrete Fourier Transform and Discrete Time Fourier Transform.

Suppose that we have a sequence $x(n)= \{1,2,3,3,2,1\}$.

So is it possible to reconstruct the Discrete Time Fourier Transform $X(e^{j\omega})$ from the Discrete Fourier Transform $X(k)$ ? And how?

In my opinion , it is possible, although I am not sure if something like this would be any good. But in order to reconstruct it we probably need as much Discrete Fourier Transform samples as possible, right?

What do you people think on this matter?

• Your question seems to be asking if you can deduce an infinite amount of information or data (samples) from a finite amount (the length of the DFT). In general, no. Maybe you can, if you know (have extra information) that all the samples outside the DFT window are either all zero, or all exactly periodic repetitions of the data window? – hotpaw2 Nov 16 '13 at 2:20

## 1 Answer

This is (trivially) possible because all Fourier transform like operations are ideally invertible. So what you ask for is actually easily realized by:

$X(e^{j\Omega}) = DTFT\{ IDFT\{X(k)\} \}$

In formulae this is

$X(e^{j\Omega}) = \sum_{l=0}^{N-1} \sum_{k=0}^{N-1} X(k)e^{2 \pi j kl/N} e^{-j\Omega l}$

which can be a bit simplified to

$X(e^{j\Omega}) = \sum_{k=0}^{N-1} X(k) \sum_{l=0}^{N-1} e^{jl (2 \pi k/N-\Omega)}$

or, finally

$X(e^{j\Omega}) = \sum_{k=0}^{N-1} X(k) \frac{e^{2 \pi j k- jN\Omega}-1}{e^{2 \pi j k/N-\Omega}-1}$.

EDIT: The question on whether you need all samples X(k) lies in the behavior of the interpolation function $I(x) = \frac{e^{j N x}-1}{e^{j x}-1}$. This is because the above result is then equal to

$X(e^{j\Omega}) = \sum_{k=0}^{N-1} X(k) \, I(2 \pi k/N - \Omega)$.

I(x) has some "sinc like" behavior, so the question on how many X(k) you need, is really when I(x) has decayed to a value "small enough".

• Just to add a little more, the above assumes that x(n) (or maybe you'd want to call it something else) is zero outside of the given finite range. If it was periodic (with the given sequence representing one period), the DTFT would just be dirac impulses at the frequencies corresponding to the DFT bins. You can relate these two by using a rectangular window on the periodic time-domain signal (convolving the impulsive DTFT with a sinc). – HerrLip Nov 16 '13 at 5:27