WIXLIB

Understanding DigitalSignal ProcessingThird Edition

This page intentionally left blank

Understanding DigitalSignal ProcessingThird EditionRichard G. LyonsUpper Saddle River, NJ Boston Indianapolis San FranciscoNew York Toronto Montreal London Munich Paris MadridCapetown Sydney Tokyo Singapore Mexico City

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 the publisher was aware of a trademark claim, thedesignations have been printed with initial capital letters or in all capitals.The author and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein.The publisher offers excellent discounts on this book when ordered in quantity for bulk purchases or specialsales, which may include electronic versions and/or custom covers and content particular to your business,training goals, marketing focus, and branding interests. For more information, please contact:U.S. Corporate and Government Sales(800) 382-3419corpsales@pearsontechgroup.comFor sales outside the United States please contact:International Salesinternational@pearson.comVisit us on the Web: informit.comLibrary of Congress Cataloging-in-Publication DataLyons, Richard G., 1948Understanding digital signal processing / Richard G. Lyons.—3rd ed.p. cm.Includes bibliographical references and index.ISBN 0-13-702741-9 (hardcover : alk. paper)1. Signal processing—Digital techniques. I. Title.TK5102.9.L96 2011621.382'2—dc222010035407Copyright 2011 Pearson Education, Inc.All rights reserved. Printed in the United States of America. This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system,or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. Toobtain permission to use material from this work, please submit a written request to Pearson Education, Inc.,Permissions Department, One Lake Street Upper Saddle River, New Jersey 07458, or you may fax your requestto (201) 236-3290.ISBN-13: 978-0-13-702741-5ISBN-10:0-13-702741-9Text printed in the United States on recycled paper at Edwards Brothers in Ann Arbor, Michigan.Fourth printing, August 2012

I dedicate this book to my daughters, Julie and Meredith—I wish Icould go with you; to my mother, Ruth, for making me finish myhomework; to my father, Grady, who didn’t know what he startedwhen he built that workbench in the basement; to my brother Rayfor improving us all; to my brother Ken who succeeded where Ifailed; to my sister Nancy for running interference for us; and to theskilled folks on the USENET newsgroup comp.dsp. They ask the goodquestions and provide the best answers. Finally, to Sigi Pardula (Batgirl): Without your keeping the place running, this book wouldn’texist.

This page intentionally left blank

ContentsPREFACE xvABOUT THE AUTHOR1DISCRETE SEQUENCES AND SYSTEMS1.11.21.31.41.51.61.71.821833Aliasing: Signal Ambiguity in the Frequency DomainSampling Lowpass Signals 38Sampling Bandpass Signals 42Practical Aspects of Bandpass Sampling 45References 49Chapter 2 Problems 50THE DISCRETE FOURIER TRANSFORM3.13.21Discrete Sequences and Their Notation 2Signal Amplitude, Magnitude, Power 8Signal Processing Operational Symbols 10Introduction to Discrete Linear Time-Invariant Systems 12Discrete Linear Systems 12Time-Invariant Systems 17The Commutative Property of Linear Time-Invariant SystemsAnalyzing Linear Time-Invariant Systems 19References 21Chapter 1 Problems 23PERIODIC SAMPLING2.12.22.32.43xxiiiUnderstanding the DFT EquationDFT Symmetry 73335960vii

.144THE FAST FOURIER TRANSFORM4.14.24.34.44.54.65DFT Linearity 75DFT Magnitudes 75DFT Frequency Axis 77DFT Shifting Theorem 77Inverse DFT 80DFT Leakage 81Windows 89DFT Scalloping Loss 96DFT Resolution, Zero Padding, and Frequency-DomainSampling 98DFT Processing Gain 102The DFT of Rectangular Functions 105Interpreting the DFT Using the Discrete-TimeFourier Transform 120References 124Chapter 3 Problems 125135Relationship of the FFT to the DFT 136Hints on Using FFTs in Practice 137Derivation of the Radix-2 FFT Algorithm 141FFT Input/Output Data Index Bit Reversal 149Radix-2 FFT Butterfly Structures 151Alternate Single-Butterfly Structures 154References 158Chapter 4 Problems 160FINITE IMPULSE RESPONSE FILTERS5.15.25.35.45.55.65.75.85.9169An Introduction to Finite Impulse Response (FIR) Filters 170Convolution in FIR Filters 175Lowpass FIR Filter Design 186Bandpass FIR Filter Design 201Highpass FIR Filter Design 203Parks-McClellan Exchange FIR Filter Design Method 204Half-band FIR Filters 207Phase Response of FIR Filters 209A Generic Description of Discrete Convolution 214

Contentsix5.106INFINITE IMPULSE RESPONSE 7253An Introduction to Infinite Impulse Response Filters 254The Laplace Transform 257The z-Transform 270Using the z-Transform to Analyze IIR Filters 274Using Poles and Zeros to Analyze IIR Filters 282Alternate IIR Filter Structures 289Pitfalls in Building IIR Filters 292Improving IIR Filters with Cascaded Structures 295Scaling the Gain of IIR Filters 300Impulse Invariance IIR Filter Design Method 303Bilinear Transform IIR Filter Design Method 319Optimized IIR Filter Design Method 330A Brief Comparison of IIR and FIR Filters 332References 333Chapter 6 Problems 336SPECIALIZED DIGITAL NETWORKS AND FILTERS7.17.27.37.47.58Analyzing FIR Filters 226References 235Chapter 5 Problems 238Differentiators 361Integrators 370Matched Filters 376Interpolated Lowpass FIR Filters 381Frequency Sampling Filters: The Lost ArtReferences 426Chapter 7 Problems 429QUADRATURE SIGNALS8.18.28.38.4361392439Why Care about Quadrature Signals? 440The Notation of Complex Numbers 440Representing Real Signals Using Complex PhasorsA Few Thoughts on Negative Frequency 450446

xContents8.58.68.78.88.99THE DISCRETE HILBERT TRANSFORM9.19.29.39.49.59.610Quadrature Signals in the Frequency Domain 451Bandpass Quadrature Signals in the Frequency DomainComplex Down-Conversion 456A Complex Down-Conversion Example 458An Alternate Down-Conversion Method 462References 464Chapter 8 Problems 465Hilbert Transform Definition 480Why Care about the Hilbert Transform? 482Impulse Response of a Hilbert Transformer 487Designing a Discrete Hilbert Transformer 489Time-Domain Analytic Signal Generation 495Comparing Analytical Signal Generation MethodsReferences 498Chapter 9 Problems 499SAMPLE RATE 010.1110.1210.1310.14479497507Decimation 508Two-Stage Decimation 510Properties of Downsampling 514Interpolation 516Properties of Interpolation 518Combining Decimation and Interpolation 521Polyphase Filters 522Two-Stage Interpolation 528z-Transform Analysis of Multirate Systems 533Polyphase Filter Implementations 535Sample Rate Conversion by Rational Factors 540Sample Rate Conversion with Half-band Filters 543Sample Rate Conversion with IFIR Filters 548Cascaded Integrator-Comb Filters 550References 566Chapter 10 Problems 568454

Contents11xiSIGNAL AVERAGING11.111.211.311.411.511.612Coherent Averaging 590Incoherent Averaging 597Averaging Multiple Fast Fourier Transforms 600Averaging Phase Angles 603Filtering Aspects of Time-Domain Averaging 604Exponential Averaging 608References 615Chapter 11 Problems 617DIGITAL DATA FORMATS AND THEIR EFFECTS12.112.212.312.412.513589Fixed-Point Binary Formats 623Binary Number Precision and Dynamic Range 632Effects of Finite Fixed-Point Binary Word Length 634Floating-Point Binary Formats 652Block Floating-Point Binary Format 658References 658Chapter 12 Problems 661DIGITAL SIGNAL PROCESSING 1113.1213.1313.1413.15623671Frequency Translation without Multiplication 671High-Speed Vector Magnitude Approximation 679Frequency-Domain Windowing 683Fast Multiplication of Complex Numbers 686Efficiently Performing the FFT of Real Sequences 687Computing the Inverse FFT Using the Forward FFT 699Simplified FIR Filter Structure 702Reducing A/D Converter Quantization Noise 704A/D Converter Testing Techniques 709Fast FIR Filtering Using the FFT 716Generating Normally Distributed Random Data 722Zero-Phase Filtering 725Sharpened FIR Filters 726Interpolating a Bandpass Signal 728Spectral Peak Location Algorithm 730

313.4413.4513.4613.4713.4813.4913.5013.51Computing FFT Twiddle Factors 734Single Tone Detection 737The Sliding DFT 741The Zoom FFT 749A Practical Spectrum Analyzer 753An Efficient Arctangent Approximation 756Frequency Demodulation Algorithms 758DC Removal 761Improving Traditional CIC Filters 765Smoothing Impulsive Noise 770Efficient Polynomial Evaluation 772Designing Very High-Order FIR Filters 775Time-Domain Interpolation Using the FFT 778Frequency Translation Using Decimation 781Automatic Gain Control (AGC) 783Approximate Envelope Detection 784A Quadrature Oscillator 786Specialized Exponential Averaging 789Filtering Narrowband Noise Using Filter Nulls 792Efficient Computation of Signal Variance 797Real-time Computation of Signal Averages and Variances 799Building Hilbert Transformers from Half-band Filters 802Complex Vector Rotation with Arctangents 805An Efficient Differentiating Network 810Linear-Phase DC-Removal Filter 812Avoiding Overflow in Magnitude Computations 815Efficient Linear Interpolation 815Alternate Complex Down-conversion Schemes 816Signal Transition Detection 820Spectral Flipping around Signal Center Frequency 821Computing Missing Signal Samples 823Computing Large DFTs Using Small FFTs 826Computing Filter Group Delay without Arctangents 830Computing a Forward and Inverse FFT Using a Single FFT 831Improved Narrowband Lowpass IIR Filters 833A Stable Goertzel Algorithm 838References 840

ContentsAxiiiTHE ARITHMETIC OF COMPLEX NUMBERSA.1A.2A.3A.4847Graphical Representation of Real and Complex Numbers 847Arithmetic Representation of Complex Numbers 848Arithmetic Operations of Complex Numbers 850Some Practical Implications of Using Complex Numbers 856BCLOSED FORM OF A GEOMETRIC SERIESCTIME REVERSAL AND THE DFTDMEAN, VARIANCE, AND STANDARD DEVIATIOND.1D.2D.3D.4D.5D.6D.7EFG863874885Using Logarithms to Determine Relative Signal PowerSome Useful Decibel Numbers 889Absolute Power Using Decibels 891DIGITAL FILTER TERMINOLOGY893FREQUENCY SAMPLING FILTER DERIVATIONSG.1G.2G.3G.4867Statistical Measures 867Statistics of Short Sequences 870Statistics of Summed Sequences 872Standard Deviation (RMS) of a Continuous SinewaveEstimating Signal-to-Noise Ratios 875The Mean and Variance of Random Functions 879The Normal Probability Density Function 882DECIBELS (DB AND DBM)E.1E.2E.3859903Frequency Response of a Comb Filter 903Single Complex FSF Frequency Response 904Multisection Complex FSF Phase 905Multisection Complex FSF Frequency Response906885

xivContentsG.5G.6Real FSF Transfer Function 908Type-IV FSF Frequency Response910HFREQUENCY SAMPLING FILTER DESIGN TABLESICOMPUTING CHEBYSHEV WINDOW SEQUENCESI.1I.2INDEX931913927Chebyshev Windows for FIR Filter Design 927Chebyshev Windows for Spectrum Analysis 929