Connexions

Site Feedback

Discrete Time Convolution

By Ricardo Radaelli-Sanchez, Richard Baraniuk, Stephen Kruzick, Catherine Elder

Introduction

Convolution, one of the most important concepts in electrical engineering, can be used to determine the output a system produces for a given input signal. It can be shown that a linear time invariant system is completely characterized by its impulse response. The sifting property of the discrete time impulse function tells us that the input signal to a system can be represented as a sum of scaled and shifted unit impulses. Thus, by linearity, it would seem reasonable to compute of the output signal as the sum of scaled and shifted unit impulse responses. That is exactly what the operation of convolution accomplishes. Hence, convolution can be used to determine a linear time invariant system's output from knowledge of the input and the impulse response.

Convolution and Circular Convolution

Convolution

Operation Definition

Discrete time convolution is an operation on two discrete time signals defined by the integral

( f * g ) ( n ) = k = - f ( k ) g ( n - k ) ( f * g ) ( n ) = k = - f ( k ) g ( n - k )
1

for all signals f,gf,g defined on ZZ. It is important to note that the operation of convolution is commutative, meaning that

f * g = g * f f * g = g * f
2

for all signals f,gf,g defined on ZZ. Thus, the convolution operation could have been just as easily stated using the equivalent definition

( f * g ) ( n ) = k = - f ( n - k ) g ( k ) ( f * g ) ( n ) = k = - f ( n - k ) g ( k )
3

for all signals f,gf,g defined on ZZ. Convolution has several other important properties not listed here but explained and derived in a later module.

Definition Motivation

The above operation definition has been chosen to be particularly useful in the study of linear time invariant systems. In order to see this, consider a linear time invariant system HH with unit impulse response hh. Given a system input signal xx we would like to compute the system output signal H(x)H(x). First, we note that the input can be expressed as the convolution

x ( n ) = k = - x ( k ) δ ( n - k ) x ( n ) = k = - x ( k ) δ ( n - k )
4

by the sifting property of the unit impulse function. By linearity

H x ( n ) = k = - x ( k ) H δ ( n - k ) . H x ( n ) = k = - x ( k ) H δ ( n - k ) .
5

Since Hδ(n-k)Hδ(n-k) is the shifted unit impulse response h(n-k)h(n-k), this gives the result

H x ( n ) = k = - x ( k ) h ( n - k ) = ( x * h ) ( n ) . H x ( n ) = k = - x ( k ) h ( n - k ) = ( x * h ) ( n ) .
6

Hence, convolution has been defined such that the output of a linear time invariant system is given by the convolution of the system input with the system unit impulse response.

Graphical Intuition

It is often helpful to be able to visualize the computation of a convolution in terms of graphical processes. Consider the convolution of two functions f,gf,g given by

( f * g ) ( n ) = k = - f ( k ) g ( n - k ) = k = - f ( n - k ) g ( k ) . ( f * g ) ( n ) = k = - f ( k ) g ( n - k ) = k = - f ( n - k ) g ( k ) .
7

The first step in graphically understanding the operation of convolution is to plot each of the functions. Next, one of the functions must be selected, and its plot reflected across the k=0k=0 axis. For each real tt, that same function must be shifted left by tt. The product of the two resulting plots is then constructed. Finally, the area under the resulting curve is computed.

Example 1

Recall that the impulse response for a discrete time echoing feedback system with gain aa is

h ( n ) = a n u ( n ) , h ( n ) = a n u ( n ) ,
8

and consider the response to an input signal that is another exponential

x ( n ) = b n u ( n ) . x ( n ) = b n u ( n ) .
9

We know that the output for this input is given by the convolution of the impulse response with the input signal

y ( n ) = x ( n ) * h ( n ) . y ( n ) = x ( n ) * h ( n ) .
10

We would like to compute this operation by beginning in a way that minimizes the algebraic complexity of the expression. However, in this case, each possible coice is equally simple. Thus, we would like to compute

y ( n ) = k = - a k u ( k ) b n - k u ( n - k ) . y ( n ) = k = - a k u ( k ) b n - k u ( n - k ) .
11

The step functions can be used to further simplify this sum. Therefore,

y ( n ) = 0 y ( n ) = 0
12

for n<0n<0 and

y ( n ) = k = 0 n ( a b ) k y ( n ) = k = 0 n ( a b ) k
13

for n0n0. Hence, provided ab1ab1, we have that

y ( n ) = 0 n < 0 1 - ( a b ) n + 1 1 - ( a b ) n 0 . y ( n ) = 0 n < 0 1 - ( a b ) n + 1 1 - ( a b ) n 0 .
14

Circular Convolution

Discrete time circular convolution is an operation on two finite length or periodic discrete time signals defined by the integral

( f * g ) ( n ) = k = 0 N - 1 f ^ ( k ) g ^ ( n - k ) ( f * g ) ( n ) = k = 0 N - 1 f ^ ( k ) g ^ ( n - k )
15

for all signals f,gf,g defined on Z[0,N-1]Z[0,N-1] where f^,g^f^,g^ are periodic extensions of ff and gg. It is important to note that the operation of circular convolution is commutative, meaning that

f * g = g * f f * g = g * f
16

for all signals f,gf,g defined on Z[0,N-1]Z[0,N-1]. Thus, the circular convolution operation could have been just as easily stated using the equivalent definition

( f * g ) ( n ) = k = 0 N - 1 f ^ ( n - k ) g ^ ( k ) ( f * g ) ( n ) = k = 0 N - 1 f ^ ( n - k ) g ^ ( k )
17

for all signals f,gf,g defined on Z[0,N-1]Z[0,N-1] where f^,g^f^,g^ are periodic extensions of ff and gg. Circular convolution has several other important properties not listed here but explained and derived in a later module.

Alternatively, discrete time circular convolution can be expressed as the sum of two summations given by

( f * g ) ( n ) = k = 0 n f ( k ) g ( n - k ) + k = n + 1 N - 1 f ( k ) g ( n - k + N ) ( f * g ) ( n ) = k = 0 n f ( k ) g ( n - k ) + k = n + 1 N - 1 f ( k ) g ( n - k + N )
18

for all signals f,gf,g defined on Z[0,N-1]Z[0,N-1].

Meaningful examples of computing discrete time circular convolutions in the time domain would involve complicated algebraic manipulations dealing with the wrap around behavior, which would ultimately be more confusing than helpful. Thus, none will be provided in this section. Of course, example computations in the time domain are easy to program and demonstrate. However, disrete time circular convolutions are more easily computed using frequency domain tools as will be shown in the discrete time Fourier series section.

Definition Motivation

The above operation definition has been chosen to be particularly useful in the study of linear time invariant systems. In order to see this, consider a linear time invariant system HH with unit impulse response hh. Given a finite or periodic system input signal xx we would like to compute the system output signal H(x)H(x). First, we note that the input can be expressed as the circular convolution

x ( n ) = k = 0 N - 1 x ^ ( k ) δ ^ ( n - k ) x ( n ) = k = 0 N - 1 x ^ ( k ) δ ^ ( n - k )
19

by the sifting property of the unit impulse function. By linearity,

H x ( n ) = k = 0 N - 1 x ^ ( k ) H δ ^ ( n - k ) . H x ( n ) = k = 0 N - 1 x ^ ( k ) H δ ^ ( n - k ) .
20

Since Hδ(n-k)Hδ(n-k) is the shifted unit impulse response h(n-k)h(n-k), this gives the result

H x ( n ) = k = 0 N - 1 x ^ ( k ) h ^ ( n - k ) = ( x * h ) ( n ) . H x ( n ) = k = 0 N - 1 x ^ ( k ) h ^ ( n - k ) = ( x * h ) ( n ) .
21

Hence, circular convolution has been defined such that the output of a linear time invariant system is given by the convolution of the system input with the system unit impulse response.

Graphical Intuition

It is often helpful to be able to visualize the computation of a circular convolution in terms of graphical processes. Consider the circular convolution of two finite length functions f,gf,g given by

( f * g ) ( n ) = k = 0 N - 1 f ^ ( k ) g ^ ( n - k ) = k = 0 N - 1 f ^ ( n - k ) g ^ ( k ) . ( f * g ) ( n ) = k = 0 N - 1 f ^ ( k ) g ^ ( n - k ) = k = 0 N - 1 f ^ ( n - k ) g ^ ( k ) .
22

The first step in graphically understanding the operation of convolution is to plot each of the periodic extensions of the functions. Next, one of the functions must be selected, and its plot reflected across the k=0k=0 axis. For each kZ[0,N-1]kZ[0,N-1], that same function must be shifted left by kk. The product of the two resulting plots is then constructed. Finally, the area under the resulting curve on Z[0,N-1]Z[0,N-1] is computed.

Interactive Element

Figure 1: Interact (when online) with the Mathematica CDF demonstrating Discrete Linear Convolution.

Convolution Summary

Convolution, one of the most important concepts in electrical engineering, can be used to determine the output signal of a linear time invariant system for a given input signal with knowledge of the system's unit impulse response. The operation of discrete time convolution is defined such that it performs this function for infinite length discrete time signals and systems. The operation of discrete time circular convolution is defined such that it performs this function for finite length and periodic discrete time signals. In each case, the output of the system is the convolution or circular convolution of the input signal with the unit impulse response.