3
$\begingroup$

Suppose we know the DFT of a discrete limited sequence, some $X[k],\ k = 0, 1,\dots ,N-1$. How can we calculate the Fourier Transform of the same signal for a random frequency $\Omega$?

EDIT:

How about this, we can get the starting signal with inverse DFT, like: $$x[n] = \frac{1}{N}\sum\limits_{k=0}^{N-1} X[k]e^{j\frac{2\pi}{N}kn}$$ and then get the Fourier Transform normally with: $$\begin{align} X(e^{j\Omega}) &= \sum\limits_{n = -\infty}^{+\infty} x[n]e^{-j\Omega n}\\ &= \frac{1}{N}\sum\limits_{n = -\infty}^{+\infty} e^{-j\Omega n}\sum\limits_{k=0}^{N-1}X[k]e^{j\frac{2\pi}{N}kn} \end{align}$$

Is this correct?

EDIT2: As @Matt L. correctly states, I want the Discrete-time Fourier transform rather than the normal Fourier Transform, of course. In my native-language textbook Fourier Transform means both FT for continuous signals and DTFT for discrete signals. I hoped that that was clear from the edit. :)

$\endgroup$
2
  • 2
    $\begingroup$ This question is pretty meaningless as asked. Fourier transforms in the conventional sense are of continuous-time signals not discrete-time signals or sequences. For a sequence, we can talk of a discrete Fourier transform (that's what DFT means) but not of just Fourier transform.... $\endgroup$ Jun 4, 2013 at 16:37
  • 2
    $\begingroup$ There is a lot of confusion. In most (good) textbooks they refer to the DFT as the OP formulated it. The DFT is discrete in frequency. The Fourier transform of a sequence is then referred to as the discrete-time Fourier transform (DTFT) and is given by the formula for $X(j\Omega)$ (more often $X(e^{j\Omega})$) as presented in the question. The DTFT is continuous in frequency. So I do not agree that the question is meaningless. $\endgroup$
    – Matt L.
    Jun 4, 2013 at 17:42

3 Answers 3

2
$\begingroup$

Your question makes perfect sense, yet your solution will not work. Note that the expression for $x[n]$

$$\begin{align} x[n]=\frac{1}{N}\sum\limits_{k=0}^{N-1}X[k]e^{j\frac{2\pi}{N}kn} \end{align}$$

is periodic with period $N$. This means that the sum

$$ \frac{1}{N}\sum\limits_{n = -\infty}^{+\infty} e^{-j\Omega n}\sum\limits_{k=0}^{N-1}X[k]e^{j\frac{2\pi}{N}kn}$$

does not converge. Let's assume that $x[n]$ is defined for $0\le n< N$ and is zero otherwise. Then we get for the discrete-time Fourier transform of $x[n]$

$$X(e^{j\Omega})=\sum_{n=0}^{N-1}x[n]e^{-jn\Omega}= \frac{1}{N}\sum_{n=0}^{N-1}\sum\limits_{k=0}^{N-1}X[k]e^{j\frac{2\pi}{N}kn}e^{-jn\Omega}\tag{1}$$

This formula actually works and can be used if only the DFT $X[k]$ is given. Of course this only works for finite length signals $x[n]$. Equation (1) simply means that the DFT contains the complete information about the (finite-length) signal $x[n]$ and any frequency point $\Omega$ of the DTFT can be evaluated using the discrete values $X[k]$.

$\endgroup$
3
  • $\begingroup$ Ok, this is great! However, how can I make sure that $x[n]$ is of finite ($N$) length? If in the beginning we stated that $X[k]$ is the DFT, where $0\leq k \leq N-1$, doesn't that imply that $x[n]$ had to be of length $N$, due to the definition of DFT? :) $\endgroup$
    – Vidak
    Jun 4, 2013 at 18:04
  • 1
    $\begingroup$ Yes, of course. But of course you CAN take the DFT of any signal by simply truncating it or windowing it. Then you lose information and the DFT is not a complete description of the time-domain sequence. That's what I meant. If $x[n]$ was of length $N$ to start with, there's no problem and you can use the interpolation formula I gave in my answer. $\endgroup$
    – Matt L.
    Jun 4, 2013 at 18:07
  • $\begingroup$ Ok its all perfectly clear now! Thanks for great help! $\endgroup$
    – Vidak
    Jun 4, 2013 at 18:09
1
$\begingroup$

There are an infinite number of continuous waveforms that have the same DFT after sampling, which then have different FTs. So you need to specify more. If some continuous signal you want is strictly band-limited, then Sinc interpolation will give you one smaller family of possible solutions from which you might be able to derive an FT.

$\endgroup$
1
  • 1
    $\begingroup$ This is not what the OP asked. He wants the discrete-time Fourier transform of the sequence $x(n)$. The DFT uniquely defines the sequence $x(n)$ (which must of course be of length $N$). The DTFT of a sequence is continuous in frequency. $\endgroup$
    – Matt L.
    Jun 4, 2013 at 17:44
0
$\begingroup$

If the frequency, f, is an integer multiple of SampleRate, fs, divided by N than it's simply the X[f/fs]. If not you have to do an sin(x)/x interpolation (see http://en.wikipedia.org/wiki/Whittaker%E2%80%93Shannon_interpolation_formula)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.