# Connexions

You are here: Home » Content » ECE 454 and ECE 554 Supplemental reading » PROPERTIES OF THE DIGITAL CONVOLUTION

### Lenses

What is a lens?

#### 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?

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

#### Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
• VOCW

This module is included inLens: Vietnam OpenCourseWare's Lens
By: Vietnam OpenCourseWare

Click the "VOCW" link to see all content affiliated with them.

### Recently Viewed

This feature requires Javascript to be enabled.

Inside Collection (Course):

Course by: Thad Welch. E-mail the author

# PROPERTIES OF THE DIGITAL CONVOLUTION

Module by: Nguyen Huu Phuong. E-mail the author

Summary: Digital convolution has serveral characteristics, allowing different system connection configurations.

## Commutativity

By a change of variable nk=k,nk=k, size 12{n - k=k rSup { size 8{,} } } {}, or k=nk,k=nk, size 12{k=n - k rSup { size 8{,} } } {} in the formula for convolution

y ( n ) = k = x ( k ) h ( n k ) = k , = x ( n k , ) h ( k , ) y ( n ) = k = x ( k ) h ( n k ) = k , = x ( n k , ) h ( k , ) size 12{y $$n$$ = Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } {x $$k$$ h $$n - k$$ } = Sum cSub { size 8{k rSup { size 6{,} } = - infinity } } cSup { infinity } {x $$n - k rSup { size 8{,} }$$ h $$k rSup { size 8{,} }$$ } } {}

and by replacing the temporary variable k’ by k, we get

y ( n ) = k = x ( n k ) h ( k ) = k = h ( k ) x ( n k ) = h ( k ) x ( k n ) y ( n ) = k = x ( n k ) h ( k ) = k = h ( k ) x ( n k ) = h ( k ) x ( k n ) size 12{y $$n$$ = Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } {x $$n - k$$ h $$k$$ } = Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } {h $$k$$ x $$n - k$$ =h $$k$$ *x $$k - n$$ } } {}

That is the order of convolution is reversed. Thus we have two formulae of convolution:

y(n)=x(n)h(n)=k=x(k)h(nk)y(n)=x(n)h(n)=k=x(k)h(nk) size 12{y $$n$$ =x $$n$$ * h $$n$$ = Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } {x $$k$$ h $$n - k$$ } } {}
(1)

and

y(n)=h(n)x(n)=k=h(k)x(nk)y(n)=h(n)x(n)=k=h(k)x(nk) size 12{y $$n$$ =h $$n$$ * x $$n$$ = Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } {h $$k$$ x $$n - k$$ } } {}
(2)

In practive we usually let the longer sequence stay fixed, and shift the shorter one.

The commutative characteristic of convolution means that we can swap the input signal with the impulse response of a system without affecting the output. This idea is depicted in Figure 2.

## Associativity

It can be shown that

[x(n)h1(n)]h2(n)=x(n)[h1(n)h2(n)][x(n)h1(n)]h2(n)=x(n)[h1(n)h2(n)] size 12{ $x $$n$$ *h rSub { size 8{1} } $$n$$$ *h rSub { size 8{2} } $$n$$ =x $$n$$ * $h rSub { size 8{1} } $$n$$ *h rSub { size 8{2} } $$n$$$ } {}
(3)

Figure 3 shows the system meaning of the associativity, where two systems in series (in cascade) can be replaced by only one whose impulse response is the convolution of the two individual impulse responses.

### Example 1

Two systems in cascade have impulse responses h 1 ( n ) = a n u ( n ) h 2 ( n ) = b n u ( n ) h 1 ( n ) = a n u ( n ) h 2 ( n ) = b n u ( n ) alignl { stack { size 12{h rSub { size 8{1} } $$n$$ =a rSup { size 8{n} } u $$n$$ } {} # h rSub { size 8{2} } $$n$$ =b rSup { size 8{n} } u $$n$$ {} } } {} Find the overall impulse response.

Solution

First aa size 12{ lline a rline } {} and bb size 12{ lline b rline } {} should be smaller than 1 to ensure the convergence of the sequences. Notice that both impulse responses are causal. The overall impulse response is

h ( n ) = h 1 ( n ) h 2 ( n ) = k = h 1 ( k ) h 2 ( n k ) h ( n ) = h 1 ( n ) h 2 ( n ) = k = h 1 ( k ) h 2 ( n k ) size 12{h $$n$$ =h rSub { size 8{1} } $$n$$ * h rSub { size 8{2} } $$n$$ = Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } {h rSub { size 8{1} } $$k$$ h rSub { size 8{2} } $$n - k$$ } } {}

The actual limits of summation are k=0k=0 size 12{k=0} {} and k=nk=n size 12{k=n} {}(see Section 4 later), hence

h ( n ) = k = 0 n a k b k n u ( k ) u ( k n ) = b n k = 0 n ( a b ) k h ( n ) = k = 0 n a k b k n u ( k ) u ( k n ) = b n k = 0 n ( a b ) k alignl { stack { size 12{h $$n$$ = Sum cSub { size 8{k=0} } cSup { size 8{n} } {a rSup { size 8{k} } b rSup { size 8{k - n} } u $$k$$ u $$k - n$$ } } {} # matrix { {} # {} # {} } =b rSub { size 8{n} } Sum cSub { size 8{k=0} } cSup { size 8{n} } { $${ { size 8{a} } over { size 8{b} } }$$ rSup { size 8{k} } } {} } } {}

Using the formula of finite geometric series.

1+x+x2+...+xM=k=0Mxk=1xM+11x,x<11+x+x2+...+xM=k=0Mxk=1xM+11x,x<1 size 12{1+x+x rSup { size 8{2} } + "." "." "." +x rSup { size 8{M} } = Sum cSub { size 8{k=0} } cSup { size 8{M} } {x rSup { size 8{k} } = { {1 - x rSup { size 8{M+1} } } over {1 - x} } } , matrix { {} # {} # {} } \lline x \lline <1} {}
(4)

here x=a/bx=a/b size 12{x= {a} slash {b} } {}, we get

h ( n ) = b n 1 ( a b ) n + 1 1 a b = b n + 1 a n + 1 b a h ( n ) = b n 1 ( a b ) n + 1 1 a b = b n + 1 a n + 1 b a size 12{h $$n$$ =b rSup { size 8{n} } { {1 - $${ { size 8{a} } over { size 8{b} } }$$ rSup { size 8{n+1} } } over {1 - { { size 8{a} } over { size 8{b} } } } } = { {b rSup { size 8{n+1} } - a rSup { size 8{n+1} } } over {b - a} } } {}

## Distributivity

It can be shown

x(n)[h1(n)+h2(n)]=x(n)h1(n)+x(n)h2(n)x(n)[h1(n)+h2(n)]=x(n)h1(n)+x(n)h2(n) size 12{x $$n$$ * $h rSub { size 8{1} } $$n$$ +h rSub { size 8{2} } $$n$$$ =x $$n$$ * h rSub { size 8{1} } $$n$$ +x $$n$$ * h rSub { size 8{2} } $$n$$ } {}
(5)

The system meaning is illustrated in Figure 4 where two systems connected in parallel can be replaced by one whose impulse response is the sum of the two ones.

## Impulse response for causal system and signal

Since impulse response is a characterization (among other characterizations) of systems. As such, the causality of a system would be reflected on its impulse response. From the convolution Figure the output at instant n0n0 size 12{n rSub { size 8{0} } } {} is:

y ( n 0 ) = k = 0 h ( k ) x ( n 0 k ) + k = 1 h ( k ) x ( n 0 k ) y ( n 0 ) = k = 0 h ( k ) x ( n 0 k ) + k = 1 h ( k ) x ( n 0 k ) size 12{y $$n rSub { size 8{0} }$$ = Sum cSub { size 8{k=0} } cSup { size 8{ infinity } } {h $$k$$ x $$n rSub { size 8{0} } - k$$ } + Sum cSub { size 8{k= - infinity } } cSup { size 8{ - 1} } {h $$k$$ x $$n rSub { size 8{0} } - k$$ } } {}

In order the output signal y(n0)y(n0) size 12{y $$n rSub { size 8{0} }$$ } {} does not depend on future (n>n0)(n>n0) size 12{ $$n>n rSub { size 8{0} }$$ } {}values of input signal x(n)x(n) size 12{x $$n$$ } {}, the second term of above equation should be zero, i.e. h(k)=0h(k)=0 size 12{h $$k$$ =0} {} for k<0k<0 size 12{k<0} {}. As k is a dummy variable, we conclude

h ( n ) = 0 at n < 0 h ( n ) = 0 at n < 0 size 12{h $$n$$ =0 matrix { {} # {} } ital "at" matrix { {} # {} } n<0} {}

Thus, the causality of a system implies that its impulse response is zero and vice versa. The output at time n0n0 size 12{n rSub { size 8{0} } } {} is now the first term of the equation

y ( n 0 ) = k = 0 h ( k ) x ( n 0 k ) y ( n 0 ) = k = 0 h ( k ) x ( n 0 k ) size 12{y $$n rSub { size 8{0} }$$ = Sum cSub { size 8{k=0} } cSup { size 8{ infinity } } {h $$k$$ x $$n rSub { size 8{0} } - k$$ } } {}

For any time n,

y(n)=k=0h(k)x(nk)(onlythesignaliscausal)y(n)=k=0h(k)x(nk)(onlythesignaliscausal) size 12{y $$n$$ = Sum cSub { size 8{k=0} } cSup { size 8{ infinity } } {h $$k$$ x $$n - k$$ } matrix { {} # {} # {} } $$matrix { ital "only" {} # ital "the" {} # ital "signal" {} # ital "is" {} # ital "causal"{} }$$ } {}
(6)

Had the convolution x(n)h(n)x(n)h(n) size 12{x $$n$$ *h $$n$$ } {} been used, the result would be

y(n)=k=nx(k)h(nk)(onlythesignaliscausal)y(n)=k=nx(k)h(nk)(onlythesignaliscausal) size 12{y $$n$$ = Sum cSub { size 8{k= - infinity } } cSup { size 8{n} } {x $$k$$ h $$n - k$$ } matrix { {} # {} # {} } $$matrix { ital "only" {} # ital "the" {} # ital "signal" {} # ital "is" {} # ital "causal"{} }$$ } {}
(7)

In above, only the causality of the system is considered. Now, the imput signal is also causal, the result is

y(n)=k=0nh(k)x(nk)(bothsystemandsignalarecausal)y(n)=k=0nh(k)x(nk)(bothsystemandsignalarecausal) size 12{y $$n$$ = Sum cSub { size 8{k=0} } cSup { size 8{n} } {h $$k$$ x $$n - k$$ } matrix { {} # {} # {} } $$matrix { ital "both" {} # ital "system" {} # ital "and" {} # ital "signal" {} # ital "are" {} # ital "causal"{} }$$ } {}
(8)

And equivalently

y(n)=k=0nx(k)h(nk)(bothsystemandsignalarecausal)y(n)=k=0nx(k)h(nk)(bothsystemandsignalarecausal) size 12{y $$n$$ = Sum cSub { size 8{k=0} } cSup { size 8{n} } {x $$k$$ h $$n - k$$ } matrix { {} # {} } $$matrix { ital "both" {} # ital "system" {} # ital "and" {} # ital "signal" {} # ital "are" {} # ital "causal"{} }$$ } {}
(9)

Notice that the summation limits for both cases are the same and the upper limit increases with n, also that the output signal y(n)y(n) size 12{y $$n$$ } {} at time n depends only the convolution summation up to n and independent of future values after n. So we can write the upper limit as size 12{ infinity } {} without effecting the result.

### Example 2

Input signal and impulse response are respectively x ( n ) = u ( n ) h ( n ) = a n u ( n ) a < 1 x ( n ) = u ( n ) h ( n ) = a n u ( n ) a < 1 alignl { stack { size 12{x $$n$$ =u $$n$$ } {} # size 12{h $$n$$ =a rSup { size 8{n} } u $$n$$ matrix { {} # {} # {} # {} } \lline a \lline <1} {} } } {} Find the output signal by analysis computation.

Solution

Notice that both x(n)x(n) size 12{x $$n$$ } {}and h(n)h(n) size 12{h $$n$$ } {} are causal and of infinite duration. The given condition a<1a<1 size 12{ lline a rline <1} {} ensures the convergence of h(n)h(n) size 12{h $$n$$ } {}. We choose to evaluate h(n)x(n)h(n)x(n) size 12{h $$n$$ *x $$n$$ } {}, using Equation 8

y ( n ) = h ( n ) x ( n ) = k = h ( k ) x ( n k ) = k = 0 n a k u ( k ) u ( n k ) = k = 0 n a k y ( n ) = h ( n ) x ( n ) = k = h ( k ) x ( n k ) = k = 0 n a k u ( k ) u ( n k ) = k = 0 n a k alignl { stack { size 12{y $$n$$ =h $$n$$ * x $$n$$ = Sum cSub { size 8{k= - infinity } } cSup { size 8{ infinity } } {h $$k$$ x $$n - k$$ = Sum cSub { size 8{k=0} } cSup { size 8{n} } {a rSup { size 8{k} } u $$k$$ u $$n - k$$ } } } {} # matrix { matrix { {} # {} # {} # {} } {} # {} # {} # {} } matrix { {} # {} # {} # {} } matrix { {} # {} } = Sum cSub { size 8{k=0} } cSup { size 8{n} } {a rSup { size 8{k} } } {} } } {}

So, the result is.

y ( 0 ) = 1 y ( 1 ) = 1 + a y ( 2 ) = 1 + a + a 2 . . . y ( n ) = 1 + a + a 2 + . . . + a n y ( 0 ) = 1 y ( 1 ) = 1 + a y ( 2 ) = 1 + a + a 2 . . . y ( n ) = 1 + a + a 2 + . . . + a n alignl { stack { size 12{y $$0$$ =1} {} # size 12{y $$1$$ =1+a} {} # size 12{y $$2$$ =1+a+a rSup { size 8{2} } } {} # "." "." "." {} # y $$n$$ =1+a+a rSup { size 8{2} } + "." "." "." +a rSup { size 8{n} } {} } } {}

The output signal y(n)y(n) size 12{y $$n$$ } {} does not go to size 12{ infinity } {}but grows asymptotically to the finite value of 11a11a size 12{ { {1} over {1 - a} } } {} (see Example ).

## System identification

In DSP sometimes we need to determine a system, assumed LTI (or LSI), when we know the input signal and output signal, e.g. by setting up an experiment. This problem is called system identification . Specifically, we must determine the impulse response of the system, and then the signal difference equation if necessary.

Adaptive filters using FIR filters are often used to identify unknown DSP systems. In control theory, also, sytem identification is a familiar problem.

For causal systems the output is given by the reduced convolution (Equation 8) which is repeated here

giving

giving

### Example 3

In order to identify an unknown DSP system (hardware or software) we applied a signal x(n) and obtained the output y(n) as follows.

Determine the impulse response.

Solution

Note that both input and output signals are causal. We proceed the evaluation of the impulse response as follows.

Continuing we will see that for . Thus the system impulse response is

The system is causal as expected.

Another method is to transform the problem to the z-domain (chapter 4).

## Content actions

EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

#### 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?

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?

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