Discrete-Time Fourier Transform

Definition

Forward transform

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

where $X(\omega +2\pi )=X(\omega )$.

Inverse transform

$$x[n]=\frac{1}{2\pi }{\int }_0^{2\pi }X(\omega )\exp (j\omega n)\mathrm{d}\omega$$

Periodic Data

If $x[n]$ is $N$-periodic, then we have

$$X(\omega )=\sum _{m=-\infty }^{\infty }\sum _{n=0}^{N-1}x[n]\exp \left[-j\omega (n+mN)\right]$$

Since $x[n+mN]=x[n]$. And here $\exp \left[-j\omega \left(n+mN\right)\right]=\exp (-j\omega n)\exp (-j\omega mN)$, so that

$$X(\omega )=\sum _{n=0}^{N-1}x[n]\exp (-j\omega n)\sum _{m=-\infty }^{\infty }\exp (-j\omega mN)$$

where we have the Dirac Comb

$$\sum _{m=-\infty }^{\infty }\exp (-j\omega mN)=\frac{2\pi }{N}\sum _{k=-\infty }^{\infty }\delta \left(\omega -\frac{2\pi k}{N}\right)$$

Thus, we get

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

And we can rearrange this into

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

which gives

$$\boxed{X(\omega )=\sum _{k=-\infty }^{\infty }2\pi a_k\delta \left(\omega -k{\omega }_0\right)}$$

where ${\omega }_0=\frac{2\pi }{T}=\frac{2\pi }{N}$, and $a_k$ is the discrete Fourier series of $x(t)$. This is quite similar to the continuous case.

Note that the discrete Fourier Series is periodic with period $N$, then we get the period of $X(\omega )$ here is $N\cdot {\omega }_0=N\cdot \frac{2\pi }{N}=2\pi$.

Properties

Property	Signal	DTFT of the signal
Linear	$ax[n]+by[n]$	$aX(\omega )+bY(\omega )$
Time shift	$x[n-n_0]$	$\exp (-j\omega n_0)X(\omega )$
Frequency shift	$\exp (j{\omega }_{0}n)x[n]$	$X(\omega -{\omega }_0)$
Conjugate	$x^{\ast }[n]$	$X^{\ast }(-\omega )$
Time inverse	$x[-n]$	$X(-\omega )$
Time expand	$x_{(k)}[n]=\{\begin{array}{ll}x[n/k],& k\mid n\\ 0,& k\nmid n\end{array}$	$X(k\omega )$
Convolution	$x[n]\ast y[n]$	$X(\omega )Y(\omega )$
Multiplication	$x[n]y[n]$	$\frac{1}{2\pi }{\int }_{2\pi }X(\theta )Y(\omega -\theta )\mathrm{d}\theta$
Time difference	$x[n]-x[n-1]$	$\left[1-\exp (-j\omega )\right]X(\omega )$
Sum	$\sum _{k=-\infty }^{n}x[k]$	$\frac{1}{1-\exp (-j\omega )}X(\omega )+\pi X(0)\sum _{k=-\infty }^{+\infty }\delta (\omega -2\pi k)$
Frequency differentiate	$nx[n]$	$j\frac{\mathrm{d}X(\omega )}{\mathrm{d}\omega }$
Frequency real part	$\mathcal{E}v\left\{x[n]\right\}=\frac{1}{2}\left(x[-n]+x[n]\right)$	$\mathcal{R}e\left\{X(\omega )\right\}$
Frequency imaginary part	$\mathcal{O}d\left\{x[n]\right\}=\frac{1}{2}(-x[-n]+x[n])$	$\mathcal{I}m\left\{X(\omega )\right\}$

Note

The singular part of the sum property, $\frac{1}{1-\exp (-j\omega )}X(\omega )+\pi X(0)\sum _{k=-\infty }^{+\infty }\delta (\omega -2\pi k)$, is aroused when $\omega =2k\pi$. In this case $\sum _{k=-\infty }^n\exp \left[-j\omega (n-k)\right]X(\omega )=\sum _{k=-\infty }^{n}X(\omega )$ does not converge.

Examples

Periodic

Signal	DTFT
$\exp (j{\omega }_{0}n)$	$2\pi \sum _{l=-\infty }^{\infty }\delta (\omega -{\omega }_0-2\pi l)$
$\cos {\omega }_{0}n$	$\pi \sum _{l=-\infty }^{+\infty }\left[\delta (\omega -{\omega }_0-2\pi l)+\delta (\omega +{\omega }_0-2\pi l)\right]$
$\sin {\omega }_{0}n$	$\frac{\pi }{j}\sum _{l=-\infty }^{\infty }\left[\delta (\omega -{\omega }_0-2\pi l)-\delta (\omega +{\omega }_0-2\pi l)\right]$
$x[n]=1$	$2\pi \sum _{l=-\infty }^{\infty }\delta (\omega -2\pi l)$
$x[n+kN]=\{\begin{array}{ll}1,& \Vert n\Vert \le N_1\\ 0,& N_1<\Vert n\Vert \le \frac{N}{2}\end{array}$	$2\pi \sum _{k=-\infty }^{\infty }{a}_k\delta \left(\omega -\frac{2\pi k}{N}\right)$, $a_k$ see here
$\sum _{k=-\infty }^{\infty }\delta [n-kN]$	$\frac{2\pi }{N}\sum _{k=-\infty }^{\infty }\delta \left(\omega -\frac{2\pi k}{N}\right)$

Non-periodic

Signal	DTFT
$a^{n}u[n],\Vert a\Vert <1$	$\frac{1}{1-a\exp (-j\omega )}$
$x[n]=\{\begin{array}{ll}1,& \Vert n\Vert \le N_1\\ 0,& \Vert n\Vert >N_1\end{array}$	$\frac{\sin \left[\omega \left(N_1+\frac{1}{2}\right)\right]}{\sin (\omega /2)}$
$\frac{\sin Wn}{\pi n},0<W<\pi$	$X(\omega )=\{\begin{array}{ll}1,& 0\le \Vert \omega \Vert \le W\\ 0,& W<\Vert \omega \Vert \le \pi \end{array}$
$\delta [n]$	$1$
$u[n]$	$\frac{1}{1-\exp (-j\omega )}+\sum _{k=-\infty }^{\infty }\pi \delta (\omega -2\pi k)$
$\delta [n-n_0]$	$\exp (-j\omega n_0)$
$(n+1)a^{n}u[n],\Vert a\Vert <1$	$\frac{1}{{\left[1-a\exp (-j\omega )\right]}^2}$
$\frac{(n+r-1)!}{n!(r-1)!}{a}^{n}u[n],\Vert a\Vert <1$	$\frac{1}{{\left[1-a\exp (-j\omega )\right]}^r}$