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

contents

transforms

  • DFT and DFS are a change of basis in \(\mathbb{C}^N\)
    • which is the space of complex numbers
  • DTFT is only a formal change of basis in \(\ell_2(\mathbb{Z})\)
    • 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[n]\)
    • with spectral representation: \(DFT\{x[n]\} = X[k] \)
  • there are two ways to embed \(x[n]\) into an infinite sequence
    • periodic extension:
      • \( \tilde{x}[n] = x[n \text{ mod } N] \)
    • finite-support extension:
      • \( \tilde{x}[n] = \Bigg \{ \begin{matrix} x[n] & 0 \leq n < N \\ 0 & \text{ otherwise }\end{matrix} \)

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}[n] = x[n \text{ mod } N]\\ \tilde{X}(e^{j\omega}) = \sum_{n = -\infty}^{\infty} \tilde{x}[n]e^{-j\omega n} \
= \sum_{n = -\infty}^{\infty} \bigg ( \frac{1}{N} \sum_{k = 0}^{N-1} \tilde{X}[k] e^{j\frac{2\pi}{N}nk} \bigg ) e^{-j\omega n} \
= \frac{1}{N} \sum_{k = 0}^{N-1} X[k] \bigg ( \sum_{n = -\infty}^{\infty} e^{j\frac{2\pi}{N}nk} e^{-j\omega n} \bigg ) \]

  • here: \[ \sum_{n = -\infty}^{\infty} e^{j\frac{2\pi}{N}nk} e^{-j\omega n} = DTFT \bigg \{ e^{j\frac{2\pi}{N}nk} \bigg \} \
    = \tilde{\delta}(\omega - \frac{2\pi}{N}k) \
    \]

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

  • example:

    dft-dtft-0

    fig: 32-N sawtooth - finite-length signal

    dft-dtft-1

    fig: DFT of the finite-length signal

    dft-dtft-2

    fig: periodically extended finite-length sawtooth

    dft-dtft-3

    fig: DTFT of periodic extension finite-length sawtooth

    • this is a weighted set of dirac-delta functions
      • they are weighted by \(X[k]\)
    • 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[k]\) values like in the DFT, the DTFT spectrum has dirac-deltas
finite-support extension DTFT

\[ \tilde{x}[n] = \Bigg \{ \begin{matrix} x[n] & 0 \leq n < N \\ 0 & \text{ otherwise }\end{matrix} \
\tilde{X}(e^{j\omega}) = \sum_{n = -\infty}^{\infty} \tilde{x}[n]e^{-j\omega n} = \sum_{n=0}^{N-1} x[n]e^{-j\omega n} \
= \sum_{n = 0}^{N-1} \bigg ( \frac{1}{N} \sum_{k = 0}^{N-1} X[k] e^{j\frac{2\pi}{N}nk} \bigg ) e^{-j\omega n} \
= \frac{1}{N} \sum_{k = 0}^{N-1} X[k] \bigg ( \sum_{n = 0}^{N-1} e^{-j(\omega - \frac{2\pi}{N}k)n} \bigg ) \]

  • here: \[ \sum_{n = 0}^{N-1} e^{-j(\omega - \frac{2\pi}{N}k)n} = \bar{R}(e^{j(\omega - \frac{2\pi}{N}k)}) \]

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

    r-bar

    fig: \( \bar{r}[n] \) - interval indicator signal

  • DTFT of interval signal \( \bar{r}[n] \) \[ \bar{R}(e^{j\omega} ) = \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(\frac{\omega}{2}N)}{\sin(\frac{\omega}{2})} e^{-j\frac{\omega}{2}(N-1)} \\
    \]

    r-bar-dtft

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

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

  • example:

    dft-dtft-10

    fig: 32-N sawtooth - finite-length signal

    dft-dtft-11

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

    dft-dtft-12

    fig: finite-support extended signal

    dft-dtft-14

    fig: DTFT sketch from smoothened \(\bar{R}\) functions

    dft-dtft-15

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

comparison between DTFTs

dft-dtft-16

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[h] = \sum_{n=0}^{M-1}x^{\prime}[n]e^{-j\frac{2\pi}{M}nh} = \sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{M}nh} \
\]

  • plug-in IDFT of \( x[n] \)

\[ = \sum_{n=0}^{N-1} \bigg ( \frac{1}{N} \sum_{k=0}^{N-1}X_N[k]e^{j\frac{2\pi}{N}nk} \bigg ) e^{-j\frac{2\pi}{M}nh} \
= \frac{1}{N} \sum_{k=0}^{N-1} X_N[k] \bigg ( \sum_{n=0}^{N-1} e^{-j(\frac{2\pi}{M}h - \frac{2\pi}{N}k)n} \bigg ) \
= \bar{X}(e^{j\omega})\vert_{\omega = \frac{2\pi}{M}h} \]

examples:

  • 32-point sawtooth DFT - zero padded

    zp-2

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

    zp-3

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

  • 96-point sawtooth DFT and DTFT

    zp-4

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

    zp-5

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

  • 200-point sawtooth DFT and DTFT

    zp-64

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

    zp-7

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

references