4: Linear Time Invariant Systems

4: Linear Time Invariant
Systems
• LTI Systems
• Convolution Properties
• BIBO Stability
• Frequency Response
• Causality +
• Convolution Complexity
• Circular Convolution
• Frequency-domain
convolution
• Overlap Add
• Overlap Save
• Summary
4: Linear Time Invariant Systems
• MATLAB routines
DSP and Digital Filters (2017-10159) LTI Systems: 4 – 1 / 13

LTI Systems

Systems
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

LTI Systems

Systems
• LTI Systems
• BIBO Stability
• Causality + Linear Time-invariant (LTI) systems have two properties:
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

LTI Systems

Systems
• LTI Systems
• BIBO Stability
• Frequency-domain Linear: H (αu[n] + βv[n]) = αH (u[n]) + βH (v[n])
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

LTI Systems

Systems
• LTI Systems
• BIBO Stability
convolution
• Overlap Add Time Invariant: y[n] = H (x[n]) ⇒ y[n − r] = H (x[n − r]) ∀r
• Overlap Save
• Summary
• MATLAB routines

LTI Systems

Systems
• LTI Systems
• BIBO Stability
convolution
• Overlap Save
• Summary The behaviour of an LTI system is completely defined by its impulse
• MATLAB routines
response: h[n] = H (δ[n])

LTI Systems

Systems
• LTI Systems
• BIBO Stability
convolution
• Overlap Save
• MATLAB routines
Proof:
P∞
We can always write x[n] = r=−∞ x[r]δ[n − r]

LTI Systems

Systems
• LTI Systems
• BIBO Stability
convolution
• Overlap Save
• MATLAB routines
Proof:
P∞
P∞
Hence H (x[n]) = H r=−∞ x[r]δ[n − r]

LTI Systems

Systems
• LTI Systems
• BIBO Stability
convolution
• Overlap Save
• MATLAB routines
Proof:
P∞
P∞
= ∞
P
r=−∞ x[r]H (δ[n − r])

LTI Systems

Systems
• LTI Systems
• BIBO Stability
convolution
• Overlap Save
• MATLAB routines
Proof:
P∞
P∞
= ∞
P
r=−∞ x[r]H (δ[n − r])
= ∞
P
r=−∞ x[r]h[n − r]

LTI Systems

Systems
• LTI Systems
• BIBO Stability
convolution
• Overlap Save
• MATLAB routines
Proof:
P∞
P∞
= ∞
P
r=−∞ x[r]H (δ[n − r])
= ∞
P
r=−∞ x[r]h[n − r]
= x[n] ∗ h[n]

Convolution Properties

P∞
Systems Convolution: x[n] ∗ v[n] = r=−∞ x[r]v[n − r]
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines


P∞
• LTI Systems
• Convolution Properties Convolution obeys normal arithmetic rules for multiplication:
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines


P∞
• LTI Systems
• BIBO Stability
• Causality + Commutative: x[n] ∗ v[n] = v[n] ∗ x[n]
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines


P∞
• LTI Systems
• BIBO Stability
• Convolution Complexity P (i) P
• Circular Convolution Proof: r x[r]v[n − r] = p x[n − p]v[p]
convolution (i) substitute p = n − r
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines


P∞
• LTI Systems
• BIBO Stability
• Overlap Add
• Overlap Save Associative: x[n] ∗ (v[n] ∗ w[n]) = (x[n] ∗ v[n]) ∗ w[n]
• Summary
• MATLAB routines


P∞
• LTI Systems
• BIBO Stability
• Overlap Add
• Summary
• MATLAB routines ⇒ x[n] ∗ v[n] ∗ w[n] is unambiguous


P∞
• LTI Systems
• BIBO Stability
• Overlap Add
• Summary
P (i) P
Proof: r,s x[n − r]v[r − s]w[s] = p,q x[p]v[q − p]w[n − q]
(i) substitute p = n − r , q = n − s


P∞
• LTI Systems
• BIBO Stability
• Overlap Add
• Summary
P (i) P
Distributive over +:
x[n] ∗ (αv[n] + βw[n]) = (x[n] ∗ αv[n]) + (x[n] ∗ βw[n])


P∞
• LTI Systems
• BIBO Stability
• Overlap Add
• Summary
P (i) P
x[n] ∗ (αv[n]
P + βw[n]) = (x[n] ∗ αv[n]) + (x[n] ∗ βw[n])
Proof: r x[n − r] (αv[r]
P + βw[r]) = P
α r x[n − r]v[r] + β r x[n − r]w[r]


P∞
• LTI Systems
• BIBO Stability
• Overlap Add
• Summary
P (i) P
x[n] ∗ (αv[n]
P + βw[n]) = (x[n] ∗ αv[n]) + (x[n] ∗ βw[n])
P + βw[r]) = P
Identity: x[n] ∗ δ[n] = x[n]


P∞
• LTI Systems
• BIBO Stability
• Overlap Add
• Summary
P (i) P
x[n] ∗ (αv[n]
P + βw[n]) = (x[n] ∗ αv[n]) + (x[n] ∗ βw[n])
P + βw[r]) = P
Identity: x[n] ∗ δ[n] = x[n]
P (i)
Proof: r δ[r]x[n − r] = x[n] (i) all terms zero except r = 0.

BIBO Stability

Systems BIBO Stability: Bounded Input, x[n] ⇒ Bounded Output, y[n]
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

BIBO Stability

• LTI Systems
• Convolution Properties The following are equivalent:
• BIBO Stability
• Frequency Response (1) An LTI system is BIBO stable
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

BIBO Stability

• LTI Systems
• BIBO Stability
P∞
(2) h[n] is absolutely summable, i.e. n=−∞ |h[n]| < ∞
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

BIBO Stability

• LTI Systems
• BIBO Stability
P∞
• Causality +
• Circular Convolution (3) H(z) region of absolute convergence includes |z| = 1.
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

BIBO Stability

• LTI Systems
• BIBO Stability
P∞
• Causality +
convolution
• Overlap Add Proof (1) ⇒ (2):(
• Overlap Save
• Summary 1 h[−n] ≥ 0
• MATLAB routines Define x[n] =
−1 h[−n] < 0
P P
then y[0] = x[0 − n]h[n] = |h[n]|.

BIBO Stability

• LTI Systems
• BIBO Stability
P∞
• Causality +
convolution
• Overlap Save
−1 h[−n] < 0
P P
then y[0] =
Px[0 − n]h[n] = |h[n]|.
But |x[n]| ≤ 1∀n so BIBO ⇒ y[0] = |h[n]| < ∞.

BIBO Stability

• LTI Systems
• BIBO Stability
P∞
• Causality +
convolution
• Overlap Save
−1 h[−n] < 0
P P
then y[0] =
Px[0 − n]h[n] = |h[n]|.
Proof (2) ⇒ (1):
P
Suppose |h[n]| = S < ∞ and |x[n]| ≤ B is bounded.

BIBO Stability

• LTI Systems
• BIBO Stability
P∞
• Causality +
convolution
• Overlap Save
−1 h[−n] < 0
P P
then y[0] =
Px[0 − n]h[n] = |h[n]|.
Proof (2) ⇒ (1):
P
P∞
Then |y[n]| = r=−∞ x[n − r]h[r]

BIBO Stability

• LTI Systems
• BIBO Stability
P∞
• Causality +
convolution
• Overlap Save
−1 h[−n] < 0
P P
then y[0] =
Px[0 − n]h[n] = |h[n]|.
Proof (2) ⇒ (1):
P
P∞
Then |y[n]| =
r=−∞ x[n − r]h[r]

P∞
≤ r=−∞ |x[n − r]| |h[r]|

BIBO Stability

• LTI Systems
• BIBO Stability
P∞
• Causality +
convolution
• Overlap Save
−1 h[−n] < 0
P P
then y[0] =
Px[0 − n]h[n] = |h[n]|.
Proof (2) ⇒ (1):
P
P∞
Then |y[n]| =
r=−∞ x[n − r]h[r]

P∞
≤ r=−∞ |x[n − r]| |h[r]|
P∞
≤ B r=−∞ |h[r]|≤ BS < ∞
Frequency Response
For a BIBO stable system Y (ejω ) = X(ejω )H(ejω )

Systems
• LTI Systems
where H(ejω )is the DTFT of h[n] i.e. H(z) evaluated at z = ejω .
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Frequency Response

Systems
• LTI Systems
• BIBO Stability
• Frequency Response Example: h[n] = 1 1 1
• Causality +
0
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Frequency Response

Systems
• LTI Systems
• BIBO Stability
• Causality +
H(ejω ) = 1 + e−jω + e−j2ω

0
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Frequency Response

Systems
• LTI Systems
• BIBO Stability
• Causality +
H(ejω ) = 1 + e−jω + e−j2ω

0
convolution
= e−jω (1 + 2 cos ω)
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Frequency Response

Systems
• LTI Systems
• BIBO Stability
• Causality +
H(ejω ) = 1 + e−jω + e−j2ω

0
convolution
= e−jω (1 + 2 cos ω)
• Overlap Add
• Overlap Save
H(ejω ) = |1 + 2 cos ω|
• Summary
• MATLAB routines

Frequency Response

Systems
• LTI Systems
• BIBO Stability
• Causality +
H(ejω ) = 1 + e−jω + e−j2ω

0
3
convolution
= e−jω (1 + 2 cos ω) 2
• Overlap Add
• Overlap Save
H(ejω ) = |1 + 2 cos ω| 1
• Summary 0
0 1 2 3
• MATLAB routines ω

Frequency Response

Systems
• LTI Systems
• BIBO Stability
• Causality +
H(ejω ) = 1 + e−jω + e−j2ω

0
3
convolution
= e−jω (1 + 2 cos ω) 2
• Overlap Add
• Overlap Save
H(ejω ) = |1 + 2 cos ω| 1
• Summary 0
0 1 2 3
10
-5
-10
0 1 2 3
ω

Frequency Response

Systems
• LTI Systems
• BIBO Stability
• Causality +
H(ejω ) = 1 + e−jω + e−j2ω

0
3
convolution
= e−jω (1 + 2 cos ω) 2
• Overlap Add
• Overlap Save
H(ejω ) = |1 + 2 cos ω| 1
∠H(ejω ) = −ω + π 1−sgn(1+2 cos ω)

• Summary 0
0 1 2 3
2
10
-5
-10
0 1 2 3
ω

Frequency Response

Systems
• LTI Systems
• BIBO Stability
• Causality +
H(ejω ) = 1 + e−jω + e−j2ω

0
3
convolution
= e−jω (1 + 2 cos ω) 2
• Overlap Add
• Overlap Save
H(ejω ) = |1 + 2 cos ω| 1
∠H(ejω ) = −ω + π 1−sgn(1+2 cos ω)

• Summary 0
0 1 2 3
2
10
-5
-10
0 1 2 3
ω
-1
∠
-2
0 1 2 3
ω

Frequency Response

Systems
• LTI Systems
• BIBO Stability
• Causality +
H(ejω ) = 1 + e−jω + e−j2ω

0
3
convolution
= e−jω (1 + 2 cos ω) 2
• Overlap Add
• Overlap Save
H(ejω ) = |1 + 2 cos ω| 1
∠H(ejω ) = −ω + π 1−sgn(1+2 cos ω)

• Summary 0
0 1 2 3
2
10
Sign change in (1 + 2 cos ω) at ω = 2.1 gives 5
(a) gradient discontinuity in |H(ejω )| 0
-5
(b) an abrupt phase change of ±π . -10
0 1 2 3
ω
-1
∠
-2
0 1 2 3
ω

Frequency Response

Systems
• LTI Systems
• BIBO Stability
• Causality +
H(ejω ) = 1 + e−jω + e−j2ω

0
3
convolution
= e−jω (1 + 2 cos ω) 2
• Overlap Add
• Overlap Save
H(ejω ) = |1 + 2 cos ω| 1
∠H(ejω ) = −ω + π 1−sgn(1+2 cos ω)

• Summary 0
0 1 2 3
2
10
-5
0 1 2 3
ω
d
Group delay is− dω ∠H(ejω ) : gives delay of the 1
modulation envelope at each ω . 0
-1
∠
-2
0 1 2 3
ω

Frequency Response

Systems
• LTI Systems
• BIBO Stability
• Causality +
H(ejω ) = 1 + e−jω + e−j2ω

0
3
convolution
= e−jω (1 + 2 cos ω) 2
• Overlap Add
• Overlap Save
H(ejω ) = |1 + 2 cos ω| 1
∠H(ejω ) = −ω + π 1−sgn(1+2 cos ω)

• Summary 0
0 1 2 3
2
10
-5
0 1 2 3
ω
d
Group delay is − dω ∠H(ejω ) : gives delay of the 1
Normally varies with ω but for a symmetric filter it is -1
∠
constant: in this case +1 samples. -2
0 1 2 3
ω

Frequency Response

Systems
• LTI Systems
• BIBO Stability
• Causality +
H(ejω ) = 1 + e−jω + e−j2ω

0
3
convolution
= e−jω (1 + 2 cos ω) 2
• Overlap Add
• Overlap Save
H(ejω ) = |1 + 2 cos ω| 1
∠H(ejω ) = −ω + π 1−sgn(1+2 cos ω)

• Summary 0
0 1 2 3
2
10
-5
0 1 2 3
ω
d
Group delay is − dω ∠H(ejω ) : gives delay of the 1
Normally varies with ω but for a symmetric filter it is -1
∠
constant: in this case +1 samples. -2
0 1 2 3
Discontinuities of ±kπ do not affect group delay. ω

Causality +

Systems
Causal System: cannot see into the future
• LTI Systems i.e. output at time n depends only on inputs up to time n.
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Causality +

Systems
• BIBO Stability
• Frequency Response Formal definition:
• Causality +
If v[n] = x[n] for n ≤ n0 then H (v[n]) = H (x[n]) for n ≤ n0 .
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Causality +

Systems
• BIBO Stability
• Causality +
• Frequency-domain The following are equivalent:
convolution
• Overlap Add (1) An LTI system is causal
• Overlap Save
• Summary
• MATLAB routines

Causality +

Systems
• BIBO Stability
• Causality +
convolution
• Overlap Save
• Summary
(2) h[n] is causal ⇔ h[n] = 0 for n < 0
• MATLAB routines

Causality +

Systems
• BIBO Stability
• Causality +
convolution
• Overlap Save
• Summary
• MATLAB routines (3) H(z) converges for z = ∞

Causality +

Systems
• BIBO Stability
• Causality +
convolution
• Overlap Save
• Summary
Any right-sided sequence can be made causal by adding a delay.

Causality +

Systems
• BIBO Stability
• Causality +
convolution
• Overlap Save
• Summary
Any right-sided sequence can be made causal by adding a delay.

All the systems we will deal with are causal.

Convolution Complexity

Systems y[n] = x[n] ∗ h[n]: convolve x[0 : N − 1] with h[0 : M − 1]
• LTI Systems
• Convolution Properties x
• BIBO Stability ∗
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines


• LTI Systems
• BIBO Stability ∗
• Causality +
• Convolution Complexity Convolution sum:
PM −1
• Frequency-domain y[n] = r=0 h[r]x[n − r]
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines


• LTI Systems
• BIBO Stability ∗ → y[0] y[9]
• Causality +
Convolution sum:
PM −1
y[n] = r=0 h[r]x[n − r]
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines
N = 8, M = 3
M + N − 1 = 10


• LTI Systems
• Causality +
Convolution sum:
PM −1
y[n] = r=0 h[r]x[n − r]
convolution
• Overlap Add y[n] is only non-zero in the range
• Overlap Save
• Summary 0≤n≤M +N −2
• MATLAB routines
N = 8, M = 3
M + N − 1 = 10


• LTI Systems
• Causality +
Convolution sum:
PM −1
y[n] = r=0 h[r]x[n − r]
convolution
• Overlap Save
• MATLAB routines Thus y[n] has only
M + N − 1 non-zero values
N = 8, M = 3
M + N − 1 = 10


• LTI Systems
• Causality +
Convolution sum:
PM −1
y[n] = r=0 h[r]x[n − r]
convolution
• Overlap Save
Algebraically: N = 8, M = 3
M + N − 1 = 10
x[n − r] 6= 0 ⇒ 0 ≤ n − r ≤ N − 1


• LTI Systems
• Causality +
Convolution sum:
PM −1
y[n] = r=0 h[r]x[n − r]
convolution
• Overlap Save
M + N − 1 = 10
x[n − r] 6= 0 ⇒ 0 ≤ n − r ≤ N − 1
⇒n+1−N ≤r ≤n


• LTI Systems
• Causality +
Convolution sum:
PM −1
y[n] = r=0 h[r]x[n − r]
convolution
• Overlap Save
M + N − 1 = 10
x[n − r] 6= 0 ⇒ 0 ≤ n − r ≤ N − 1
⇒n+1−N ≤r ≤n
Pmin(M −1,n))
Hence: y[n] = r=max(0,n+1−N ) h[r]x[n − r]


• LTI Systems
• Causality +
Convolution sum:
PM −1
y[n] = r=0 h[r]x[n − r]
convolution
• Overlap Save
M + N − 1 = 10
x[n − r] 6= 0 ⇒ 0 ≤ n − r ≤ N − 1
⇒n+1−N ≤r ≤n
Pmin(M −1,n))
Hence: y[n] = r=max(0,n+1−N ) h[r]x[n − r]
We must multiply each h[n] by each x[n] and add them to a total
⇒ total arithmetic complexity (× or + operations) ≈ 2M N
Circular Convolution

Systems y⊛ [n] = x[n] ⊛N h[n]: circ convolve x[0 : N − 1] with h[0 : M − 1]
• LTI Systems
• BIBO Stability ⊛N
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines


• LTI Systems
• BIBO Stability ⊛N
• Causality +
• Convolution Complexity Convolution sum:
convolution
PM −1
• Overlap Add
y⊛N [n] = r=0 h[r]x[(n − r)mod N ]
• Overlap Save
• Summary
• MATLAB routines


• LTI Systems
• BIBO Stability ⊛N → y[0] y[7]
• Causality +
Convolution sum:
• Frequency-domain PM −1
convolution y⊛N [n] = r=0 h[r]x[(n − r)mod N ]
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines
N = 8, M = 3


• LTI Systems
• Causality +
Convolution sum:
• Overlap Add
• Overlap Save
• Summary y⊛N [n] has period N
• MATLAB routines
N = 8, M = 3


• LTI Systems
• Causality +
Convolution sum:
• Overlap Add
• Overlap Save
• MATLAB routines ⇒ y⊛N [n] has N distinct values
N = 8, M = 3


• LTI Systems
• Causality +
Convolution sum:
• Overlap Add
• Overlap Save
N = 8, M = 3
• Only the first M − 1 values are affected by the circular repetition:


• LTI Systems
• Causality +
Convolution sum:
• Overlap Add
• Overlap Save
N = 8, M = 3
y⊛N [n] = y[n] for M − 1 ≤ n ≤ N − 1


• LTI Systems
• Causality +
Convolution sum:
• Overlap Add
• Overlap Save
N = 8, M = 3
y⊛N [n] = y[n] for M − 1 ≤ n ≤ N − 1
• If we append M − 1 zeros (or more) onto x[n], then the circular
repetition has no effect at all and:
y⊛N +M −1 [n] = y[n] for 0 ≤ n ≤ N + M − 2


• LTI Systems
• Causality +
Convolution sum:
• Overlap Add
• Overlap Save
N = 8, M = 3
y⊛N [n] = y[n] for M − 1 ≤ n ≤ N − 1
• If we append M − 1 zeros (or more) onto x[n], then the circular
repetition has no effect at all and:
y⊛N +M −1 [n] = y[n] for 0 ≤ n ≤ N + M − 2
Circular convolution is a necessary evil in exchange for using the DFT

Frequency-domain convolution

Systems
Idea: Use DFT to perform circular convolution - less computation
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines


Systems
• LTI Systems
• Convolution Properties (1) Choose L ≥ M + N − 1 (normally round up to a power of 2)
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines


Systems
• LTI Systems
• BIBO Stability
• Causality +
(2) Zero pad x[n] and h[n] to give sequences of length L: x̃[n] and h̃[n]
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines


Systems
• LTI Systems
• BIBO Stability
• Causality +
• Circular Convolution (3) Use DFT: ỹ[n] = F −1 (X̃[k]H̃[k]) = x̃[n] ⊛L h̃[n]
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines


Systems
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Add (4) y[n] = ỹ[n] for 0 ≤ n ≤ M + N − 2.
• Overlap Save
• Summary
• MATLAB routines


Systems
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Save
• Summary Arithmetic Complexity:
• MATLAB routines
DFT or IDFT take 4L log2 L operations if L is a power of 2
(or 16L log2 L if not).


Systems
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Save
• MATLAB routines
Total operations: ≈ 12L log2 L ≈ 12 (M + N ) log2 (M + N )


Systems
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Save
• MATLAB routines
Beneficial if both M and N are >∼ 70 .


Systems
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Save
• MATLAB routines
Example: M = 103 , N = 104 :


Systems
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Save
• MATLAB routines
Example: M = 103 , N = 104 :
Direct: 2M N = 2 × 107


Systems
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Save
• MATLAB routines
Example: M = 103 , N = 104 :
Direct: 2M N = 2 × 107
with DFT: = 1.8 × 106 ,


Systems
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Save
• MATLAB routines
Example: M = 103 , N = 104 :
Direct: 2M N = 2 × 107
with DFT: = 1.8 × 106 ,
But: (a) DFT may be very long if N is large

(b) No outputs until all x[n] has been input.

Overlap Add

Systems
If N is very large:
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Overlap Add

Systems
If N is very large:
N
• LTI Systems (1) chop x[n] into K chunks of length K
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Overlap Add

Systems
If N is very large:
N
• BIBO Stability (2) convolve each chunk with h[n]
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Overlap Add

Systems
If N is very large:
N
• Causality +
• Frequency-domain Each output chunk is of length K + M − 1 and overlaps the next chunk
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Overlap Add

Systems
If N is very large:
N
• Causality +
(3) add up the results
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Overlap Add

Systems
If N is very large:
N
• Causality +
convolution
N
• Overlap Add Operations: ≈ K × 8 (M + K) log2 (M + K)
• Overlap Save
• Summary
• MATLAB routines

Overlap Add

Systems
If N is very large:
N
• Causality +
convolution
N
Computational saving if ≈ 100 < M ≪ K ≪ N
• Overlap Save
• Summary
• MATLAB routines

Overlap Add

Systems
If N is very large:
N
• Causality +
convolution
N
• Overlap Save
• Summary
• MATLAB routines
Example: M = 500, K = 104 , N = 107
Direct: 2M N = 1010

Overlap Add

Systems
If N is very large:
N
• Causality +
convolution
N
• Overlap Save
• Summary
• MATLAB routines
Example: M = 500, K = 104 , N = 107
Direct: 2M N = 1010
single DFT: 12 (M + N ) log2 (M + N ) = 2.8 × 109

Overlap Add

Systems
If N is very large:
N
• Causality +
convolution
N
• Overlap Save
• Summary
• MATLAB routines
Example: M = 500, K = 104 , N = 107
Direct: 2M N = 1010
N
overlap-add: K × 8 (M + K) log2 (M + K) = 1.1 × 109 ,

Overlap Add

Systems
If N is very large:
N
• Causality +
convolution
N
• Overlap Save
• Summary
• MATLAB routines
Example: M = 500, K = 104 , N = 107
Direct: 2M N = 1010
N
Other advantages:
(a) Shorter DFT

Overlap Add

Systems
If N is very large:
N
• Causality +
convolution
N
• Overlap Save
• Summary
• MATLAB routines
Example: M = 500, K = 104 , N = 107
Direct: 2M N = 1010
N
Other advantages:
(a) Shorter DFT
(b) Can cope with N = ∞

Overlap Add

Systems
If N is very large:
N
• Causality +
convolution
N
• Overlap Save
• Summary
• MATLAB routines
Example: M = 500, K = 104 , N = 107
Direct: 2M N = 1010
N
Other advantages:
(a) Shorter DFT
(b) Can cope with N = ∞
(c) Can calculate y[0] as soon as x[K − 1] has been read:
algorithmic delay = K − 1 samples

Overlap Save

Systems
Alternative method:
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Overlap Save

Systems
Alternative method:
N
• LTI Systems (1) chop x[n] into K overlapping
• BIBO Stability chunks of length K + M − 1
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Overlap Save

Systems
Alternative method:
N
• Causality +
(2) ⊛K+M −1 each chunk with h[n]
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Overlap Save

Systems
Alternative method:
N
• Causality +
convolution
• Overlap Add
• Overlap Save The first M − 1 points of each output chunk are invalid
• Summary
• MATLAB routines

Overlap Save

Systems
Alternative method:
N
• Causality +
• Convolution Complexity (3) discard first M − 1 from each chunk
convolution
• Overlap Add
• Summary
• MATLAB routines

Overlap Save

Systems
Alternative method:
N
• Causality +
• Frequency-domain (4) concatenate to make y[n]
convolution
• Overlap Add
• Summary
• MATLAB routines

Overlap Save

Systems
Alternative method:
N
• Causality +
convolution
• Overlap Add
• Summary
• MATLAB routines
Operations: slightly less than overlap-add because no addition needed to
create y[n]

Overlap Save

Systems
Alternative method:
N
• Causality +
convolution
• Overlap Add
• Summary
• MATLAB routines
Operations: slightly less than overlap-add because no addition needed to
create y[n]
Advantages: same as overlap add
Strangely, rather less popular than overlap-add

Summary

Systems
• LTI systems: impulse response, frequency response, group delay
• LTI Systems
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Summary

Systems
• LTI Systems
• Convolution Properties • BIBO stable, Causal, Passive, Lossless systems
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Summary

Systems
• LTI Systems
• BIBO Stability
• Causality +
• Convolution and circular convolution properties
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

Summary

Systems
• LTI Systems
• BIBO Stability
• Causality +
• Circular Convolution • Efficient methods for convolution
convolution ◦ single DFT
• Overlap Add
• Overlap Save ◦ overlap-add and overlap-save
• Summary
• MATLAB routines

Summary

Systems
• LTI Systems
• BIBO Stability
• Causality +
• Circular Convolution • Efficient methods for convolution
convolution ◦ single DFT
• Overlap Add
• Overlap Save ◦ overlap-add and overlap-save
• Summary
• MATLAB routines
For further details see Mitra: 4 & 5.

MATLAB routines

Systems fftfilt Convolution using overlap add
• LTI Systems
x[n]⊛y[n] real(ifft(fft(x).*fft(y)))
• BIBO Stability
• Causality +
convolution
• Overlap Add
• Overlap Save
• Summary
• MATLAB routines

4: Linear Time Invariant Systems

Uploaded by

Copyright:

Available Formats

4: Linear Time Invariant Systems

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

4: Linear Time Invariant Systems

Uploaded by

Copyright:

Available Formats

4: Linear Time Invariant

DSP and Digital Filters (2017-10159) LTI Systems: 4 – 1 / 13