Discrete-time Fourier transform

The discrete-time Fourier transform (or DTFT) is part of the family of Fourier transforms. It transforms a function $f (n)$ of a discrete "time" variable n where $n \in \mathbb{Z}$ . The DTFT produces a continuous, periodic spectrum $F (e i ω)$ .

Contents

1 Definition

2 Periodicity of the DTFT

3 Difference between the DTFT and DFT

3.1 Frequency interpolation of the DTFT via the DFT
3.2 DTFT from the DFT by infinite zero padding

4 Difference between the DTFT and the Fourier series

5 Relationship with the Z-transform

6 References

Definition

The DTFT of $f (n)$ is given by the following equation.

$F(e^{i \omega}) = \sum_{n=-\infty}^{\infty} f(n) \,e^{-in\omega}$

We can recover $f (n)$ via the inverse DTFT.

$f(n) =\frac{1}{2 \pi}\int_{-\pi}^{\pi} F(e^{i \omega})\,e^{i n \omega} \, d \omega$

Periodicity of the DTFT

The DTFT is $2π$ periodic, i.e.,

$F(e^{i \omega}) \,\!= F(e^{i (\omega + 2\pi)})$

as shown by the following proof.

$F(e^{i (\omega + 2 \pi)}) = \sum_{n=-\infty}^{\infty} f(n) \,e^{-i n (\omega + 2\pi)} = \sum_{n=-\infty}^{\infty} f(n) \,e^{-i n \omega} e^{-i n 2\pi}$

Since $e^{i 2 \pi} = \,\!1$ (See complex numbers), the above equals

$\sum_{n=-\infty}^{\infty} f(n) \,e^{-i n \omega} 1^{-n} = \sum_{n=-\infty}^{\infty} f(n) \,e^{-i n \omega} = F(e^{i \omega})$

thereby proving the periodicity. Thus, we see that the discreteness in one domain leads to periodicity in the conjugate domain because of the result from complex number theory that $e^{i 2 \pi} = \,\!1$ .

Difference between the DTFT and DFT

The DTFT differs from the discrete Fourier transform (DFT) in that the latter transforms a discrete-time function $f (n)$ that is periodic. For a length $N$ finite signal $f(n) : n \in \{0, 1, \ldots, N-1 \}$ , the DFT actually samples the DTFT at uniform intervals $k \in \{ 0, 1, \ldots, N-1 \}$ in the frequency domain.

$F(k) = \left. F(e^{i \omega}) \, \right|_{\omega = 2 \pi \frac{k}{N}} = \left. \sum_{n=0}^{N-1} f(n) \,e^{-i \omega n} \, \right|_{\omega = 2 \pi \frac{k}{N}} = \sum_{n=0}^{N-1} f(n) \,e^{-i 2 \pi \frac{k n}{N}}$

Frequency interpolation of the DTFT via the DFT

Missing image
No-zeropad.png

DFT of the signal without zero padding.

Missing image
Zeropad.png

DFT of the signal after zero padding.

A common technique to obtain more resolution in the frequency domain is to zero pad $f (n)$ . Zero padding a signal simply means that we append a finite number of zeros to the end of the signal. So, if we add $M - N$ zeros to the end of $f (n)$ so that the signal is of length $M$ , the DFT becomes the following.

$\sum_{n=0}^{M-1} f(n) \,e^{-i 2 \pi \frac{k n}{M}} \mbox{ where } k \in \{0, 1, \ldots, M - 1\}$

Since the values of $f (n)$ from $N$ to $M - 1$ are zero, the above reduces to the following.

$\sum_{n=0}^{N-1} f(n) \,e^{-i 2 \pi \frac{k n}{M}} + \sum_{n=N}^{M-1} f(n) \,e^{-i 2 \pi \frac{k n}{M}} = \sum_{n=0}^{N-1} f(n) \,e^{-i 2 \pi \frac{k n}{M}}$

Thus, we have obtained more resolution in the frequency domain since we have $M$ discrete frequencies rather than $N$ discrete frequencies.

As an example, we performed the DFT on the length 64 signal $e^{i \frac{\pi}{4} n}$ where $n \in \{0, 1, \ldots, 63 \}$ . The top figure is the plot of the magnitude of the DFT. As expected, it is an impulse at $π / 4$ . Then, we zero padded the signal with 192 zeros and took the DFT. The bottom plot shows the magnitude of this DFT. In the bottom plot, we obtain more resolution in the frequency domain from zero padding.

DTFT from the DFT by infinite zero padding

If we append an infinite number of zeros to f(n), then the DFT approaches the DTFT. This padding is equivalent to having $M \rightarrow \infty$ and $k \rightarrow \infty$ at different rates. As a result, the quantity given below approaches the continuous variable $ω$ .

$\lim_{M \to \infty, k \to \infty} \frac{2 \pi k}{M} = \omega$

and it follows that

$\lim_{M \to \infty, k \to \infty} \sum_{n=0}^{N-1} f(n) \,e^{-i 2 \pi \frac{k n}{M}} = \sum_{n=0}^{N-1} f(n) \,e^{-i \omega n}$

Thus, we obtain the DTFT by zero padding the signal $f (n)$ with an infinite number of zeros.

Difference between the DTFT and the Fourier series

Essentially, the DTFT is the reverse of the Fourier series, in that the latter has a continuous, periodic input and a discrete spectrum. The applications of the two transforms, however, are quite different.

Relationship with the Z-transform

The DTFT is a special case of the Z-transform. The Z-transform is defined as follows.

$F(z) = \sum_{n=-\infty}^{\infty} f(n) \,z^{-n}$

If we evaluate the Z-transform at $z = e i ω$ , then we recover the DTFT. (For this reason, the notation $F (e i ω)$ is generally preferred over the notation $F (ω)$ for representing the DTFT.)

$\left. F(z) \right|_{z = e^{i \omega}} = \sum_{n=-\infty}^{\infty} f(n) \,e^{-in\omega} = F(e^{i \omega})$

Note that evaluating at $z = e i ω$ is equivalent to evaluating the Z-transform along the unit circle in the complex plane.

References

Boaz Porat : A Course in Digital Signal Processing, pp. 27-29, pp. 104-105, John Wiley and Sons, ISBN 0-471-14961-6