Digital Signal Processing/Transforms

From Wikibooks, the open-content textbooks collection

Current revision (unreviewed)

Digital Signal Processing

This page is going to list some of the transforms from the book, explain their uses, and list some transform pairs of common functions.

[edit] Continuous-Time Fourier Transform (CTFT)

[CTFT]

$\mathcal{F}(\omega) = \int f(t) e^{j \omega t} dt$

[edit] CTFT Table

	Time Domain	Frequency Domain
	$x(t) = \mathcal{F}^{-1}\left\{ X(\omega) \right\}$	$X(\omega) = \mathcal{F} \left\{ x(t) \right\}$
1	$x(t)=\frac{1}{2 \pi} \int_{-\infty}^{\infty} X(j \omega)e^{j \omega t}d \omega$	$X(j \omega)=\int_{-\infty}^\infty x(t) e^{-j \omega t}d t$
2	$1 \,$	$2\pi\delta(\omega) \,$
3	$-0.5 + u(t) \,$	$\frac{1}{j \omega} \,$
4	$\delta (t) \,$	$1 \,$
5	$\delta (t-c) \,$	$e^{-j \omega c} \,$
6	$u(t) \,$	$\pi \delta(\omega)+\frac{1}{j \omega} \,$
7	$e^{-bt}u(t) \,$	$\frac{1}{j \omega+b} \,$
8	$\cos \omega_0 t \,$	$\pi \left[ \delta(\omega+\omega_0)+\delta(\omega-\omega_0) \right] \,$
9	$\cos (\omega_0 t + \theta) \,$	$\pi \left[ e^{-j \theta}\delta(\omega+\omega_0)+e^{j \theta}\delta(\omega-\omega_0) \right] \,$
10	$\sin \omega_0 t \,$	$j \pi \left[ \delta(\omega +\omega_0)-\delta(\omega-\omega_0) \right] \,$
11	$\sin (\omega_0 t + \theta) \,$	$j \pi \left[ e^{-j \theta}\delta(\omega +\omega_0)-e^{j \theta}\delta(\omega-\omega_0) \right] \,$
12	$\mbox{rect} \left( \frac{t}{\tau} \right) \,$	$\tau \mbox{sinc} \left( \frac{\tau \omega}{2 \pi} \right) \,$
13	$\tau \mbox{sinc} \left( \frac{\tau t}{2 \pi} \right) \,$	$2 \pi p_\tau(\omega)\,$
14	$\left( 1-\frac{2 \|t\|}{\tau} \right) p_\tau (t) \,$	$\frac{\tau}{2} \mbox{sinc}^2 \left( \frac{\tau \omega}{4 \pi} \right) \,$
15	$\frac{\tau}{2} \mbox{sinc}^2 \left( \frac{\tau t}{4 \pi} \right) \,$	$2 \pi \left( 1-\frac{2\|\omega\|}{\tau} \right) p_\tau (\omega) \,$

Notes:	$sinc(x) = sin(x) / x$ $p τ (t)$ is the rectangular pulse function of width $τ$
This transcluded page: view • talk • edit

[edit] Discrete-Time Fourier Transform (DTFT)

[edit] DTFT Table

The information in the table below may be inaccurate - The DTFT transfers into the periodic frequency domain. The signals shown in the table are not periodic, and hence they are obviously wrong. The table seems to list ordinary Fourier transforms for angular frequency, which coincidentally also uses the greek letter ω, although with a different meaning.

Time domain $x(n) \,$ where $n\in\Z$	Frequency domain $X(\omega) \,$ where $\omega\in [-\pi,\pi)$	Remarks
$\delta (n) \!$	$1 \!$	Here $\delta (n) \!$ represents the delta function which is 1 if $n = 0$ and zero otherwise.
$\delta (n - k) \!$	$e^{-i k \omega} \!$	for some $k \in \mathbb{Z}$
$u(n)=\begin{cases}0 &\text{for } n\\ 1 &\text{for } n\geq 0\end{cases}$	$\frac{1}{1-e^{-i \omega}} \!$
$e^{-ian} \!$	$\delta (\omega + a) \,$	For any real number $a \,$ . Here $δ(ω)$ is a periodic Dirac delta function. That is $\textstyle \delta(\omega)=\delta(\omega+2\pi),$ $\textstyle\int_{-\pi}^\pi\delta(\omega)\,d\omega=1$ and informally $δ(ω) = 0$ if $\omega\neq 0$
$\cos (a n) \!$	$\frac{1}{2} \Big( \delta (\omega - a) + \delta (\omega + a) \Big)$	$a \in \mathbb{R}$
$\sin (a n) \!$	$\frac{1}{2 i} \Big( \delta (\omega - a) - \delta ( \omega + a) \Big)$	$a \in \mathbb{R}$
$\mathrm{rect} \left( { ( n - M/2 ) \over M } \right)$	${ \sin\Big( \omega (M+1) / 2 \Big) \over \sin( \omega / 2 ) } \, e^{ -i \omega M / 2 }$	$M \in \mathbb{Z}$
$\operatorname{sinc} (a + n)$	$e^{i a \omega} \!$	$a \in \mathbb{R}$
$W\cdot \operatorname{sinc}^2(W n)\,$	${ 1 \over 2\pi W}\cdot \operatorname{tri} \left( { \omega \over 2\pi W } \right)$	$W \in \mathbb{Z}$
$W\cdot \operatorname{sinc} \Big( W (n + a)\Big)$	$\operatorname{rect} \left( { \omega \over 2\pi W } \right) \cdot e^{j a \omega}$	$a, W \in \mathbb{R}$ $0 < W \le 1$
$\frac{W}{(n + a)} \Big[ \cos \big( \pi W (n+a)\big) - \operatorname{sinc} \big( W (n+a)\big) \Big]$	$j \omega \cdot \operatorname{rect} \left( { \omega \over \pi W } \right) e^{j a \omega}$	$a, W \in \mathbb{R}$
$\frac{1}{\pi n^2} \Big[(-1)^n - 1\Big]$	$\| \omega \| \!$
$\frac{C (A + B)}{2 \pi} \cdot \operatorname{sinc} \left( \frac{A - B}{2\pi} n \right) \cdot \operatorname{sinc} \left( \frac{A + B}{2\pi} n \right)$		$A, B \in \mathbb{R}$ $C \in \mathbb{C}$

[edit] DTFT Properties

Property	Time domain $x[n] \!$	Frequency domain $X(\omega) \!$	Remarks
Linearity	$a x[n] + b y[n] \!$	$a X(e^{i \omega}) + b Y(e^{i \omega}) \!$
Shift in time	$x[n - k] \!$	$X(e^{i \omega}) e^{-i \omega k} \!$	integer k
Shift in frequency	$x[n] e^{i a n} \!$	$X(e^{i (\omega-a)}) \!$	real number a
Time reversal	$x[- n] \!$	$X(e^{-i \omega}) \!$
Time conjugation	$x[n]^* \!$	$X(e^{-i \omega})^* \!$
Time reversal & conjugation	$x[-n]^* \!$	$X(e^{i \omega})^* \!$
Derivative in frequency	$\frac{n}{i} x[n] \!$	$\frac{d X(e^{i \omega})}{d \omega} \!$
Integral in frequency	$\frac{i}{n} x[n] \!$	$\int_{-\pi}^{\omega} X(e^{i \vartheta}) d \vartheta \!$
Convolve in time	$x[n] * y[n] \!$	$X(e^{i \omega}) \cdot Y(e^{i \omega}) \!$
Multiply in time	$x[n] \cdot y[n] \!$	$\frac{1}{2 \pi} X(e^{i \omega}) * Y(e^{i \omega}) \!$
Correlation	$\rho_{xy} [n] = x[-n]^* * y[n] \!$	$R_{xy} (\omega) = X(e^{i \omega})^* \cdot Y(e^{i \omega}) \!$

Where:

$*\!$ is the convolution between two signals
$x[n]^*\!$ is the complex conjugate of the function x[n]
$\rho_{xy} [n]\!$ represents the correlation between x[n] and y[n].

[edit] Discrete Fourier Transform (DFT)

[edit] DFT Table

Time-Domain x[n]	Frequency Domain X[k]	Notes
$x_n\equiv\frac{1}{N}\sum_{k=0}^{N-1}X_k \cdot e^{i 2 \pi kn/N}$	$X_k\equiv\sum_{n=0}^{N-1}x_n \cdot e^{-i 2 \pi kn/N}$	DFT Definition
$x_n \cdot e^{i 2 \pi kn/N} \,$	$X_{n-k}\,$	Shift theorem
$x_{n-k}\,$	$X_k \cdot e^{-i 2 \pi kn/N}$	Shift theorem
$x_n \in \mathbf{R}$	$X_k=X_{N-k}^*\,$	Real DFT
$a^n\,$	$\frac{1-a^N}{1-a \cdot e^{-i 2 \pi k/N} }$
${N-1 \choose n}\,$	$\left(1+e^{-i 2 \pi k/N} \right)^{N-1}\,$

[edit] Z-Transform

[edit] Z-Transform Table

Here:

u[n]=1 for n>=0, u[n]=0 for n<0
δ[n] = 1 for n=0, δ[n] = 0 otherwise

	Signal, $x [n]$	Z-transform, $X (z)$	ROC
1	$\delta[n] \,$	$1\,$	$\mbox{all }z\,$
2	$\delta[n-n_0] \,$	$z^{-n_0} \,$	$z \neq 0\,$
3	$u[n] \,$	$\frac{1}{1-z^{-1} }$	$\|z\| > 1\,$
4	$- u[-n-1] \,$	$\frac{1}{1 - z^{-1}}$	$\|z\| < 1\,$
5	$n u[n] \,$	$\frac{z^{-1}}{( 1-z^{-1} )^2}$	$\|z\| > 1\,$
6	$- n u[-n-1] \,$	$\frac{z^{-1} }{ (1 - z^{-1})^2 }$	$\|z\| < 1 \,$
7	$n^2 u[n] \,$	$\frac{ z^{-1} (1 + z^{-1} )}{(1 - z^{-1})^3}$	$\|z\| > 1\,$
8	$- n^2 u[-n - 1] \,$	$\frac{ z^{-1} (1 + z^{-1} )}{(1 - z^{-1})^3}$	$\|z\| < 1\,$
9	$n^3 u[n] \,$	$\frac{z^{-1} (1 + 4 z^{-1} + z^{-2} )}{(1-z^{-1})^4}$	$\|z\| > 1\,$
10	$- n^3 u[-n -1] \,$	$\frac{z^{-1} (1 + 4 z^{-1} + z^{-2} )}{(1-z^{-1})^4}$	$\|z\| < 1\,$
11	$a^n u[n] \,$	$\frac{1}{1-a z^{-1}}$	$\|z\| > \|a\|\,$
12	$-a^n u[-n-1] \,$	$\frac{1}{1-a z^{-1}}$	$\|z\| < \|a\|\,$
13	$n a^n u[n] \,$	$\frac{az^{-1} }{ (1-a z^{-1})^2 }$	$\|z\| > \|a\|\,$
14	$-n a^n u[-n-1] \,$	$\frac{az^{-1} }{ (1-a z^{-1})^2 }$	$\|z\| < \|a\|\,$
15	$n^2 a^n u[n] \,$	$\frac{a z^{-1} (1 + a z^{-1}) }{(1-a z^{-1})^3}$	$\|z\| > \|a\|\,$
16	$- n^2 a^n u[-n -1] \,$	$\frac{a z^{-1} (1 + a z^{-1}) }{(1-a z^{-1})^3}$	$\|z\| < \|a\|\,$
17	$\cos(\omega_0 n) u[n] \,$	$\frac{ 1-z^{-1} \cos(\omega_0) }{ 1-2z^{-1}\cos(\omega_0)+ z^{-2} }$	$\|z\| >1\,$
18	$\sin(\omega_0 n) u[n] \,$	$\frac{ z^{-1} \sin(\omega_0) }{ 1-2z^{-1}\cos(\omega_0)+ z^{-2} }$	$\|z\| >1\,$
19	$a^n \cos(\omega_0 n) u[n] \,$	$\frac{ 1-a z^{-1} \cos( \omega_0) }{ 1-2az^{-1}\cos(\omega_0)+ a^2 z^{-2} }$	$\|z\| > \|a\|\,$
20	$a^n \sin(\omega_0 n) u[n] \,$	$\frac{ az^{-1} \sin(\omega_0) }{ 1-2az^{-1}\cos(\omega_0)+ a^2 z^{-2} }$	$\|z\| > \|a\|\,$