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. Analysis: If the input signal and the system are given, find the output signal. Control: If the system and the output signal are given, find the input signal. 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) and the output sequence by y(n) and show the process of the system by x(n)→y(n). Although the independent variable n 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. Linear . A system is classified as linear if two conditions are true. If x(n)→y(n) then ax(n)→ay(n) for all a. This property is called homogeneity or scaling. If x1(n)→y1(n) and x2(n)→y2(n), then (x1(n)+x2(n))→(y1(n)+y2(n)) for all x1 and x2. 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. Time Invariant , also called index invariant or shift invariant. A system is classified as time invariant if x(n+k)→y(n+k) for any integer k. 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. 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. 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 n 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→-∞, 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. 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. If a system is linear and time-invariant, and δ(n)→h(n), the output y(n) can be calculated from its input x(n) by the operation called convolution denoted and defined by y ( n ) = h ( n ) * x ( n ) = ∑ m = - ∞ ∞ h ( n - m ) x ( m ) 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) for m=0,1,2,⋯,∞. The input 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). Using the time invariant property of the system, δ(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). We now calculate the output due to 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 ) or y ( n ) = ∑ m = - ∞ ∞ x ( m ) h ( n - m ) and changing variables gives y ( n ) = ∑ m = - ∞ ∞ h ( n - m ) x ( m ) If the system is linear but time varying, we denote the response to an impulse at n=m by δ(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 ) . 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 ) . If the system is causal, h(n)=0 for n<0 and the upper limit on the summation in (2.2) becomes m=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 ) or, showing the operations commute y ( n ) = h ( n ) * x ( n ) = ∑ m = 0 n h ( m ) x ( n - m ) . 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 L 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 If the input sequence x is of length N and the operator signal h is of length M, the output is of length L=N+M-1. This is shown for N=4 and M=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 It is clear that if the system is causal (h(n)=0 for n<0), the H matrix is lower triangular. It is also easy to see that the system being time-invariant is equivalent to the matrix being Toeplitz . 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 (), derived in (), and given in matrix form in () 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 This matrix description makes it clear that the matrix operator is always square and the three signals, x(n), h(n), and y(n), are necessarily of the same length. There are several useful conclusions that can be drawn from linear algebra . 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 N values of the DFT of 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 H being a cyclic convolution matrix and are not at all a function of the values of h(n). The DFT matrix equation from (3.10) is given by X = Fx and Y = Fy where X is the length-N vector of the DFT values, H is the matrix operator for the DFT, and x is the length-N vector of the signal x(n) values. The same is true for the comparable terms in y. The matrix form of the length-N cyclic convolution in (3.10) is written y = Hx Taking the DFT both sides and using the IDFT on x gives Fy = Y = FHx = FHF - 1 X If we define the diagonal matrix Hd as an L by L matrix with the values of the DFT of h(n) on its diagonal, the convolution property of the DFT becomes Y = H d X This implies H d = FHF - 1 and H = F - 1 H d F which is the basis of the earlier statement that the eigenvalues of the cyclic convolution matrix are the values of the DFT of h(n) and the eigenvectors are the orthogonal columns of F. The DFT matrix diagonalizes the cyclic convolution matrix. This is probably the most concise statement of the relation of the DFT to convolution and to linear systems. An important practical question is how one calculates the non-cyclic convolution needed by system analysis using the cyclic convolution of the DFT. The answer is easy to see using the matrix description of H. The length of the output of non-cyclic convolution is N+M-1. If N-1 zeros are appended to the end of h(n) and M-1 zeros are appended to the end of x(n), the cyclic convolution of these two augmented signals will produce exactly the same N+M-1 values as non-cyclic convolution would. This is illustrated for the example considered before. y 0 y 1 y 2 y 3 y 4 y 5 = h 0 0 0 0 h 2 h 1 h 1 h 0 0 0 0 h 2 h 2 h 1 h 0 0 0 0 0 h 2 h 1 h 0 0 0 0 0 h 2 h 1 h 0 0 0 0 0 h 2 h 1 h 0 x 0 x 1 x 2 x 3 0 0 Just enough zeros were appended so that the nonzero terms in the upper right-hand corner of H are multiplied by the zeros in the lower part of x and, therefore, do not contribute to y. This does require convolving longer signals but the output is exactly what we want and we calculated it with the DFT-compatible cyclic convolution. Note that more zeros could have been appended to h and x and the first N+M-1 terms of the output would have been the same only more calculations would have been necessary. This is sometimes done in order to use forms of the FFT that require that the length be a power of two. If fewer zeros or none had been appended to h and x, the nonzero terms in the upper right-hand corner of H, which are the “tail" of h(n), would have added the values that would have been at the end of the non-cyclic output of y(n) to the values at the beginning. This is a natural part of cyclic convolution but is destructive if non-cyclic convolution is desired and is called aliasing or folding for obvious reasons. Aliasing is a phenomenon that occurs in several arenas of DSP and the matrix formulation makes it easy to understand.

The Z-Transform Transfer Function Although the time-domain convolution is the most basic relationship of the input to the output for linear systems, the z-transform is a close second in importance. It gives different insight and a different set of tools for analysis and design of linear time-invariant discrete-time systems. If our system in linear and time-invariant, we have seen that its output is given by convolution. y ( n ) = ∑ m = - ∞ ∞ h ( n - m ) x ( m ) Assuming that h(n) is such that the summation converges properly, we can calculate the output to an input that we already know has a special relation with discrete-time transforms. Let x(n)=zn which gives y ( n ) = ∑ m = - ∞ ∞ h ( n - m ) z m With the change of variables of k=n-m, we have y ( n ) = ∑ k = - ∞ ∞ h ( k ) z n - k = [ ∑ k = - ∞ ∞ h ( k ) z - k ] z n or y ( n ) = H ( z ) z n We have the remarkable result that for an input of x(n)=zn, we get an output of exactly the same form but multiplied by a constant that depends on z and this constant is the z-transform of the impulse response of the system. In other words, if the system is thought of as a matrix or operator, zn is analogous to an eigenvector of the system and H(z) is analogous to the corresponding eigenvalue. We also know from the properties of the z-transform that convolution in the n domain corresponds to multiplication in the z domain. This means that the z-transforms of x(n) and y(n) are related by the simple equation Y ( z ) = H ( z ) X ( z ) The z-transform decomposes x(n) into its various components along zn which passing through the system simply multiplies that value time H(z) and the inverse z-transform recombines the components to give the output. This explains why the z-transform is such a powerful operation in linear discrete-time system theory. Its kernel is the eigenvector of these systems. The z-transform of the impulse response of a system is called its transfer function (it transfers the input to the output) and multiplying it times the z-transform of the input gives the z-transform of the output for any system and signal where there is a common region of convergence for the transforms.

Frequency Response of Discrete-Time Systems The frequency response of a Discrete-Time system is something experimentally measurable and something that is a complete description of a linear, time-invariant system in the same way that the impulse response is. The frequency response of a linear, time-invariant system is defined as the magnitude and phase of the sinusoidal output of the system with a sinusoidal input. More precisely, if x ( n ) = cos ( ω n ) and the output of the system is expressed as y ( n ) = M ( ω ) cos ( ω n + φ ( ω ) ) + T ( n ) where T(n) contains no components at ω, then M(ω) is called the magnitude frequency response and φ(ω) is called the phase frequency response. If the system is causal, linear, time-invariant, and stable, T(n) will approach zero as n→∞ and the only output will be the pure sinusoid at the same frequency as the input. This is because a sinusoid is a special case of zn and, therefore, an eigenvector. If z is a complex variable of the special form z = e j ω then using Euler's relation of ejx=cos(x)+jsin(x), one has x ( n ) = e j ω n = cos ( ω n ) + j sin ( ω n ) and therefore, the sinusoidal input of (3.22) is simply the real part of zn for a particular value of z, and, therefore, the output being sinusoidal is no surprise.

Fundamental Theorem of Linear, Time-Invariant Systems The fundamental theorem of calculus states that an integral defined as an inverse derivative and one defined as an area under a curve are the same. The fundamental theorem of algebra states that a polynomial given as a sum of weighted powers of the independent variable and as a product of first factors of the zeros are the same. The fundamental theorem of arithmetic states that an integer expressed as a sum of weighted units, tens, hundreds, etc. or as the product of its prime factors is the same. These fundamental theorems all state equivalences of different ways of expressing or calculating something. The fundamental theorem of linear, time-invariant systems states calculating the output of a system can be done with the impulse response by convolution or with the frequency response (or z-transform) with transforms. Stated another way, it says the frequency response can be found from directly calculating the output from a sinusoidal input or by evaluating the z-transform on the unit circle. Z { h ( n ) } | z = e j ω = A ( ω ) e j Θ ( ω )

Pole-Zero Plots

Relation of PZ Plots, FR Plots, Impulse R

State Variable Formulation

Difference Equations

Flow Graph Representation

Standard Structures

FIR and IIR Structures

Quantization Effects

Multidimensional Systems