[DSP] W04 - Relationship Between DFT and DTFT

• DFT, DFS, DTFT
• DTFT of periodic sequences
• DTFT of finite-support sequences
• Zero-padding

---

contents

• transforms
  • basis vectors
  • embedding finite-length signals
  • relation between DFT and DTFT
    • periodic extension DTFT
    • finite-support extension DTFT
  • comparison between DTFTs
• zero-padding
  • DFT of zero-padded signal
  • examples

---

transforms

• DFT and DFS are a change of basis in $C^N$
  • which is the space of complex numbers
• DTFT is only a formal change of basis in ${\ell }_2\left(Z\right)$
  • which is the space of finite-energy sequences

basis vectors:

• basis vectors are the building blocks for any signal

• a signal can be written as a combination of basis vectors

• for DTFT:
  • the basis vectors are only a formal definition
  • this is due to the index of DTFT, which is the frequency $\omega$, being uncountable
  • so, no countable basis for DTFT
  • only the intuition of the DFT and DFS is carried over to DTFT spaces
• DFT: numerical algorithm (computable)
  • linear algebra
• DTFT: mathematical tool (proofs)
  • to see properties of fourier transforms

embedding finite-length signals

• for an N-point signal $x\left[n\right]$
  • with spectral representation: $DFT\left\{x\right[n\left]\right\}=X\left[k\right]$
• there are two ways to embed $x\left[n\right]$ into an infinite sequence
  • periodic extension:
    • $\tilde{x}\left[n\right]=x\left[n\text{mod}N\right]$
  • finite-support extension:
    • $\tilde{x}\left[n\right]=\{\begin{array}{cc}x\left[n\right]& 0\le n<N\\ 0& \text{otherwise}\end{array}$

relation between DFT and DTFT

• here DFT is the spectral analysis of the original finite-length signal
• the DTFT is the spectral for the extended infinite-length sequence
  • the relationship between the two is explored below

periodic extension DTFT:

$$\tilde{x}\left[n\right]=x\left[n\text{mod}N\right]\tilde{X}\left(e^{j\omega }\right)=\sum _{n=-\infty }^{\infty }\tilde{x}\left[n\right]e^{-j\omega n}=\sum _{n=-\infty }^{\infty }(\frac{1}{N}\sum _{k=0}^{N-1}\tilde{X}\left[k\right]e^{j\frac{2\pi }{N}nk})e^{-j\omega n}=\frac{1}{N}\sum _{k=0}^{N-1}X\left[k\right](\sum _{n=-\infty }^{\infty }{e}^{j\frac{2\pi }{N}nk}{e}^{-j\omega n})$$

• here: $$\sum _{n=-\infty }^{\infty }{e}^{j\frac{2\pi }{N}nk}{e}^{-j\omega n}=DTFT\{e^{j\frac{2\pi }{N}nk}\}=\tilde{\delta }(\omega -\frac{2\pi }{N}k)$$

• so DTFT in terms of DFT coefficients: $$\tilde{X}\left(e^{j\omega }\right)=\frac{1}{N}\sum _{k=0}^{N-1}X\left[k\right]\tilde{\delta }(\omega -\frac{2\pi }{N}k)$$

• example:

  

  fig: 32-N sawtooth - finite-length signal

  

  fig: DFT of the finite-length signal

  

  fig: periodically extended finite-length sawtooth

  

  fig: DTFT of periodic extension finite-length sawtooth

  • this is a weighted set of dirac-delta functions
    • they are weighted by $X\left[k\right]$
  • they sit at multiples of $\frac{2\pi }{N}$
  • the DFT and the DTFT spectrum are essentially the same
    • they are displayed differently from each other
  • the 0 frequency of the DFT is at the left end of the spectrum, but is in the center in the DTFT spectrum
  • the DTFT spectrum is $2\pi$ periodic
    • only shown between range $[-\pi ,\pi ]$
  • instead of finite $X\left[k\right]$ values like in the DFT, the DTFT spectrum has dirac-deltas

finite-support extension DTFT

$$\tilde{x}\left[n\right]=\{\begin{array}{cc}x\left[n\right]& 0\le n<N\\ 0& \text{otherwise}\end{array}\tilde{X}\left(e^{j\omega }\right)=\sum _{n=-\infty }^{\infty }\tilde{x}\left[n\right]e^{-j\omega n}=\sum _{n=0}^{N-1}x\left[n\right]e^{-j\omega n}=\sum _{n=0}^{N-1}(\frac{1}{N}\sum _{k=0}^{N-1}X\left[k\right]e^{j\frac{2\pi }{N}nk})e^{-j\omega n}=\frac{1}{N}\sum _{k=0}^{N-1}X\left[k\right](\sum _{n=0}^{N-1}{e}^{-j(\omega -\frac{2\pi }{N}k)n})$$

• here: $$\sum _{n=0}^{N-1}{e}^{-j(\omega -\frac{2\pi }{N}k)n}=\overline{R}\left(e^{j(\omega -\frac{2\pi }{N}k)}\right)$$

• where $\overline{R}\left(e^{j\omega }\right)$ is the DTFT of $\overline{r}\left[n\right]$, the interval indicator signal

  

  fig: $\overline{r}\left[n\right]$ - interval indicator signal

• DTFT of interval signal $\overline{r}\left[n\right]$ $$\overline{R}\left(e^{j\omega }\right)=\sum _{k=0}^{N-1}{e}^{-j\omega n}=\frac{1-e^{-j\omega N}}{1-e^{-j\omega }}=\frac{e^{-j\frac{\omega N}{2}}[e^{j\frac{\omega N}{2}}-e^{-j\frac{\omega N}{2}}]}{e^{-j\frac{\omega }{2}}[e^{j\frac{\omega }{2}}-e^{-j\frac{\omega }{2}}]}=\frac{\sin \left(\frac{\omega }{2}N\right)}{\sin \left(\frac{\omega }{2}\right)}{e}^{-j\frac{\omega }{2}(N-1)}$$

  

  fig: DTFT of interval indicator signal (N = 9)

• to finish the computation of DTFT of the finite-support signal: $$\tilde{x}\left[n\right]e^{-j\omega n}=\sum _{k=0}^{N-1}X\left[k\right]\Lambda (\omega -\frac{2\pi }{N}k)$$
  • with $\Lambda \left(\omega \right)=\frac{1}{N}\overline{R}\left(e^{j\omega }\right)$
    • re-normalized version of $\overline{R}$
  • smooth interpolation of DFT values

• example:

  

  fig: 32-N sawtooth - finite-length signal

  

  fig: DFT of 32-N sawtooth - finite-length signal

  

  fig: finite-support extended signal

  

  fig: DTFT sketch from smoothened $\overline{R}$ functions

  

  fig: fully constructed DTFT of finite-support extension with the smoothened functions

comparison between DTFTs

fig: comparison between DTFT of periodic and finite-support extension

• the interpolated curves of the finite-support DTFT pass through the dirac-deltas of the periodic extension DTFT

---

zero-padding

• when computing DFT numerically, the data-vector may be padded with zeros to obtain cleaner plots
  • this is called ‘zero-padding’
• zero-padding does not add any information to the signal
• a zero-padded DFT is simply a sampled DTFT of the finite-support extension

DFT of zero-padded signal:

$$X_M\left[h\right]=\sum _{n=0}^{M-1}{x}^{\prime }\left[n\right]e^{-j\frac{2\pi }{M}nh}=\sum _{n=0}^{N-1}x\left[n\right]e^{-j\frac{2\pi }{M}nh}$$

• plug-in IDFT of $x\left[n\right]$

$$=\sum _{n=0}^{N-1}(\frac{1}{N}\sum _{k=0}^{N-1}{X}_N\left[k\right]e^{j\frac{2\pi }{N}nk})e^{-j\frac{2\pi }{M}nh}=\frac{1}{N}\sum _{k=0}^{N-1}{X}_N\left[k\right](\sum _{n=0}^{N-1}{e}^{-j(\frac{2\pi }{M}h-\frac{2\pi }{N}k)n})=\overline{X}\left(e^{j\omega }\right){|}_{\omega =\frac{2\pi }{M}h}$$

examples:

• 32-point sawtooth DFT - zero padded

  

  fig: one half of the 32-pt DFT of saw-tooth wave

  

  fig: one-half 32-pt DFT of saw-tooth wave with its DTFT overlaid

• 96-point sawtooth DFT and DTFT

  

  fig: one half of the 96-pt DFT of saw-tooth wave

  

  fig: one-half 96-pt DFT of saw-tooth wave with its DTFT overlaid

• 200-point sawtooth DFT and DTFT

  

  fig: one half of the 200-pt DFT of saw-tooth wave

  

  fig: one-half 200-pt DFT of saw-tooth wave with its DTFT overlaid

---

references

• ecole dsp