GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.
Spring 2016: Signal Processing
[TOC]
-
signal : description of the evolution of a physical phenomenon
- processing
- analysis : understanding the information carried by the signal
- synthesis : creating a signal to contain the given information
- communication
- reception : analysis of an incoming signal
- transmission : synthesis of an outgoing signal
- processing
-
digital model
- discrete time :
$\bar{x} = \frac{1}{N}\sum_{n=0}^{N-1}x[n]$ - discrete amplitude : important for storage, processing, transmission
- storage :
${0,1}$ - data transmission :
$x_1(t)=G\sgn[x(t)+G\sigma(t)]$ as quantized signals
- discrete time :
-
analog model
- continuous time :
$\bar{x} = \frac{1}{b-a}\int_a^b f(t)dt$ - storage : paper, vinyl, VHS, silver plates
- data transmission :
$x_N(t)=x(t)+NG\sigma(t)$ with$N$ repeaters ($sign$ after each repetion to avoid noise multiplication)
- continuous time :
-
sampling theorem :
$x(t)=\sumi x[n]\sinc(\frac{t-nT_s}{T_s})$ -
discrete-time signal : a sequence of complex numbers
$x:\Z\to\C$ noted as$x[n]$ - analysis : periodic measurement
- synthesis : stream of generated samples
- delta signal :
$x[n]=\delta[n]$ - unit step :
$x[n]=u[n]=1_{n\ge 0}$ - exponential decay :
$x[n]=\abs a^n u[n]$ with$\abs a< 1$
-
signal classes
- finite-length :
$\vec{x}=[x_0\ldots x_{N-1}]^T$ - infinite-length :
$x[n]$ - periodic :
$\tilde x[n]=\tilde x[n+kN]$ , replicated finite-lenght - finite-support : finite-length completed with
$0$ 's
- finite-length :
-
elementary operators
- scaling :
$y[n]=\alpha x[n]$ - sum :
$y[n]=x[n]+z[n]$ - product :
$y[n]=x[n]\cdot z[n]$ - shift by
$k$ (delay) :$y[n]=x[n-k]$ , best with periodic extension (circular)
- scaling :
-
energy :
$E_x=\sumi \abs{x[n]}^2$ - periodic :
$E_x=\infty$
- periodic :
-
power :
$P_x=\lim_{N\to\infty}\frac{1}{2N+1}\sum_{n=-N}^N\abs{x[n]}^2$ - periodic :
$P_x=\frac{1}{N}\sum_{n=0}^{N-1}\abs{\tilde x[n]}^2$
- periodic :
-
DSP as building block
- adder :
$x[n]+y[n]$ - multiplier :
$\alpha x[n]$ - delay :
$z^{-N}$ giving$x[n-N]$ - moving average :
$y[n]=\frac{x[n]+x[n-1]}{2}$ - zero initial conditions : set a start time
$n_0=0$ , assume input and output are zero for all time before$n_0$ - recursion :
$y[n]=x[x]+\alpha y[n-1]$
- zero initial conditions : set a start time
- adder :
-
Karplus-Strong algorithm :
$y[n]=\alpha y[n-3]+\bar x[n]$ with$\bar x[n]=\delta[n]+2\delta[n-1]+3\delta[n-2]$ - build a recursion loop with a delay of
$M$ ($M$ -tap) : controls pitch - choose a signal
$\bar x[n]$ that is nonzero only for$0\le n < M$ : controls color (timbre) - choose a decay factor :
$\alpha$ controls envelope (decay) - input
$\bar x[n]$ to the system - play the output
- frequency :
$f=\frac{1}{MT}Hz$ with time$T$ associated to$M$ sample interval
- build a recursion loop with a delay of
-
vector spaces : usefull in approximation and compression, easy sampling, interpolation, Fourier Transform, fundamental in communication system design
- euclidian :
$\R^2,\R^3$ - linear algebra :
$\R^N,\C^N$ - space of square-summable infinite sequences :
$l_2(\Z)$ - space of quare-integrable functions over an interval :
$L_2([a,b])$ - inner product :
$<x,y>=\int_{b}^a x(t)y^*(t)dt$
- inner product :
- once you know the properties are satisfied, you can use all the tools for the space
- ingredients
- set of vectors :
$V$ - set of scalars :
$\C$
- set of vectors :
- properties :
$x,y,z$ are vectors$x+y=y+x$ $(x+y)+z=x+(y+z)$ $\alpha (x+y)=\alpha y +\alpha x$ $(\alpha+\beta)x=\alpha x+\beta x$ $\alpha(\beta x)=(\alpha\beta)x$ $\exists 0\in V\mid x+0=0+x=x$ $\forall x\in V\exists (-x)\mid x+(-x)=0$
- inner (dot) product :
$<\cdot,\cdot> : V\times V\to\C$ $<x+y,z>=<x,z>+<y,z>$ $<x,y>=<y,x>^*$ $<\alpha x,y>=\alpha^*<x,y>$ $<x,\alpha y>=\alpha <x,y>$ $<x,x>=\norm x^2\ge 0$ $<x,x>=0\iff x=0$ $<x,y>=\norm x\norm y\cos\alpha$ -
$<x,y>=0$ with$x,y\not=0$ : orthogonal (maximally different) - defines a norm :
$\norm x = \sqrt{<x,x>}$ - norm defines a distance :
$d(x,y)=\norm{x-y}$ - mean square error :
$\norm{x-y}^2$ - for signals :
$<x,y>=\sum_{n=0}^{N-1} x^*[n]y[n]$ , requires square-summable$\sum\abs{x[n]}^2 <\infty$ - pythagorean theorem :
$\norm{x+y}^2=\norm{x}^2+\norm{y}^2$ for$x\perp y$
- euclidian :
-
canonical basis : set of
$K$ vectors in a vector space with basis$W={w^{(k)}}_{k=0,\ldots, K-1}$ - linear combination :
$\forall x;x=\sum_{k=0}^{K-1}\alpha_k w^{(k)}$ with$\alpha_k\in\C$ unique - unique representation implies linear independence :
$\sum_{k=0}^{K-1}\alpha_k w^{(k)}=0\iff \alpha_k=0; k=0,\ldots,K-1$ - basis for functions over an interval :
$v^{(v)}=\sin(\pi(2k+1)t)$ with$\sum_{k=0}^N(1/N)v^{(k)}$ - orthogonal basis :
$<w^{(k)},w^{(n)}>=0$ for$k\not=n$ - orthonormal bassis :
$<w^{(k)},w^{(n)}>=\delta[n-k]$ for$k\not=n$ (using Gram-Schmidt) - basis expansion :
$\alpha_k=<w^{(k)},x>$ - change of basis :
$x=\sum_{k=0}^{K-1}\alpha_k w^{(k)}=\sum_{k=0}^{K-1}\beta_k v^{(k)}$ - if
${v^{(k)}}$ orthnormal $\beta_h=<v^{(h)},x>=<v^{(h)},\sum_{k=0}^{K-1}\alpha_k w^{(k)}>=\sum_{k=0}^{K-1}\alpha_k<v^{(h)},w^{(k)}>=\sum_{k=0}^{K-1}\alpha_k c_{hk}$ - parseval's theorm : energy is conserved across change of basis
$\norm{x}^2=\sum_{k=0}^{K-1}\abs{\alpha_k}^2$ - rotation matrix : $R=\begin{bmatrix}\cos\theta & \sin\theta \\ -\sin\theta & \cos\theta \end{bmatrix}$ with new coefficient
$\beta = R\alpha$
- if
- linear combination :
-
subspace : subset of vectors closed under addition and scalar multiplication
- approximation : less dimensionnal projection
- least-square approximation for subset
$S$ :$\hat x=\sum_{k=0}^{K-1}<s^{(k)},x>s^{(k)}$ (orthogonal projection)- has minimum-norm error :
$\arg\min_{y\in S}\norm{x-y}=\hat x$ - error orthogonal to approximation :
$<x-\hat x,\hat x>=0$
- has minimum-norm error :
-
Gram-schmidt : original set
${s^{(k)}}\to{u^{(k)}}$ orthonormal set$p^{(k)}=s^{(k)}-\sum_{n=0}^{k-1}<u^{(n)},s^{(k)}>u^{(n)}$ -
$u^{(k)}=p^{(k)}/\norm{p^{(k)}}$ for each step$k$
-
Legendre polynormials : orthonormal basis for
$P_N([-1,1])$ ,$\alpha_k=<u^{(k)},x>$ with naive basis$s^{(k)}=t^k$ $u^{(0)}=\sqrt{1/2}$ $u^{(1)}=\sqrt{3/2}t$ $u^{(2)}=\sqrt{5/8}(3t^2-1)$
-
Hilbert space : vector space
$H(V,\C)$ , inner product$<\cdot,\cdot>:V\times V\to\C$ , completeness (limiting operations must yield vector space elements)- finite-length and periodic signals live in
$\C^N$ - inifinte-length signals live in
$l_2(\Z)$ - different bases are different observation tools for signals
- subspace projections useful in filtering and compression
- finite-length and periodic signals live in
-
time domain : linear combination of atomic time units
$x[n]=\sum_{k=0}^{N-1} x[k]\delta^{(k)}$ -
oscillations are everywhere
- sustainable dynamic systems exhibit oscillatory behavior
- things that don't move in circles can't last
- human receptors
- cochlea : ear, air pressure, frequencies between 20Hz and 20KHz
- rods and cones : retina, electromagnetic sinusoids, frequencies between 430THz to 790THz
- oscillatory heartbeat :
$x[n]=A\cos(\omega n+\phi)$ with frequency$\omega$ , initial phase$\phi$ , amplitude$A$ - complex exponential :
$x[n]=Ae^{j(\omega n+\phi)}=A[\cos(\omega n +\phi)+j\sin(\omega n +\phi)]$ - periodic in
$n$ :$e^{j\omega n}$ with$\omega=\frac{M}{N}2\pi$ with$M,N\in\N$ - wagonwheel effect : max speed at
$\omega=\pi$ - digital frequency : how many samples before pattern repeats, no unit
- physical frequency : how many secondes before pattern repeats, hertz,
$\frac{1}{MT_s}$ with$M$ samples of$T_s$ system clock
- frequency domain : as important as the time domain, hidden signal properties
-
fourier : simple change of basis, change of perspective
- analysis : express signal as combination of periodic oscillations, from time to frequency domain
- synthesis : create signal with frequency content, from frequency to time domain
- orthogonal basis :
$w_k[n]=w_n^{(k)}=e^{j\frac{2\pi}{N}nk}$ (normalization$1/\sqrt{N}$ ) - proof =
$<w^{(k)},w^{(h)}>=N$ for$h=k$ otherwise$0$ - wrapping the phase :
$[-\pi,\pi]$ by adding$2\pi$
-
discrete fourier transform : DFT, numerical algorithm
- analysis :
$X_k=<w^{(k)},x>$ or$X[k]=\sum^{N-1}_{n=0}x[n]e^{-j\frac{2\pi}{N}nk}$ - synthesis : $x=\frac{1}{N}\sum^{N-1}{k=0}X_kw^{(k)}$ or $x[n]=\frac{1}{N}\sum{k=0}^{N-1}X[k]e^{j\frac{2\pi}{N}nk}$
- parseval :
$\sum_{n=0}^{N-1}|x[n]|^2=\frac{1}{N}\sum_{k=0}^{N-1}|X[k]|^2$ - finite-length time shifts :
$IDFT{e^{-j\frac{2\pi}{N}Mk}X[k]}=x[(n-M)\mod N]$ circular - real signal : symmertic in magnitude
$|X[k]|=|X[N-k]|$ for$k=1,\ldots,\lceil N/2\rceil$ - DFT of length
$M$ step :$X[k]=\frac{\sin(\frac{\pi}{N}Mk)}{\sin(\frac{\pi}{N}k)}e^{-j\frac{\pi}{N}(M-1)k}$ $X[0]=M$ -
$X[k]=0$ if$Mk/N$ integer - DFT of
$L$ periods :$X_L[k]=L\bar X[k/L]$ if$k$ multiple of$L$ otherwise$0$ with$\bar X[k/L]=\sum_{n=0}^{M-1}\bar x[n]e^{-j\frac{2\pi}{M}n\frac{k}{L}}$ 
- analysis :
-
matrix form basis change : $\begin{bmatrix}1 & 1 & 1 & \cdots & 1\\ 1 & W^1 & W^2 & \cdots & W^{N-1}\\ 1 & W^2 & W^4 & \cdots & W^{2(N-1)}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & W^{N-1} & W^{2(N-1)} & \cdots & W^{(N-1)^2}\end{bmatrix}$ with
$W[n,m]=W_N^{nm}=e^{-j\frac{2\pi}{N}nm}$ - analysis :
$X=Wx$ - synthesis :
$\frac{1}{N}W^HX$ - hermitian :
$W^H$ conjugate transpose - dft :
$W^m_N=W_N^{(m\mod N)}$
- analysis :
-
short-time fourier transform : STFT
- time obfuscates frequency :
$\Delta t\Delta f=2\pi$ - small singal pieces of length
$L$ :$X[m;k]=\sum_{n=0}^{L-1} x[m+n]e^{-j\frac{2\pi}{L}nk}$ - spectrogram : magnitude (dark small, white large),
$10\log_{10}(|X[m,k]|)$ 
- system clock :
$F_s=1/T_s$ - highest positive frequency :
$F_s/2$ Hz - frequency resolution :
$F_s/L$ Hz - width of time slices :
$LT_s$ s - wideband (short window) : precise location of transistions, poor frequency resolution
- narrowband (long window) : more frequency resolution, less precision in time
- system clock :
- time obfuscates frequency :
-
discrete fourier series : DFS,
$N$ -periodic, equivalent to DFT of one period- analysis :
$X[k]=\sum_{k=0}^{N-1} x[n]e^{-j\frac{2\pi}{N}nk}$ with$n\in\Z$ - synthesis :
$x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X[k]e^{j\frac{2\pi}{N}nk}$ with$n\in\Z$
- analysis :
-
discrete-time fourier transform : DTFT, infinite signals, mathematical tool
- analysis :
$F(\omega)=X(e^{j\omega})=\sum_{n=-\infty}^\infty x[n]e^{-j\omega n}=<e^{j\omega n},x[n]>$ , represented over$[-\pi,\pi]$ with$x[n]\in l_2(\Z)$ - synthesis :
$x[n]=\frac{1}{2\pi}\int_{-\pi}^{\pi} F(\omega)e^{j\omega n}d\omega$ - periodicity :
$F(\omega)$ is$2\pi$ -periodic, can be rescales$M$ times$X(e^{j\omega M})$ 
- splitting into chunks :
$\sum_{n=-\infty}^{\infty}y[n]=\sum_{p=-\infty}^\infty\sum_{m=0}^{M-1}y[pM+m]$ - signal symmetric : DTFT symmetric
$x[n]=x[-n]\iff X(e^{j\omega})=X(e^{-j\omega})$ - signal real : DTFT hermitian symmetric $x[n]=x^[n]\iff X(e^{j\omega})=X^(e^{-j\omega})$ (symmetric magnitude)
- signal symmetric real : DTFT symmetric and real
- analysis :
-
review DFT : numerical algorithm (computable)
-
review DFS
-
review DTFT : mathematical tool (proofs)
-
pulse train :
$\tilde\delta(\omega)=2\pi\sum_{k=-\infty}^\infty\delta(\omega-2\pi k)$ (Dirac delta in space of$2\pi$ -periodic functions) -
embedding finite-length signals :
$N$ -tap signal, spectral DFT to infinite sequence- periodic extension :
$\tilde x[n]=x[n\mod N]$ $\tilde X(e^{j\omega})=\frac{1}{N}\sum_{k=0}^{N-1}X[k]\tilde\delta(\omega-\frac{2\pi}{N}k)$
- finite-support extension :
$\bar x[n]=x[n]$ for$0\le n\le N$ otherwise$0$ - interval indicator signal :
$\bar r[n]=1$ when$0\le n< N$ else 0 $\bar X(e^{j\omega})=\sum_{k=0}^{N-1}X[k]\Lambda(\omega-\frac{2\pi}{N}k)$ -
$\Lambda(\omega)=(1/N)\bar R(e^{j\omega})$ : smooth interpolation of DFT values -
$\bar R(e^{j\omega})=\frac{\sin(\frac{\omega}{2}N)}{\sin(\frac{\omega}{2})}e^{-j\frac{\omega}{2}(N-1)}$ : DTFT of interval signal
- interval indicator signal :
- periodic extension :
- zero-padding : pad data vector with 0's to obtain nicer plots, no information added
-
modulation :
$x[n]$ baseband,$DTFT{x[n]\cos(\omega_c n)}=\frac{1}{2}[X(e^{j(\omega-\omega_c)})+X(e^{j(\omega+\omega_c)})]$ , caution if too large
-
demodulation :
$DTFT{x[n]\cos(\omega_c n)2\cos(\omega_c n)}=X(e^{j\omega})+\frac{1}{2}[X(e^{j(\omega-2\omega_c)})+X(e^{j(\omega+2\omega_c)})]$ 
-
fast fourrier transform : FFT
- original complexity :
$O(N^2)$ for$X=W_nx$ - divide and conquer :
$O(N\log(N))$ 
- original complexity :
-
LTI
- linearity :
$\H{a_1x_1[n]+a_2x_2[n]}=a_1\H{x_1[n]}+a_2\H{x_2[n]}$ - time invariance :
$\H{x[n]}=y[n]\iff\H{x[n-n_0]}=y[n-n_0]$
- linearity :
-
impulse response :
$h[n]=\H{\delta[n]}$ -
convolution : $x[n]h[n]=\sum_{k=-\infty}^\infty x[k]h[n-k]=<x^[k],h[n-k]>$
- algorithm : time-reverse
$h[m]$ , center it in$n$ , compute inner product
- algorithm : time-reverse
-
moving average : MA,
$y[n]=\frac{1}{M}\sum_{k=0}^{M-1}x[n-k]$ - impulse reponse :
$h[n]=1/M$ for$0\le n < M$ - smoothing effect : proportional to
$M$ , # operations and storage
- impulse reponse :
-
leaky integrator : LI,
$y[n]=\lambda y[n-1]+(1-\lambda)x[n]$ with leak$\lambda <1$ - impulse response :
$h[n]=(1-\lambda)\lambda^n u[n]$ - smoothing effect : depends on
$\lambda$ , constant operations and storage
- impulse response :
-
stability
- finite impulse response (FIR) : finite support, finite # of samples involved in the computation of each output, always stable
- infinite impulse response (IIR) : infinite support, infinite # of samples involed in the computation of each output (finite computation though)
- causal : impulse response zero for
$n<0$ , only past samples - noncausal : impulse response nonzero for
$n<0$ , need future samples - bounded-input bounded-output (BIBO) : require impulse response absolutely summable
- nice signal : bounded signal
-
frequency reponse : DTFT of impulse response determines the frequency characteristic of a filter
- eigensequences : complex exponentials, cannot change frequency of sinusoids
- convolution theorem : multiplication in frequency space
- amplitude : amplification when
$\abs{H(e^{j\omega})}>1$ or attentuation when$\abs{H(e^{j\omega})}<1$ - phase : overall delay, shape change
- zero phase :
$\angle H(e^{j\omega}=0$ - linear phase :
$\angle H(e^{j\omega})=d\omega$ (almost linear phase on region of interest can do also the trick) - nonlinear phase : for example
$1/2\sin(\omega_0 n)+\cos(2\omega_0n+2\theta_0)$
- zero phase :
-
filter types (magnitude response)
- lowpass : basebands, MA, LI
- highpass
- bandpass
- allpass
-
filter types (phase response)
- linear phase
- nonlinear phase
-
ideal lowpass filter :
$H(e^{j\omega})=1$ for$|\omega|\le\omega_c$ otherwise$0$ ($2\pi$ -periodic implicit)- zero-phase : no delay
- impulse response :
$h[n]=\frac{\sin(\omega_c n)}{\pi n}$ - cannot compute in finite time : infinite support, two-sided
- approximation : decay slowly in time
- sinc-rect pair :
$rect(x)=1$ for$|x|\le 1/2$ and$sinc(x)=\frac{\sin(\pi x)}{\pi x}$ for$x\not=0$ ,$1$ if$x=0$ ($0$ if$x$ nonzero integer, not summable)
-
ideal highpass filter :
$H(e^{j\omega})=1$ for$\pi\ge|w|\ge\omega_c$ ($2\pi$ -periodic implicit)- impulse response :
$H_{hp}(e^{j\omega})=1-H_{lp}(e^{j\omega})$ give$h_{hp}[n]=\delta[n]-\frac{\omega_c}{\pi}sinc(\frac{\omega_c}{\pi}n)$ 
- impulse response :
-
ideal bandpass filter :
$H(e^{j\omega})=1$ for$|\omega\pm\omega_0|\le\omega_c$ ($2\pi$ -periodic implicit)- impulse response :
$h_{bp}[n]=2\cos(\omega_0 n)\frac{\omega_c}{\pi}sinc(\frac{\omega_c}{\pi}n)$ 
- impulse response :
-
impulse truncation
- FIR appromixation of length
$M=2N+1$ :$\hat h[n]=h[n]$ for$|n|\le N$ - MSE minimized by symmetric impulse truncation around zero :
$MSE=\sumi |h[n]-\hat h[n]|^2$ - gibbs phenomenon : maximum error around 9% regardless of
$N$ - A, B integrals :
$(A+B)/2\pi\approx 1.09$ with$A\approx\pi$ and$B\approx2\pi 0.589$ (independant of$M$ )
- A, B integrals :
- FIR appromixation of length
-
window method : narrow mainlobe (transition sharp), small sidelobe (small error), short window (FIR efficient)
- MSE minimized, simple
- cannot control max error
-
frequency sampling : take
$M$ of desired frequency response$S[k]=H(e^{j\omega_k})$ where$\omega_k=(2\pi/M)k$ , compute inverse DFT of$S[k]$ , use$s[n]$ to build$\hat h[n]$ (finite support)- simple, works with arbitrary frequency response
- cannot control max error
- sampling in the frequency : periodization in time domain
$s[n]=\sum_{m=-\infty}^\infty h[n+mM]$ 
-
z-transform : power series, convergence always absolute
- analysis :
$X(z)=\sum_{n=-\infty}^\infty x[n]z^{-n}$ - synthesis :
- region of convergence : ROC, circular symmetry
- finit support signals : converge everywhere
- causal signals : extends outwards from circle touching largest magnitude pole, converge if ROC include unit circle
- independent of values of
$H(z)$ : assume$Y(z)$ exists for$x[n]=\delta[n]$ -
$z_n$ : zeros of transfert function, glue sheet to ground -
$p_n$ : poles of transfert function, push sheet up
- constant coefficient difference equation :
$\sum_{k=0}^{N-1}a_ky[n-k]=\sum_{k=0}^{M-1}b_kx[n-k]$ give$Y(z)\sum_{k=0}^{N-1}a_k=X(z)\sum_{k=0}^{M-1}b_k x[n-k]$ with$Y(z)=H(z)X(z)$
- analysis :
-
abstract filter implementation
-
resonator : narrow bandpass filter, detect presence of sinusoid of given frequency, shift passband of LI
$H(z)=\frac{G_0}{1-2\lambda\cos(\omega_0 z^{-1})+|\lambda|^2z^{-2}}$ -
$a_1=2\lambda\cos\omega_0$ and$a_2=-|\lambda|^2$ 
-
DC removal : DC balanced signal has zero sum, kill zero frequency
-
hum removal : remove a specific nonzero frequency
$H(z)=\frac{(1-e^{j\omega_0}z^{-1})(1-e^{-j\omega_0}z^{-1})}{(1-\lambda e^{j\omega_0}z^{-1})(1-\lambda e^{-j\omega_0}z^{-1})}$ - fractional delay : compute in-between values for sample, ideal, approximated with local interpolation
-
Hilbert filter : allpass,
$H(e^{j\omega_0})=-j$ for$0\le\omega <\pi$ or$j$ for$-\pi\le \omega <0$ ,$h[n]=\frac{2}{\pi n}$ for$n$ odd otherwise$0$ - Hilbert demodulation :
$(jy[n]*h[n]+y[n])e^{j\omega_0 n}=x[n]$ for$y[n]=x[n]\cos(\omega_0n)$ 
- Hilbert demodulation :
-
requirements
- frequency response : passband, stopband
- phase : overall delay, linearity
- limit on computational resources or precision
- determine
$N$ ,$M$ ,$a_k$ ,$b_k$ :$H(z)=\frac{b_0+b_1z^{-1}+\cdots+b_{M-1}z^{-(M-1)}}{a_0+a_1z^{-1}+\cdots+a_{N-1}z^{-(N-1)}}$ , hard nonlinear problem
-
limitations
- transitions cannot be infinitely sharp :
$H(z)=B(z)/A(z)$ is$\C^\infty$ - magnitude response cannot be constant over an interval :
$B(z)-cA(z)$ infinite number of roots, need to be$0$ for all$z$ - higher filter order : small transition band, small error, expensive, large delay
- equiriplle error
- transitions cannot be infinitely sharp :
-
IIR
- pros : computationally efficient, strong attenuation easy, good for audio
- cons : stability issues, difficult to design for arbitrary response, nonlinear phase
- method : conversion fo analog design, deeply studied field
- butterworth : lowpass
- magnitude response : maximally flat, monotonic over
$[0,\pi]$ - design parameters : order
$N$ ($N$ poles and zeros), cutoff frequency - design test criterion : width of transition band, passband error
- magnitude response : maximally flat, monotonic over
- chebyshev : lowpass
- magnitude response : equiriplle in passband, monotonic in stopband
- design parameters : order
$N$ ($N$ poles and zeros), passband max error, cutoff frequency - design test criterion : width of transition band, stopband error
- elliptic : lowpass
- magnitude response : equiriplle in passband and in stopband
- design parameters : order
$N$ ($N$ poles and zeros), passband max error, cutoff frequency, stopband min attenuation - design test criterion : width of transition band
- magnitude response in decibels : filter attenuation expressed
$A_{dB}=20\log_{10}(|H(e^{j\omega})|/G)$ with filter max passband$G$ 
-
FIR
- pros : always stable, optimal design techniques exist, can be designed with linear phase
- cons : computationally much more expensive, may sound harsh
- method : optimal minimax filter design, algorithm for linear phase, equiriplle error in passband and stopband (proceeds by minimizing the maximum error)
- half length :
$L$ - even FIR :
$M=2L$ taps - odd FIR :
$M=2L+1$ taps - delay :
$(M-1)/2$ - FIR only have zeros : if
$z_0$ zero, so is$z_0^*$ and$1/z_0$ 
- type I :
$h[L+n]=h[L-n]$ ,$h_d[n]=h[n+L]$ ,$h_d[n]=h_d[-n]$ - $H(z)=z^{-L}(h_d[0]+\sum_{n=1}^Lh_dn)$
- zero locations :
$H(z^{-1})=z^{2L}H(z)$
- type II :
$h[n]=h[2L-1-n]$ - $H(z)=z^{-C}\sum_{n=0}^{L-1}hn$ with
$C=L-1/2$ - zero locations :
$H(z^{-1})=z^{2C}H(z)=z^{2L-1}H(z)$ - always have zero : at
$\omega=\pi$
- $H(z)=z^{-C}\sum_{n=0}^{L-1}hn$ with
- type III
- $H(z)=z^{-L}\sum_n h_dn$
- always have zero : at
$\omega=0,\pi$
- type IV
-
Parks-McClellan algorithm : optimal, polynomial fitting
$H_d(e^{j\omega})=h_d[0]+2\sum_{n=1}^Lh_d[n]\cos\omega n$ - magnitude response : equiriplle in passband and stopband
- design parameters : order
$N$ (number of taps), passband edge$\omega_p$ , stopband edge$\omega_s$ , ratio of passband to stopband error$\delta_p/\delta_s$ - design test criterion : width of transition band, stopband error
- Chebyshev polynomials :
$T_n(\cos\omega)=\cos n\omega$ $T_0(x)=1$ $T_1(x)=x$ $T_2(x)=2x^2-1$ $\ldots$ $T_n(x)=2xT_{n-1}(x)-T_{n-2}(x)$
- convert the space to
$x=\cos\omega$ $l_p=[0,\omega_p]\to l_p'=[\cos\omega_p,1]$ -
$l_s=[\omega_s,\pi]\to l_s'0[-1,\cos\omega_s]$ 
- minimize maximum error :
$E=\min_{P(x)}\max_{x\in l_p'\cup l_s'}{|P(x)-D(x)|}$ $P(x)=h_d[0]+\sum_{n=1}^L2h_d[n]T_n(x)$ -
$D(x)=1$ when$x\in l_p'$ else 0
- alternation theorem : min max works only if
$P(x)-D(x)$ alternates$M+2$ times in$l_p'\cup l_s'$ between$\pm E$ - works also with weighting function :
$W(x)=1$ when$x\in l_p'$ or$\delta_p/\delta_s$ else ($x\in l_s'$ ) - weighted min max :
$\min\max_{x\in l_p'\cup l_s'}\abs{W(x)[P(x)-D(x)]}$ - max number of alternations :
$L+3$ - polynomial of degree
$L$ :$L-1$ local extrema -
$\omega_p$ and$\omega_s$ - sometimes :
$\omega=0$ or$\omega=\pi$
- polynomial of degree
- in-band alternations :
$L-1$
- works also with weighting function :
- Remez algorithm : guess positions of alternations, if not satisfied find extrema or error and repeat
- algorithm :
$M$ filter coefficients, stopband and passband tolerances$\delta_s$ and$\delta_p$ , if error too big, increase$M$ and retry
- eliptic vs 51-tap minimax
- design bandpass and highpass by modulating lowpass
-
system clock : at most
$T_s$ - record value :
$x_i[n]$ - process value in causal filter
- output value :
$x_o[n]$
- record value :
- buffering : interrupt for each samples would be too much overhead
-
input
-
output
-
double buffering
- delay :
$d=T_s \frac{L}{2}$ seconds - underflow : CPU does not fill fast enough
- delay :
-
multiple buffering (> 2) for protection
- delay :
$d=T_s L$ seconds - underflow : more protection
- delay :
-
echo
-
reverb : superposition of many echos with different delays and magnitudes, costly, cheap alternative is allpass
$H(z)=\frac{-\alpha + z^{-N}}{1-\alpha z^{-N}}$ 
-
non-LTI effects
- distortion : clip signal
$y[n]=trunc(ax[n])/a$ - tremolo : sinusoidal amplitude modulation
$y[n]=(1+\cos(\omega_0 n)/G)x[n]$ - flanger : sinusoidal delay
$y[n]=x[n]+x[n-\lfloor d(1+\cos(\omega_0n))\rfloor]$ - wah : time-varying bandpass filter
- distortion : clip signal
-
gaussian random variable :
$f(x)=N(m,\sigma^2)=\frac{1}{\sqrt{2\pi\sigma^2}}\exp{-\frac{(x-m)^2}{2\sigma^2}}$ - mean :
$m$ - variance :
$\sigma^2$
- mean :
-
uniform random variable :
$f(x)=U(A,B)=\frac{1}{B-A}$ - mean :
$m=\frac{A+B}{2}$ - variance :
$\sigma^2=\frac{(B-A)^2}{12}$
- mean :
-
discrete uniform random variable :
$f(x)=U{A,B}=\frac{1}{B-A+1}\sum_{k=A}^B\delta(x-k)$ - mean :
$m=\frac{A+B}{2}$ - variance :
$\sigma^2=\frac{(B-A+1)^2-1}{12}$
- mean :
-
autocorrelation :
$R_{XY}=E[XY]$ -
covariance :
$C_{XY}=E[(X-m_X)(Y-m_Y)]$ - uncorrelated elements :
$E[XY]=E[X]E[Y]\Rightarrow C_{XY}=0$ - independent elements :
$f_{XY}(x,y)=f_X(x)f_Y(y)\Rightarrow C_{XY}=0$
- uncorrelated elements :
-
random vector
- cdf :
$F_X(\alpha)=P[X_n\le \alpha_n, n=0,\ldots,N-1]$ with$\alpha\in\R^N$ - pdf :
$f_X(\alpha)=\frac{\partial^N}{\partial\alpha_0\cdots\partial\alpha_{N-1}}F_X(\alpha_0,\ldots,\alpha_{N-1})$ - mean :
$E[X]=m_x=[E[X_0]\ldots E[X_{N-1}]]^T\in\R^N$ - cross-correlation :
$R_{XY}=E[XY^T]\in\R^{N\times N}$ - covariance matrix :
$C_{XY}=E[(X-m_X)(Y-m_Y)^T]\in\R^{N\times N}$ , symmetric, postive-definite, diagonal if uncorrelated or independent
- cdf :
-
gaussian random vector :
$f(x)=\frac{1}{\sqrt{(2\pi)^n\abs{\Lambda}}}\exp{-\frac{1}{2}(x-m)^T\Lambda^{-1}(x-m)}$ - mean :
$m\in\R^N$ - covariance matrix :
$\Lambda\in\R^{N\times N}$ - uncorrelated elements : independent elements
- mean :
-
random process
- full characterization : all possible sets of
$k$ indices for all$k\in\N$ , too much - first-order :
$f_{X[n]}(x[n])]\to$ time-varying mean$\bar x[n]=E[x[n]]$ - second-order : first order +
$f_{X[n]X[m]}(x[n],x[m])\to$ time-varying cross-correlation$\sigma_x[n,m]=E[x[n]x[m]]$ - ... : time-varying further moment
- full characterization : all possible sets of
-
stationarity : time-invariant partial-order descriptions
$f_{X[n_0]\cdots X[n_{k-1}]}(\cdots)=f_{X[n_0+M]\cdots X[n_{k-1+M}]}(\cdots)$ - mean : time-invariant
- correlation : depends only on time lag
- higher-order moments : depend only on relative time differences
-
wide-sense stationarity (WSS) : stationarity up to second-order descriptions
- mean :
$E[X[n]]=m$ - correlation :
$E[X[n]X[m]]=r[n-m]$
- mean :
-
independent, identically distributed process (IID) :
$f_{X[n_0]\cdots X_[n_{k-1}]}(x)=\Pi_{n=0}^k f(x_n)$ - mean :
$E[X[n]]=m$ - correlation :
$E[X[n]X[m]]=\sigma^2\delta[n-m]$
- mean :
-
power spectral density (PSD) : independent of pdf
- intuition :
$P[k]=E[\abs{X_N[k]}^2/N]$ - energy distributions in frequency :
$\abs{X_N[k]}^2$ - power distributions in frequency :
$\abs{X_N[k]}^2/N$ , aka density - frequency-domain representations for stochastic processes is power
-
$P[k]=1$ : power is equally distributed over all frequencies, cannot predict how fast signal moves
- energy distributions in frequency :
- truncated DTFT :
$X_N(e^{j\omega})=\sum_{n=-N}^Nx[n]e^{-j\omega n}$ - for signal :
$P(e^{j\omega})=\lim_{N\to\infty}\frac{1}{2N+1}\abs{X_N(e^{j\omega})}^2$ - for WSS random process :
$P_X(e^{j\omega})=\lim_{N\to\infty}\frac{1}{2N+1}E[\abs{X_N(e^{j\omega})}^2]=\lim_{N\to\infty}\sum_{k=-2N}^{2N}\frac{2N+1-\abs{k}}{2N+1}r_X[k]e^{-j\omega k}$ $P_X(e^{j\omega})=\lim_{N\to\infty}\sum_{k=-\infty}^{\infty}w_N[k]r_X[k]e^{-j\omega k}=DTFT{r_X[k]}$ -
$\lim_{N\to\infty} w_N[k]=1$ 
- intuition :
-
white noise : IDD
- zero mean : autocorrelation = covariance
$P_X(e^{j\omega})=\sigma^2$
-
additive white gaussian noise (AWGN) : IID, zero mean gaussian process, WSS
$\Rightarrow$ full stationary -
filter random process : output is WSS if input WSS
- mean :
$m_Y=m_X H(e^{j0})$ - correlation :
$r_Y[n]=h[n]*h[-n]*r_X[n]$ - power distribution :
$P_Y(e^{j\omega})=\abs{H(e^{j\omega})}^2 P_X(e^{j\omega})$ - deterministict signal filter : works in magnitude in stochastic case but concept of phase lost
- mean :
-
bridging two world : sampling and interpolation
-
continuous-time signal processing :
$x(t)\in L_2(\R)$ complex function of real variable with finite energy - analog LTI filters : $y(t)=(xh)(t)=<h^(t-\tau),x(\tau)>$
-
fourier
- frequence :
$F=\frac{\Omega}{2\pi}$ Hz with$\Omega$ rad/s and period$T=\frac{1}{F}$ - analysis :
$X(j\Omega)=<e^{j\Omega t},x(t)>=\int_{-\infty}^\infty x(t)e^{-j\Omega t}dt$ not periodic - synthesis :
$x(t)=\frac{1}{2\pi}\int_{-\infty}^\infty X(j\Omega)e^{j\Omega t}d\Omega$ 
- frequence :
-
convolution theorem :
$Y(j\Omega)=X(j\Omega)H(j\Omega)$ -
bandlimitedness :
$X(j\Omega)=0$ for$\abs{\Omega}>\Omega_N$ - total bandwidth :
$\Omega_B=2\Omega_N$ - prototypical function :
$T_s=\frac{2\pi}{\Omega_B}=\frac{\pi}{\Omega_N}$ $\varphi(t)=\sinc(\frac{t}{T_s})$ -
$\Phi(j\Omega)=\frac{\pi}{\Omega_N} rect(\frac{\Omega}{2\Omega_N})$ 
- total bandwidth :
-
interpolation : fill the gaps between samples
- requirement : decide interval
$T_s$ , make sure$x(nT_s)=x[n]$ , make sure$x(t)$ is smooth (infinitely differentiable)
- requirement : decide interval
-
polynomial interpolation :
$N$ points, polynomial of degree$N-1$ ,$p(t)=a_0+a_1t+\cdots+a_{N-1}t^{N-1}$ -
$N$ -degree polynomial bases in interval- naive :
$1,t,\ldots,t^N$ - Legendre basis : orthonormal, increasing degree
- Chebyshev basis : orthonormal, increasing degree
- Lagrange : interpolation property, same degree
- naive :
- consider symmetric interval :
$l_N=[-N,\ldots,N]$ - naive :
$p(0)=x[0]$ ,$p(T_s)=x[1]$ ,$p((N-1)T_s)=x[N-1]$ - space of degree-$2N$ polynomial over
$l_N$ :$P_N$ -
$P_N$ basis :$2N+1$ Lagrange polynomials$L_n^{(N)}(t)=\Pi_{k=-N,k\not=n}^N\frac{t-k}{n-k}$ for$n=-N,\ldots,N$ 
- Lagrange interpolation :
$p(t)=\sum_{n=-N}^N x[n]L_n^{(N)}(t)$ - polynomial of degree
$2N$ through$2N+1$ points unique - satifies :
$p(n)=x[n]$ for$-N\le n\le N$ since$L_n^{(N)}(m)=1$ only if$n=m$ else$0$ 
- polynomial of degree
- pros : maximally smooth
- cons : interpolation bricks depend on
$N$
-
-
zero-order interpolation :
$-N\le t\le N$ ,$x(t)=\sum_{n=-N}^N x[n]rect(t-n)$ $x(t)=x[\lfloor t + 0.5\rfloor]$ - kernel :
$i_0(t)=rect(t)$ (support$1$ )
- not continuous
-
first-order interpolation :
$x(t)=\sum_{n=-N}^N x[n]i_1(t-n)$ - kernel :
$i_1(t)=1-\abs{t}$ for$\abs{t}\le 1$ else 0 (support$2$ ) - continuous but derivative is not
- kernel :
-
third-order interpolation :
$x(t)=\sum_{n=-N}^N x[n]i_3(t-n)$ - kernel : splicing two cubic polynomials (support
$4$ ) - continous up to second derivative
- kernel : splicing two cubic polynomials (support
-
local interpolation :
$x(t)=\sum_{n=-N}^N x[n]i_c(t-n)$ - requirements :
$i_c(0)=1$ and$i_c(t)=0$ for$t$ nonzero integer
- pros : same interpolating function independently of
$N$ - cons : lack of smoothness
- limit : local = global interpolation,
$\lim_{N\to\infty}L_n^{(N)}(t)=f(t-n)$
- requirements :
-
sinc interpolation :
$x(t)=\sum_{n=-\infty}^\infty x[n]\sinc(\frac{t-nT_s}{T_s})$ 
- convergence :
$\sinc(t-n)$ and$L_n^{(\infty)}(t)$ share an infinite number of zeros
- spectral representation :
$X(j\Omega)=(\pi/\Omega_N)X(e^{j\pi (\Omega/\Omega_N)})$ for$\abs{\Omega}\le\Omega_N$ else$0$ 
- fast interpolation :
$T_s$ small, wider spectrum - slow interpolation :
$T_s$ large, narrower spectrum
- convergence :
-
space of bandlimited functions :
$\Omega_N$ -BL$\subset L_1(\R)$, hilbert space
-
sampling theorem
- special case :
$T_s=1$ and$\Omega_N=\pi$ - basis :
$\varphi^{(n)}(t)=\sinc(t-n)$ with$n\in\Z$ - sampling as basis expansion :
$<\varphi^{(n)}(t),x(t)>=<\sinc(t-n),x(t)>=<sinc(n-t),x(t)>=(\sinc*x)(n)\= \frac{1}{2\pi}\int_{-\infty}^\infty rect(\frac{\Omega}{2\pi})X(j\Omega)e^{j\Omega n}d\Omega=\frac{1}{2\pi}\int_{-\pi}^\pi X(j\Omega)e^{j\Omega n}d\Omega=x(n)$ - analysis :
$x[n]=<\sinc(t-n),x(t)>$ - synthesis :
$x(t)=\sum_{n=-\infty}^\infty x[n]\sinc(t-n)$ - sufficient representation :
$x[n]=x(n)$ with$n\in\N$
- basis :
- general case :
$T_s=\pi/\Omega_N$ - basis :
$\varphi^{(n)}(t)=\sinc((t-nT_s)/T_s)$ - analysis :
$x[n]=<\sinc(\frac{t-nT_s}{T_s}), x(t)>=T_s x(nT_s)$ - synthesis :
$x(t)=\frac{1}{T_s}\sum_{n=-\infty}^\infty x[n]\sinc(\frac{t-nT_s}{T_s})$ - coefficient :
$T_s x(nT_s)$ for any $x(t)\in\Omega_N-$BL - sufficient representation :
$x[n]=x(nT_s)$ for any$x(t)\in\Omega_N$ -BL
- basis :
- corollary :
$\Omega_N$ -BL$\subset\Omega$-BL for any$\Omega\ge\Omega_N$ - sufficient representation :
$x[n]=x(nT_s)$ for any$x(t)\in\Omega_N$ -BL and any$T_s\le\pi/\Omega_N$
- sufficient representation :
- hertz : any signal
$x(t)$ bandlimited to $F_N$Hz can be sampled with no loss of information using sampling frequency$F_s\ge 2 F_N$ (i.e. sampling period$T_s\le 1/2 F_N$ )
- special case :
-
sinc sampling
-
sinc sampling for
$\Omega_N$ -BL signals
-
raw sampling
-
raw sampling continuous-time complex expoential :
$x(t)=e^{j\Omega_0t}$ - all angular speed allowed
- periodic :
$T=2\pi/\Omega_0$ $FT{e^{e^{j\Omega_0t}}}=2\pi\delta(\Omega-\Omega_0)$ - bandlimited : to
$\Omega_0^+$ - raw sample : snapshots at regular intervals of rotating point
$x[n]=e^j\Omega_0T_s n$ - digital frequency :
$\omega_0=\Omega_0T_s$ - easy :
$T_s<\pi/\Omega_0\Rightarrow \omega_0<\pi$ 
- tricky :
$\pi/\Omega_0<T_s<2\pi/\Omega_0\Rightarrow \pi<\omega_0<2\pi$ 
- trouble :
$T_s>2\pi/\Omega_0\Rightarrow \omega_0>2\pi$ 
- digital frequency :
- aliasing
-
raw sampling arbitrary signal
- spectrum :
$x[n]=x_c(nT_s)$ , start with inverse Fourier Transform
- split intergration interval (aliased) :
$x[n]=\frac{1}{2\pi}\sum_{k=-\infty}^\infty\int_{(2k-1)\Omega_N}^{(2k+1)\Omega_N}X_c(j\Omega)e^{j\Omega nT_s}d\Omega$ - periodzation :
$\tilde X_c(j\Omega)=\sum_{k=-\infty}^\infty X_c(j(\Omega-2k\Omega_N))$ give$x[n]=\frac{1}{2\pi}\int_{-\Omega_N}^{\Omega_N} \tilde X_C(j\Omega)e^{j\Omega T_s n}d\Omega$ - set
$\omega=\Omega T_s$ :$x[n]=IDTFT{\frac{1}{T_s}\tilde X_C(j\frac{\omega}{T_s})}$ - final :
$X(e^{j\omega})=\frac{\pi}{\Omega_N}\sum_{k=-\infty}^\infty X_C(j\frac{\omega\Omega_N}{\pi}-2jk\Omega_N)$ - bandlimited to
$\Omega_0$ :$\Omega_N>\Omega_0$ 
- bandlimited to
$\Omega_0$ :$\Omega_N=\Omega_0$ 
- bandlimited to
$\Omega_0$ :$\Omega_N<\Omega_0$ 
- non-bandlimited
- split intergration interval (aliased) :
- spectrum :
-
sampling stategies : given a sampling period
$T_s$ - bandlimited to
$\pi/T_s$ or less : raw sampling is fine (equivalent to sinc sampling up to scaling factor$T_s$ ) - non-bandlimited
- bandlimit via a lowpass filter in continuous-time domain before sampling
- raw sample and incur aliasing - bandlimiting : optimal with respect to least squares approximation
- bandlimit via a lowpass filter in continuous-time domain before sampling
- aliasing : error cannot be controlled, better bandlimit
- bandlimited to
-
sinc sampling and interpolation
-
least squares approximation with sinc sampling and interpolation
-
processing of analog signals
- impulse invariance :
$H_C(j\Omega)=H(e^{j\pi\Omega/\Omega_N})$ 
- duality :
$H(e^{j\omega})=H_C(j\omega)$ 
- fractional delay :
$H(e^{j\omega})=e^{-j\omega d}$ with$d\not\in\Z$ - discrete time : ideal filter (approximation with cubic local interpolation)
- discrete time : ideal filter (approximation with cubic local interpolation)
- digital differentiator :
$H(e^{j\omega})=j\omega$ ,$FT{x_c'(t)}=j\Omega X_C(j\Omega)$ - discrete time :
$h[n]=\frac{(-1)^n}{n}$ for$n\not=0$ else$0$ , ideal filter (approximations exist)
- discrete time :
- impulse invariance :
-
advanced sampling
- from continous to discrete
- discrete to continuous
- practial interpolation :
- time :
$x(t)=\sum_{n=-\infty}^\infty x[n]i(\frac{t-nT_s}{T_s})$ - frequency :
$X(j\Omega)=T_s\sum_{n=-\infty}^\infty x[n]I(jT_s\Omega)e^{jnT_s\Omega}=\frac{\pi}{\Omega_N}I(j\pi\frac{\Omega}{\Omega_N})X(e^{j\pi\frac{\Omega}{\Omega_N}})$
- time :
- sinc interpolation :
$i(t)=\sinc(t)$ and$I(j\Omega)=rect(\frac{\Omega}{2\pi})$ - zero-order hold :
$i(t)=rect(t)$ and$I(j\Omega)=sinc(\frac{\Omega}{2\pi})$ ($X(j\Omega)=\frac{\pi}{\Omega_N}\sinc(\frac{\Omega}{2\Omega_N})X(e^{j\pi\Omega/\Omega_N})$)
- first-order
- from continous to discrete
-
bandpass sampling : sampling theorem is only sufficient condition, in theory
$\Omega_N>\Omega_{max}$ what if signal is bandpass- bandpass :
$X(j\Omega)=0$ for$\abs{\Omega-\Omega_c}>\Omega_0$ - no aliasing : requires at least
$\Omega_N\ge\Omega_0$ - baseband condition :
$\Omega_N=\Omega_c/k$ for some$k\in\N$ - samples : for
$T_s=\pi/\Omega_N$ ,$x[n]=x(nT_s)$ is alias-free, baseband DT version of$x(t)$ 
- AM channel
- bandpass :
-
upsampling : zoom,
$X_{NU}[n]=x[k]$ for$n=kN$ else$0$ with$k\in\Z$ - zero-fill
- spectral representation :
$X_{NU}(e^{j\omega})=X(e^{j\omega N})$ - time domain : zeros between nonzero samples not natural
- frequency domain : extra replicas of spectrum not natural
- zero-order interpolator : for
$N$ -upsampling,$i_0[n]=u[n]-u[n-N]$ and$\abs{I_0(e^{j\omega})}=\abs{\frac{\sin(\frac{\omega}{2}N)}{\sin(\frac{\omega}{2})}}$ 
- first-order interplator :
$i_1[n]=(i_0[n]*i_0[n])/N$ 
- ideal digital interpolator
- zero-fill
-
downsampling : dezoom,
$X_{ND}[n]=x[nN]$ 
- spectral representation :
$X_{ND}(e^{j\omega})=\frac{1}{N}\sum_{m=0}^{N-1}X(e^{j\frac{w-2\pi m}{N}})$ - without aliasing
- with aliasing
- with aliasing filter
- caution with highpass signal
- rational sampling rate change : in pratice, time-varying local interpolation
- subsample interpolation : compute
$x(n+\tau)$ with$\abs{\tau}<1/2$ - local Lagrange approximation :
$x(n+\tau)\approx x_L(n;\tau)=\sum_{k=-N}^N x[n-k]L_k^{(N)}(\tau)=(x*d_\tau)[n]$ with$2N+1$ -tap FIR$d_\tau[k]=L_k^{(N)}(\tau)$ 
- local Lagrange approximation :
- spectral representation :
-
quantitzation : map range of signal onto finite set
- factors : storage budget (bits per sample), storage scheme (fixed, floating), input properties (range, distribution)
- irreversiable : quantization noise
- simplest quantizer : each sample encoded individually (scalar), quantized independently (memoryless), encoded using
$R$ bits
- scalar :
$A\le x[n]\le B$ ,$2^R$ intervals
- error :
$e[n]=Q{x[n]}-x[n]=\tilde x[n]-x[n]$ , model error as white noise - uniform : interval
$\Delta=(B-A)2^{-R}$ - hypothesis :
$f_x(\tau)=\frac{1}{B-A}$ - MSE :
$\sigma^2_e=\sum_{k=0}^{2^R-1}\int_{l_k}f_x(\tau)(\tilde x_k-\tau)^2d\tau$ - minimizing error :
$\frac{\partial \sigma_e^2}{\partial \tilde x_m}=0$ for$\tilde x_m=A+m\Delta+\frac{\Delta}{2}$ , interval midpoint - error energy :
$\sigma_e^2=\frac{\Delta^2}{12}$ - signal energy :
$\sigma_x^2=(B-A)^2/12$ - signal to noise ratio :
$SNR=\sigma_x^2/\sigma_e^2=2^{2R}$ ($SNR_{dB}=10\log_{10}2^{2R}\approx 6R$ db)
- hypothesis :
- unbounded : clip samples to
$[A,B]$ (linear distortion) vs smoothly saturate input (simulate saturation curves of analog electronics)
- gaussian :
$\sigma_e^2=\frac{\sqrt{3}\pi}{2}\sigma^2\Delta^2$ - Lloyd-Max algo : design optimal quantizer for distribution
- companders
-
A/D converter : sampling discretizes time, quantization discretises amplitude
- oversampling : reduce quantization error
- oversampling : reduce quantization error
-
D/A converter
- oversampling : cheaper hardware for interpolation, undo in-band distortion in analog domain, significant out-of-band distortion, minimal D/A rate
- oversampling using ZOH
- oversampling : cheaper hardware for interpolation, undo in-band distortion in analog domain, significant out-of-band distortion, minimal D/A rate
-
digital image : two-dimensional
$M_1\times M_2$ finite-support signal$x[n_1,n_2]$ , pixel grid- grayscale : scalar pixel value
- color : multidimensional pixel value
- still works : linearity, convolution, fourier, interpolation, sampling
- breaks : fourier analysis less relevant, filter design hard, IIRs rare, linear operators only mildly useful
- news : affine transforms, finite-support signals, causality loses meaning
-
rect :
$rect(\frac{n_1}{2N_1},\frac{n2}{2N_2})=1$ only if$\abs{n_1}<N_1$ and$\abs{n_2}<N_2$ else$0$ -
separable signals
- dirac :
$\delta[n_1,n_2]=\delta[n_1]\delta[n_2]$ - rect :
$rect(\frac{n_1}{2N_1},\frac{n2}{2N_2})=rect(\frac{n_1}{2N_1})rect(\frac{n_2}{2N_2})$
- dirac :
-
nonseparable signal :
$x[n_1,n_2]=1$ if$\abs{n_1}+\abs{n_2}<N$ else$0$ -
2D convolution :
$x[n_1,n_2]*h[n_1,n_2]=\sum_{k_1=-\infty}^\infty\sum_{k_2=-\infty}^\infty x[k_1,k_2]h[n_1-k_1,n_2-k_2]$ - operations :
$M_1*M_2$ per output sample
- operations :
-
2D convolution for separable signals : $x[n_1,n_2]h[n_1,n_2]=\sum_{k_1=-\infty}^\infty h_1[n_1-k_1]\sum_{k_2=-\infty}^\infty x[k_1,k_2]h_2[n_2-k_2]=h_1[n_1](h_2[n_2]*x[n_1,n_2])$
- operations :
$M_1+M_2$ per output sample
- operations :
-
affine transforms : mapping
$\R^2\to\R^2$ that reshapes coordinate system$t'=At-d\in\R^2\not=\Z^2$ - translation :
$A=I$ , $d=\begin{bmatrix}d_1 \\ d_2\end{bmatrix}$ - scaling : $A=\begin{bmatrix}a_1 & 0 \\ 0 & a_2\end{bmatrix}$,
$d=0$ - rotation : $A=\begin{bmatrix}\cos\theta & -\sin\theta \\ \sin\theta & \cos\theta\end{bmatrix}$,
$d=0$ - horizontal flips : $A=\begin{bmatrix}-1 & 0 \\ 0 & 1\end{bmatrix}$,
$d=0$ - vertical flips : $A=\begin{bmatrix}1 & 0 \\ 0 & -1\end{bmatrix}$,
$d=0$ - horizontal shear : $A=\begin{bmatrix}1 & s \\ 0 & 1\end{bmatrix}$,
$d=0$ - vertical shear : $A=\begin{bmatrix}1 & 0 \\ s & 1\end{bmatrix}$,
$d=0$ - discrete-space solution
- inverse transform :
$t=A^{-1}(m+d)$ - interpolate mid-points :
$(t_1,t_2)=(\eta_1+\tau_1,\eta_2+\tau_2)$ with$\eta_{1,2}\in\Z$ and$0\le\tau_{1,2}<1$
- inverse transform :
- translation :
-
bilinear interpolation
- first-order interpolator :
$y[m_1,m_2]=(1-\tau_1)(1-\tau_2)x[\eta_1,\eta_2]+\tau_1(1-\tau_2)x[\eta_1+1,\eta_2]+(1-\tau_1)\tau_2x[\eta_1,\eta_2+1]+\tau_1\tau_2x[\eta_1+1,\eta_2+1]$ 
- first-order interpolator :
-
2D DFT
- analysis :
$X[k_1,k_2]=\sum_{n_1=0}^{N_1-1}\sum_{n_2=0}^{N_2-1}x[n_1,n_2]e^{-j\frac{2\pi}{N_1}n_1k_1}e^{-j\frac{2\pi}{N_2}n_2k_2}$ - synthesis :
$x[n_1,n_2]=\frac{1}{N_1N_2}\sum_{k_1=0}^{N_1-1}\sum_{k_2=0}^{N_2-1}X[k_1,k_2]e^{-j\frac{2\pi}{N_1}n_1k_1}e^{-j\frac{2\pi}{N_2}n_2k_2}$ - orthogonal basis :
$N_1N_2$ vectors,$w_{k_1,k_2}[n_1,n_2]=e^{j\frac{2\pi}{N_1}n_1k_1}e^{j\frac{2\pi}{N_2}n_2k_2}$ - basis for
$k_1=3$ and$k_2=230$ 
- matrix form
- HDR images : need to compress the levels
- remove flagrant outliers
- nonlinear mapping :
$y=x^{1/3}$ after normalization$x\le 1$
- magnitude : does not carry much information
- phase : carry some info
- analysis :
-
image filtering
- lowpass : smoothing
- highpass : enhancement, edge detection
- 2D IIRs : nonlinear phase, border effects, stability (fundamental theorem of algebra does not hold in multiple dimensions)
- noncomputable CCDE
- 2D FIR : generally zero centered, odd number of taps in both directions, stable
- moving average
- gaussian blur :
$h[n_1,n_2]=\frac{1}{2\pi\sigma^2}e^{-\frac{n_1^2+n_2^2}{2\sigma^2}}$ - sobel
- Laplacian :
$\Delta f(t_1,t_2)=\frac{\partial^2 f}{\partial t_1^2}+\frac{\partial^2 f}{\partial t_2^2}$ 
- moving average
-
compression : exploit physical redundancy, allocate bits for things that matter
- lossy : some information discarded
- key : compressing at block level, using suitable transform (change of basis), smart quantization, entropy coding
-
level compressing
- pixel level : reduce number bits per pixel, coarser quantization, limit 1bpp
- block level : divide in blocks, code average value with 8 bits, less than 1bpp, exploit local spatial correlation, compress remote regions independently
-
transform coding
- discrete cosine transform :
$C[k_1,k_2]=\sum_{n_1=0}^{N-1}\sum_{n_2=0}^{N-1} x[n_1,n_2]\cos[\frac{\pi}{N}(n_1+1/2)k_1]\cos[\frac{\pi}{N}(n_2+1/2)k_2]$ 
-
smart quantization
- standard :
$\hat x=floor(x)+0.5$ - deadzone :
$\hat x=round(x)$ - variable step : fine to coarse
- standard :
-
JPEG standard
- split image into 8x8 non-overlapping blocks
- computed DCT of each block
- quantize DCT coefficients according to psycovisually-tuned tables
- zigzag scan to maximize ordering
- run-length encoding : each nonzero value encoded as
$[(r,s),c]$ , 8 bit per pair- runlength :
$r$ number of zeros before current value - size :
$s$ number of bits needed to encode value - actual value :
$c$ -
$(0,0)$ : indicates only zeros from now
- runlength :
- huffman coding
-
success factors
- DSP paradigm : integer easy to regenerate, good phase control, adaptive algo
- algo : entropy coding, error correction, trellis-coded modulation, viterbi
- hardware : miniatuziation, general-purpose platforms, power efficiency
-
analog channel : affect capacity
- bandwidth constraint : grow as
$1/T_s$ 
- power constraint : limit max amplitude
- AM radio channel : from $530$kHz to $1.7$MHz, each channel $8$kHz, power limited by law (daytime, nighttime, interference, health)
- bandwidth constraint : grow as
- channel capacity : maximum amount of information that can be reliably delivered over a channel (bit per second)
- all-digital paradigm : keep everything digital until we hit physical channel
-
transmitter design
- white random sequence :
$a[n]$ - shaping bandwidth : shrink support of full-band signal with upsampling (does not change data rate)
- Baud rate : available bandwidth
$W=F_{max}-F_{min}$ ,$F_s=KW>2F_{max}$ thus$\omega_{max}-\omega_{min}=2\pi\frac{W}{F_s}=\frac{2\pi}{K}$ 
- raised cosine :
$1/n^2$ decay
- white random sequence :
-
transmission reliability :
$â[n]=a[n]+\eta[n]$ - error : depends on power of noise vs of signal, decoding strategy, alphabet
- signaling alphabet
- mapper : split incoming bitstream into chunks, assign symbol
$a[n]$ from finite alphabet$A$ to each - slicer : receive value
$â[n]$ , decide which symbol is closest, piece back blocks
- mapper : split incoming bitstream into chunks, assign symbol
- two-level signaling :
- alphabet :
$\pm G$ - transmitted power :
$\sigma_s^2=G^2$ - error probability :
$Q(G/\sigma_0)=Q(\sigma_s/\sigma_0)=Q(\sqrt{SNR})$ 
- alphabet :
-
signaling scheme
- PAM : chunks of
$M$ bits (corresponding$k[n]\in{0,\ldots,2^M-1}$ ),$a[n]=G((-2^M+1)+2k[n])$ ,$a'[n]=\arg\min_{a\in A}[\abs{â[n]-a}]$ , zero-mean, distance$2G$ - QAM : chunks of
$M$ even bits,$M/2$ for PAM$a_r[n]$ and$a_i[n]$ ,$a[n]=G(a_r[n]+ja_i[n]$ ,$a'[n]=\arg\min_{a\in A}[\abs{â[n]-a}]$ - error probability : circular approximation
$P_{err}\approx\exp{-\frac{G^2}{\sigma_0^2}}\approx\exp{-3 SNR/2^{M+1}}$ - transmitted power :
$\sigma_s^2=G^2\frac{2}{3}(2^M-1)$ - recipe :
$M=\log_2(1-\frac{3}{2}\frac{SNR}{\ln(p_e)})$ - passband :
$c[n]=b[n]e^{j\omega_cn}$ ,$s[n]=\Re{c[n]}=b_r[n]\cos\omega_cn-b_i[n]\sin\omega_cn$ 
- error probability : circular approximation
- PAM : chunks of
-
receiver
- issues
- propagation delay : handshake, delay estimation
- linear distortion :
$D(j\Omega)$ , adapative equalization - interference : line probing
- clock drifts : timing recovery
- Hilbert demodulation
- throughput :
$WM$ bps
- issues
-
shannon capacity upperbound :
$C=W\log_2(1+SNR)$ -
delay compensation :
$D(j\Omega)=e^{-j\Omega d}$ ,$d=(L+\tau)T_s$ with$\abs{\tau}<1/2$ and$L\in\N$ - bulk delay :
$L$ 
- fractional delay :
$\tau$ - transmit :
$b[n]=e^{j\omega_0n}$ ,$s[n]=\cos((\omega_c+\omega_0)n)$ - receive :
$\hat s[n]=\cos((\omega_c+\omega_0)(n-L-\tau))$ - after demodulation :
$\hat b[n]=e^{j\omega_0(n-\tau)}$ (known frequency) - compensating :
$\hat s[n]=s((n-\tau)T_s)$ (after offsetting bulk delay), in theory compensate with sinc fractional delay ($h[n]=\sinc(n+\tau)$), in practive filter local Lagrange approx
- transmit :
- bulk delay :
-
adaptive equalization : in theory
$E(z)=1/D(z)$ but change over time- bootstrapping using training sequence
- bootstrapping using training sequence
-
ADSL channel :
$N$ sub-channel,$M$ -QAM- discrete multitone modulation : insteadd of lowpassing, use
$2N$ -tap interval indicator - complex output signal :
$c[n]=\sum_{k=0}^{N-1}a_k[\lfloor n/2N\rfloor]e^{j\frac{2\pi}{2N}nk}$ - specs : $F_{max}=1104$KHz,
$N=256$ ,$M=4$ , voice channel 0-7, upstream data: 7-31, max throughput 14.9Mbps (downstream)
- discrete multitone modulation : insteadd of lowpassing, use
