Chapter 3: Discrete-Time Fourier Transform

Introduction

The Discrete-Time Fourier Transform (DTFT) provides a frequency-domain representation for discrete-time aperiodic signals.

Definition

Definition: DTFT

The Discrete-Time Fourier Transform of $x[n]$ is:

$$X(e^{j\omega })=\sum _{n=-\mathrm{\infty }}^{+\mathrm{\infty }}x[n]e^{-j\omega n}$$

The inverse DTFT is:

$$x[n]=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }X(e^{j\omega })e^{j\omega n}d\omega$$

Proposition: Periodicity

The DTFT is periodic with period $2\pi$:

$$X(e^{j(\omega +2\pi )})=X(e^{j\omega })$$

Therefore, we only need to consider $\omega \in [-\pi ,\pi ]$ or $[0,2\pi ]$.

Existence Conditions

Proposition: Sufficient Condition

The DTFT exists if $x[n]$ is absolutely summable:

$$\sum _{n=-\mathrm{\infty }}^{+\mathrm{\infty }}|x[n]|<\mathrm{\infty }$$

Common DTFT Pairs

Signal $x[n]$	DTFT $X(e^{j\omega })$
$\delta [n]$	$1$
$1$	$2\pi \sum _{k=-\mathrm{\infty }}^{\mathrm{\infty }}\delta (\omega -2\pi k)$
$u[n]$	$\frac{1}{1-e^{-j\omega }}+\pi \delta (\omega )$
$a^{n}u[n],|a|<1$	$\frac{1}{1-a{e}^{-j\omega }}$
$e^{j{\omega }_{0}n}$	$2\pi \delta (\omega -{\omega }_0)$ (periodic extension)
$\cos ({\omega }_{0}n)$	$\pi [\delta (\omega -{\omega }_0)+\delta (\omega +{\omega }_0)]$
$\frac{\sin ({\omega }_{c}n)}{\pi n}$	$\text{rect}(\omega /2{\omega }_c)$

Properties

Theorem: DTFT Properties

Let $x[n]\leftrightarrow X(e^{j\omega })$.

Linearity:

$$ax[n]+by[n]\leftrightarrow aX(e^{j\omega })+bY(e^{j\omega })$$

Time Shift:

$$x[n-n_0]\leftrightarrow X(e^{j\omega })e^{-j\omega n_0}$$

Frequency Shift:

$$x[n]e^{j{\omega }_{0}n}\leftrightarrow X(e^{j(\omega -{\omega }_0)})$$

Time Reversal:

$$x[-n]\leftrightarrow X(e^{-j\omega })$$

Conjugation:

$$x^{\ast }[n]\leftrightarrow X^{\ast }(e^{-j\omega })$$

Differentiation in Frequency:

$$nx[n]\leftrightarrow j\frac{dX(e^{j\omega })}{d\omega }$$

Convolution:

$$x[n]\ast h[n]\leftrightarrow X(e^{j\omega })H(e^{j\omega })$$

Multiplication:

$$x[n]\cdot y[n]\leftrightarrow \frac{1}{2\pi }X(e^{j\omega })⊛Y(e^{j\omega })$$

where $⊛$ denotes circular convolution over $[-\pi ,\pi ]$.

Parseval's Theorem

Theorem: Parseval's Theorem

$$\sum _{n=-\mathrm{\infty }}^{+\mathrm{\infty }}|x[n]{|}^2=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }|X(e^{j\omega }){|}^{2}d\omega$$

Discrete Fourier Transform (DFT)

Definition: DFT

For a finite-length sequence $x[n]$ of length $N$, the DFT is:

$$X[k]=\sum _{n=0}^{N-1}x[n]e^{-j2\pi kn/N},k=0,1,\dots ,N-1$$

The inverse DFT is:

$$x[n]=\frac{1}{N}\sum _{k=0}^{N-1}X[k]e^{j2\pi kn/N},n=0,1,\dots ,N-1$$

Relationship with DTFT

The DFT samples the DTFT at $N$ equally spaced frequencies:

$$X[k]=X(e^{j\omega }){|}_{\omega =2\pi k/N}$$

Twiddle Factor

Definition: Twiddle Factor

$$W_N=e^{-j2\pi /N}$$

The DFT can be written as:

$$X[k]=\sum _{n=0}^{N-1}x[n]W_N^{kn}$$

Fast Fourier Transform (FFT)

Theorem: FFT Complexity

The FFT is an efficient algorithm to compute the DFT:

• Direct DFT computation: $O(N^2)$ operations
• FFT (radix-2): $O(N{\log }_{2}N)$ operations

For $N=1024$, FFT is about 100 times faster.

Example: 8-Point DFT

For $x[n]=\{1,1,1,1,0,0,0,0\}$ (rectangular pulse):

$$X[k]=\sum _{n=0}^3{e}^{-j2\pi kn/8}=\frac{1-e^{-j\pi k}}{1-e^{-j\pi k/4}}$$

The magnitude spectrum $|X[k]|$ shows the main lobe centered at $k=0$ with side lobes.