Understanding Digital Signal Processing

Preface\ This book is an expansion of the original Understanding Digital Signal Processing textbook published in 1997 and, like the first edition, its goal is to help beginners understand this relatively new technology of digital signal processing (DSP). Additions to this second edition include:\ \ Expansion and clarification of selected spectrum analysis and digital filtering topics covered in the first edition making that material more valuable to the DSP beginner.\ Expanded coverage of quadrature (complex I/Q) signals. In many cases we used three-dimension time and frequency plots to enhance the description of, and give physical meaning to, these two-dimensional signals.\ With the new emphasis on quadrature signals, material was added describing the Hilbert transform and how it’s used in practice to generate quadrature signals.\ Discussions of Frequency Sampling, Interpolated FIR, and CIC filters; giving these important filters greater exposure than they’ve received in past DSP textbooks.\ A significant expansion of the popular “Digital Signal Processing Tricks” chapter.\ Revision of the terminology making it more consistent with the modern day language of DSP.\ \ It’s traditional at this point in the preface of a DSP textbook for the author to tell readers why they should learn DSP. I don’t need to tell you how important DSP is in our modern engineering world, you already know that. I’ll just say that the future of electronics is DSP, and with this book you will not be left behind.\ Learning Digital Signal Processing\ Learning the fundamentals, and how to speak the language, of digital signal processing does not require profound analytical skills or an extensive background in mathematics. All you need is a little experience with elementary algebra, knowledge of what a sinewave is, this book, and enthusiasm. This may sound hard to believe, particularly if you’ve just flipped through the pages of this book and seen figures and equations that look rather complicated. The content here, you say, looks suspiciously like the material in technical journals and textbooks that, in the past, have successfully resisted your attempts to understand. Well, this is not just another book on digital signal processing.\ This book’s goal is to gently provide explanation followed by illustration, not so that you may understand the material, but that you must understand the material. Remember the first time you saw two people playing chess? The game probably appeared to be mysterious and confusing. As you now know, no individual chess move is complicated. Given a little patience, the various chess moves are easy to learn. The game’s complexity comes from deciding what combinations of moves to make and when to make them. So it is with Understanding Digital Signal Processing. First we learn the fundamental rules and processes, and then practice using them in combination.\ If learning digital signal processing is so easy, then why does the subject have the reputation of being hard to understand? The answer lies partially in how the material is typically presented in the literature. It’s difficult to convey technical information, with its mathematical subtleties, in written form. It’s one thing to write equations, but it’s another matter altogether to explain what those equations really mean from a practical standpoint, and that’s the goal of this book.\ Too often, written explanation of digital signal processing theory appears in one of two forms: either mathematical miracles occur and the reader is simply given a short and sweet equation without further explanation, or the reader is engulfed in a flood of complex variable equations and phrases such as “it is obvious that,” and “with judicious application of the homogeneity property.” In their defense, authors usually do provide the needed information, but too often the reader must figuratively grab a pick and shovel, put on a miner’s helmet, and try to dig the information out of a mountain of mathematical expressions. (This book presents the results of several fruitful mining expeditions.) How many times have you followed the derivation of an equation, after which the author states they’re going to illustrate that equation with an example—which turns out to be just another equation? Although mathematics is necessary to describe digital signal processing, I’ve tried to avoid overwhelming the reader with math because a recipe for technical writing that’s too rich in equations is hard for the beginner to digest.\ The intent of this book is expressed by a popular quote from E.B. White in the introduction of his Elements of Style (Macmillan Publishing, New York, 1959): “Will (Strunk) felt that the reader was in serious trouble most of the time, a man floundering in a swamp, and that it was the duty of anyone attempting to write English to drain the swamp quickly and get his man up on dry ground, or at least throw him a rope.”\ I’ve attempted to avoid the traditional instructor-student relationship, but rather to make reading this book like talking to a friend while walking in the park. I’ve used just enough mathematics to develop a fundamental understanding of the theory, and then illustrate that theory with practical examples.\ The Journey\ Learning digital signal processing is not something you accomplish; it’s a journey you take. When you gain an understanding of some topic, questions arise that cause you to investigate some other facet of digital signal processing. Armed with more knowledge, you’re likely to begin exploring further aspects of digital signal processing much like those shown in the following diagram. This book is your tour guide during the first steps of your journey.\ You don’t need a computer to learn the material in this book, but it would sure help. DSP simulation software allows the beginner to verify signal processing theory through the time-tested trial and error process. In particular software routines that plot signal data, perform the fast Fourier transforms, and analyze digital filters would be very useful.\ As you go through the material in this book, don’t be discouraged if your understanding comes slowly. As the Greek mathematician Menaechmus curtly remarked to Alexander the Great, when asked for a quick explanation of mathematics, “There is no royal road to mathematics.” Menaechmus, was confident in telling Alexander the only way to learn mathematics is through careful study. The same applies to digital signal processing. Also, don’t worry if you have to read some of the material twice. While the concepts in this book are not as complicated as quantum physics, as mysterious as the lyrics of the song Louie Louie, or as puzzling as the assembly instructions of a metal shed, they do get a little involved. They deserve your attention and thought. So go slow and read the material twice if you have to; you’ll be glad you did. If you show persistence, to quote a phrase from Susan B. Anthony, “Failure is impossible.”\ Coming Attractions\ Chapter 1 begins by establishing the notation used throughout the remainder of the book. In that chapter we introduce the concept of discrete signal sequences, show how they relate to continuous signals, and illustrate how those sequences can be depicted in both the time and frequency domains. In addition, Chapter 1 defines the operational symbols we’ll use to build our signal processing system block diagrams. We conclude that chapter with a brief introduction to the idea of linear systems and see why linearity enables us to use a number of powerful mathematical tools in our analysis.\ Chapter 2 introduces the most frequently misunderstood process in digital signal processing, periodic sampling. Although it’s straightforward to grasp the concept of sampling a continuous signal, there are mathematical subtleties in the process that require thoughtful attention. Beginning gradually with simple examples of low-pass sampling, and progressing to the interesting subject of bandpass sampling, Chapter 2 explains and quantifies the frequency domain ambiguity (aliasing) associated with these important topics.\ Chapter 3 is devoted to one of the foremost topics in digital signal processing, the discrete Fourier transform (DFT) used for spectrum analysis. Coverage begins with detailed examples illustrating the important properties of the DFT and how to interpret DFT spectral results, progresses to the topic of windows used to reduce DFT leakage, and discusses the processing gain afforded by the DFT. The chapter concludes with a detailed discussion of the various forms of the transform of rectangular functions that the beginner is likely to encounter in the literature. That last topic is included there to clarify and illustrate the DFT of both real and complex sinusoids.\ Chapter 4 covers the innovation that made the most profound impact on the field of digital signal processing, the fast Fourier transform (FFT). There we show the relationship of the popular radix-2 FFT to the DFT, quantify the powerful processing advantages gained by using the FFT, demonstrate why the FFT functions as it does, and present various FFT implementation structures. Chapter 4 also includes a list of recommendations to help the reader use the FFT in practice.\ Chapter 5 ushers in the subject of digital filtering. Beginning with a simple low-pass finite impulse response (FIR) filter example, we carefully progress through the analysis of that filter’s frequency domain magnitude and phase response. Next we learn how window functions affect, and can be used to design, FIR filters. The methods for converting low-pass FIR filter designs to bandpass and high pass digital filters are presented, and the popular Remez Exchange (Parks McClellan) FIR filter design technique is introduced and illustrated by example. In that chapter we acquaint the reader with, and take the mystery out of, the process called convolution. Proceeding through several simple convolution examples, we conclude Chapter 5 with a discussion of the powerful Convolution Theorem and show why it’s so useful as a qualitative tool in Understanding Digital Signal Processing.\ Chapter 6 is devoted to a second class of digital filters, infinite impulse response (IIR) filters. In discussing several methods for the design of IIR filters, the reader is introduced to the powerful digital signal processing analysis tool called the z-transform. Because the z-transform is so closely related to the continuous Laplace transform, Chapter 6 starts by gently guiding the reader from the origin, through the properties, and on to the utility of the Laplace transform in preparation for learning the z-transform. We’ll see how IIR filters are designed and implemented, and why their performance is so different from FIR filters. To indicate under what conditions these filters should be used, that chapter concludes with a qualitative comparison of the key properties of FIR and IIR filters.\ Chapter 7 introduces two specialized digital filter types that have not received their deserved exposure in traditional DSP textbooks. Called frequency sampling and interpolated FIR filters, and providing enhanced lowpass filtering computational efficiency, they belong in our arsenal of filter design techniques. Although these are FIR filters, their introduction is delayed to this chapter because familiarity with the z-transform (in Chapter 6) makes the properties of these filters easier to understand.\ Chapter 8 presents a detailed description of quadrature signals (also called complex signals). Because quadrature signal theory has become so important in recent years, in both signal analysis and digital communication implementations, it deserves its own chapter. Using three-dimensional illustrations, this chapter gives solid physical meaning to the mathematical notation, processing advantages, and use of quadrature signals. Special emphasis is given to quadrature sampling (also called complex down-conversion).\ Chapter 9 provides a mathematically gentle, but technically thorough, description of the Hilbert transform—a process used to generate a quadrature (complex) signal from a real signal. In this chapter we describe the properties, behavior, and design of practical Hilbert transformers.\ Chapter 10 presents a brief introduction to the fascinating, and very useful, process of sample rate conversion (changing the effective sample rate of discrete data sequences through decimation or interpolation). Sample rate conversion—so useful in improving the performance and reducing the computational complexity of many signal processing operations—is essentially an exercise in lowpass filter design. As such, polyphase and cascaded integrator-comb filters are also described in this chapter.\ Chapter 11 covers the important topic of signal averaging. There we learn how averaging increases the accuracy of signal measurement schemes by reducing measurement background noise. This accuracy enhancement is called processing gain, and that chapter shows how to predict the processing gain associated with averaging signals in both the time and frequency domains. In addition, the key differences between coherent and incoherent averaging techniques are explained and demonstrated with examples. To complete that chapter the popular scheme known as exponential averaging is covered in some detail.\ Chapter 12 presents an introduction to the various binary number formats the reader is likely to encounter in modern digital signal processing. We establish the precision and dynamic range afforded by these formats along with the inherent pitfalls associated with their use. Our exploration of the critical subject of binary data word width (in bits) naturally leads us to a discussion of the numerical resolution limitations of analog to digital (A/D) converters and how to determine the optimum A/D converter word size for a given application. The problems of data value overflow roundoff errors are covered along with a statistical introduction to the two most popular remedies for overflow, truncation, and rounding. We end that chapter by covering the interesting subject of floating point binary formats that allow us to overcome most of the limitations induced by fixed point binary formats, particularly in reducing the ill effects of data overflow.\ Chapter 13 provides a collection of tricks of the trade used to make digital signal processing algorithms more efficient. Those techniques are compiled into a chapter at the end of the book for two reasons. First, it seems wise to keep our collection of tricks in one chapter so that we’ll know where to find them in the future. Second, many of these schemes require an understanding of the material from the previous chapters, so the last chapter is an appropriate place to keep our arsenal of clever tricks. Exploring these techniques in detail verifies and reiterates many of the important ideas covered in previous chapters.\ The appendices include a number of topics to help the beginner understand the nature and mathematics of digital signal processing. A comprehensive description of the arithmetic of complex numbers is covered in Appendix A, while Appendix B derives the often used, but seldom explained, closed form of a geometric series. The subtle aspects and two forms of time reversal in discrete systems (of which zero-phase digital filtering is an application) are explained in Appendix C. The statistical concepts of mean, variance, and standard deviation are introduced and illustrated in Appendix D, while Appendix E provides a discussion of the origin and utility of the logarithmic decibel scale used to improve the magnitude resolution of spectral representations. Appendix F, in a slightly different vein, provides a glossary of the terminology used in the field of digital filters.\ Acknowledgments\ Much of the new material in this edition results from what I’ve learned from those clever folk on the USENET newsgroup comp.dsp. (I could list a dozen names, but in doing so I’d make 12 friends and 500 enemies.) So I say thanks to my DSP pals on comp.dsp for teaching me so much signal processing theory.\ For their patient efforts in the unpleasant task of reviewing early versions of the manuscript, I was lucky to have help from the talented Eric Jacobsen, Dr. Peter Kootsookos, Matthew Donadio, Dr. Ian Buckner, Dr. Mike Rosing, Jerry Olup, Clay S. Turner, Ray Andraka, Jim Thomas, Robert Bristow-Johnson, Julius Kusuma, and Dr. Ing. Rune Allnor. Thanks guys, I owe you.\ I also thank Patty Donovan, of Pine Tree Composition, Inc., for converting the jumbled mess of papers plopped on her desk into a readable book; Production Gurus Lisa Iarkowski and Anne Garcia, of Prentice Hall, for skillfully riding herd on the publication process; and my upbeat Acquisition Editor Bernard Goodwin for his generous encouragement and guidance.\ If you’re still with me this far into the preface, I end by saying I had a ball writing this book and sincerely hope you benefit from reading it. If you have any comments or suggestions regarding this material, or detect any errors no matter how trivial, please send them to me at r.lyons@ieee.org. I promise I’ll reply to your E-mail.

Preface1Discrete Sequences and Systems12Periodic Sampling213The Discrete Fourier Transform454The Fast Fourier Transform1255Finite Impulse Response Filters1516Infinite Impulse Response Filters2117Specialized Lowpass Fir Filters2838Quadrature Signals3359The Discrete Hilbert Transform36110Sample Rate Conversion38111Signal Averaging41112Digital Data Formats and Their Effects43913Digital Signal Processing Tricks471App. AThe Arithmetic of Complex Numbers585App. BClosed Form of a Geometric Series595App. CTime Reversal and the DFT599App. DMean, Variance, and Standard Deviation603App. EDecibels (DB and DBM)613App. FDigital Filter Terminology621App. GFrequency Sampling Filter Derivations633App. HFrequency Sampling Filter Design Tables643Index657About the Author667