• 1ng
`
`GOOGLEEXHIBIT 1012
`
`RICHARD G. LYONS
`
`Page 1 of 534
`
`Page 1 of 534
`
`GOOGLE EXHIBIT 1012
`
`

`

`Understanding Digital
`Signal Processing
`
`Page 2 of 534
`
`

`

`Understanding Digital
`Signal Processing
`
`Richard G. Lyons
`
`ADDISON-WESLEY PUBLISHING COMPANY
`
`An imprint of Addison Wesley Longman, Inc.
`Reading, Massachusetts • Harlow, England · Menlo Park, California
`Berkeley, California · Don Mills, Ontario · Sydney
`Bonn · Amsterdam · Tokyo · Mexico City
`
`Page 3 of 534
`
`

`

`IT}
`
`I dedicate this book to m3
`could go with you; to my
`work; to my father Grady~
`that workbench in the base
`to my brother Ken who sue
`running interference for us;
`Schlessinger for keeping us
`the Iron Riders Motorcycle
`
`Many of the designations used by manufacturers and sellers to
`distinguish their products are claimed as trademarks. Where
`those designations appear in this book and Addison-Wesley was
`aware of a trademark claim, the designations have been printed
`with initial capital letters.
`
`The publisher offers discounts on this book when ordered in
`quantity for special sales.
`
`For more information, please contact:
`Corporate & Professional Publishing Group
`Addison Wesley Longman, Inc.
`One Jacob Way
`Reading, Massachusetts 02867
`
`Library of Congress Cataloging-in-Publication Data
`
`Lyons,Richard G., 1948-
`Understanding digital signal processing / Richard G. Lyons.
`p.
`cm.
`Includes bibliographical references and index.
`ISBN 0-201-63467-8 (he)
`1. Signal processing--Digital techniques.
`TK5102.9.L96
`1997
`621.382'2--dc20
`
`I. Title.
`
`96-28818
`CIP
`
`Copyright 1997
`
`By Addison Wesley Longman, Inc.
`
`All rights reserved. No part of this publication may be repro(cid:173)
`duced, stored in a retrieval system, or transmitted, in anyJorm or
`by any means, electronic, mechanical, photocopying, recording,
`or otherwise, without the prior written permission of the pub(cid:173)
`lisher. Printed in the United States of America. Published simul(cid:173)
`taneously in Canada.
`
`0-201-63467-8
`
`1 2 3 4 5 6 7 8 9-MA-00999897
`
`First Printing, October 1996
`
`Page 4 of 534
`
`

`

`DEDICATION
`
`I dedicate this book to my two daughters Julie and Meredith, I wish I
`could go with you; to my mother Ruth for making me finish my home(cid:173)
`work; to my father Grady who didn't know what he started when he built
`that workbench in the basement; to my brother Ray for improving us all;
`to my brother Ken who succeeded where r failed; to my sister Nancy for
`running interference for us; to John Lennon for not giving up; to Dr. Laura
`Schlessinger for keeping us honest; to my advisor Glenn Caldwell and to
`the Iron Riders Motorcycle Club (Niles, CA) who keep me alive.
`
`:1d sellers to
`:irks. Where
`-Wesley was
`Jeen printed
`
`1 ordered in
`
`ta
`
`d G. Lyons.
`
`itle.
`
`96-28818
`CIP
`
`Inc.
`
`my be repro(cid:173)
`n any form or
`1g, recording,
`n of the pub(cid:173)
`,lished simul-
`
`Page 5 of 534
`
`

`

`CONTENTS
`
`Preface ... .. ... ........ ... ... ... .... ... • .. . .. ...... . ......... xi
`
`DISCRETE SEQUENCES AND SYSTEMS .......... ..... .... . .... 1
`
`1.1 Discrete Sequences and Their Notation ... .. ... ........ . ..... 2
`1.2
`Signal Amplitude, Magnitude, Power ........ ... ......... .. .. 8
`1.3
`Signal Processing Operational Symbols .... ..... ....... ..... 10
`1.4
`Introduction to Discrete Linear Time-Invariant Systems ... ... .. 12
`1.5 Discrete Linear Systems ... ..... .......... .... ....... ..... 13
`1.6 Time-Invariant Systems ..... . ............ .... ............ 18
`1.7 The Commutative Property of Linear Time-Invariant Systems .. 20
`1.8 Analyzing Linear Time-Invariant Systems ............... . ... 20
`
`2 PERIODIC SAMPLING . ....... .... .. ............. . . ....... ... 23
`
`2.1 Alir1sini· Si~r1l Amhirp1ity in thP FrP<JllPnry Domain .. .. .. . . . 23
`2.2
`Sampling Low-Pass Signals .. . ........... .. ....... ....... . 29
`2.3
`Sampling Bandpass Signals ........ .... .... . . . .... . . . . .... 32
`2.4
`Spectral Inversion in Bandpass Sampling ........... .... . .... 43
`
`3 THE DISCRETE FOURIER TRANSFORM . .. . .. .. .. . .............. 49
`
`3.1 Understanding the DFT Equation .......... ... . ............ 50
`3.2 DFT Symmetry .......................... .. . .. .. ......... 63
`3.3 DFT Linearity ........... . .. . . .. ' .......... . . . ... .. .. .. .. . 65
`3.4 DFT Magnitudes .... ........ ..... .... ... . ... .. .. ....... . 66
`3.5 DFT Frequency Axis ........ ... .. .. . . .... . .. ... . . . . ..... . 67
`3.6 DFT Shifting Theorem ............ .. ... . . .. .. ... .. ... . ... 68
`3.7
`Inverse DFT ......... .... ........... ... ... .. ..... ....... 70
`3.8 DFT Leakage ... ............ ..... ....... .. .... . . .... . ... 71
`3.9 Windows .. ...... ....... ...... .... . .... . ...... .. ..... . . 80
`3.10 DFT Scalloping Loss .......... ....... .......... .. .. .... .. 88
`3.11 DFT Resolution, Zero Stuffing, and Frequency-Domain
`Sampling ..................... . ............... ......... 89
`3.12 DFT Processing Gain ........ ...... ....... ....... . .. ..... . 93
`3.13 The DFT of Rectangular Functiuus ........ .... ...... ... .. . . 97
`3.14 The DFT Frequency Response to a Complex Input .... .. . .... 119
`3.15 The DFT Frequency Response to a Real Cosine Input . . . ... ... 123
`3.16 The DFT Single-Bin Frequency Response to a Real
`Cosine Input ................................... . .. ..... 125
`
`vii
`
`Page 6 of 534
`
`

`

`viii
`
`Understanding Digital Signal Processing
`
`4 THE FAST FOURIER TRANSFORM .. ... . . ............... .... .. 129
`
`4.1 Relationship of the FFT to the DFT ... . .. .................. 130
`4.2 Hints on Using FFTs in Practice . ........ .. ... . .......... . . 131
`4.3
`FFT Software Programs ................ . . . .... .. . . . ...... 136
`4.4 Derivation of the Radix-2 FFT Algorithm . ................. . 136
`4.5
`FFT Input/Output Data Index Bit Reversal .... . ......... . .. 145
`4.6 Radix-2 FFT Butterfly Structures . ....... ............ _ . ... . 146
`
`5 FINITE IMPULSE RESPONSE FILTERS ............. . .... . . .... . . 157
`
`5.1 An Introduction to Finite Impulse Response FIR Filters ... ... . 158
`5.2 Convolution in FIR Filters .... .. ........ . .. .......... .... 163
`5.3 Low-Pass FIR Filter Design . ... ... ... ... ....... .. .... . . __ 174
`5.4 Bandpass FIR Filter Design .. ......... ..... ...... ........ 191
`5.5 Highpass FIR Filter Design ...................... ..... , .. 193
`5.6 Remez Exchange FIR Filter Design Method . .. ........ ...... 194
`5.7 Half-Band FIR Filters ... ... . ... ........ ... ....... .... ... 197
`5.8 Phase Response of FIR Filters .......... . . .. . .. . .. . ...... . 199
`5.9 A Generic Description of Discrete Convolution ...... ....... . 204
`
`6
`
`INFINITE IMPULSE RESPONSE FILTERS . ..... . .. .. ..... ... ..... 219
`
`6.1 An Introduction to Infinite Impulse Response Filters ......... 220
`6.2 The Laplace Transform ........ .. .... .......... ... , ...... 223
`6.3 The z-Transform .. ........ ..... ...... .... ... . .. ... ... . . 238
`6.4
`Impulse Invariance IIR Filter Design Method ... ... ..... . . ... 254
`6.5 Bilinear Transform IIR Filter Design Method ... .. ...... .... . 272
`6.6 Optimized IIR Filter Design Method . ..... .. ..... .... ...... 284
`6.7
`Pitfalls in Building IIR Digital Filters . .. ... . . . ..... . ...... .. 286
`6.8 Cascade and Parallel Combinations of Digital Filters .. . . ... .. 290
`6.9 A Brief Comparison of IIR and FIR Filters ........ .......... 292
`
`7 ADVANCED SAMPLING TECHNIQUES ....... ... ." .. . ..... . .. 297
`
`7.1 Quadrature Sampling .............. ... ..... . ........ .... 297
`7.2 Quadrature Sampling with Digital Mixing ... .. _ . . .. .• .. . . . . 301
`7.3 Digital Resampling ......... . .. •. · ...... . ...... . . . . ... .. .. 303
`
`8 SIGNAL AVERAGING ................ . ......... . ..... _. _ ... 319
`
`8.1 Coherent Averaging ...... . ............ . ...... . ...... . .. 320
`8.2
`Incoherent Averaging ...... ... .......... . ..... ... .. .. . . . 327
`8.3 Averaging Multiple Fast Fourier Transforms .... _ ... . ... ... . 330
`8.4
`Filtering Aspects of Time-Domain Averaging . . . . _ . . . ........ 340
`8.5 Exponential Averaging .............. ... ... . . .. .. . ....... 341
`
`Page 7 of 534
`
`

`

`Contents
`
`ix
`
`9 DIGITAL DATA FORMATS AND THEIR EFFECTS ... . . .... . . .... 349
`
`Fixed-Point Binary Formats .. . .... ..... . . .. . . . ........... 349
`9.1
`9.2 Binary Number Precision and Dynamic Range .. .. . .... .... . 356
`9.3 Effects of Finite Fixed-Point Binary Word Length . .... .... . . . 357
`9.4
`Floating-Point Binary Formats . ............ . . . ... ......... 375
`9.5 Block Floating-Point Binary Format ... . ... . . .. . ... . . .. ..... 381
`
`10 DIGITAL SIGNAL PROCESSING TRICKS ..... ....... .. ...... . 385
`
`10.1 Frequency.Translation without Multiplication .. ...... . . ... . . 385
`10.2 High-Speed Vector-Magnitude Approximation . ........ .. . .. 400
`10.3 Data Windowing Tricks .... . .. . . . ............ . ... .. . . . . . 406
`10.4 Fast Multiplication of Complex Numbers .... .... .... . . .... . 411
`10.5 Efficiently Performing the FFT of Real Sequences ..... . . .. . .. 412
`10.6 Calculating the Inverse FFT Using the forward }'Fl' .... .. ... . 42-J
`10.7 Fast FFT Averaging ......... .. ................... . ...... 429
`10.8 Simplified FIR Filter Structure ... .. . ... ... . ... ...... ...... 430
`10.9 Accurate A / D Converter Testing Technique .. .. . . . . . ....... 432
`10.10 Fast FIR Filtering Using the FFT . ... ........ .. . . .... ....... 435
`10.11 Calculation of Sines and Cosines of Consecutive Angles . . . . .. 436
`10.12 Generating Normally Distributed Random Data ...... . . .. .. . 438
`
`APPENDIX A. THE ARITHMETIC OF COMPLEX NUMBERS ..... ...... 443
`
`A.I Graphical Representation of Real and Complex Numbers ..... 443
`A.2 Arithmetic Representation of Complex Numbers ...... .. .. . . 444
`A.3 Arithmetic Operations of Complex N1.1mher.5
`. . . . .. . .. ...... 446
`A.4 Some Practical Implications of Using Complex Numbers . . ... . 453
`
`APPENDIX B. CLOSED FORM OF A GEOMETRIC SERIES ...... .. . . .. 455
`
`APPENDIX C. COMPLEX SIGNALS AND NEGATIVE FREQUENCY . .. . 458
`
`C.1 Development of Imaginary Numbers ..... .. , .......... . ... 460
`C.2 Representing Real Signals Using Complex Phasors ... . . . . . ... 462
`C.3 Representing Real Signals Using Negative Frequencies .. . .... 467
`C.4 Complex Signals and Quadrature Mixing .. .. , . . .... ........ 471
`
`APPENDIX D. MEAN, VARIANCE, AND STANDARD DEVIATION ..... 476
`
`D.1 Statistical Measures ......... . ............ . ........ ..... . 476
`D.2 Slandard Deviation, or RMS, of a Continuous Sine,vave .. . ... 480
`D.3 The Mean and Variance of Random Functions .. . . ..... .. .. .. 481
`D.4 The Normal Probability Density Function .. ... . . . . . . . . . .... 484
`
`Page 8 of 534
`
`

`

`x
`
`Understanding Digital Signal Processing
`
`APPENDIX E. DECIBELS (dB AND dBm) . ... .. . . .... .. ... . ... .... . . 486
`
`E.1 Using Logarithms to Determine Relative Signal Power .. ..... 486
`E.2 Some Useful Decibel Numbers .... ... ........ . .. ... ...... 492
`E.3 Absolute Power Using Decibels ............. . .. . ... . ...... 493
`
`APPENDIX F. DIGITAL FILTER TERMINOLOGY . . .... .. .. . ............ 494
`
`Index . .... .. . .. . .. .. ... . .... . ... . . . . .. ... .......... .. .... . . 507
`
`Page 9 of 534
`
`

`

`PREFAC .E
`
`Learning Digital Signal Processing
`
`Learning the fundamentals, and how to speak the language, of digital sig(cid:173)
`nal processing does not require profound analytical skills or an extensive
`background in mathematics. All you need is a little experience with ele(cid:173)
`mentary algebra, knowledge of what a sinewave is, this book, and enthu(cid:173)
`siasm. This may sound hard to believe, particularly if you've just flipped
`through the pages of this book and seen figures anrl e'111r11irms th;it appP,H
`rather complicated. The content here, you say, looks suspiciously like the
`material in technical journals and textbooks, material that is difficult to
`understand. Well, this is not just another book on digital ~ignal processing.
`This book's goal is to gently provide explanation followed by illustra(cid:173)
`tion, not so that you may understand the material, but that you must
`understand the materiai.t Remember the first time you saw two people
`· playing chess? The game probably appeared to be mysterious and con(cid:173)
`fusing. 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 m;ikp thP.m. 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 sub(cid:173)
`ject have the reputation of being difficult tu uudersland? 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 you
`are simply given a short and sweet equation without further explanation,
`or you are engulfed in a flood of complex variable equations and phrases
`
`t "Here we have the opportunity of expounding more clearly what has already been said "
`(Rene Descartes).
`
`xi
`
`Page 10 of 534
`
`

`

`xii
`
`Understanding Digital Signal Processing
`
`such as "it is obvious that," "such that W(f) 2". 0 't:/ f," and "with judicious
`application of the homogeneity property." Authors usually do provide the
`needed information, but, too often, the reader must 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 that he or she
`is going to illustrate that equation with a physical example-and this
`turns out to be another equation? Although mathematics is necessary to
`describe digital signal processing, I've tried to avoid overwhelming the
`reader because a recipe for technical writing that's too rich in equations is
`hard for the beginner to digest.t
`The intent of this book is expressed in a popular quote from E. B. White
`in the introduction of his Elements of Style (New York: Macmillan
`Publishing, 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 any(cid:173)
`one 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 walk(cid:173)
`ing in the park. I've used just enough mathematics to develop a funda(cid:173)
`mental understanding of the theory, and, then, illustrate that theory with
`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, ques(cid:173)
`tions 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 help. Digital signal processing software allows the beginner to ver-
`
`t "We need elucidation of the obvious more than investigation of th(;' obscure" (Oliver
`Wendell Holmes).
`
`Page 11 of 534
`
`

`

`Preface
`
`xiii
`
`Periodic sampling
`
`How can the spectra of sampled
`signals be analyzed?
`
`How can the effective sample
`rates of discrete signals be
`changed?
`
`How can DFT
`measurement accuracy
`be improved?
`I
`
`How can digital filter
`frequency responses be
`improved?
`
`How can
`spectra be -+------~
`modified?
`
`How does
`windowing work?
`
`leakage?
`
`How can spectral
`noise be reduced to
`enhance signal
`
`How can the noise
`reduction effects of
`averaging be analyzed?
`
`de<ect;oo? \ ___ -.,t
`
`Signal averaging
`
`Figure P-1
`
`ify signal processing theory through trial and error.t In particular, soft(cid:173)
`ware routines that plot signal data, perform the fast Fourier transform,
`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
`
`t "One must learn by doing the thing; for though you think you know it, you have no cer(cid:173)
`tainty until you try it" (Sophocles).
`
`Page 12 of 534
`
`

`

`xiv
`
`Understanding Digital Signal Processing
`
`curtly remarked to Alexander the Great, when asked for a quick explana(cid:173)
`tion of mathematics, "There is no royal road to mathematics." Menaechmus
`was confident in telling Alexander that 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 con(cid:173)
`cepts in this book are not as complicated as quantum physics, as mysteri(cid:173)
`ous 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 h-vice 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 of this book begins by establishing the notation used through(cid:173)
`out the remainder of our study. 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 sym(cid:173)
`bols we'll use to build our signal processing system block diagrams. We
`conclude that chapter with a brief introduction to the idea of linear sys(cid:173)
`tems and see why linearity enables us to use a number of powerful math(cid:173)
`ematical tools in our analysis.
`Chapter 2 introduces the most frequently misunderstood process in
`digital signal processing, periodic sampling. Although it's straightfor(cid:173)
`ward 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) asso(cid:173)
`ciated with these important topics. The discussion there highlights the
`power and pitfalls of periodic sampling.
`Chapter 3 is devoted to one of the foremost topics in digital signal pro(cid:173)
`cessing, the discrete Fourier transform (OFT). Coverage begins with
`detailed examples illustrating the important properties of the OFT and
`how to interpret OFT spectral results, progresses to the topic of windows
`used to reduce OFT leakage, and discusses the processing gain afforded
`by the OFT. The chapter concludes with a detailed discussion of the vari(cid:173)
`ous 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 OFT of both real and complex sinusoids.
`
`Page 13 of 534
`
`

`

`Preface
`
`xv
`
`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 recommenda(cid:173)
`tions to help us when we 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 care(cid:173)
`fully 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 highpass digital filters are
`presented, and the popular Remez Exchange (!-'arks McClellan) FIR fil(cid:173)
`ter design technique is introduced and illustrated by example. In that
`c:hapter we acquaint the reader with, and take the mystery out of, the
`process called convolution. Proceeding through several simple convolu(cid:173)
`tion 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
`understandinr; ciir;it;:i l f,ir;n;:i l processing.
`Chapter 6 introduces 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 pro(cid:173)
`cessing analysis tool called the z-transform. Because the z-transform is
`so closely related to the continuous Lapl_ace transform, Chapter 6 starts
`by gently guiding the reader from th~ origin, through the properties,
`and on to the utility of the Laplace transform in preparation for learn(cid:173)
`ing the z-transform. We'll see how IIR filters are designed and imple(cid:173)
`mented, and why their performance is so different from FIR filters. To
`indicate under what conditions these filters should be used, the chap(cid:173)
`ter concludes with a qualitative comparison of the key properties of FIR
`and IIR filters.
`01apter 7 discusses two important advanced sampling techniques
`prominent in digital signal processing, quadrature sampling and digital
`resampling. In the chapter we discover why quadrature sampling is so
`useful when signal phase must be analyzed and preserved, and how this
`special sampling process can circwnvent some of the limitations of tradi(cid:173)
`tional periodi<.: ·a111pliHg ledutlques. Our introduction to digitul rcsam(cid:173)
`pling shows how we can, and when we should, change the effective
`sample rate of discrete data after the data has already been digitized.
`We've delayed the discussion of digital resampling to this chapter
`
`Page 14 of 534
`
`

`

`xvi
`
`Understanding Digital Signal Processing
`
`because some knowledge of low-pass digital filters is necessary to under(cid:173)
`stand how resampling schemes operate.
`Chapter 8 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 the chapter shows how to pre(cid:173)
`dict 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 the chapter, the popular scheme known as
`exponential averaging is covered in some detail.
`Chapter 9 presents an introduction to the various binary number for(cid:173)
`mats that the reader is likely to encounter in modern digital signal pro(cid:173)
`cessing. 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) natu(cid:173)
`rally leads us to a discussion of the numerical resolution limitations of ana(cid:173)
`log to digital (A/D) converters and how to determine the optimum AID
`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 the 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 10 provides a collection of tricks of the trade that the profes(cid:173)
`sionals often use to make their 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 collection 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 under(cid:173)
`stand the 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. Appendix C strives to clarify the troubling top(cid:173)
`ics of complex signals and negative frequency. The statistical concepts of
`
`Page 15 of 534
`
`

`

`Preface
`
`xvii
`
`mean, variance, and standard deviation are introduced and illustrated in
`Appendix D, and Appendix E provides a discussion of the origin and util(cid:173)
`ity of the logarithmic decibel scale used to improve the magnitude reso(cid:173)
`lution of spectral representations. In a slightly different vein, Appendix F
`provides a glossary of the terminology used in the field of digital filters.
`
`Acknowledgments
`How do I sufficiently thank the people who helped me write this book? I
`do this by stating tha.'t any quality existing herein is due to the following
`talented people: for their patient efforts in the unpleasant task of review(cid:173)
`ing early versions of the 111.anuscript, I am grateful to Sean McCrory, Paul
`Chestnut, Paul Kane, John Winter, Terry Daubek, and Robin Wiprud.
`Special thanks go to Nancy Silva for her technical and literary guidance,
`and encouragement, without which this book would not have been writ(cid:173)
`ten. For taking time to help me understand digital signal processing, I
`thank Frank Festini, Harry Glaze, and Dick Sanborn. I owe you people.
`Gratitude goes to the reviewers, under the auspices of Addison-Wesley,
`whose suggestions improved much of the material. They are Mark
`Sullivan, David Goodman, Satyanarayan Namdhari, James Kresse,
`Ryerson Gewalt, David Cullen, Richard Herbert, Maggie Carr, and anony(cid:173)
`mous at Alcatel Bell. Finally, I acknowledge my good fortune in being able
`to work with those talented folks at Addison-Wesley: Rosa Aimee
`Gonzalez, Simon Yates, and Tara Herries.
`If you're still with me this far into the Preface, I end by saying that I had
`a ball writing this book and hope you get some value out of reading it.
`
`Page 16 of 534
`
`

`

`CHAPTER ONE
`
`Discrete Sequences
`and System.s
`
`Digital signal processing has never been more prevalent or easier to per(cid:173)
`form. It wasn't that long ago when the fast Fourier transform (FFT), a
`topic we'll discuss in Chapter 4, was a mysterious mathematical process
`used only in industrial research centers and universities. Now, amazingly,
`the FFT is readily available to us all. It's even a built-in function provided
`by inexpensive spreadsheet software for home computers. The availabil(cid:173)
`ity of more suphislicc1led commercial signal processing software now
`allows us to analyze and develop complicated signal processing applica(cid:173)
`tions rapidly and reliably. We can now perform spectral analysis, design
`digital filters, develop voice recognition, data communication, and image
`compression processes using software that's interactive in both the way
`algorithms are defined and how the resulting data are graphically dis(cid:173)
`played. Since the mid-1980s the same integrated circuit technology that
`led to affordable home computers has prodµced powerful and inexpen(cid:173)
`sive hardware development systems on which to implement our digital
`signal processing designs.t Regardless, though, of the ease with which
`these new digital signal processing development systems and software
`can be applied, we still need a solid foundation in understanding the
`basics of digital signal processing. The purpose of this book is to build
`that foundation.
`In this chapter we'll set the stage for the topics we'll study throughout the
`remainder of this book by defining the terminology used in digital signal
`
`D uring a television interview in the early 1990s, a leading computer scientist stated that
`had automobile technology made the same strides as the computer industry, we'd all have
`a car that would go a half million miles per hour and get a half million mi les per gallon. The
`cost of that car would be so low that it would be cheaper to throw it away than pay for one
`day's parking in San Francisco.
`
`Page 17 of 534
`
`

`

`2
`
`Discrete Sequences and Systems
`
`processing, illush·ating the various ways of graphically representing discrete
`signals, establishing the notation used to describe sequences of data values,
`presenting the symbols used to depict signal processing operations, and
`briefly introducing the concept of a linear discrete system.
`
`l . 1 Discrete Sequences and Their Notation
`In general, the term signal processing refers to the science of analyzing
`time-varying physical processes. As such, signal processing is divided
`into two categories, analog signal processing and digital signal process(cid:173)
`ing. The term analog is used to describe a waveform that's continuous in
`time and can take on a continuous range of amplitude values. An exam(cid:173)
`ple of an analog signal is some voltage that can be applied to an oscillo(cid:173)
`scope resulting in a continuous display as a function of time. Analog
`signals can also be applied to a conventional spectrum analyzer to deter(cid:173)
`mine their frequency content. The term analog appears to have stemmed
`from the analog computers used prior to 1980. These computers solved
`linear differential equations by means of connecting physical (electronic)
`differentiators and integrators using old-style telephone operator patch
`cords. That way, a continuous voltage or current in the actual circuit was
`analogous to some variable in a differential equation, such as speed, tem(cid:173)
`perature, air pressure, etc. (Although the flexibility and speed of modern(cid:173)
`day digital computers have since made analog computers obsolete, a
`good description of the short-lived utility of analog computers can be
`found in reference [l].) Because present-day signal processing of continu(cid:173)
`ous radio-type signals using resistors, capacitors, operational amplifiers,
`etc., has nothing to do with analogies, the term analog is actually a mis(cid:173)
`nomer. The more correct term is continuous signal processing for what is
`today so commonly called analog signal processing. As such, in this book
`we'll minimize the use of the term analog signals and substitute the phrase
`continuous signals whenever appropriate.
`The term discrete-time signal is used to desc~ibe a signal whose inde(cid:173)
`pendent time variable is quantized so that we know only the value of the
`signal at discrete instants in time. Thus a discrete-time signal is not repre(cid:173)
`sented by a continuous waveform but, instead, a sequence of values. In
`addition to quantizing time, a discrete-time signal quantizes the signal
`amplitude. We can illustrate this concept with an example. Think of a con(cid:173)
`tiirnous sinewave with a peak amplitude of 1 at a frequency f 0 described
`by the equation
`
`x(t) = sin(2rcf0 t) .
`
`(1-1)
`
`Page 18 of 534
`
`

`

`Discrete Sequences and Their Notation
`
`3
`
`The frequency J0 is measured in hertz (Hz). (In physical systems, we usu(cid:173)
`ally measure frequency in units of hertz. One Hz