Cheatsheet

SIGNALS DIGITIZATION 6. Coding 3.Discrete Systems,Types,Properties • rxx [k] and ryy [k] are even fcts, while
rxy [k] = ryx [−k]
1.Sampling • [−Am , +Am ]: Range of amplitudes possible to
x[k] → G → y[k] = G{x[k]}
encode. (Am = 2N . q2 )
• Ideal Delay System:
• Sampling interval: Ts = f1s • Any amplitude that exceeds this value → the y[k] = x[k − kd ] , −∞ < k < ∞
• Periodic real sampling: signal is clipped → degradation.
FREQUENCY ANALYSIS
kd : the delay of the system
xs (t) = x(t).s(t) kd > 0 → a time delay (shifts input to right)
t
P∞ t−kT
= repTs {rect( D )= k=−∞ rect( D ) kd < 0 → a time advance (shifts input to left) 1.Fourier Series
• Periodic ideal sampling: • Memoryless(static) system: y[k] at every
xs (t) =Px(t).δT (t) DISCRETE SIGNALS value of k depends only on x[k] at the same
= x(t). ∞ k=−∞ δ(t − kT ) value of k • x[k] periodic if x[k] = x[k + N ]
• Memory(dynamic) system:
P∞
= k=−∞ x(kT ).δ(t − kT ) 1.Discrete Time Signals Properties • Discrete-time complex exponential:
y[k] depends in addition to k on kd 2π
• Fourier Transform of xs (t): Φl [k] = ejlω0 k = ejl( N )k ,(l = 0 ± 1 ± 2..)
P∞ • Time Shift: x[k], x[k − k0 ] (k0 new 0) • Linear System:
Xs (f ) = fs .X(f − nfs ) • Φl [k] = Φl+rN [k]
Pn=−∞ • Time Reversal: x[k] obtained from x[−k] by G{ax1 [k] + bx2 [k]} = ay1 [k] + by2 [k]
∞ • Fourier representation of x[k]:
Xs (ω) = n=−∞ fs .X(ω − nωs ) a reflection about k = 0 = aG{ax1 [k]} + bG{bx2 [k]} P P jlω0 k
• Time-Invariant System: x[k] = l cl Φ[k] = l cl e =
• Periodicity: x[k] = x[k + N ] ;
x[k − k0 ] → y[k − k0 ]
P jl( 2π )k
2.Nyquist Shanon Theorem x[k] periodic for N, 2N, 3N... l c l e N
N :period of x[k] (positive integer) • For an LTI System: l = 0, 1, ..., N P − 1 or l = 3, 4, ..., N + 2
• fs ≥ 2fm → Perfect Reconstruction • x[k] even if: x[k] = x[−k] y[k]
P= x[k] ∗ h[k] x[k] = c0 + 2 L l=1 |cl | cos ( 2π lk + θl )
= ∞
x[k′ ]h[k − k′ ] P N
(Nyquist condition) x[k] even if: x[k] = −x[−k] k′ =−∞ x[k] = a0 + 2 L 2π
l=1 {al cos ( N lk) −
• fs < 2fm → Aliasing (overlapping) → can- • Causality: bl sin ( 2π lk)}
N
not reconstruct x(t) if x[k] = 0 for k ≤ k − 0 (
then y[k] = 0 for k ≤ k0 a0 = c0 ; al = 2|cl | cos(θl ); bl = 2|cl | sin(θl )
fs :Nyquist frequency (ωs = 2πfs ) • N −1
2.Common Discrete Time Signals • Memory-less → Causal L= N 2 , (N even); L = 2 , (N odd)
fm :maximum frequency • Stability:
P∞ an LTI system is BIBO stable if: • Fourier series coeffs:
( 2π
k=−∞ |h[k]| < ∞ 1 −jl( )k
; ω0 = 2π
P
1 if k = 0 cl = N k x[k]e
N
• Dirac Impulse: δ[k] = • Invertibility and Inverse system: N
3.Reconstruction of x(t) 0 o.w x[k] y[k] w[k]=x[k]
• cl = cl+N (Periodicity)
✓x[k]δ[k] = x[0]δ[k] −
−−→ h[k] −
−−→ h1 [k] −−−−−−−→
• to reconstruct x(t) (a band-limited continuous ✓x[k]δ[k − k0 ] = x[k
(0 ]δ[k − k0 ] h[k] ∗ h1 [k] = δ[k]
signal)→ a perfect low pass filter H(ω) must be • properties of discrete convolution: 2.DTFT
1 if k ≥ 0
used: • Unit step: u[k] = ✓Commutative:
( 0 o.w
T if − ωc ≤ ω < ωc P∞ y[k] = x[k] ∗ h[k] = h[k] ∗ x[k] • x[k] = x̃[k] over a longer interval
H(ω) = ✓u[k] = k′ =0
δ[k − k′ ] ✓Associative:
0 o.w jl( 2π )k
• x̃[k] =
P
l cl e
N
δ[k′ ]
Pk
= k′ =−∞ x[k] ∗ (y[k] ∗ z[k]) = (x[k] ∗ y[k]) ∗ z[k]
xs (t) → h(t) → x(t)
PN1 −jl( 2π )k
✓δ[k] = u[k] − (u[k − 1] ✓Distributive: x[k] ∗ (y[k] + z[k]) = (x[k] ∗ • cl = N 1
k=−N1 x[k]e
N

✓x(t) = xs (t) ∗ h(t) k if k ≥ 0 P + (x[k] ∗ z[k])

y[k]) −N1 ≤ k ≤ N1
P∞ • Ramp: r[k] = ✓ ∞ k=−∞ x[k]δ[k − l] = x[l] • DTFT:
= k=−∞ x(kT )h(t − kT ) 0 o.w
✓x[k] ∗ δ[k − l] = x[k − l] X(ω) =
P∞ −jωk
k=−∞ x[k]e
• Exponential: x[k] = ak ✓x[k − l] ∗ δ[k − l′ ] = x[k − l − l′ ] P∞ −j2πf k
4. Cosine Signal Aliasing • Unit Rectangular: of width (N + 1) 1 X(f ) = k=−∞ x[k]e
✓δ[ak] = |a| δ[k]
1
cl = N X(lω0 )
(
1 if −N ≤k≤ N ✓h1 [k] and h2 [k] are cascaded
• Aliasing of cosine signal: when two distinct rectN [k] = 2 2 1 jlω0 k
P
0 o.w → h[k] = h1 [k] ∗ h2 [k] = h2 [k] ∗ h1 [k] x̃[k] = 2π l X(lω0 )e ω0
continuous signals x1 (t) and x2 (t) produce the ✓h1 [k] and h2 [k] are parallel • IDTFT:
same x[k] PN ′ 1
X(ω)ejωk dω
R
✓rectN [k] = 2 → h[k] = h1 [k] + h2 [k] x[k] = 2π
x[k] = cos(2πf. fks ) ′ −N δ[k ]
k =−
2π
• Unit step response s[k]: x[k] = 1 X(f )ej2πf k df
R
2
• f and f ′ are aliases of each other if f ′ = ✓rectN [k] = u[k + N N
2 ] − u[k − ( 2 + 1)] ✓s[k] = u[k] ∗ h[k] = h[k] ∗ u[k] • Energy Density: Sxx = |X(ω)|2
f ± k.fs ; k = 0, 1, 2, 3... • Unit Triangular Pulse: of width (2N + 1) P∞
(
|k| ✓s[k] = k′ =−∞
h[k′ ]
1− N if |k| ≤ N
triN [k] = ✓h[k] = s[k] − s[k − 1]
5. Quantification 0 o.w 3.DFT
• Sinusoid: (ω0 = 2π
N )
−j2π
• q quantification step. 2π(k−k0 ) PN −1 nk
x[k] = A sin N = A sin (ω0 k + φ) • DFT: X[n] = k=0 x[k]e N
• Uniform Quantization if constant q.
x[k] = A cos
2π(k−k0 )
= A cos (ω0 k + φ)
4.Correlation of Discrete Signals n=0,1,2,...,N-1
N
• Real growing/decaying sinusoidal: • Autocorrelation
P∞ fct: • IDFT: x[k] =
PN −1
X[n]e
j2π
N
nk
x(kT ) → Quantif ication → xq (kT ) rxx [k] = l=−∞ x[l + k]x[l]
n=0
x[k] = Cαk = C|α|k ejkω0 k=0,1,2,...,N-1
rxx [k] = x[k] ∗ x[−k] 2π 2π nk
• Rounding: median value. |α| < 1 → sinusoidal sequence multiplied by a • cross-correlation fct: • WNnk
= e−j N nk , WN
−nk
= ej N
• Truncation:minimum value. • N-point DFT computed in:
P∞
decaying exponential rxy [k] = l=−∞ x[l + k]y[l]
• e(t) = x(t) − xq (t): the quantization noise (dis- |α| > 1 → sinusoidal sequence multiplied by a x[k] ∗ y[−k]
rxy [k] = P ✓N 2 complex multiplications
∞
tortion) growing exponential ryx [k] = l=−∞ y[l + kx[l] ✓N (N − 1) complex additions

1
 PL−1 DFT Properties
4.FFT y[k] = m=0 h[k]x[k − m] + cj,2 xj [k − 2] − dj,1 yj [k − 1] − dj,2 yj [k − 2] x3 [k] = ax1 [k] + bx2 [k] ⇐ ⇒
• FIR filters Transfer PMFunction: Parallel: Linearity X3 [n] = aX1 [n] + bX2 [n]of du-
Y (z) −m Y (z)
2π H(z) = X(z) = a1 H(z) = X(z) = β0 + Y
P
= e−j N kn m=0 bm z j=1 Hj (z)
ration N3 = max(N1 , N2 )
• WN kn
0
x[−n] = DF T { 1 x[k]} 1 X[k] =
• N • Its Impuse response: Duality N N
2 log2 N Complex multiplications. (
= β0 + H1 (z) + H2 (z) + · · · + HJ (z) IDF T {x[−n]}
• To calculate DFT: XN = WN xN bk if 0 ≤ k ≤ L − 1 Relationship

X[0]
 h[k] = • 1st order: between x[k] = 1 [DF T {X ∗ [n]}]
0 o.w Yj (z) cj N
 X[1]  ✓Hj (z) = X(z) = −1
DFT,IDFT
• Realization of FIR: 1+dj z DF T {x∗ [k]} X ∗ [−n],
 
 X[2]  =
symmetry
 = DF T {x∗ [−k]} = X ∗ [n]
 

 .  Direct-form: ✓yj [k] = cj x[k] − dj yj [k − 1]
. −j 2π nm
• 2nd order:
 
 .  ✓Direct(canonical)realization: Circular Shift x[k ⊖ m] ⇐ ⇒ X[n]e N
X[N − 1] cj,0 +cj,1 z −1
PL−1 Yj (z)
y[k] = m=0 h[k]x[k − m]
P
1 1 1 ··· 1 ✓Hj (z) = = Circular Con- y[k] = x[k] ⊛ h[k] = l x[l]h[k −
1+dj,1 z −1 +dj,2 z −2

 PL−1 X(z) volution l] ⇐⇒ Y [n] = X[n].H[n]
m=0 bm x[k − m]
N −1  =

1 WN WN2 ··· W x[0]
 N   x[1] 
2(N −1)  ✓Software realization:
✓yj (k) = cj,0 x(k) + cj,1 x(k − 1) Parseval’s
1 PN −1 |x[k]|2 =
2 4 N k=0

1 WN WN ··· W   x[2] 
h(n)z −n − dj,1 yj (k − 1) − dj,2 yj (k − 2)
 N   Y (z) = X(z)
PL−1 Equality PN −1 2
n=0 |X[n]|
.
PL−1 n=0−m

  .
. 
. . . .  
.

. . . .
  . = X(z)

bm z
.
 
. . . .  . m=0 ZT of Common Sequences
(N −1)2 x[N − 1] Cascade-form:
 
N −1 2(N −1) Sequence ZT Conv Region
1 W W ··· W PM −m
N N N H(z) = m=0 bm z δ[k] 1 Alltheplanz
• 4-Point

1 1 1
DFT(N=4):
1

W4 = ✓Software
H(z) = J
Q realization: Appendix: u[k] z
z−1
z
|z| > 1

j=1 Hj (z) −u[−k − 1]

z−1
|z| < 1
1 −j −1 j 
= j=1 c0,j + c1,j z −1 + c2,j z −2
QJ
all the plan
1 −1 Assuming that M = N and M is even.
1 −1 
z except (0 if
L+1
1. FIR filter structre δ[k − l] z −l
1 j −1 −j J = L2 (L even),J = 2 (L odd) Structure Multiplication Addition Register l > 0 or ∞ if
l < 0)
• 6-Point DFT(N=6): c2,j = 0 (if L odd) Direct form M+1 M M
ak u[k]
z |z| > |a|
1 Yj (z) Cascade form M+1 M M z−a
1 1 1 1 1

1 a b −1 c d Hj (z) = Xj (z)
for j = 1, . . . , J 2. IIR filter structre −ak u[−k − 1]
z
z−a
|z| < |a|
az
kak u[k]
1 b c 1 b c 
W6 =  ✓time domain: |z| > |a|
Structure Multiplication Addition Register (z−a)2

1 −1 1 −1 1 −1
1 c b 1 c b yj (k) = c0,j xj [k] + c1,j xj [k − 1] + c2,j xj [k − 2] Direct form 2 M+1 2 M 2 M −kak u[−k − az
Canonic form 2 M+1 2 M M |z| < |a|
1 d c −1 b a 1] (z−a)2
√ √ Cascade form 2 M+1 2 M M
1 3 1 3 ak if 0 ≤ k ≤ z N −aN
a= 2 − j 2√; b = − 2 − j √2 2.IIR Parallel form 2 M+1 3M/2+1 M
N − 1; 0 o.w
|z| > |a|
1 3 1 3 z N −1 (z−a)
c= −2 + j 2 ;d = 2 + j 2 cos(ω0 k)u[k] 1−cos(ω0 )z −1 |z| > 1
• 8-Point DFT(N=8): • IIR
PN filters diff eqt:PM Fourier Series Properties 1−2cos(ω0 )z −1 +z −2
Linearity Ax[n] + By[n] ⇐ ⇒ Aal + Bbl sin(ω0 )z −1
n=0 an y[k − n] = m=0 bm x[k − m]
1 1 1 1 1 1 1 1

sin(ω0 k)u[k] |z| > 1
11 a j b −1 c −j d • with the cd N ̸= 0 Time Shift- x[n − n0 ] ⇐⇒ ak e
−jM ( 2π )n0
N
1−2cos(ω0 )z −1 +z −2
j −1 −j 1 j −1 −j 
• FIR filters Transfer 1−rcos(ω0 )z −1


1 b −j a −1 d j c  Function: ing r k cos(ω0 k)u[k] |z| > r
W8 =  1 M bm z −m jM ( 2π )n0 1−2rcos(ω0 )z −1 +r 2 z −2
P
−1 1 1 −1 1 −1 1  Y (z) Frequency N
H(z) = = Pm=0 e x[n] ⇐
⇒ al−M
rsin(ω0 )z −1
X(z) N −n Shifting r k sin(ω0 k)u[k] |z| > r
 
1 c −j d −1 a j b 
n=0 an z Time Re- x[−n] ⇐
⇒ a−k 1−2rcos(ω0 )z −1 +r 2 z −2
1
1
−j
d
1
j
j
c
−1
−1
−j
b
1
−j
j
a
• Realization of FIR: versal
1−j −1−j Congugation x∗ [n] ⇐⇒ a∗ −k ZT Properties
a= √ ;b =
2
√
2 Direct-form 1: Multiplication x[k]y[k] ⇐ F.s P Property ROC
−1+j ===⇒ dl = m am bl−m
c= √
2
; d = 1+j
√
2
✓Software realization: R− =
M bm z −m F.s
P
m=0 x[k] − x[k − 1] ⇐===⇒ (1 − ax1 [k] + bx2 [k] ⇐
⇒ max[R − , R − ];
Y (z) = −n X(z) First Linearity x1 x2
1+ N
P
n=1 an z Diffrence −jl( 2π ) aX1 [z] + bX2 [z] R+ =
e N )al
Z-Transform: ✓time Pdomain:
M PN Parseval’s 1 P |x[k]|2 = P |a |2
min[R + , R + ]
x1 x2
m=0 bm x(k − m) − n=1 an y(k − n)
y(k) = N k l l
Relation
Time Shift- x[k − k′ ] ⇐
⇒
P∞ −k Direct-form 2: Rx
ZT: X(z) = ′
k=0 x[k]z
Y (z) W (z) ing
H(z) = W (z) X(z) z −k X(z)
Inverse ZT: DTFT Properties |a|Rx− < |z| <
PM −m 1 ak x[k] ⇐
⇒ X( z )
• By inspection. = m=0 bm z · PN −n Linearity
⇐
ax1 [k] + bx2 [k]⇒ aX1 (ω) + Expo multip
a |a|Rx+
1+ n=1 an z
• By Partial Fraction Expansion: bX2 (ω) kx[k] ⇐⇒
PN An PM realization:
✓Software Time Shifting ⇒ X(w)e−jωk0
x[k − k0 ] ⇐ Deffrentiation Rx
X(z) = n=0 −1
1−dn z
Y (z) = m=0 bm z −m W (z) Frequency
−z dX (z)
dz
ejω0 k x[k] ⇐ x∗ [−k] 1 . 1
W (z) = X(z) − n=1 an z −n W (z) ⇒ X(ω − ω0 )
−1
PN ⇐
⇒ < |z| <
An = (1 − dn z )X(z)|z=dn Shifting Time Rever- Rx Rx−
1 s−m ✓time P domain: Conjugate
x∗ [k] ⇐
⇒ X ∗ (−ω)
sal X ∗ ( 1∗ ) 1
Cm = { d [(1 − M Symmetry z Rx+
(s−m)!(−dl )s−m dws−m y(k) = m w(k − m)
m=0 bP Time Diffrence ⇒ (1 − e−jω )X(ω)
x[k] − x[k − 1] ⇐ x1 [k] ∗ x[ k] ⇐
⇒
dl w)s X(w−1 )]}w=d−1
T
w(k) = x(k) − N n=1 an w(k − n) Time Reversal x[−k] ⇐
⇒ X(−ω)
Convolution
X1 (z)X2 (z)
Rx
1
Rx
2
l Cascade(series):
• By Power Series Expansion: Differentiation dX(ω)
bm z −m
PM kx[k] ⇐
⇒ j
P∞ −1 Y (z) in frequency dω
X(z) = k=−∞ x[k]z H(z) = X(z) Pm=0
= N −n X(ω + 2π) = X(ω) , X(f + 1) =
n=0 an z Periodicity
X(f )
Yj (z)
β0 J
Q QL
= j=1 H j (z) = β 0 j=1 Xj (z)
Parseval’s Re- P
|x[k]|2 = 1 2π |X(ω)|2 dω
R
DIGITAL FILTERS: • 1st order:
lation
P∞ 2π
k=−∞ |x[k]| < ∞ or
Yj (z) 1+cj z −1 Convergence P∞ 2
✓Hj (z) = = ✓yj [k] = xj [k] + k=−∞ |x[k]| < ∞
1.FIR Xj (z) 1+dj z −1
y[k] = x[k] ∗ h[k] ⇐
⇒ Y (ω) =
cj xj [k − 1] − dj yj [k − 1] Convolution
X(ω)H(ω)
• FIR
PN filters diff eqt: PM • 2nd order: y[k] = x1 [k]x2 [k] ⇐
⇒ Y (ω) =
n=0 an y[k − n] = m=0 bm x[k − m] Yj (z) 1+cj,1 z −1 +cj,2 z −2 Multiplication
✓Hj (z) = = 1 R X (θ)X2 (ω − θ)dθ
• if N = 0, a0 ̸= 0, L = M + 1 : y[k] = Xj (z) 1+dj,1 z −1 +dj,2 z −2 2π 2π 1
1
P M
a 0 m=0 bm x[k − m] ✓yj [k] = xj [k] + cj,1 xj [k − 1]