Skip to content Skip to navigation

Connexions

You are here: Home » Content » Discrete-Time Systems

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

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

      What is in a lens?

      Lens makers point to Connexions 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 Connexions member, a community, or a respected organization.

    • External bookmarks
  • E-mail the author

Recently Viewed

This feature requires Javascript to be enabled.

Discrete-Time Systems

Module by: C. Sidney Burrus

In the context of discussing signal processing, the most general definition of a system is similar to that of a function. A system is a device, formula, rule, or some process that assigns an output signal from some given class to each possible input signal chosen from some allowed class. From this definition one can pose three interesting and practical problems.

  1. Analysis: If the input signal and the system are given, find the output signal.
  2. Control: If the system and the output signal are given, find the input signal.
  3. Synthesis: If the input signal and output signal are given, find the system.

The definition of input and output signal can be quite diverse. They could be scalars, vectors, functions, functionals, or other objects.

All three of these problems are important, but analysis is probably the most basic and its study usually precedes that of the other two. Analysis usually results in a unique solution. Control is often unique but there are some problems where several inputs would give the same output. Synthesis is seldom unique. There are usually many possible systems that will give the same output for a given input.

In order to develop tools for analysis, control, and design of discrete-time systems, specific definitions, restrictions, and classifications must be made. It is the explicit statement of what a system is, not what it isn't, that allows a descriptive theory and design methods to be developed.

Classifications

The basic classifications of signal processing systems are defined and listed here. We will restrict ourselves to discrete-time systems that have ordered sequences of real or complex numbers as inputs and outputs and will denote the input sequence by x(n)x(n) and the output sequence by y(n)y(n) and show the process of the system by x(n)→y(n)x(n)→y(n). Although the independent variable nn could represent any physical variable, our most common usages causes us to generically call it time but the results obtained certainly are not restricted to this interpretation.

  1. Linear . A system is classified as linear if two conditions are true.
    • If x(n)→y(n)x(n)→y(n) then ax(n)→ay(n)ax(n)→ay(n) for all aa. This property is called homogeneity or scaling.
    • If x1(n)→y1(n)x1(n)→y1(n) and x2(n)→y2(n)x2(n)→y2(n), then (x1(n)+x2(n))→(y1(n)+y2(n))(x1(n)+x2(n))→(y1(n)+y2(n)) for all x1x1 and x2x2. This property is called superposition or additivity.
    If a system does not satisfy both of these conditions for all inputs, it is classified as nonlinear. For most practical systems, one of these conditions implies the other. Note that a linear system must give a zero output for a zero input.
  2. Time Invariant , also called index invariant or shift invariant. A system is classified as time invariant if x(n+k)→y(n+k)x(n+k)→y(n+k) for any integer kk. This states that the system responds the same way regardless of when the input is applied. In most cases, the system itself is not a function of time.
  3. Stable . A system is called bounded-input bounded-output stable if for all bounded inputs, the corresponding outputs are bounded. This means that the output must remain bounded even for inputs artificially constructed to maximize a particular system's output.
  4. Causal . A system is classified as causal if the output of a system does not precede the input. For linear systems this means that the impulse response of a system is zero for time before the input. This concept implies the interpretation of nn as time even though it may not be. A system is semi-causal if after a finite shift in time, the impulse response is zero for negative time. If the impulse response is nonzero for n→-∞n→-∞, the system is absolutely non-causal. Delays are simple to realize in discrete-time systems and semi-causal systems can often be made realizable if a time delay can be tolerated.
  5. Real-Time . A discrete-time system can operate in “real-time" if an output value in the output sequence can be calculated by the system before the next input arrives. If this is not possible, the input and output must be stored in blocks and the system operates in “batch" mode. In batch mode, each output value can depend on all of the input values and the concept of causality does not apply.

These definitions will allow a powerful class of analysis and design methods to be developed and we start with convolution.

Convolution

The most basic and powerful operation for linear discrete-time system analysis, control, and design is discrete-time convolution. We first define the discrete-time unit impulse, also known as the Kronecker delta function, as

δ ( n ) = 1 for n = 0 0 otherwise. δ ( n ) = 1 for n = 0 0 otherwise. (1)

If a system is linear and time-invariant, and δ(n)→h(n)δ(n)→h(n), the output y(n)y(n) can be calculated from its input x(n)x(n) by the operation called convolution denoted and defined by

y ( n ) = h ( n ) * x ( n ) = ∑ m = - ∞ ∞ h ( n - m ) x ( m ) y ( n ) = h ( n ) * x ( n ) = ∑ m = - ∞ ∞ h ( n - m ) x ( m ) (2)

It is informative to methodically develop this equation from the basic properties of a linear system.

Derivation of the Convolution Sum

We first define a complete set of orthogonal basis functions by δ(n-m)δ(n-m) for m=0,1,2,⋯,∞m=0,1,2,⋯,∞. The input x(n)x(n) is broken down into a set of inputs by taking an inner product of the input with each of the basis functions. This produces a set of input components, each of which is a single impulse weighted by a single value of the input sequence (x(n),δ(n-m))=x(m)δ(n-m)(x(n),δ(n-m))=x(m)δ(n-m). Using the time invariant property of the system, δ(n-m)→h(n-m)δ(n-m)→h(n-m) and using the scaling property of a linear system, this gives an output of x(m)δ(n-M)→x(m)h(n-m)x(m)δ(n-M)→x(m)h(n-m). We now calculate the output due to x(n)x(n) by adding outputs due to each of the resolved inputs using the superposition property of linear systems. This is illustrated by the following diagram:

x ( n ) = x ( n ) δ ( n ) = x ( 0 ) δ ( n ) → x ( 0 ) h ( n ) x ( n ) δ ( n - 1 ) = x ( 1 ) δ ( n - 1 ) → x ( 1 ) h ( n - 1 ) x ( n ) δ ( n - 2 ) = x ( 2 ) δ ( n - 2 ) → x ( 2 ) h ( n - 2 ) ⋮ ⋮ x ( n ) δ ( n - m ) = x ( m ) δ ( n - m ) → x ( m ) h ( n - m ) = y ( n ) x ( n ) = x ( n ) δ ( n ) = x ( 0 ) δ ( n ) → x ( 0 ) h ( n ) x ( n ) δ ( n - 1 ) = x ( 1 ) δ ( n - 1 ) → x ( 1 ) h ( n - 1 ) x ( n ) δ ( n - 2 ) = x ( 2 ) δ ( n - 2 ) → x ( 2 ) h ( n - 2 ) ⋮ ⋮ x ( n ) δ ( n - m ) = x ( m ) δ ( n - m ) → x ( m ) h ( n - m ) = y ( n ) (3)

or

y ( n ) = ∑ m = - ∞ ∞ x ( m ) h ( n - m ) y ( n ) = ∑ m = - ∞ ∞ x ( m ) h ( n - m ) (4)

and changing variables gives

y ( n ) = ∑ m = - ∞ ∞ h ( n - m ) x ( m ) y ( n ) = ∑ m = - ∞ ∞ h ( n - m ) x ( m ) (5)

If the system is linear but time varying, we denote the response to an impulse at n=mn=m by δ(n-m)→h(n,m)δ(n-m)→h(n,m). In other words, each impulse response may be different depending on when the impulse is applied. From the development above, it is easy to see where the time-invariant property was used and to derive a convolution equation for a time-varying system as

y ( n ) = h ( n , m ) * x ( n ) = ∑ m = - ∞ ∞ h ( n , m ) x ( m ) . y ( n ) = h ( n , m ) * x ( n ) = ∑ m = - ∞ ∞ h ( n , m ) x ( m ) . (6)

Unfortunately, relaxing the linear constraint destroys the basic structure of the convolution sum and does not result in anything of this form that is useful.

By a change of variables, one can easily show that the convolution sum can also be written

y ( n ) = h ( n ) * x ( n ) = ∑ m = - ∞ ∞ h ( m ) x ( n - m ) . y ( n ) = h ( n ) * x ( n ) = ∑ m = - ∞ ∞ h ( m ) x ( n - m ) . (7)

If the system is causal, h(n)=0h(n)=0 for n<0n<0 and the upper limit on the summation in (2.2) becomes m=nm=n. If the input signal is causal, the lower limit on the summation becomes zero. The form of the convolution sum for a linear, time-invariant, causal discrete-time system with a causal input is

y ( n ) = h ( n ) * x ( n ) = ∑ m = 0 n h ( n - m ) x ( m ) y ( n ) = h ( n ) * x ( n ) = ∑ m = 0 n h ( n - m ) x ( m ) (8)

or, showing the operations commute

y ( n ) = h ( n ) * x ( n ) = ∑ m = 0 n h ( m ) x ( n - m ) . y ( n ) = h ( n ) * x ( n ) = ∑ m = 0 n h ( m ) x ( n - m ) . (9)

Convolution is used analytically to analyze linear systems and it can also be used to calculate the output of a system by only knowing its impulse response. This is a very powerful tool because it does not require any detailed knowledge of the system itself. It only uses one experimentally obtainable response. However, this summation cannot only be used to analyze or calculate the response of a given system, it can be an implementation of the system. This summation can be implemented in hardware or programmed on a computer and become the signal processor.

The Matrix Formulation of Convolution

Some of the properties and characteristics of convolution and of the systems it represents can be better described by a matrix formulation than by the summation notation. The first LL values of the discrete-time convolution defined above can be written as a matrix operator on a vector of inputs to give a vector of the output values.

y 0 y 1 y 2 ⋮ y L - 1 = h 0 0 0 ⋯ 0 h 1 h 0 0 h 2 h 1 h 0 ⋮ ⋮ h L - 1 ⋯ h 0 x 0 x 1 x 2 ⋮ x L - 1 y 0 y 1 y 2 ⋮ y L - 1 = h 0 0 0 ⋯ 0 h 1 h 0 0 h 2 h 1 h 0 ⋮ ⋮ h L - 1 ⋯ h 0 x 0 x 1 x 2 ⋮ x L - 1 (10)

If the input sequence xx is of length NN and the operator signal hh is of length MM, the output is of length L=N+M-1L=N+M-1. This is shown for N=4N=4 and M=3M=3 by the rectangular matrix operation

y 0 y 1 y 2 y 3 y 4 y 5 = h 0 0 0 0 h 1 h 0 0 0 h 2 h 1 h 0 0 0 h 2 h 1 h 0 0 0 h 2 h 1 0 0 0 h 2 x 0 x 1 x 2 x 3 y 0 y 1 y 2 y 3 y 4 y 5 = h 0 0 0 0 h 1 h 0 0 0 h 2 h 1 h 0 0 0 h 2 h 1 h 0 0 0 h 2 h 1 0 0 0 h 2 x 0 x 1 x 2 x 3 (11)

It is clear that if the system is causal (h(n)=0h(n)=0 for n<0n<0), the HH matrix is lower triangular. It is also easy to see that the system being time-invariant is equivalent to the matrix being Toeplitz Entry 1. This formulation makes it obvious that if a certain output were desired from a length 4 input, only 4 of the 6 values could be specified and the other 2 would be controlled by them.

Although the formulation of constructing the matrix from the impulse response of the system and having it operate on the input vector seems most natural, the matrix could have been formulated from the input and the vector would have been the impulse response. Indeed, this might the appropriate formulation if one were specifying the input and output and designing the system.

The basic convolution defined in (Equation 2), derived in (Equation 3), and given in matrix form in (Equation 10) relates the input to the output for linear systems. This is the form of convolution that is related to multiplication of the DTFT and z-transform of signals. However, it is cyclic convolution that is fundamentally related to the DFT and that will be efficiently calculated by the fast Fourier transform (FFT) developed in Part III of these notes. Matrix formulation of length-L cyclic convolution is given by

y 0 y 1 y 2 ⋮ y L - 1 = h 0 h L - 1 h L - 2 ⋯ h 1 h 1 h 0 h L - 1 h 2 h 2 h 1 h 0 h 3 ⋮ ⋮ h L - 1 ⋯ h 0 x 0 x 1 x 2 ⋮ x L - 1 y 0 y 1 y 2 ⋮ y L - 1 = h 0 h L - 1 h L - 2 ⋯ h 1 h 1 h 0 h L - 1 h 2 h 2 h 1 h 0 h 3 ⋮ ⋮ h L - 1 ⋯ h 0 x 0 x 1 x 2 ⋮ x L - 1 (12)

This matrix description makes it clear that the matrix operator is always square and the three signals, x(n)x(n), h(n)h(n), and y(n)y(n), are necessarily of the same length.

There are several useful conclusions that can be drawn from linear algebra Entry 1. The eigenvalues of the non-cyclic are all the same since the eigenvalues of a lower triangular matrix are simply the values on the diagonal.

Although it is less obvious, the eigenvalues of the cyclic convolution matrix are the NN values of the DFT of h(n)h(n) and the eigenvectors are the basis functions of the DFT which are the column vectors of the DFT matrix. The eigenvectors are completely controlled by the structure of HH being a cyclic convolution matrix and are not at all a function of the values of h(n)h(n). The DFT matrix equation from (3.10) is given by

X = Fx and Y = Fy X = Fx and Y = Fy (13)

where XX is the length-N vector of the DFT values, HH is the matrix operator for the DFT, and xx is the length-N vector of the signal x(n)x(n) values. The same is true for the comparable terms in yy.

The matrix form of the length-N cyclic convolution in (3.10) is written

y = Hx y = Hx (14)

Taking the DFT both sides and using the IDFT on xx gives

Fy = Y = FHx = FHF - 1 X Fy = Y = FHx = FHF - 1 X (15)

If we define the diagonal matrix HdHd as an LL by LL matrix with the values of the DFT of h(n)h(n) on its diagonal, the convolution property of the DFT becomes

Y = H d X Y = H d X (16)

This implies

H d = FHF - 1 and H = F - 1 H d F