A CO""f'e.l<-Vct.'lot~J ser.,e.tce Xet:~J ~s: ca.lleJ cortj~«-te-Sj"'tl"te-tv-tc.

;t )(e["'-J~x:Gtt]
J ct CD...,r,e~-vct l ~eJ se~. XotvtJ ;~ ccc.llecl ~"Jjt.tj'l+t"-cUoJi;l SJ&o1~e~r1c ;f x.[.,_] =-X:[-rtJ.
11\.,j ~t-{-vqv] Co'"'lf\ex- vet t"' eJ Seft.4~~ xt "l) COU, be Je..cowtf•~eJ \ "'t6
XLV\.)= Xe[~J + Xe[vt] vJhe-ve Xe[a.t) Wo~J Xo[vt] CJJrf j\ve,.., ~J

J(e [ "J ~ -±-- (x t>'~} + X 4 [->t1) .,.,J x.l'1]: ~ (xt01]- x•[-'1.] ).

Discrete-Time Signals
and Systems

This chapter reviews some of the basic principles and definitions of digital signal pro-
cessing. It uses several representations for signals, including functional expressions,
graphs, and sequences of numbers. Pictorial representations of signals are particu-
larly useful because they provide visual insight. Figure 2.1 graphically represents the
sequence x[n] as a function of the index n.

x[n]

Figure 2.1. Pictorial representation of a sequence z[n].

Equally important to a discussion of discrete-time signal processing is the concept

of a discrete-time system. Section 2.2 discusses discrete-time systems and means for
classifying them. Linear, time-invariant systems are highlighted because they have
special properties that make them relatively easy to analyze, implement, and design.

2.1 DISCRETE-TIME SIGNALS

A number of elementary signals appear frequently in signal processing applications.
Some of these are listed below and are pictured in Fig. 2.2.

33
34 Dlscret•Time Signals and Systems

• The unit sample or unit impulse

o[n] ~ { ol', ifn = 0

otherwise;

• The unit step

1 ifn~O
u[n] ~ { '
0, ifn < 0;

• The complex exponential

(wo is called the frequency);

• The sinusoid
sin[Won + Bo]
(wo is the frequency and 8o is the phase offset);
• The one-sided exponential
a 8 u[n],
where lal < 1 and u[n] is the step function.
These elementary signals play an important role in descnbing more complex signals.
For example, many useful signals can be expressed as weighted sums of damped ex-
ponentials or sinusoids. These and other elementary signals are examined in the ex-
ercises at the end of this section.

f I I I I ~-: "
1

• • • • • • •

(a) Unit impulse, c5(n) (b) Unit step, u(n)

• • • -• 1 f- I I T ! "' n n

(c) One-sided exponential (d) Sinusoid

Figure 2.2. Some common signals.

The signal processing literature is filled with many terms that describe signals.
These constitute a basic DSP vocabulary. These terms and acronyms are usually based
 Sec.2.1 Dlscret•nme Signals 35

on general characteristics of the signal. One such characteristic is whether the se-
quence is of finite or infinite length. A finite length sequence has a leftmost nonzero
sample and a rightmost nonzero sample. The unit impulse is an example of a finite
length sequence. An infinite length sequence extends infinitely far in one or both of
the two directions. The unit step, exponential, and sinusoid are all examples of infinite
length sequences.
Another useful signal characteristic is periodicity. A periodic sequence, x[n], is
infinite in duration and satisfies the relationship

x[n] = x[n + N] - oo < n < oo

for some N > 0 called the period. The period N is always restricted to be a finite pos-
itive integer. Signals that are not periodic are called aperiodic. Aperiodic sequences
may be of either finite or infinite duration and do not repeat indefinitely.
Signals can also be classified by whether their sample values are real or complex.
~though most signals encountered in applications are real, it is often useful to work
with complex signals in analyzing systems. Complex sequences can be represented in
terms of their real and imaginary parts, ~e{x[n]} and 9m{x[n]}, which are both real
sequences, or in t.erms of their magnitudes and phases, lx[n]l and Lx[n]. For a complex
sequence, x[n], these are defined by

x[n] ~ ~e{x[n]} + j 9m{x[n]}

~ lx[n]le;L:e(n)

The complex conjugate of x[n] is the sequence x•[n].

x• [n] ~ ~e{ x[n]} - j 9m{ x[n]}

~ lx[n]le-;L:e(n)

Chapter 6 explores complex sequences in greater detail.

Signals may also be classified as deterministic or random. Deterministic sequences
are sequences that can be expressed in a functional form. These include elementary
signals such as sinusoids, steps, ramps, and the like, and arbitrary sequences composed
of a weighted combination of element~ry signals. Random signals, on the other hand,
are probabilistic and "noise-like." The individual values in the sequence are less im-
portant than their distribution. VIrtually all of the signals examined here are deter-
ministic, but a few exercises at the end of this chapter and in the next focus on the
I generation of random signals and their properties.
Finally, signals may be classified according to their symmetry characteristics. Not
all signals are symmetric, but all signals can be decomposed into even and odd sym-
I metric sequences. Any arbitrary real sequence, x[n], can be viewed as having two
additive components: an even part, Xe [n] = ev{ x[n] }, defined as

Xe[n] = ~(x[n] + x[-n]);

I
I
38 Discrete-Time Signals and Systems

and an odd part, z 0 [n] = od{z[n]}, defined as

zo[n] = !(z[n] - z(-n]).

The sum of the even and odd parts results in the original sequence. This concept is
easily generalized to include complex signals of the form

z[n] = a[n] + jb(n]

where a[n] and b[n] are the real and imaginary parts, respectively. All complex se-
quences can be expressed as the sum of the four terms shown below

z[n] = ae[n] + ao[n] +j be(n] +j bo[n]

-..,...,
(2.1)
~ ~ ~
real-even real-odd imaginary-even imaginary-odd

where the subscripts e and o denote the even and odd parts, respectively. Examining
sequences in terms of their symmetry can sometimes greatly simplify their analysis and
enable difficult problems to be solved in a simple way.
Summations involving sequences often arise in analyzing discrete-time systems.
These summations can be expressed explicitly using the summation operator, E· How-
ever, in many cases these summations can be reduced to compact, closed-form expres-
sions. Three of these can be derived from the geometric series:

~ n_1-aN (2.2)
L-a - 1-a' V a,
n=O

where the symbol V denotes "for all";

00 1
"""an= - ,
L- 1-a
if lal < 1; (2.3)
n=O
and
00

""" a
L-nan = (1-a)2' if lal < 1. (2.4)
n=O

Equation (2.2) is valid for all complex values of the parameter a. Equation (2.3) is
obtained by taking the limit of (2.2) as N goes to infinity. This is subject to the con-
dition that lal < 1. Equation (2.4) is related to equation (2.3) by differentiation. The
exercises that follow explore some properties of sequences in more depth.

EXERCISE 2.1.1. Shifting and Reversing Sequences

Discrete-time signals are often expressed in terms of time-shifted and time-reversed
combinations of other signals.
 Sec.2.1 Discrete-Time Signals 37

(a) The signal, aa[n- N], is said to be time shifted by N where N is an integer. This
means that the signal, aa[n], is translated by N samples to the right if N > 0
and/or by INI samples to the left if N < 0. 1b illustrate this relatively simple con-
cept, consider the following exercise. Begin by displaying the S-point sequence,
aa[n], that may be found in the file aa using the x view function.
(I) Sketch aa[n].
(II) Sketch aa[n - 2].
(Ill) Sketch aa[n + 4].
Now check your sketches by using the computer. Use the x lshift function
to perform the time shifting. Note that specifying positive integers shifts to the
right; specifying negative ~tegers shifts to the left.
(b) The signal, aa[-n], is said to be time reversed. This means that the signal is flipped
about the point n = 0.
(I) Sketch aa[-n].
(II) If v[n] = aa[n- 4], sketch v[-n].
(ill) If r[n] = aa[n + 2], sketch r[-n].
Again check your sketches using the computer. Use the function x reverse to
perform the time reversal.

EXERCISE 2.1.2. Finite Length Sequences

The sequence
h[n] = u[n] - u[n - 10]
is a finite length sequence consisting of ones for n in the range 0 ~ n < 10 and zeros
everywhere else. It begins at n = 0 and ends at n = 9. Thus its length is 10 samples.
On the other hand, the sequence

h[n] = an u[n]

is an example of an infinite length sequence, because it contains an infinite number of

nonzero samples.
Several finite length sequences are listed below. Find the sequence lengths for
each of these sequences and determine their starting and ending points. This exercise
should be performed initially without the aid of the computer.

(a) x[n] = u[n - 2] - u[n - 12]

(b) v[n] = u[n + 16] - u[n - 7]
(c) y[n] = x[n] · v[n]
r[n] = x[n] + v[n]
I (d)
 38 Discrete-Time Signals and Syaterne

(e) s[n] = .z[n + 2] · v[n- 2]

(I) t[n] = y[n - 1] + y[n + 1]
You can check your answers on the computer by using the x siggen, x add, x
subtract, x lshift, and x multiply functions. For parts (a) and (b) the block
option in x siggen can be used to approximate a step function .
.
Comment. It is important to note that a true step is infinite in duration, but a long
block sequence can be used to approximate the step. A true step minus a shifted
step results in a block or pulse. If steps are represented as finite length blocks, the
difference between the block and shifted block produces erroneous sample values at
the end of the sequence. 1b avoid this difficulty in this exercise, use block sequences of
length 100 for the step functions. Before displaying your final result use x truncate
with L = 30 to remove the erroneous samples at the end of the sequence.
-EXERCISE 2.1.3. ~lementary Signals
This problem explores a number of discrete-time signals that commonly arise in
digital signal processing and provides a vehicle for becoming acquainted with the sig-
nal generator that will be used throughout this text. The signal generator can be exe-
cuted by typing x siggen. It can generate a variety of different signals.
A small set of elementary signals is needed in this exercise. To begin, create the
following signals of length 16 (0 ~ n ~ 15).
• b[n], a 16-point block sequence with unit amplitude.
• r[n), the first 16 points of the ramp function, defined as nu[n].
• t[n], 16 points of a periodic triangular wave with period 8, a maximum value of
one, and starting point n = 0.
• e[n], the first 16 points of the one-sided exponential, (5/6)nu[n).
Display and sketch them using x view. Signals aJ;e often formulated or expressed
in terms of elementary signals. Using the elementary signals just created, sketch the
following new signals:

(a) v[n] = r[n - 6) u[n];

(b) a[n] = { b[n)- b[n - 6], n < 10
0, otherwise;
(c) y[n] = e[n + 10] b[n];
(d) z[n] = t[n] (u[n]- u[n- 10]);
(e) ee[n] = ev{e[n]} (u[n + 5]- u[n- 5]);
(I) e0 [n] = od{e[n]} (u[n + 5]- u[n- 5]).

This should be done initially without the aid of the computer, but you may use the
functions x lshift, x subtract, x truncate, x reverse, and x view to
check your results.
 Sec. 2.1 Discrete-Time Signals 31

- EXERCISE 2.1.4. Time Axis Alteration

The time axis of a signal, x[n], can be altered to produce a new signal, y[n]. The
method of alteration can be as simple as a time shift, or it can be a more complicated
operation. A general time axis alteration can be expressed as

y[n] = x[/[n)]
where /[n] is the time axis alteration function. The value of /[n] must be an integer
because the time index for digital sequences is only defined for integer values. As a
simple example of time axis alteration, consider the problem of determining

y[n] = x[n - 6]
when
x[n] = u[n]- u[n- 5].
The sequence x[n] is simply shifted to the right by six samples to produce the sequence
y[n]. While this example poses no difficulty, determining the result of other alterations
may not be so easy. For example, consider sketching

y[n] = x[3 - n]
where /[n] = 3- n and x[n] is an arbitrary signal. A simple and systematic procedure
for determining y[n] = x[/[n]] can be summarized as follows:
1. Sketch x[n].
2. Sketch another time ~underneath it for y[n].
3. Write the expression for /[n].
4. 1b find y[O], evaluate /[0] (which will always be an integer). Next evaluate
x[/[0]] and enter this value for y[O] on the time axis for y[n] at the point n = 0.
5. 1b find y[1], evaluate /[1] and x[/[1]]. Set y[1] = x[/[1]] and enter it on the
y[n] time axis at the point n = 1.
6. Continue this procedure until all values, -oo < n < oo, of y[n] have been
found.
1b test your understanding, consider the sequence x[n] where
I x[n] = ur (u[n]- u[n- 5]).
I (a) Without the aid of the computer, sketch
using the procedure just described.
y[n] for each of the cases given below

(i) y[n] = x[-n].

I (ii)
(iii)
y[n] = x[-7- n].
y[n] = x[-n + 15].

I
I
 40 Discrete-Time Signals and Systems

(b) Develop a rule based on using the x lshift and x reverse operations that can
be used to obtain y[n] for each ofthe cases in part (a). Use x siggen to generate
the damped exponential sequence segment, x[n). Write a macro (as described in
Section 1.3) using the x reverse and x lshift functions that will produce y[n)
for each of the cases in part (a). Indicate the specific shift parameter values that
must be used in order for your macro to work properly. Check to verify that the
answers obtained manually agree with those produced by your macro.
(c) Manually sketch the sequence

y[n) = x[2n).

Check your answer by using the function x dnsample. By selecting M = 2 in

this function, you will be able to generate y[n).
(d) Sketch the sequence

y[n) = x[5 - 2n).

- EXERCISE 2.1.5. Working with Summations

Several useful closed-form expressions for summations exist, three of which are
given in equations (2.2-24). Summations, like integrals, can be changed to alternate,
but equivalent, forms through change-of-variables operations. This exercise should
be performed analytically (without the aid of the computer).

(a) Consider the expressions shown below:

00

at= L (it
n=O
c

00

" " (l)n-10

a2 = L..J 2 -
n=lO
00

a3= 2
5
L (it·
n=5

(i) Determine the numerical values of ah a2 , and a3.

(ii) Show by using a change of variables in the summation index or by another
approach that these summation expressions are related.
(b) Now consider these finite sums:

10
b1 = L:(it
n=O
 Sec.2.1 Discrete-Time Signals 41

0
~=a1 L 2n - i
n=-10

16
t>:J= a2 L: Ht
n=6
I o('l., '
10

b4 = aa L (~ t+ 2
• , 3 = Y
n=O

Determine the values for a 1, a 2, and a 3 so that

-EXERCISE 2.1.6. The Geometric Series

Many problems become straightforward if the mathematical equations used in the
problem descriptions are simplified. The signals shown below are expressed in terms
of summations. Determine a simplified expression for each sequence so that it can be
computed easily. Display and sketch each of these signals for the range 0 ~ n ~ 20.
Give the numerical values for the last three signal values (i.e., for n = 18, 19, 20) in
each case. (Hint: Use the geometric series expressions to transform the signals into
a convenient form.) Then use the computer to generate the final sequences using x
siggen, x add, x gain, and x multiply. Examine the requested numerical
values by either using a text editor or by typing the signal files to the screen.
(a)

x[n) = [~ m'- ~ m') u[n).

(b)

oo t . n t]
x[n] = [ ~(l + 1) (!) + ~ (i) u[n].
(c)

I x[n] =
n-10
t~o (i)t u[n].
]

(d)

x[n) = [~ t (().9)'] u[n).

Part (d) may require some careful thought.
I ~

"- (1-o<tt) 1
n·ot'~ 1 (n+l} ·o<"+ 1+o<
I L
~:o
I( . o( =:
o(

( l-o<)2.
-
tt·o(l\...

I -o(
- ~--=----;:.........;..~-:'"-----
(I -ad~.
 42 Dlserete-Time Signals and Systems

- EXERCISE 2.1.1. Characteristics of Signals

In the introductory discussion, several common signal characteristics were defined.
These included periodicity, signal duration, and the disposition of the sequence values
with respect to being purely real, purely imaginary, or complex.

(a) Consider the signal

x[n] = cos(Won).
(l) Assume wo = 1r /8. Is this signal periodic? If so, determine its period and
sketch one period of x{n].
(li) Now let wo = 1. Is the discrete-time signal, x[n], periodic? Now consider
the continuous-time signal,

x(t) =cost.
What is the period of this signal? Explain why the discrete-time and continu-
ous-time cosine signals behave differently.
(b) The signal

is infinite in duration. It is also complex valued. Generate a 40-point segment of

the sequence, x[n), where "-'0 = 1r /10. This can be done by using the exponen-
tial K eon option in x siggen with K = 1, alpha = 0 1r /10, and starting point
at zero. Display and sketch the real and imaginary parts and the magnitude and
phase of x[n) using x view. Note that the real and imaginary parts are cosine
and sine functions. This illustrates the relationship which is attnbuted to Euler:

eiwon = cos won + j sin won.

(c) Using the 40-point signal x[n] defined in part (b), manually sketch each of the
signals shown below:
Yo[n] = 110 x[n]l
Y1 [n] = Lx* [n]
Y2[n) = Re{jx[n]}
Y3[n] = 9m{(jx[n])*}.

Now verify your results using the computer. The x view function will allow
you to display the real and imaginary parts as well as the magnitude and phase.
The x gain function (with gain = 0 1} can be used to generate jxfn]; the x
conjugate function wi11 generate x*[n).
 Sec. 2.2 Dlacr8le-Time Syatema a
2.2 DISCRETE·TIME SYSTEMS
A discrete-time system can be viewed as a set of manipulations performed on one or
more sequences. This text will primarily consider single input single output systems,
since these represent the most common systems in traditional digital signal processing
applications. Figure 2.3 depicts a typical system with input x[n] and output y[n]. The
input/output relationship can be written as y[n] = T{x[n]} where T{·} denotes the
system operation. Systems are commonly diScussed and classified in terms of specific
properties, some of which are now defined:
• Additivity. A system is additive if

T{xl[n] + x2[n]} = T{x1[n]} + T{x2[n]}

for all real and complex inputs x1[n] and x2[n].
• Homogeneity. A system is homogeneous if

T{ax[n]} = aT{x[n]}
for aU complex values of a, and for all x[n).
• Linearity. A system is linear if it js both additive and homo&e;neous.
• Tune Jnvariance or Shift Jnvariance. A system is time invariant if a time shift in
the input results in time shifting the output by the same amount. In other words,
given that
y[n] = T { x[n]}

a time-invariant system must satisfy the condition

y[n- no] = T{x[n- no]}
.
for aU integers, no. and aU inputs, x[n].
• Stability. A system is unstable if there exists a bounded input (lx[n]l < oo for aU
n) that causes the output signal y[n) to be unbounded, i.e., jy[n]l = oo. Other-
wise the system is stable. 1
• Causality. A system is causal if the output at time n is not dependent on future
input samples. In other words, in a causal system output samples are only ob-
tained from past or present samples of the input. Future input samples cannot
be required to compute the output. For example, the system represented by the
difference equation
y[n] = x[n] + x[n + 1]

is not causal since x[n + 1] is a future sample of the input. To see this clearly,
assume that the present time is n = 1. Then y[1] = x[1] +x[2]. We see that y[1]
1This is called bounded input bounded output (BIBO) stability. There are other definitions of stability,
but they will not be treated in this text.
44 Discrete-Time Signals and Systems

requires that the present value x(1) and the future value x[2) be known. The
system

y[n) = x(n) + x(n - 1),

on the other hand, is causal because x[n) and x[n- 1) represent present and
past input samples, respectively.

_x[_~--~.~~---T-{·-}--~-~~_[n_J_
Figure 2.3. Block diagram representation of a system with input z(n) and output y(n].

Syst~ms that are both linear and time invariant (LTI) are of special significance
because they are well understood and can be conveniently analyzed in both the time
domain and the frequency domain. The following exercises are designed to help you
classify several unknown systems in terms of their properties. These systems, sys-
tem!, system2, and system3, are provided as part of the software. Execution
of these systems is best illustrated by an example. To execute system I, for example,
you should simply type

system I inputfile outputfile

EXERCISE 2.2.1. Testing Linearity I

Here you will work with an unknown system T {·}. Use x siggen to create a ramp
sequence x 1 [n) with a duration of five points in the range 0 ~ n < 5. Then create a
5-point sequence of ones, x 2 [n), also in the range 0 :5 n < 5 using the block option in
x siggen. For the first part of this exercise, use system I as the unknown system.
'I
• Generate y 1 [n) = T{xt[n)}.
• Generate Y2[n] = T{x2[n]}.
!I
• Generate y3 [n) = T{axt[n) + bx2 [n]} by using the x gain and x add func-
tions. Select arbitrary but convenient values for a and b.
I
(a) Examine the sequences ay1 [n) and by2 (n) for the same values of a and b. Does
system I appear to be
(i) homogeneous?
(ii) additive?
(iii) linear?
Explain your reasoning.
(b) Now repeat this exercise using system2 as the system T{·} .

..
 Sec. 2.2 Dlscret•Time Systems 45

Note that if a counterexample is found that violates the linearity tests, one can be
certain that the system is nonlinear. Proving that a system is linear based on this kind
of probing is not practical since the definition requires that the linearity conditions be
satisfied for all possible inputs.

EXERCISE 2.2.2. 'Jesting Time Invarlance

This exercise attempts to determine if a system T {·} is time invariant by observ-
ing the system's response to shifted inputs. Use aS-point ramp sequence, x[n], as
the input and the unknown system, system3, as the system to be tested. It can be
implemented by typing

system3 inputfile outputfile.

Compute yl[n] = T{x[n]}. Then use the x lshift function to generate the sequence
x[n -1]. Finally, compute Y2[n] = T{x[n -1]}, using system3.
(a) What is your conclusion about the time invariance of this system?
(b) Repeat this problem using systeml as the unknown system. Can you prove
that systeml is either time invariant or time varying based on your experi-
mentation?

EXERCISE 2.2.3. Linear Time-Invariant (LTI) Systems

The trial-and-error method that was used in the previous exercises can be effec-
tive in determining if a system is nonlinear or time varying if a counterexample can
be identified. However, it is very difficult to prove that an unknown system is linear
or time invariant following this approach. If the equation that describes the system is
known, we can determine with certainty whether a system is LTI. Based on the defi-
nitions, determine if the following systems with real inputs x[n] and outputs y[n] are:
(1) linear and (2) time invariant.

(a) y[n] = y'x[n] · x[n].

(b) y[n] = x[M].
(c:) y[n] = log21()z[nJ.
(d) y[n] = cos(x[n]) + cosn.
(e) y[n] = x[n] + x[n + 1] + x[n - 2].

EXERCISE 2.2.4. Stability

Unstable systems are characterized by the ability to produce output sample values
of infinite amplitude for bounded inputs. In practice, values of infinity cannot be rep-
resented, but an unstable system will often produce an output that saturates. This, in
tum, leads to erroneous outputs if processing is allowed to continue. The system
 I
48 Discrete-Time Signals and Systems

1
y[n) = z[n)
is reasonably well behaved except when the numerical value of z[n) is close to zero.
When x[n) = 0, the output is clearly infinite and therefore the system is unstable.
Consider the system described by the relationship

y[n) = e~lnl.

(a) Is this system stable?

(b) What numerical difficulties might be encountered in using this system?
(c) What is the approximate limit on the amplitude of the input for this system to
operate properly on your machine? Check this experimentally using the function
x nlinear to generate the signal e~lnl. One way to do this is to generate a
short block sequence (x[n) = 1) using x siggen. Use x gain to increase the
amplitude of x[n) until e~lnl saturates, i.e., results in an overflow error. You may
wish to begin by considering the range 600 < x[n) < 800.

EXERCISE 2.2.5. Stability of LTI Systems

For an LTI system with the impulse response, h(n), a simple stability criterion ex-
ists. If
00

L lh[nJI < oo
n=-oo

then the LTI system is stable. The impulse responses for several LTI systems are listed
below. Determine if they are stable.

(a) h[n) = 2"u[n).

(b) h[n) = 2"u[-n).
(c) h[n] = (10n)- 1 u[n- 1).
(d) h[n) = u(n)- u(-n).
(e) h[n] = 6-lnl.

EXERCISE 2.2.6. More on Stability

In this exercise, you will determine if a system is stable by examining the equation
that defines the system. The system input and output are x[n) and y(n], respectively.
For each of the systems shown below, analytically determine if the system is stable or
unstable. Note that some of these systems are not LTI. This exercise does not require
the use of the computer.

(a) y[n] = x[n- 1]· x[n]. ~ .. lx[... ],~l

...
''\; ·) ~
 Sec. 2.2 Discrete-nme Systems 47

(b) y[n] = x[n- 1]/x[n]. ~ WJ \X [ t'\J \ ~ 1

00
(c) y[n] = E x[n- k].
A:=O
00
(d) y[n] = E x[n- k]jk. X[.,)< t
A:=l , +~

<e> u[nJ = lx[nJ12. \ ~ \wCl~fr~~~L re

(f) y[n] = sin(x[n]).
EXERCISE 2.2.7. Causality
Causality is important in many practical systems, but it is critical in real-time sys-
tems. These are systems in which the input samples arrive sequentially and for which
I one output sample must be produced immediately after each input sample is received.
These systems must be causal because only present or past input samples are available
to be used to obtain the current output sample. This exercise does not require the use
I of the computer.

(a) To appreciate the importance of causality, consider the LTI system

I y[n] = x[n] + 2x[n- 1] + 3x[n- 2].

Assume that the input signal is zero for n < 0 and calculate the system output
I step by step by using the following steps:
(I) The first input sample (at time n = 0) is 1. What is the output y[O]?

I (il) The second input sample (n = 1) is 2. What is the output y[1]?

(iii) The next input sample (n = 2) is 3. What is the output y[2]?
aearly, there is no problem in determining the value of each output sample as
I each input sample is received. This is because this system is causal. By contrast,
consider repeating this exercise for the system

I y[n] = x[n] + 2x[n + 1] + 3x[n + 2] + 4x[n + 3].

It should be clear that it is not possible to determine y[O] at time n = 0, y[1] at
time n = 1, etc., because all of the quantities on the right side of this equation
I are not available when they are needed.
(b) A way to circumvent the causality problem is to introduce a system delay. In

I particular, consider the same noncausal system of part (a) with a three sample
system delay, i.e.,

I y[n] = x[n- 3] + 2x[n- 2J + 3x[n- 1] + 4x[n].

This is identical to the earlier system except that the output appears three samples

I delayed in time. Moreover, note that the new system is causal. If the input to the

I
 48 Discrete-Time Signals and Systems

system is x(n] = u(n] - u(n - 4], determine the first four samples of the output
analytically.
(c) The idea of using a system delay to make a noncausal system causal as discussed
in part (b) has limitations. For example, if
y(n] = x[n]x[ -n]
it is not possible to find a finite length delay to implement this system as a causal
one. Find another noncausal system for which a causal implementation cannot
be found by using a system delay.

2.3 CONVOLUTION
The impulse response of a system is the response of that system to a discrete-time im-
pulse or unit sample. The impulse response has particular significance when a system
is LTI because it completely characterizes the system. The impulse response provides
all of the information that is necessary to determine the output of an LTI system in
every situation. The output, y[n], of an LTI system is given by the convolution of the
input, x[n], with the system impulse response, h[n]. This operation can be written as
the convolution sum,
00

y[n] = L x[m] h(n- m]. (2.5)

m=-oo
It is common to use the shorthand notation
y[n] = x[n] * h(n] (2.6)
where the asterisk "•" denotes (linear) convolution.
Convolution appears extensively in signal processing. While it may be viewed as a
description of the input-output relationship for an LTI system, it can also be viewed
as an operation performed between two arbitrary signals. Using this viewpoint, con-
volution can be used as a tool for analyzing the properties of signals or the processes
that produced those signals.
Although it is not difficult to write a program to evaluate the convolution sum ex-
plicitly,~ alternate method called graphical convolution can provide valuable insight
into the convolution process. Using this approach, it is often possible to visualize the
result of a convolution by inspecting the input sequences. The method involves prop-
erly aligning the two sequences on a common time axis, multiplying them, and then
adding sequence values. The following exercises introduce convolution.

- EXERCISE 2.3.1. The Convolution Sum .

The definition of convolution is given in equation (2.5).

(a) Write a program, in any language that is supported in your computing environ-
ment, that will read in two sequences, convolve them, and write out the result.
 Sec. 2.3 Convolution 41

Use the signal format described in Section 1.2 in your program so that it will be
compatible with the other functions that are provided. 11y to make the program
as short and efficient as possible. Only a few lines of code should be needed for
the program.
(b) The fWtction x convolve, which is provided, also performs linear convolution.
Generate two ramp functions using x siggen, one of length 15 and the other
of length 10. Convolve these two seq.uences and provide a sketch of the two
inputs and the output. Now use your program from part (a) to perform the same
convolution and verify that your program works correctly.

- EXERCISE 2.3.2. An Interpretation of Convolution

This exercise presents another interpretation of the convolution operation. Care-
fully examine the convolution sum and observe that

c5(n) • x[n) = x[n),

I c5(n- 1) • x[n) = x[n- 1],
and
c5[n - 2) • x[n) = x(n - 2).
Generalizing this observation, it follows that

c5[n - no] • x[n) = x[n - no]

where no is an arbitrary integer. Now consider the simple convolution y(n) = aa(n] •
x[n) where
x[n) = c5[n] + c5[n- 1] + c5[n- 2] + c5(n- 3).

(a) The sequence aa[n) is provided for you in the file aa Use the block option of the
function x siggen to generate x [n). Sketch and display both of these sequences.
(b) Now create the four individual signals, c5[n), c5(n-l], c5[n- 2), and c5[n-3) using x
siggen. This can be done using the block option with different starting locations
for the length 1 sequences. Sketch these sequences.
(c) Using the x convolve function create the sequence y[n) = aa[n) • x[n) and
I J
sketch the result. j [Yl] =o(o( II'\.J -t "<'"(' l 111 -1 -to<o<l VJ- .z] -to(-<l VI- 3
J
(d) Again using the x convolve function, convolve aa[n) with each of the four
sequences that you generated in part (b). Sketch these individual sequences.
I (e) Add the resulting sequences from part (d) together using the x add function
and sketch the result. Use x view2 to compare the result with the result of part

I (b). Observe that the sum is identical to the sequence obtained by convolution.
 50 Dtscret•Time Signals and Systems

The important point here is that any input sequence can be represented as a superpo-
sition of delayed unit impulses. The output is then equal to the same superposition of
delayed unit impulse responses.
- EXERCISE 2.3.3. Introduction to Graphical Convolution
Graphical convolution is a straightf01ward and intuitive procedure to cwaluate the
convolution sum without the aid of a computer. The method is motivated by rec-
ognizing that the term h[n - m) in the convolution summation (2.S) can be inter-
preted as a signal in the variable m with n interpreted as a shift parameter. Since
h[n- m] = h[-(m- n)), it is a time-reversed copy of h[m) that is then shifted by n
samples on the m-axis. Thus, given h[n), h[n-m) can be obtained by first reflecting the
signal on the m-axis about the point m = 0 to form h[-m) and shifting it In! places to
the left if n is negative-or n places to the right if n is positive. This is illustrated in Fig.
2.4. The convolution at sample n can now be found by displaying x[m] and h[n-m) on
a common m-axis, multiplying the two aligned sequences on a point-for-point basis,
and summing the products. This exercise will walk through this procedure one step at
a time.

h[n) h[n -m)

• • • II I .
0 1 2 3
t • ..
n • •n-3 t! I I
n
• • .. m
Figure 2.4. The reflected impulse response of the convolution sum expressed as a sequence.

bb and
(a) First examine the sequences x[n) and h[n) that are provided in the files
cc, respectively, using x view. As you go through the procedure for the first
time, sketch each of the shifted signals on graphs that are aligned vertically.
(i) Reflect the sequence h[n) about the origin using the x reverse function.
Display and sketch your results. This is the signal h[-m).
(ii) To find h[no - m) at an arbitrary value n = no, shift the reflected sequence
no places to the right for no > 0 or lnol places to the left for no < 0. For this
example, begin by finding the value of y[2), i.e., no = 2. Use the x lshift
function to slide the reflected signal two places to the right. Display and
sketch your result.
(iii) Now that the two sequences h[m) and x[2 - m) are aligned, multiply them
pointwise using the x multiply function. Display and sketch your result.
(iv) Add all the sample values in the product sequence together and assign that
value to y[no] (in this case y[2]). Do this step manually by printing the signal
file to the screen. For this example, the correct value is -11. Therefore on
a separate sheet of paper, record y[2) graphically with a height of -11.
 Sec. 2.3 Convolution 11

(Y) Repeat this procedure for all values of n, -oo < n < oo. In practice it is
obviously not necessary to do this an infinite number of times when finite
duration sequences are being convolved. Observe that shifting the reflected
sequence too far to the left or right results in nonoverlapping sequences,
in which case the result of the multiplication is an all-zero sequence. It is
typical to start with the shift corresponding to the leftmost nonzero value of
the output and increment n until the convolution is complete.
(b) Given this step-by-step illustration of the procedure, determine and sketch the
complete sequence y(n]. Observe that y(n] is zero outside the range 0 $ n $ 7.
Moreover, observe that the total length of the output sequence is one less than
the sum of the lengths of the two sequences that are convolved. Use the function
x convolve to check your answer.
(c) Determine and sketch y(n] using graphical convolution by reflecting x(n] instead
of h[n]. Verify that your result is the same.

After this procedure becomes familiar, you should be able to reflect and align these-
I quences mentally to obtain a quick estimate of output values for simple convolutions.

- EXERCISE 2.3.4. Convolving Sequences

I In this exercise, discrete-time convolution is examined by example. Generate the
following sequences:
xt(n] = u(n]- u[n- 4], n. 0 1 I, 2, 3
x2[n] = u[n]- u(n- 6], r} - o 1 L, .. . , S
x3[n]=(l)"(u(n]-u[n-5]), rt-o,I, •.. J 4
x4(n] =sin(~; +f) (u[n]- u(n- 6]). t'\ 1
I .. S.
Notice that x 1 [n] and x 2 (n] are~point and~point blocks, respectively, and that they
can be created using x siggen. The signals x 3 (n] and x 4 (n] can be created using
options 5 arid 3, respectively. Test your intuition by performing the following convo-
lutions in your head using the graphical convolution method.
(a) Yt (n] = Xt (n] * x2[n];
(b) t12[n] = xt[n] * x3(n- 3];
I (c) Y3[n] = Xt (n] * x4(n];
(d) Y4(n] = x3(n] * x4(n].
I In each case provide a rough and quick sketch. How long are the resulting sequences?
Then check the accuracy of your result by performing the convolution operations using
x convolve and x lshift.
I -EXERCISE 2.3.5. More Convolution
Consider the sequences shown below:
 52 Discrete-Time Signals and Systems

2
vl[n] = L c5(n- 6m} J ._v -t S''[Y\- {; _.. ln 12]
m=O
3 2
V2[nJ=EEc5ln-6m-kl =u["'-1J -tV 1 [YJ-2 _.
k=lm=O

v3[n] = Ut (u[n]- u(n- 5]).

(a) Use x siggen to create these sequences. This can be done easily by using
options 8, 1, and 5. Alternatively, in the case of v. [n] you may wish to convolve a
block signal with an impulse train. Display and sketch each result.
(b) Using graphical convolution, sketch the following sequences as accurately as you
can.
(I) Yo[n] = vl[n] * v3[n];
(ii) 111 [n] = vi [n] * v1 [n] * v1 [n];
(iii) 112[n] = vl(n] * v2[n];
(iv) Ya[n] = va[n] * U2(n];
(v) Y4[n] = va[n] * va[n- 1].
(Note: For this case your sketch will probably be rather rough. However,
you should be able to capture the general shape of the output.)

Check your results using the computer.

- EXERCISE 2.3.6. Beginning and End Points
The convolution of two finite length sequences always results in a sequence of finite
length. Graphical convolution can be used to determine when the output sequence
begins and ends.
This exercise will use the following sequences:
(i) x[n] = u[n] - u[n- 50]; ~~-th 50 n == 0 : 4 ~
(il) v[n]=u[n-31]-u[n-42}; :1~ rt-3l:l\1
(iii) w[n]=u[n+51]-u[n+17]. :34-, t1=-51:-t«6
(a) Determine the first and last nonzero samples for each of the following:
(i) yl[n] = x[n] * v[n]; Qe-.1~-th · bO
(ii) 112[n] = v[n] * w[n]; 44
(iii) Ya[n] = x[n] * w[n]. g)
Use the computer to check your results. Derive a rule for determining the initial
and final samples for the convolution of two finite length sequences.
(b) Determine the initial and final samples for the following sequences without using
the computer:
 ;
'l
I
I
;
I
I
;
I
Sec. 2.3 Convolution 13 I
;
;
I
(I) Y4[n] = x[n] * z[n]; yt =- \40.%20:261 1 l h (1q)- \L-t \ I
I

(II) Ys[n] = v[n] * z[n]; tt .:: - \1..\0.l S., ; .2.S 3 , "'js) "" \ 4 \. 0 I.J) I
(Ill) Y6[n] =z[n] •w[n]. Vl_.:: -l"o.Stl: lqL\ 1 ~e."' -t ~ l;,)~ '1.\l.O{,(; I
[! ] . n :: -I L\ og 2..0. 12 where z[n] = u[n + 140820] - u[n - 213]. Note that ~e length of z[n] exceeds
I

,. · ' ~ the signal length limit of the software. Hence you cannot use the computer to il
" z.) -14 to~~ get the correct answer. .

EXERCISE 2.3.7. Convolution of Infinite Length Sequences i

Consider the sequences I
xt[n] = (!)n u[n]
I I

x2[n] = 2nu[-n}
xa[n] = u[n] - u[n- 10]. I I
{)sing graphical convolution, sketch the general shape of the following infinite length
signals.
l
(a)
(b)
Ya[n] = * x1 [n].
x1 [n]

Yb[n] = x2[n] * x2[n].

I
(c)
(d)
Yc[n] = x2[n] * xa[n].
Yd[n] = xt[n] * x2[n].
I
You can obtain an approximate check of your answer using x siggen to generate
finite length approximations (of 20 samples or so) to these signals and then convolv-
ing them together using x convolve. To generate x 2 [n] first create 20 samples of
I
(1/2)nu[n] using x siggen and then use x reverse.
EXERCISE 2.3.8. Using Graphical Convolution
1
l!
In this exercise, you are to obtain the value of the convolution of two sequences at !
one specific sample location. Consider the sequences i!
!
(i) x[n] = u[n] - u[n - 47]; !
!
(ii) v[n] = u[n + 28] - u[n - 10]; l
;
I (iii) w[n] = (it u[n]; j
I
(iv) r[n] = (i)lnl;
I
I (v) z[n] = (n + 12) (u[n + 12] - u[n- 30]).
Using the graphical convolution procedure and without the aid of the computer, de-
!
il
!
termine the values as indicated below. ll
I (a) If Ya[n] = x[n] * v[n], find Ya[10] and Ya[43]. I!
!
(b) If Yb[n] = x[n] * w[n], find Yb[40] and Yb[60]. !
I
!
!
l
I
I
l
I
I
I
54 Discrete-Time Signals and Systems

(c) If Yc[n] = v[n]• r[n], find Yc[-29] and Yc[-2].

(d) If Yc~[n] = w[n]• z[n], find yc~[l2].

EXERCISE 2.3.9. Algebraic Properties of Convolution

Several properties of convolution that are often exploited in discrete-time signal
processing are examined here. These properties will be examined by using the se-
quences x[n] and h[n], where ·

x[n] = n (u[n] - u[n - 32])

h[n] = 2n (u[n]- u[n- 26]).
(a) Show analytically that y[n] =x[n]• h[n] = h[n]• x[n] by changing the variables in
the summation in equation (2.5). Then verify that x[n]•h[n] = h[n]•x[n] by gen-
erating these sequences with x siggen and using the x convolve function.
The convolution operation is said to be commutative. Sketch y[n].
(b) Now split x[n] into two sequences ofthe same length (32 points), called xi [n] and
x2[n], such that x[n] = xi[n] + x2[n]. Provide a sketch of these two sequences.
Note that there are many choices for xi [n] and x2[n] that satisfy this condition. A
simple way to do this is to use x siggen to design two 32-point ramp functions
(perhaps with different slopes) that add to x[n]. Compute and sketch YI[n] =
xi[n] • h[n], 112[n] = x2 [n] • h[n], and y[n] = y1 [n] + 112[n]. Observe that y[n] is
exactly the same as x[n]• h[n] computed in part (a).
(c) Repeat the exercise performed in part {b), but with the condition that xi[n] and
x2 [n] are of different lengths. One way to do this is to let XI [n] be a truncated
version of x[n] and x2[n] be x[n]-x 1 [n]. Is the equal length condition a necessary
requirement? Convolution is said to be distributive with respect to addition.

EXERCISE 2.3.10. System Impulse Response

Knowledge of the impulse response of a system is important in digital signal pro-
cessing. Here you will find the impulse response of the system T {·} that is imple-
mented in systeml.

(a) Find and sketch the impulse response, h[n], of the system T{·}. Use the block
option of x siggen to create the impulse.
(b) Compute and sketch yi[n] = T{xt[n]} where xt[n] = 26[n- 3]. Use the state-
ment
systeml inputfile outputfile
to implement systeml and x siggen to generate XI [n]. _Compute and sketch
Y2[n] = xi[n] • h[n] using x convolve.
(c) Do the sequences yi[n] and y2[n] suggest that T{-} is LTI? Explain.
 Sec. 2.4 Difference Equations 51

2.4 DIFFERENCE EQUATIONS

There are many types of difference equations. The most common type in digital signal
processing is the linear constant coefficient difference equation or LCCDE. These can
be used to represent certain LTI systems. Assume that a system with input, x[n], and
output, y[n], is defined by an LCCDE of the form

y[n] + a1y[n- 1] + a2y[n ""'- 2] + · · · + aNy[n- N]

= box[n] + b1x[n- 1] + · · · + bMx[n- M].
This equation can be rewritten as the recursion

y[n] = -a1y[n- 1] - a2y[n- 2] - · · ·- aNy[n- N]

+ box[n] + b1x[n- 1] + · · · + bMx[n- M]
where a11 a2, ... , aN and bo, b11 ... , bM are the constant coefficients. To specify the
output uniquely we must also specify N initial sample values of y[n]. If the system is
causal and its output samples are to be evaluated beginning at n = 0 (i.e., y[n] is to be
evaluated for n = 0, 1, ... ), then the sample values

y[-1], y[-2], ... , y[-N]

must be prespecified. These are called the initial conditions. Once the initial condi-
tions are given, the output samples can be computed sequentially. When these initial
conditions are assumed to be zero, LCCDEs can define causal, linear, time invariant
systems for inputs that are zero for n < 0. These difference equations are commonly
used to implement discrete-time LTI systems. LCCDEs are discussed further in Chap-
ter 5.

EXERCISE 2.4.1. Evaluating a Difference Equation

In this exercise you will evaluate the output of a causal LTI system specified by the
simple difference equation

y[n] = iu[n- 1] + x[n] + 2x[n- 1]

with zero initial conditions. Assume that the input is

x[n] = D[n] + D[n- 1].

A convenient way to evaluate the output samples without a computer is to arrange the
computation in a chart.

I n x[n] x[n-1] y[n- 1] y[n]

n= -1 x[-1] = 0 x[-2] = 0 y[-2] = 0 y[-1] = 0
n=O x[OJ = 1 x[-1] = 0 . y[-1] ='0 y[O] = 1
n=1 x[1] = 1 x[O] = 1 y[OJ = 1 y[1] = 3.5
.
 58 Discrete-Time Signals and Systems

Since this system is linear and causal, no nonzero output sample is produt.ed until a
nonzero input sample is received. The input in our example begins at n ::= (II. There-
fore all samples in the output sequence will be zero until this time and tbedw"t can
begin at n = 0. On the line corresponding ton= 0, x(O] = 1 and x[-1] = *1] = 0.
Substituting these values into the difference equation gives y(O] = 1. This pocedure
can be continued by going to the next line, entering the values for y(O], x[fj;., 1Uld x(O],
and then evaluating y(1] using the difference equation and continuing simillarly until
all the desired samples of y(n] have been computed.

(a) Following this procedure, fill in the lines for n = 2, 3, 4. The column 811 the chart
labeled y(n] is the system output.
(b) A computer is ideally suited to evaluate the output samples specified by a dif-
ference equation. Use x siggen to create the input, then use x Jccde to
compute the output. Record the first seven values of y(n] by typing abe output
file to the screen.

EXERCISE 2.4.2. Convolution Versus LCCDEs

LCCDEs with zero initial conditions are often used to implement L'fl systems.
Consider the causal LCCDE
y(n] = ~y[n - 1] + x(n]
I
with input x(n] and output y(n].

(a) Determine the impulse response, h(n], of this system by evaluating the difference
equation using an impulse as the input and zero for the initial condition at n =
-1. The function x siggen can be used to create the impulse and the function
-
x lccde will implement the difference equation. The impulse respoJJJe has the
form
h(n] = o."u(n]. }3
What is the value of o.? Note that we can implement this system even though its
impulse response is infinite in duration.
1
(b) In part (a) you found the impulse response and observed that it was infinitely { 2._ ~
long. If it can be assumed that all values of h(n] less than 0.001 are negligible = 0
and can be ignored, what is the effective length of h(n]? You may find it more
convenient to read the sequence amplitude values by typing the signal file to the ·*"" [.
screen or by using a text editor rather than by using x view. Generate this finite
length version of h(n] and the sequence I [ J _(
2.!)., f [
.,_tY ~ .- 31 z_ti [t'lj-
x(n] = u(n] - u(n - 6]
using x siggen. Compute and sketch x(n] * h[n].

I -.J c~ ;: ~ [~J + ~H~E· -1..\ .f •• ~trf -sJ= r

I
()

il
 Sec. 2.4 Difference Equations 17

(c) Now implement the convolution in part (b) explicitly using a difference equation.
Use the x lccde function with zero initial conditions. Compare your results
with the sequence obtained by convolution. By using the function x subtract
display and sketch the difference between the two results. How many multiplies
and adds are required on average to obtain each output sample using both of
these methods?

EXERCISE 2.4.3. The First Backward Difference

The discrete-time first backward difference operation is similar to taking the deriva-
tive of a continuous-time signal in certain respects. It takes the difference between the
current sample of x[n] and the previous one, i.e.,

y[n] = x[n] - x[n - 1]. (2.7)

It corresponds to an LTI system with the impulse response
h[n] = c5[n] - c5[n- 1]. (2.8)
Th explore this operation, this exercise will consider the effects of the first backward
difference operation on several sequences. Th begin use the create file option in x
siggen to create a file containing h[n].
(a) Sketch the continuous-time function,

tria(t) = t u(t)- 2(t- 20) u(t- 20) + (t- 40) u(t- 40).

Note that this is a continuous-time triangular function beginning at t = 0 and

ending at t = 40, with a peak value at t = 20. In addition, sketch the continuous-
time square pulse,

S<Ja(t) = u(t)- u(t- 20).

Now compute (by inspection) and sketch the first derivative of each of these
continuous-time waveforms.
(b) Generate the 41-point triangular pulse

tri[n] = nu[n]- 2(n- 20) u[n- 20] + (n- 40) u[n- 40].
This can be done easily using the triangular wave option in x siggen by specify-
ing the period to be 40 and the number of periods to be one. In addition, generate
and sketch the square pulse

sq[n] = u[n] - u[n- 20].

Use the square wave option in x siggen with pulse length 20, period 40, and
number of periods 1. Now compute and sketch the first backward difference
58 Discrete-Time Signals and Systems

of each of these signals using either x lccde to implement the system using
equation (2.7) or x convolve. Note the similarity to the continuous-time case.
The function x view2 may be used to display the signal and its first backward
difference one above the other. In many cases the first backward difference is
used as an approximation to a derivative operator.

EXERCISE 2.4.4. The Running Sum .

The discrete-time running sum operation is in many ways analogous to continuous-
time integration. The running sum of a sequence x[n] is defined by
n

y[n] = L x[k].
A:=-oo

It is a linear, time-invariant operation that can be implemented as a difference equa-

tion. If the input is x[n] and the running sum output is y[n], then

y[n] = y[n- 1] + z[n]

where zero initial conditions are assumed. This exercise will consider the performance
of the running sum operation on several elementary sequences.
I
(a) Consider the continuous-time signals: I
s<t&(t) = u(t)- u(t- 20),
6
imp4 (t) = L6(t -10k),
I
A:=O
and
cos( ft).
Sketch each of these signals and also the signals that you would expect to obtain
by integrating each of them.
(b) Generate the following discrete-time signals:
(i) One period of a square wave, :JI
sq(n] = u[n] - u(n - 20].
Do this by using the square wave option in x siggen with the pulse length
specified to be 20 and the period 128.
(ii) Six periods of the impulse train,
6
imp[n] = L 6[n- 10k].
k=O
This can be done using the impulse train option in x siggen with period
10.
 Sec. 2.4 Difference Equations 51

(Ill) A sine wave of the form

sin(~n).

Generate this sequence by using the sine wave option in x siggen with
alpha =1r /40, phi = 0 and length = 128.

Evaluate and sketch the running sum of each of these signals. Compare these
results with the results found for the continuous-time case in part (a). You should
observe that the running sum performs like a discrete-time integrator.

- EXERCISE 2.4.5. Nonlinear Difference Equations

The class of nonlinear difference equations is extremely broad, but its use is often
limited by the lack of a well-developed theory for nonlinear systems. This exercise
explores a nonlinear difference equation that generates a Gaussian sequence of the
form
/[n) = exp( -a(nr) 2 ) (2.9)
where a is positive. For this exercise, assume a = 1 and r = 0.02.

(a) Generate the Gaussian function described by equation (2.9) for n = 0, 1, 2, .. . ,

99. Do this by using the ramp option in x siggen and the x gain function
to generate nr, the x nlinear and x gain functions to form -a(nr )2 , and x
nlinear to perform the exponentiation. Sketch and display your results.
(b) Write a program for evaluating this same function using the nonlinear difference
equation (or recursion)
fro1=t
P[n]
f[n + 1] = c /(n _ 11 f [-1}" e_)(~ (-olT'-)
where c = exp( -2ar 2 ). This recursion is due to Teager (see Kaiser [1}). The
two required initial conditions, /(-1] and /[0), can be obtained directly from
the Gaussian function. Evaluate the function over the range 0 :$ n :$ 511 and
sketch the result. Your computer program may be written in any language that
you choose.
(c) Kaiser [1] has shown that Thager's difference equation can be expressed as the
I following pair of first-order nonlinear difference equations

h[n + 1] = c h[n]
I f[n + 1] = h[n + 1] /[n].
To begin the recursion, a value for h[O] is needed. Observe from the equation
that h[O] = /[0]//[- 1]. The initial conditions for f[n] can be obtained from
equation (2.9). Write a program that implements this simple pair of equations
and evaluate the Gaussian as in part (b). Compare the results in all three cases.
What is the maximum error?

I
 80 Dlacret•Time Signals and Syatema

-EXERCISE 2.4.6. Autocorrelation

In some applications, such as radar signal processing, seismic analysis, and signal
enhancement, an information-bearing signal is obscured by some form of noise. The
goal is to estimate certain signal characteristics from the corrupted signal. This ex-
ercise will examine autocorrelation as a procedure for determining the period of a
quasi-periodic sequence that is embedded in additive noise.
The autocorrelation of a real signal v(n) is defined as
00

.A[n] = L v(n + m) v(m).

m=-oo

It is related to the convolution of v(n] with itself, since

.A(n) = v(n) • v[-n).

A[n) provides a mc:asure of similarity for different alignments of the signal.

(a) Generate 128 points of the sequence x(n), where

x(n) =!sin( ~n) + sin(;.n),

using the sine wave option in x siggen and the x add function. Next, generate
128 samples of a random noise sequence r[n) using x rgen. Use x gain and
x add to generate the sequence
y(n) = x[n) + 3r(n)
that will serve as the noisy signal. Examine x(n) using the x view function
and determine the period of this signal. Now examine y(n] using x view and
observe that it is difficult to determine the period by inspection.
(b) The autocorrelation function can be used to estimate the periodicity of the signal
'x[n). In part (a) you determined the period of x[n] by inspection. Compute the
autocorrelation of x(n) using x reverse and x convolve and sketch your
results. Using the concept of graphical convolution, explain why peaks in the
autocorrelation function appear at values of n that are multiples of the period.
(c) The autocorrelation function can be used to estimate the periodicity of the signal
x(n], given the noisy signaly(n]. Specifically, the distance between the peak at the
origin and either of the adjacent peaks in the autocorrelation function gives an
estimate of the period of x(n). Display and sketch the autocorrelation function
of y(n] and estimate the period of the underlying signal x[n).

-EXERCISE 2.4.7. Cross Correlation

Cross correlation can be viewed as a generalization of autocorrelation. The cross
correlation of two real sequences v[n] and w[n) is defined as
 Sec. 2.4 Difference Equations 11

00

i)[n] = L v[n + m] w[m].

m=-oo

If v[n] and w[n] are equal, the cross correlation and autocorrelation are identical.
Cross correlation also has a convolutional interpretation,

i)[n] = w[nj • v[-n].

It can be used to determine when two sequences are best aligned in time. For example,
if x[n] and v[n] are two different but similar sequences, one may wish to determine
which value of l results in the best approximation

x[n] ~ v{n + l].

This can be done by computing the cross correlation and looking for the time index, n,
of the maximum peak of i)[n]. To examine this point further, create the sequences x[n]
and v[n] where x[n] is a random finite length sequence that is nonzero in the range
-32 :5 n :5 32. Let
v[n] = x[n] • h[n]
where h[n] is a 15-point lowpass filter with cutoff frequency of 21r /3 and starting point
zero. Use x rgen to create x[n] and x lshift to shift the starting point to -32. The
Hamming window option in x fdesign can be used to create h[n].
(a) Use x view2 to display and sketch x[n] and v[n]. These signals are not the same
but are similar in terms of their distribution of samples. Such sequences have a
degree of correlation as defined by their cross correlation function. Now com-
pute and sketch i)[n]. Identify the index n corresponding to the peak in i)[n]. Th
simplify the task of finding the peak location, use the x extract function to ex-
I tract the 20-point block in i) [n] beginning at -10. Write this block to a sequence
file that also begins at -10 and display it. By examining the extracted sequence
file, you will be able to determine the peak location by inspecting the display.
This location provides an indication of how much displacement is necessary for
v[n] to be most nearly aligned with x[n]. Based on your examination of the peak
location, by how many samples should v[n] be shifted to produce the best align-
I ment between the sequences? Check your answer by shifting v[n] by that amount
and visually comparing it to x[n]. Approximately how many multiplies and adds
are required to compute the cross correlation in this example?
(b) In this part, a method for increasing the efficiency of computing the cross correla-
tion function is examined. Quantize each of the sequences into binary sequences
in the following way:

1 if x[n] ~ 0
x[n] =
4 {

-1 if x[n] < 0
I
I
 82 Discrete-Time Signals and Systema

v(n] ~ 0
v[n] < 0.
Use the x quantize function to do this with min = -1 and max = 1 and the
number of levels equal to two. Compute the cross correlation function of z(n]
and v(n]. Use x view2 to display this cross correlation function and the one
in part (a) simultaneously. What is the required shift in v(n] to produce the best
alignment using this approach? How many multiplies and adds are required?
How do the methods in parts (a) and (b) compare? (Note: Multiplication by +1
or -1 should not be counted as a multiply.) You will not observe any speedup
in the software that is provided because those programs do not check to avoid
multiplications by ±1.
(c) 1\vo random signals generated with different seed values should not bear any sim-
ilarity to each other and are said to be uncorrelated. Consequently, they should
not produce a cross correlation function with a dominant peak indicating a pre-
ferred alignment. Use x rgen and x lshift as before to create another random
sequence, y(n], (with a different seed) in the same range. Display and sketch the
cross correlation of z(n) and y(n). Observe that there is no dominant peak that
clearly marks a "best alignment" between the two sequences.

-EXERCISE 2.4.8. Random Sequences

It is often important to generate a random sequence of numbers that has a Gaus-
sian distribution instead of a uniform distribution. There are many methods available
for doing this. A simple one that transforms a uniform random sequence into a Gaus-
sian random sequence is investigated here.
The central limit theorem states that the sum of N identically distn'buted, inde-
pendent random variables approaches a Gaussian distribution in the limit as N goes
to infinity.

(a) Generate a uniform random sequence z 1 (n) of length 128 usingx rgen. Use the
x gain function to multiply the sequence by 100 to produce a random sequence,
y(n), with amplitude values in the range -50 to 50. 1b examine the distribution
of y(n), compute and display its histogram using x histogram and x view.
The histogram is a plot of sample amplitude on the z-axis versus the number of
occurrences of that amplitude on the y-axis. If the histogram is roughly flat, the
sequence is said to be uniformly distributed.
(b) Now generate eight additional random sequences z2[n), z3(n), ... , zg(n). Add
the sequences z 1 (n], ... , x 9 (n) together using x add to form Y2(n]. Multiply
y2 (n] by 11 so that its amplitude range will be from -50 to +50. Display and
sketch the histogram of the new sequence. Does this distnbution more closely
resemble that of a Gaussian random sequence?

- EXERCISE 2.4.9. Gaussian Random Sequences

This problem considers a different method for creating a Gaussian sequence [2]
with a specific standard deviation u. With this method, a uniform random sequence
 Sec. 2.5 References 83

0 < XI [n] ~ 1 is first transformed into a Rayleigh-distributed random sequence r[n]

by the relation

r[n] = 2u21n (xt~n]}

1\vo uncorrelated (and therefore independent) Gaussian random variables, 9I[n] and
92[n] can then be formed using the equations

9I[n] = r[n] cos(21rxt[n + 1]},

92[n] = r[n] sin(21fxi [n + 1]}.
The standard deviation is the value of u used to generate r[n].

(a) Write a macro that will accept a uniform random sequence as its input and pro-
duce 9I[n] and 92[n] as its outputs. The functions x divide, x log, x mul-
tiply, x lshift, and x nlinear will be helpful in computing r[n]. Use your
macro to generate 9I[n] and 92[n] with u = 1 and length 1024. List all necessary
functions and intermediate signal files in your macro. Note that the random sig-
nal XI [n] should have an amplitude range between 0 and 1. Therefore you should
add a block sequence with amplitude .5 to the random sequence generated by
x rgen in constructing xi [n].
(b) Determine the maximum absolute value A for 9I[n] and 92[n]. Multiply each
by 1000/A so that the amplitude range of each signal will be between -500 and
+500. Now compute the histogram of 9I [n] and 92[n] and sketch the results.
Does this distnbution appear to be Gaussian?
(c) Cross correlation was introduced in Exercise 2.4.7. Compute the cross correla-
tion function for 9I [n] and 92[n]. Do these sequences appear to be uncorrelated?
Justify your conclusion.

2.5 REFERENCES

[1] J. E Kaiser, "On the Fast Generation of Equally Spaced Values of the Gaussian
Function A exp (-at* t)," IEEE Transactions on Acoustics, Speech, and Signal
Processing, Vol. ASSP-35, No. 10, pp. 1480-1481, Oct. 1987.
[2] L. Rabiner and B. Gold, Theory and Application ofDigital Signal Processing, Prentice-
Hall, Englewood Cliffs, NJ, 1975.