Customer Reviews

ISBN-13:

9780137028528

Publisher: Pearson Education
Publication date: 11/01/2010
Sold by: Barnes & Noble
Format: eBook
Pages: 944
File size: 49 MB
Note: This product may take a few minutes to download.

Richard G. Lyons is a consulting Systems Engineer and lecturer with Besser Associates in Mountain View, California. He is author of the book "Understanding Digital Signal Processing", editor and contributor to the book "Streamlining Digital Signal Processing", and has authored numerous articles on DSP. Lyons has taught DSP at the University of California Santa Cruz Extension and recently received the IEEE Signal Processing Society's 2012 Educator of the Year award.

Preface xv

About the Author xxiii

Chapter 1: 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 12

1.6 Time-Invariant Systems 17

1.7 The Commutative Property of Linear Time-Invariant Systems 18

1.8 Analyzing Linear Time-Invariant Systems 19

References 21

Chapter 1 Problems 23

Chapter 2: Periodic Sampling 33

2.1 Aliasing: Signal Ambiguity in the Frequency Domain 33

2.2 Sampling Lowpass Signals 38

2.3 Sampling Bandpass Signals 42

2.4 Practical Aspects of Bandpass Sampling 45

References 49

Chapter 2 Problems 50

Chapter 3: The Discrete Fourier Transform 59

3.1 Understanding the DFT Equation 60

3.2 DFT Symmetry 73

3.3 DFT Linearity 75

3.4 DFT Magnitudes 75

3.5 DFT Frequency Axis 77

3.6 DFT Shifting Theorem 77

3.7 Inverse DFT 80

3.8 DFT Leakage 81

3.9 Windows 89

3.10 DFT Scalloping Loss 96

3.11 DFT Resolution, Zero Padding, and Frequency-Domain Sampling 98

3.12 DFT Processing Gain 102

3.13 The DFT of Rectangular Functions 105

3.14 Interpreting the DFT Using the Discrete-Time Fourier Transform 120

References 124

Chapter 3 Problems 125

Chapter 4: The Fast Fourier Transform 135

4.1 Relationship of the FFT to the DFT 136

4.2 Hints on Using FFTs in Practice 137

4.3 Derivation of the Radix-2 FFT Algorithm 141

4.4 FFT Input/Output Data Index Bit Reversal 149

4.5 Radix-2 FFT Butterfly Structures 151

4.6 Alternate Single-Butterfly Structures 154

References 158

Chapter 4 Problems 160

Chapter 5: Finite Impulse Response Filters 169

5.1 An Introduction to Finite Impulse Response (FIR) Filters 170

5.2 Convolution in FIR Filters 175

5.3 Lowpass FIR Filter Design 186

5.4 Bandpass FIR Filter Design 201

5.5 Highpass FIR Filter Design 203

5.6 Parks-McClellan Exchange FIR Filter Design Method 204

5.7 Half-band FIR Filters 207

5.8 Phase Response of FIR Filters 209

5.9 A Generic Description of Discrete Convolution 214

5.10 Analyzing FIR Filters 226

References 235

Chapter 5 Problems 238

Chapter 6: Infinite Impulse Response Filters 253

6.1 An Introduction to Infinite Impulse Response Filters 254

6.2 The Laplace Transform 257

6.3 The z-Transform 270

6.4 Using the z-Transform to Analyze IIR Filters 274

6.5 Using Poles and Zeros to Analyze IIR Filters 282

6.6 Alternate IIR Filter Structures 289

6.7 Pitfalls in Building IIR Filters 292

6.8 Improving IIR Filters with Cascaded Structures 295

6.9 Scaling the Gain of IIR Filters 300

6.10 Impulse Invariance IIR Filter Design Method 303

6.11 Bilinear Transform IIR Filter Design Method 319

6.12 Optimized IIR Filter Design Method 330

6.13 A Brief Comparison of IIR and FIR Filters 332

References 333

Chapter 6 Problems 336

Chapter 7: Specialized Digital Networks and Filters 361

7.1 Differentiators 361

7.2 Integrators 370

7.3 Matched Filters 376

7.4 Interpolated Lowpass FIR Filters 381

7.5 Frequency Sampling Filters: The Lost Art 392

References 426

Chapter 7 Problems 429

Chapter 8: Quadrature Signals 439

8.1 Why Care about Quadrature Signals? 440

8.2 The Notation of Complex Numbers 440

8.3 Representing Real Signals Using Complex Phasors 446

8.4 A Few Thoughts on Negative Frequency 450

8.5 Quadrature Signals in the Frequency Domain 451

8.6 Bandpass Quadrature Signals in the Frequency Domain 454

8.7 Complex Down-Conversion 456

8.8 A Complex Down-Conversion Example 458

8.9 An Alternate Down-Conversion Method 462

References 464

Chapter 8 Problems 465

Chapter 9: The Discrete Hilbert Transform 479

9.1 Hilbert Transform Definition 480

9.2 Why Care about the Hilbert Transform? 482

9.3 Impulse Response of a Hilbert Transformer 487

9.4 Designing a Discrete Hilbert Transformer 489

9.5 Time-Domain Analytic Signal Generation 495

9.6 Comparing Analytical Signal Generation Methods 497

References 498

Chapter 9 Problems 499

Chapter 10: Sample Rate Conversion 507

10.1 Decimation 508

10.2 Two-Stage Decimation 510

10.3 Properties of Downsampling 514

10.4 Interpolation 516

10.5 Properties of Interpolation 518

10.6 Combining Decimation and Interpolation 521

10.7 Polyphase Filters 522

10.8 Two-Stage Interpolation 528

10.9 z-Transform Analysis of Multirate Systems 533

10.10 Polyphase Filter Implementations 535

10.11 Sample Rate Conversion by Rational Factors 540

10.12 Sample Rate Conversion with Half-band Filters 543

10.13 Sample Rate Conversion with IFIR Filters 548

10.14 Cascaded Integrator-Comb Filters 550

References 566

Chapter 10 Problems 568

Chapter 11: Signal Averaging 589

11.1 Coherent Averaging 590

11.2 Incoherent Averaging 597

11.3 Averaging Multiple Fast Fourier Transforms 600

11.4 Averaging Phase Angles 603

11.5 Filtering Aspects of Time-Domain Averaging 604

11.6 Exponential Averaging 608

References 615

Chapter 11 Problems 617

Chapter 12: Digital Data Formats and their Effects 623

12.1 Fixed-Point Binary Formats 623

12.2 Binary Number Precision and Dynamic Range 632

12.3 Effects of Finite Fixed-Point Binary Word Length 634

12.4 Floating-Point Binary Formats 652

12.5 Block Floating-Point Binary Format 658

References 658

Chapter 12 Problems 661

Chapter 13: Digital Signal Processing Tricks 671

13.1 Frequency Translation without Multiplication 671

13.2 High-Speed Vector Magnitude Approximation 679

13.3 Frequency-Domain Windowing 683

13.4 Fast Multiplication of Complex Numbers 686

13.5 Efficiently Performing the FFT of Real Sequences 687

13.6 Computing the Inverse FFT Using the Forward FFT 699

13.7 Simplified FIR Filter Structure 702

13.8 Reducing A/D Converter Quantization Noise 704

13.9 A/D Converter Testing Techniques 709

13.10 Fast FIR Filtering Using the FFT 716

13.11 Generating Normally Distributed Random Data 722

13.12 Zero-Phase Filtering 725

13.13 Sharpened FIR Filters 726

13.14 Interpolating a Bandpass Signal 728

13.15 Spectral Peak Location Algorithm 730

13.16 Computing FFT Twiddle Factors 734

13.17 Single Tone Detection 737

13.18 The Sliding DFT 741

13.19 The Zoom FFT 749

13.20 A Practical Spectrum Analyzer 753

13.21 An Efficient Arctangent Approximation 756

13.22 Frequency Demodulation Algorithms 758

13.23 DC Removal 761

13.24 Improving Traditional CIC Filters 765

13.25 Smoothing Impulsive Noise 770

13.26 Efficient Polynomial Evaluation 772

13.27 Designing Very High-Order FIR Filters 775

13.28 Time-Domain Interpolation Using the FFT 778

13.29 Frequency Translation Using Decimation 781

13.30 Automatic Gain Control (AGC) 783

13.31 Approximate Envelope Detection 784

13.32 AQuadrature Oscillator 786

13.33 Specialized Exponential Averaging 789

13.34 Filtering Narrowband Noise Using Filter Nulls 792

13.35 Efficient Computation of Signal Variance 797

13.36 Real-time Computation of Signal Averages and Variances 799

13.37 Building Hilbert Transformers from Half-band Filters 802

13.38 Complex Vector Rotation with Arctangents 805

13.39 An Efficient Differentiating Network 810

13.40 Linear-Phase DC-Removal Filter 812

13.41 Avoiding Overflow in Magnitude Computations 815

13.42 Efficient Linear Interpolation 815

13.43 Alternate Complex Down-conversion Schemes 816

13.44 Signal Transition Detection 820

13.45 Spectral Flipping around Signal Center Frequency 821

13.46 Computing Missing Signal Samples 823

13.47 Computing Large DFTs Using Small FFTs 826

13.48 Computing Filter Group Delay without Arctangents 830

13.49 Computing a Forward and Inverse FFT Using a Single FFT 831

13.50 Improved Narrowband Lowpass IIR Filters 833

13.51 A Stable Goertzel Algorithm 838

References 840

Appendix A: The Arithmetic of Complex Numbers 847

A.1 Graphical Representation of Real and Complex Numbers 847

A.2 Arithmetic Representation of Complex Numbers 848

A.3 Arithmetic Operations of Complex Numbers 850

A.4 Some Practical Implications of Using Complex Numbers 856

Appendix B: Closed Form of a Geometric Series 859

Appendix C: Time Reversal and the DFT 863

Appendix D: Mean, Variance, and Standard Deviation 867

D.1 Statistical Measures 867

D.2 Statistics of Short Sequences 870

D.3 Statistics of Summed Sequences 872

D.4 Standard Deviation (RMS) of a Continuous Sinewave 874

D.5 Estimating Signal-to-Noise Ratios 875

D.6 The Mean and Variance of Random Functions 879

D.7 The Normal Probability Density Function 882

Appendix E: Decibels (DB and DBM) 885

E.1 Using Logarithms to Determine Relative Signal Power 885

E.2 Some Useful Decibel Numbers 889

E.3 Absolute Power Using Decibels 891

Appendix F: Digital Filter Terminology 893

Appendix G: Frequency Sampling Filter Derivations 903

G.1 Frequency Response of a Comb Filter 903

G.2 Single Complex FSF Frequency Response 904

G.3 Multisection Complex FSF Phase 905

G.4 Multisection Complex FSF Frequency Response 906

G.5 Real FSF Transfer Function 908

G.6 Type-IV FSF Frequency Response 910

Appendix H: Frequency Sampling Filter Design Tables 913

Appendix I: Computing Chebyshev Window Sequences 927

I.1 Chebyshev Windows for FIR Filter Design 927

I.2 Chebyshev Windows for Spectrum Analysis 929

Index 931

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.

Understanding Digital Signal Processing

eBook

Customer Reviews

Table of Contents