An Introduction to Digital Signal Processing John H. Karl Department of Physics and Astronomy The University of Wisconsin-Oshkosh Oshkosh, Wisconsin Academic Press, Inc. Harcourt Brace Jovanovich, Publishers San Diego New York Berkeley Boston London Sydney Tokyo Toronto Copyright © 1989 by Academic Press, Inc. All Rights Reserved. No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Academic Press, Inc. San Diego, California 92101 United Kingdom Edition published by Academic Press Limited 24-28 Oval Road, London NW1 7DX Library of Congress Cataloging in Publication Data Karl, John H. An introduction to digital signal processing / by John H. Karl. p. cm. Includes index. ISBN 0-12-398420-3 (alk. paper) 1. Signal processing—Digital techniques. I. Title. TK5102.5.K352 1989 621.38*043-dcl9 88-26822 CIP Printed in the United States of America 89 90 91 92 9 8 7 6 5 4 3 2 1 To Karen Preface This book is written to provide a fast track to the high priesthood of digital signal processing. It is for those who need to understand and use digital signal processing and yet do not wish to wade through a three- or four-semester course sequence. It is intended for use either as a one-semester upper-level text or for self-study by practicing professionals. The number of professionals requiring knowledge of digital signal process­ ing is rapidly expanding because the amazing electronic revolution has made convenient collection and processing of digital data available to many disciplines. The fields of interest are impossible to enumerate. They range widely from astrophysics, meteorology, geophysics, and computer science to very large scale integrated circuit design, control theory, communications, radar, speech analysis, medical technology, and economics. Much of what is presented here can be regarded as the digital version of the general topic Extrapolation, Interpolation, and Smoothing of Stationary Time Series, a title published in 1942 by the famous Massachusetts Institute of Technology mathematician Norbert Wiener. This original classified Depart­ ment of War report was called "the yellow peril" by those working on the practical exploitation of this theoretical document. The nickname came from the report's frightening mathematics, lurking within a yellow book binding. Since the report became available in the open literature in 1949, many works have followed, including textbooks on many facets of the subject. Yet topics important for the digital implementation of these ideas have not been made available at an introductory level. This book fills that gap. To minimize the required mathematical paraphernalia, I first take the view­ point that the signals of interest are deterministic, thereby avoiding a heavy reliance on the theory of random variables and stochastic processes. Only xi xii Preface after these applications are fully discussed do I turn attention to the nondeter- ministic applications. Throughout, only minimal mathematical skills are required. The reader need only have a familiarity with differential and integral calculus, complex numbers, and simple matrix algebra. Super proficiency is not required in any of these areas. The book assumes no previous knowledge of signal processing but builds rapidly to its final chapters on advanced signal processing techniques. I have strived to present a natural development of fundamentals in parallel with prac­ tical applications. At every stage, the development is motivated by the desire for practical digital computing schemes. Thus Chapter 2 introduces the Z transform early, first as a simple device to represent advance and delay operators and then as an indispensable tool for investigating the stability and invertibility of computational schemes. Likewise, the discrete Fourier transform is not introduced as an independent mathematical entity but is developed quite naturally as a tool for computing the frequency response of digital operators. The discrete Fourier transform then becomes a major tool of digital signal processing, connecting the time and frequency domains by an efficient computing algorithm, the fast Fourier transform. The idea of a data model is threaded throughout much of the discussion. Since continuous functions are an underlying model for many sampled data, Chapter 6 is devoted to the continuous Fourier transform and Chapter 7 addresses its all-important relationship to discrete data. Using the fundamental concepts developed in these early chapters, each of the last five chapters covers a topic in digital signal processing that is rich in important applications. The treatment of each is sufficiently detailed to guide readers to practical solutions of their own signal processing problems and to enable them to advance to the research literature relevant to their applications. Much effort has been spent in making the text as complete as possible, avoiding distracting detours to references. Consequently, few references are included. Those that are included, however, provide the tip of a rapidly expanding pyramid of references for readers desiring further study. Problems at the end of each chapter reinforce the material presented in the text. Because many of these problems include practical computing applications, it would be best if the book were read with at least a small com­ puter available to the reader. Computer routines are presented in a psuedo- FORTRAN code for all of the fundamental processing schemes discussed. My purpose is not to provide commercial-grade digital signal processing algorithms; rather it is to lay open the utter simplicity of these little gems. Then, armed with a sound understanding of concepts, readers with a working knowledge of computer coding will be able to quickly adapt these central ideas to any application. Preface xiii I greatly appreciate the patience of my students, who suffered through using the manuscript in its developmental stages. Sue Birch is gratefully acknowl­ edged for helping draft the figures and for being a pleasure to work with. I especially extend my greatest appreciation to Joan Beck for typing the manuscript, which required a multitude of corrections and changes, and for cheerfully tolerating all my ineptness. Any remaining errors are my respon­ sibility, not hers. John H. Karl 1 Signals and Systems The feeling of pride and satisfaction swelled in his heart every time he reached inside the green, felt-lined mahogany box. At last the clouds were breaking up, so now Captain Cook reached for the instrument, exquisitely fashioned from ebony with an engraved ivory scale and hand-fitted optics mounted in brass to resist the corrosive environment of the sea. With mature sea legs, he made his way up to the poop deck of the Resolution. There the sun was brightening an aging sea—one whose swells still remained after the quieting of gale force winds. James Cook steadied himself against the port taffrail. His body became divided. Below the waist he moved with the roll of the ship; above it he hung suspended in inertial space. Squinting through his new Galilean ocular, he skillfully brought the lower limb of the noon sun into a gentle kiss with the horizon. As always, Master Bligh dutifully recorded the numbers slowly recited by the navigator as he studied the vernier scale under the magnifying glass. At first the numbers slowly increased, then seemed to hover around 73 degrees and 24 minutes. When it was certain that the readings were decreasing, Cook called a halt to the procedure, took Bligh's record, and returned to his cabin below deck. After first returning his prized octant to its mahogany case, the navigator sat at his chart table, carefully plotting Bligh's numbers in search for the sun's maximum altitude for use in computing the Resolution's latitude. Next course and estimated speed were applied to the ship's previous position to produce a revised position of 16° 42' north latitude and 135° 46' west longitude. A line drawn on the chart with a quick measurement of its azimuth produced a beckon to Bligh: (<tell the helmsman to steer west northwest one-quarter west." 1 2 1/ Signals and Systems This one example from the cruise of the Resolution includes analog to digital conversion, interpolation, extrapolation, estimation, and feedback of digital data. Digital signal processing certainly extends back into history well before Cook's second voyage in 1772-1775 and was the primary form of data analysis available before the development of calculus by Newton and Leibnitz in the middle of the seventeenth century. But now, after about 300 years of reigning supreme, the classical analytical methods of continuous mathematics are giving way to the earlier discrete approaches. The reason, of course, is electronic digital computers. In recent years, their remarkable computing power has been exceeded only by their amazing low cost. The applications are wide ranging. In only seconds, large-scale super computers of today carry out computations that could not have been even seriously entertained just decades ago. At the other end of the scale, small, special-purpose microprocessors perform limited hard-wired computations perhaps even in disposable environments—such as children's toys and men's missiles. The computations and the data they act on are of a wide variety, pertaining to many different fields of interest: astrophysics, meteorology, geophysics, computer science, control theory, communications, medical technology, and (of course) navigation—fundamentally not unlike that of James Cook. For example, a modern navigation system might acquire satellite fixes to refine dead reckoning computations derived from the integration of accelerometer outputs. In modern devices, the computations would act on digital data, just as in Cook's day. In the many examples given above, the data involved can have different characteristics, fundamentally classified by four properties: analog, digital, deterministic, and innovational. These properties are not all-inclusive, mutually exclusive, nor (since all classification schemes contain arbitrary elements) are they necessarily easy to apply to every signal. We will now discuss these four properties of signals, considering that the independent variable is time. In fact, for convenience throughout most of the book, we will take this variable to be time. But, it could be most anything. Our signals could be functions of spatial coordinates x, y, or z; temperature, volume, or pressure; or a whole host of other possibilities. The independent variable need not be a physical quantity. It could be population density, stock market price, or welfare support dollars per dependent family. Mostly we will consider functions of a single variable. An analog signal is one that is defined over a continuous range of time. Likewise its amplitude is a continuous function of time. Examples are mathematical functions such as a + bt2 and sin (cot). Others are measured physical quantities, such as atmospheric pressure. We believe that a device designed to measure atmospheric pressure (such as a mercurial barometer) will have a measurement output defined over a continuous 1/ Signals and Systems 3 range of times, and that the values of this output (the height of the mercury column) will have continuous values. When sighting the barometer's col­ umn, any number of centimeters is presumed to be a possible reading. A meteorologist might read the barometer at regular periods (for exam­ ple, every four hours) and write the result down, accurate to, for example, four decimal digits. He has digitized the analog signal. This digital data is defined only over a discrete set of times. Furthermore, its amplitude has been quantized; in this example, the digital data can only have values that are multiples of 0.01 cm. A digital signal specified at equally spaced time intervals is called a discrete-time sequence. We see that our definitions of analog and digital signals include two separate and independent attributes: (1) when the signal is defined on the time scale and (2) how its amplitude is defined. Both of these attributes could have the continuous analog behavior or the quantized discrete be­ havior, giving rise to four possibilities. For example, we might record values of a continuous-time function on an analog tape recorder every millisecond. Then the resulting record has analog amplitudes defined only at discrete-time intervals. Such a record is called sampled data. Another combination is data that are defined over continuous time, but whose amplitude values only take on discrete possibilities. An example is the state of all the logic circuits in a digital computer. They can be measured at any time with an oscilloscope or a logic probe, but the result can only take on one of two possible values. Generally speaking, in our work we will either be considering con­ tinuous signals (continuous values over a continuous range of time) or digital signals (discrete values over a discrete set of time). The other aspect of signals that we wish to consider is their statistical nature. Some signals, such as sin(wr), are highly deterministic. That is, they are easily predictable under reasonably simple circumstances. For exam­ ple, sin(cot) is exactly predicated ahead one time step At from the equation U = aU - U (1.1) t+2At t+At t if we know the frequency (o of the sinusoid and only two past values at 0 t + At and t. You can easily verify that Eq. (1.1) is a trigonometric identity if a = 2cos(coAt) and U = Asin(oot+ cj>). An interesting and significant 0 0 property of Eq. (1.1) is that its predictive power is independent of a knowledge of the origin of time (or equivalently, the phase </>) and the amplitude A. Hence it seems reasonable to claim that sinusoids are very predictable, or deterministic. On the other hand, some signals seem to defy predication, no matter how hard we may try. A notorious example is the Dow Jones stock market indicator. When a noted analyst was once asked what he thought the market would do, he replied, "It will fluctuate." When these fluctuations 4 1/ Signals and Systems defy prediction or understanding, we call their behavior random, stochas­ tic, or innovative. Some call it noise-like as opposed to deterministic signal-like behavior. There are many other examples of random signals: noise caused by electron motion in thermionic emission, in semiconductor currents, and in atmospheric processes; backscatter from a Doppler radar beam; and results from experiments specifically designed to produce ran­ dom results, such as the spin of a roulette wheel. Many of these random signals contain significant information that can be extracted using a statis­ tical approach: temperature from electron processes, velocities from Dop­ pler radar, and statistical bias (fairness) from the roulette wheel. It is not universally recognized that it is not necessarily the recorded data that determines whether a certain process is random. But rather, we usually have a choice of two basically different approaches to treating and interpreting observed data, deterministic and statistical. If our understand­ ing of the observed process is good and the quantity of data is relatively small, we may well select a deterministic approach. If our understanding of the process is poor and the quantity of data is large, we may prefer a statistical approach to analyzing the data. Some see these approaches as fundamentally opposing methods, but either approach contains the poten­ tial for separating the deterministic component from the nondeterministic component of a given process, given our level of understanding of the process. For example, the quantum mechanical description of molecules, atoms, nuclei, and elementary particles contains both deterministic and statistical behavior. One question is, can the behavior which appears statistical be shown, in fact, to be deterministic via a deeper understanding of the pro­ cess? (This is the so-called hidden variable problem in quantum mechan­ ics.) Some, like Albert Einstein even to his death, believe that the statistical nature of quantum mechanics can be removed with a deeper understanding. Because it requires less mathematical machinery, and hence it is more appropriate for an initial study of digital signal processing, we will use primarily a deterministic approach to our subject. Only in later chapters when we discuss concepts such as prediction operators and the power spectrum of noise-like processes will we use the statistical approach. Sampling and Aliasing Our immediate attention turns to deterministic digital signals. Frequently these digital signals come from sampling an analog signal, such as Captain Cook's shooting of the noonday sun. More commonly today, this sampling