1
$\begingroup$

How would you get the DTFT from the DFT samples?

How will the DFT indexes map to the discrete frequency and what kind of an interpolation would be required?

$\endgroup$
2
$\begingroup$

Myth: DTFT is Sinc-interpolated DFT.

Problem with the above statement: Sinc is not $2\pi$-Periodic function, but all DTFTs are.

Correct Answer:

  1. Theoretical, Continuous-$\omega$ $2\pi$-Periodic DTFT can be obtained by continuous Lagrangian-interpolation of the DFT Samples. So that the values at $\omega = 2\pi k/N$ will be the DFT Samples $X[k]$ for $k=0,1,...,N-1$ and the Interpolation-function's zero-crossings are at $2\pi k/N$.

In other words, DTFT will take same values at roots of unity as DFT Samples, but it will be a smooth interpolation of the DFT at other values of digital frequency $\omega$.

Mathematically, let $x[n]$ be N-Length sequence and $X[k]$ be it's N-point DFT. Now, DTFT is defined for infinite length sequences. So, lets derive DTFT of a finite length $x[n]$.

$$X(e^{j\omega}) = \sum^{N-1}_{n=0} x[n]e^{-j\omega n},$$ now write IDFT of $X[k]$ in place of $x[n]$.

$$X(e^{j\omega}) = \sum^{N-1}_{n=0} (1/N.\sum^{N-1}_{k=0}X[k]e^{j 2\pi k/N})e^{-j\omega n},$$ now bring summation w.r.t n inside,

$$X(e^{j\omega}) = \sum^{N-1}_{k=0} (X[k] (\sum^{N-1}_{n=0}1/N e^{j 2\pi k/N}e^{-j\omega n}))$$

$$ = \sum^{N-1}_{k=0} (X[k] (\sum^{N-1}_{n=0}1/N e^{-jn(\omega - 2\pi k/N)}))$$

So, basically, $$X(e^{j\omega}) = \sum^{N-1}_{k=0} X[k]. \Lambda(w - 2\pi k/N),$$ where $$\Lambda(w) = 1/N \sum^{N-1}_{n=0} e^{-jn\omega}.$$

What this means is each sample of $X[k]$ is multiplied a $2\pi k/N$ shifted copy of $\Lambda(\omega)$ and added together. Basically, $X[k]$ is interpolated by a continuous-$\omega$ and $2\pi$-Periodic function $\Lambda(\omega)$. And this function is not a Sinc-function but something else. Sure it looks like Sinc and it will approach to Sinc in the limit.

Further , $$\Lambda(\omega) = \frac{1}{N}*e^{-j\omega\frac{(N-1)}{2}} \frac{\sin(N\omega/2)}{\sin(\omega/2)}.$$ Plotting this function in $[-\pi,\pi]$ is below:

>> w = -pi:0.0001:pi;
>> y = 1/64 * sin(w*64/2)./sin(w/2);
>> plot(w,y)

enter image description here

I repeat, it is not a sinc interpolation. Sinc is not $2\pi$-Periodic function. There is no way we can get a DTFT by interpolating with sinc.

  1. Practically, you can get DTFT by interpolating with the MATLAB snippet I have provided which approximates $\Lambda(\omega)$ function.

What you can check yourself is extending the above plot to $[-4\pi:4\pi]$ and see that it indeed is Periodic function.

| improve this answer | |
$\endgroup$
  • $\begingroup$ That explains it. Thanks for the answer $\endgroup$ – Dsp guy sam Apr 3 at 18:32
0
$\begingroup$

Simply append zeros prior to computing the DFT. The phase result will change based on where you add the zeros (prepend vs postpend vs both) given it can potentially time shift the waveform but the amplitude result in exactly identical to samples of the DTFT.

Note the difference between the DTFT and DFT below:

DTFT

$$X(\omega) = \sum_{n=-\infty}^{\infty}x[n]e^{-j\omega n}$$

DFT

$$X[k] = \sum_{n= 0}^{N-1}x[n]e^{-jk \omega_o n}$$

Note that for the DTFT $\omega$ is a continuous function of frequency, while in the DFT the frequency is discrete as an index k from $0$ to $N-1$ with a constant $\omega_o = 2\pi/N$

In the DTFT the index n extends to $\pm \infty$, even if the function x[n] is non-zero over a finite length. Adding zeros to the DFT is adding more of these zero samples, so interpolates samples on the DTFT. As n extends approaches infinity in the limit, the resulting function becomes continuous (the DTFT).

Here is a simple example:

The DFT for the sequence $[1, 1, 1, 1, 1]$ is $[5, 0, 0, 0, 0]$

The DTFT in this case is a continuous function of frequency given by:

$$1 + e^{-j\omega_o n}+e^{-j2\omega_o n}+e^{-j3\omega_o n}+e^{-j4\omega_o n}$$

with $\omega_o = 2\pi/N$

Here is a plot of the DFT if we append 995 zeros, which is done in MATLAB/Octave simply by specifying a longer length for the DFT in the FFT function:

x = [1 1 1 1 1]
y = fff(x, 1000);
plot(abs(y)

Which results in a plot of the magnitude of 1000 samples the DTFT of $[1, 1, 1, 1, 1]$

This gives us more samples in the frequency domain, but does NOT increase frequency resolution. If you notice, we still have the original DFT samples of $[5,0,0,0,0]$ in the plot with additional frequency samples interpolated in between.

DTFT of x

| improve this answer | |
$\endgroup$
  • $\begingroup$ Let's say I have a 64 point DFT and also a 4096 point DFT of the same sequence. Now, the frequency resolution in the first case is 0.098 radians whereas in the second case is 0.001 radians. So, if I now try to look imagine the DTFT, we already know the value the DTFT will take at these frequencies separated by the respective resolution mentioned above starting from the 0 radians. I don't get now where do we want to insert these zeros and by what amount. Do you suggest inserting zero samples in between the DTFT values at these resolutions before interpolation? $\endgroup$ – Dsp guy sam Apr 2 at 5:32
  • $\begingroup$ First I want to be sure you are not making the mistake that the DTFT of the 64 point DFT will have any more frequency resolution (it doesn't). The frequency resolution in Hz is from the reciprocal of the total time length of the sequence, regardless of the sampling rate (so regardless of the number of samples). To get more samples of the DTFT, you append zeros, not insert between samples but add them to the end (or the beginning, or both). Notice how adding more and more zeros causes the second equation (DFT) to approach that of the first equation (DTFT) which has an infinite number of zeros $\endgroup$ – Dan Boschen Apr 4 at 21:17
  • $\begingroup$ This post may help you: dsp.stackexchange.com/questions/37927/… $\endgroup$ – Dan Boschen Apr 4 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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