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 \omega})

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 \pi

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

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

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

\pi / 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

\omega

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