Getting the DTFT from the DFT samples

Question

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?

Answer 1

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} \left(\frac{1}{N}\sum^{N-1}_{k=0}X[k]\cdot e^{j\frac{ 2\pi k}{N}n} \right) e^{-j\omega n},$$ now bring summation w.r.t n inside,

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

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

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

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)

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.

2. 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.

Answer 2

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.