Skip to content Skip to navigation Skip to collection information

Connexions

You are here: Home » Content » ECE 454 and ECE 554 Supplemental reading » LSI/LTI Systems

Navigation

Table of Contents

Recently Viewed

This feature requires Javascript to be enabled.
 

LSI/LTI Systems

Module by: Richard Baraniuk. E-mail the author

Summary: Introduction to LSI/LTI systems.

Definition 1: linear shift invariant system
A linear shift invariant system is one that is both:
  • linear
  • shift invariant
Also known as LSI, LTI (Figure 1).
Figure 1
All Systems
All Systems (systems.png)

Note:

LSI systems are the bread 'n' budduh of DSP (Figure 2).
Figure 2
Figure 2 (bread.png)

Characterizing LSI Systems

1.

Since the system is linear, it can be represented as a matrix multiply (Figure 3).

Figure 3: x∈CN x N , y∈CN y N , and ℋ ℋ is an N×N N N complex matrix.
Figure 3 (matmult.png)

2.

Since ℋ ℋ is shift invariant, it cannot be just any old matrix. Its values are highly constrained.

In particular we know that

C - m ⁢ℋ⁢ C m =ℋ C - m ℋ C m ℋ
(1)
Let's understand this...

Understanding Conditions on Matrix ℋ for Shift Invariance

Recall Figure 3.

y⁢n= ( row n of ℋ | x ) = ( h n r | x ) y n ( row n of ℋ | x ) ( h n r | x )
(2)
y=ℋ⁢x y ℋ x
·=( ⋯⋯⋯⋯→ )⁢⋮⋮⋮⋮↓ · ⋯ ⋯ ⋯ ⋯ → ⋮ ⋮ ⋮ ⋮ ↓
(3)
where the · is in the nth n th row.

Now shift x x down circularly m m units. If the system is SI then y y will also shift down circularly m m units. i.e.: C m ⁢y=ℋ⁢ C m ⁢x C m y ℋ C m x

·▪=( ⋯⋯⋯⋯→ )⁢⋮↓⋮⋮⋮ · ▪ ⋯ ⋯ ⋯ ⋯ → ⋮ ↓ ⋮ ⋮ ⋮
(4)
where the · is in the nth n th row, the ▪ is in the n+mth n m th row, and the ↓ has been shifted down circularly mm units.

Key: we want the value ▪ in C m ⁢y C m y to equal the · value in yy.

This implies that the rows of ℋ ℋ must circularly shift as we shift xx and yy. i.e.: row n+m n m of ℋ ℋ is equal to the circular shift right of row nn of ℋℋ by mm. i.e.: h n + m r = h n r ⁢ C m T h n + m r h n r C m i.e.: all rows of ℋℋ are circular shifts of each other.

Example 1

y 0 y 1 y 2 =( 147 258 369 )⁢ x 0 x 1 x 2 y 0 y 1 y 2 1 4 7 2 5 8 3 6 9 x 0 x 1 x 2 LSI also needs m=1 m 1 : y 2 y 0 y 1 =( 147 258 369 )⁢ x 2 x 0 x 1 y 2 y 0 y 1 1 4 7 2 5 8 3 6 9 x 2 x 0 x 1 and m=2 m 2 : y 1 y 2 y 0 =( 147 258 369 )⁢ x 1 x 2 x 0 y 1 y 2 y 0 1 4 7 2 5 8 3 6 9 x 1 x 2 x 0 i.e.: 1=5=9 1 5 9 2=6=7 2 6 7 3=4=8 3 4 8 ℋ=( 132 213 321 ) ℋ 1 3 2 2 1 3 3 2 1

ℋ ℋ is called a circulant matrix.

  • each row is a circulary shifted version of the row above (right).
  • each column is a circularly shifted version of the column to the left (down).
ℋ=( 132 213 321 )= h 0 r h 0 r ⁢ C 1 T⋮ h 0 r ⁢ C N - 1 T=( h 0 c C 1 ⁢ h 0 c … C N - 1 ⁢ h 0 c ) ℋ 1 3 2 2 1 3 3 2 1 h 0 r h 0 r C 1 ⋮ h 0 r C N - 1 h 0 c C 1 h 0 c … C N - 1 h 0 c
(5)
which implies that either the first row or first column are all you need to know to know all of ℋℋ.

Note:

Circulant matrices are a special case of Toeplitz matrices, which are constant along diagonals. e.g.: T=( ⋱⋱⋱⋱ ⋱⋱⋱⋱ ⋱⋱⋱⋱ ⋱⋱⋱⋱ )=( 1356 2135 4213 7421 ) T ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ ⋱ 1 3 5 6 2 1 3 5 4 2 1 3 7 4 2 1 Tn,k=t⁢n−k T n k t n k

Example 2

3-point smoother ℋℋ?

Edge detector ℋℋ?

Also, row nn, column kk element of ℋℋ is

ℋn,k=h⁢(n−k)modN ℋ n k h n k N
(6)
where 0≤n≤N−1 0 n N 1 and 0≤k≤N−1 0 k N 1 and h h is the signal corresponding to the first (i.e. the zeroth!) column of ℋ ℋ.

Example 3

N=2 N 2 , h 0 c =-173T h 0 c -1 7 3

ℋ=( h⁢(0−0)modNh⁢(0−1)modNh⁢(0−2)modN h⁢(1−0)modNh⁢(1−1)modNh⁢(1−2)modN h⁢(2−0)modNh⁢(2−1)modNh⁢(2−2)modN )=( h⁢0h⁢2h⁢1 h⁢1h⁢0h⁢2 h⁢2h⁢1h⁢0 ) ℋ h 0 0 N h 0 1 N h 0 2 N h 1 0 N h 1 1 N h 1 2 N h 2 0 N h 2 1 N h 2 2 N h 0 h 2 h 1 h 1 h 0 h 2 h 2 h 1 h 0
(7)

Example 4

Apply a 3-point moving average smoother to a signal x=( -2-101210-1 ) x -2 -1 0 1 2 1 0 -1 .

Figure 4: R8 8 .
Figure 4 (smoother.png)
In Figure 4,
y⁢n=1⁢x⁢(n−1)modN+2⁢x⁢n+3⁢x⁢(n+1)modN y n 1 x n 1 N 2 x n 3 x n 1 N
(8)
y=( 23000001 12300000 01230000 00123000 00012300 00001230 00000123 30000012 )⁢-2-101210-1=-8-42884-2-8 y 2 3 0 0 0 0 0 1 1 2 3 0 0 0 0 0 0 1 2 3 0 0 0 0 0 0 1 2 3 0 0 0 0 0 0 1 2 3 0 0 0 0 0 0 1 2 3 0 0 0 0 0 0 1 2 3 3 0 0 0 0 0 1 2 -2 -1 0 1 2 1 0 -1 -8 -4 2 8 8 4 -2 -8
(9)

The relationship between rows and columns of ℋ ℋ:

ℋn,k=h⁢(n−k)modN ℋ n k h n k N
(10)
where nn is the row, kk is the column, and 0≤n≤N−1 0 n N 1 and 0≤k≤N−1 0 k N 1 .

Note:

Rows and columns run time in reverse order!!!

Example 5

R4 4

y⁢0y⁢1y⁢2y⁢3=( 2301 1230 0123 3012 )⁢x⁢0x⁢1x⁢2x⁢3 y 0 y 1 y 2 y 3 2 3 0 1 1 2 3 0 0 1 2 3 3 0 1 2 x 0 x 1 x 2 x 3
(11)
where the zeroth column, 2103 2 1 0 3 , is the impulse response, h⁢n h n (Figure 5).
Figure 5: Reponse to impulse at n=0 n 0 : 2 comes out, then 1, then 0, ….
Figure 5 (impulse.png)
In Equation 11, the zeroth row, ( 2301 ) 2 3 0 1 , is the time-reversed impulse response, h⁢−k h k .

Upshot for LSI Systems

Figure 6: The impulse response; the zeroth column of ℋ ℋ.
Figure 6 (impulse0.png)
Figure 7: The shifted impulse response. Here, δ 1 δ 1 is a shifted impulse.
Figure 7 (impulse1.png)
Figure 8: The m-shifted impulse response. Here, C m ⁢ δ 0 C m δ 0 is an m-shifted impulse.
Figure 8 (impulsem.png)
i.e.: if we input Figure 6 and measure output h 0 c h 0 c , we can place it in the zeroth column of ℋℋ and then replicate it with circular shifts to build the entire ℋℋ!!

Summary: LSI Systems and Imuplse Response

Given an LSI system (Figure 3), we can characterize it by the impulse response, hh (Figure 9).

Figure 9
Figure 9 (response.png)
and build up ℋℋ with circular shifts of the zeroth column, hh:
ℋ=( h C 1 ⁢h… C N - 1 ⁢h ) ℋ h C 1 h … C N - 1 h
(12)
Then we can compute y y for any input x∈CN x N through
y=ℋ⁢x y ℋ x
(13)

Exercise 1

How to get the impulse response?

4-point edge detector for 8-point signals in complex space (Figure 10).

Figure 10
Figure 10 (edge.png)

1.a)

h h =

1.b)

ℋ ℋ =

Collection Navigation

Content actions

Download module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks