INTRODUCTION TO Signal Processing
INTRODUCTION TO Signal Processing
INTRODUCTION TO Signal Processing Sophocles I.Orfanidis Rutgers University http://www.ece.rutgers.edu/~orfanidi/intro2sp
INTRODUCTION TO Signal Processing Sophocles J. Orfanidis Rutgers University http://www.ece.rutgers.edu/~orfanidi/intro2sp
To my lifelong friend George Lazos Copyright O 2010 by Sophocles J.Orfanidis This book was previously published by Pearson Education,Inc. Copyright 1996-2009 by Prentice Hall,Inc.Previous ISBN 0-13-209172-0. All rights reserved.No parts of this publication may be reproduced,stored in a retrieval system,or transmitted in any form or by any means,electronic,mechanical,photocopy- ing,recording or otherwise,without the prior written permission of the author. MATLAB is a registered trademark of The MathWorks,Inc. Web page:www.ece.rutgers.edu/~orfanidi/i2sp
To my lifelong friend George Lazos Copyright © 2010 by Sophocles J. Orfanidis This book was previously published by Pearson Education, Inc. Copyright © 1996–2009 by Prentice Hall, Inc. Previous ISBN 0-13-209172-0. All rights reserved. No parts of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without the prior written permission of the author. MATLABR is a registered trademark of The MathWorks, Inc. Web page: www.ece.rutgers.edu/~orfanidi/i2sp
Contents Preface xiii 1 Sampling and Reconstruction 1 1.1 Introduction,I 1.2 Review of Analog Signals,1 1.3 Sampling Theorem,4 1.3.1 Sampling Theorem,6 1.3.2 Antialiasing Prefilters,7 1.3.3 Hardware Limits,8 1.4 Sampling of Sinusoids,9 1.4.1 Analog Reconstruction and Aliasing,10 1.4.2 Rotational Motion,27 1.4.3 DSP Frequency Units,29 1.5 Spectra of Sampled Signals*,29 1.5.1 Discrete-Time Fourier Transform,31 1.5.2 Spectrum Replication,33 1.5.3 Practical Antialiasing Prefilters,38 1.6 Analog Reconstructors*,42 1.6.1 Ideal Reconstructors,43 1.6.2 Staircase Reconstructors,45 1.6.3 Anti-Image Postfilters,46 1.7 Basic Components of DSP Systems,53 1.8 Problems,55 2 Quantization 61 2.1 Quantization Process,61 2.2 Oversampling and Noise Shaping*,65 2.3 D/A Converters,71 2.4 A/D Converters,75 2.5 Analog and Digital Dither*,83 2.6 Problems,90 3 Discrete-Time Systems 95 3.1 Input/Output Rules,96 3.2 Linearity and Time Invariance,100 3.3 Impulse Response,103 i
Contents Preface xiii 1 Sampling and Reconstruction 1 1.1 Introduction, 1 1.2 Review of Analog Signals, 1 1.3 Sampling Theorem, 4 1.3.1 Sampling Theorem, 6 1.3.2 Antialiasing Prefilters, 7 1.3.3 Hardware Limits, 8 1.4 Sampling of Sinusoids, 9 1.4.1 Analog Reconstruction and Aliasing, 10 1.4.2 Rotational Motion, 27 1.4.3 DSP Frequency Units, 29 1.5 Spectra of Sampled Signals∗, 29 1.5.1 Discrete-Time Fourier Transform, 31 1.5.2 Spectrum Replication, 33 1.5.3 Practical Antialiasing Prefilters, 38 1.6 Analog Reconstructors∗, 42 1.6.1 Ideal Reconstructors, 43 1.6.2 Staircase Reconstructors, 45 1.6.3 Anti-Image Postfilters, 46 1.7 Basic Components of DSP Systems, 53 1.8 Problems, 55 2 Quantization 61 2.1 Quantization Process, 61 2.2 Oversampling and Noise Shaping∗, 65 2.3 D/A Converters, 71 2.4 A/D Converters, 75 2.5 Analog and Digital Dither∗, 83 2.6 Problems, 90 3 Discrete-Time Systems 95 3.1 Input/Output Rules, 96 3.2 Linearity and Time Invariance, 100 3.3 Impulse Response, 103 vii
viii CONTENTS 3.4 FIR and IIR Filters,105 3.5 Causality and Stability,112 3.6 Problems.117 4 FIR Filtering and Convolution 121 4.1 Block Processing Methods,122 4.1.1 Convolution,122 4.1.2 Direct Form,123 4.1.3 Convolution Table,126 4.1.4LTΠFom,127 4.1.5 Matrix Form,129 4.1.6 Flip-and-Slide Form,131 4.1.7 Transient and Steady-State Behavior,132 4.1.8 Convolution of Infinite Sequences,134 4.1.9 Programming Considerations,139 4.1.10 Overlap-Add Block Convolution Method,143 4.2 Sample Processing Methods,146 4.2.1 Pure Delays,146 4.2.2 FIR Filtering in Direct Form,152 4.2.3 Programming Considerations,160 4.2.4 Hardware Realizations and Circular Buffers,162 4.3 Problems,178 5 Z-Transforms 183 5.1 Basic Properties,183 5.2 Region of Convergence,186 5.3 Causality and Stability,193 5.4 Frequency Spectrum,196 5.5 Inverse z-Transforms,202 5.6 Problems,210 6 Transfer Functions 214 6.1 Equivalent Descriptions of Digital Filters,214 6.2 Transfer Functions,215 6.3 Sinusoidal Response,229 6.3.1 Steady-State Response,229 6.3.2 Transient Response,232 6.4 Pole/Zero Designs,242 6.4.1 First-Order Filters,242 6.4.2 Parametric Resonators and Equalizers,244 6.4.3 Notch and Comb Filters,249 6.5 Deconvolution,Inverse Filters,and Stability,254 6.6 Problems,259
viii CONTENTS 3.4 FIR and IIR Filters, 105 3.5 Causality and Stability, 112 3.6 Problems, 117 4 FIR Filtering and Convolution 121 4.1 Block Processing Methods, 122 4.1.1 Convolution, 122 4.1.2 Direct Form, 123 4.1.3 Convolution Table, 126 4.1.4 LTI Form, 127 4.1.5 Matrix Form, 129 4.1.6 Flip-and-Slide Form, 131 4.1.7 Transient and Steady-State Behavior, 132 4.1.8 Convolution of Infinite Sequences, 134 4.1.9 Programming Considerations, 139 4.1.10 Overlap-Add Block Convolution Method, 143 4.2 Sample Processing Methods, 146 4.2.1 Pure Delays, 146 4.2.2 FIR Filtering in Direct Form, 152 4.2.3 Programming Considerations, 160 4.2.4 Hardware Realizations and Circular Buffers, 162 4.3 Problems, 178 5 z-Transforms 183 5.1 Basic Properties, 183 5.2 Region of Convergence, 186 5.3 Causality and Stability, 193 5.4 Frequency Spectrum, 196 5.5 Inverse z-Transforms, 202 5.6 Problems, 210 6 Transfer Functions 214 6.1 Equivalent Descriptions of Digital Filters, 214 6.2 Transfer Functions, 215 6.3 Sinusoidal Response, 229 6.3.1 Steady-State Response, 229 6.3.2 Transient Response, 232 6.4 Pole/Zero Designs, 242 6.4.1 First-Order Filters, 242 6.4.2 Parametric Resonators and Equalizers, 244 6.4.3 Notch and Comb Filters, 249 6.5 Deconvolution, Inverse Filters, and Stability, 254 6.6 Problems, 259
CONTENTS 4 7 Digital Filter Realizations 265 7.1 Direct Form,265 7.2 Canonical Form,271 7.3 Cascade Form,277 7.4 Cascade to Canonical,284 7.5 Hardware Realizations and Circular Buffers,293 7.6 Quantization Effects in Digital Filters,305 7.7 Problems,306 8 Signal Processing Applications 316 8.1 Digital Waveform Generators,316 8.1.1 Sinusoidal Generators,316 8.1.2 Periodic Waveform Generators,321 8.1.3 Wavetable Generators,330 8.2 Digital Audio Effects,349 8.2.1 Delays,Echoes,and Comb Filters,350 8.2.2 Flanging,Chorusing,and Phasing,355 8.2.3 Digital Reverberation,362 8.2.4 Multitap Delays,374 8.2.5 Compressors,Limiters,Expanders,and Gates,378 8.3 Noise Reduction and Signal Enhancement,382 8.3.1 Noise Reduction Filters,382 8.3.2 Notch and Comb Filters,398 8.3.3 Line and Frame Combs for Digital TV,409 8.3.4 Signal Averaging,421 8.3.5 Savitzky-Golay Smoothing Filters*,427 8.4 Problems,453 9 DFT/FFT Algorithms 464 9.1 Frequency Resolution and Windowing,464 9.2 DTFT Computation,475 9.2.1 DTFT at a Single Frequency,475 9.2.2 DTFT over Frequency Range,478 9.2.3DFT,479 9.2.4 Zero Padding,481 9.3 Physical versus Computational Resolution,482 9.4 Matrix Form of DFT,486 9.5 Modulo-N Reduction,489 9.6 Inverse DFT,496 9.7 Sampling of Periodic Signals and the DFT,499 9.8FFT,504 9.9 Fast Convolution,515 9.9.1 Circular Convolution,515 9.9.2 Overlap-Add and Overlap-Save Methods,520 9.10 Problems,523
CONTENTS ix 7 Digital Filter Realizations 265 7.1 Direct Form, 265 7.2 Canonical Form, 271 7.3 Cascade Form, 277 7.4 Cascade to Canonical, 284 7.5 Hardware Realizations and Circular Buffers, 293 7.6 Quantization Effects in Digital Filters, 305 7.7 Problems, 306 8 Signal Processing Applications 316 8.1 Digital Waveform Generators, 316 8.1.1 Sinusoidal Generators, 316 8.1.2 Periodic Waveform Generators, 321 8.1.3 Wavetable Generators, 330 8.2 Digital Audio Effects, 349 8.2.1 Delays, Echoes, and Comb Filters, 350 8.2.2 Flanging, Chorusing, and Phasing, 355 8.2.3 Digital Reverberation, 362 8.2.4 Multitap Delays, 374 8.2.5 Compressors, Limiters, Expanders, and Gates, 378 8.3 Noise Reduction and Signal Enhancement, 382 8.3.1 Noise Reduction Filters, 382 8.3.2 Notch and Comb Filters, 398 8.3.3 Line and Frame Combs for Digital TV, 409 8.3.4 Signal Averaging, 421 8.3.5 Savitzky-Golay Smoothing Filters∗, 427 8.4 Problems, 453 9 DFT/FFT Algorithms 464 9.1 Frequency Resolution and Windowing, 464 9.2 DTFT Computation, 475 9.2.1 DTFT at a Single Frequency, 475 9.2.2 DTFT over Frequency Range, 478 9.2.3 DFT, 479 9.2.4 Zero Padding, 481 9.3 Physical versus Computational Resolution, 482 9.4 Matrix Form of DFT, 486 9.5 Modulo-N Reduction, 489 9.6 Inverse DFT, 496 9.7 Sampling of Periodic Signals and the DFT, 499 9.8 FFT, 504 9.9 Fast Convolution, 515 9.9.1 Circular Convolution, 515 9.9.2 Overlap-Add and Overlap-Save Methods, 520 9.10 Problems, 523
CONTENTS 10 FIR Digital Filter Design 532 10.1 Window Method,532 10.1.1 Ideal Filters,532 10.1.2 Rectangular Window,535 10.1.3 Hamming Window,540 10.2 Kaiser Window,541 10.2.1 Kaiser Window for Filter Design,541 10.2.2 Kaiser Window for Spectral Analysis,555 10.3 Frequency Sampling Method,558 10.4 Other FIR Design Methods,558 10.5 Problems,559 11 IIR Digital Filter Design 563 11.1 Bilinear Transformation,563 11.2 First-Order Lowpass and Highpass Filters,566 11.3 Second-Order Peaking and Notching Filters,573 11.4 Parametric Equalizer Filters,581 11.5 Comb Filters,590 11.6 Higher-Order Filters,592 11.6.1 Analog Lowpass Butterworth Filters,594 11.6.2 Digital Lowpass Filters,599 11.6.3 Digital Highpass Filters,603 11.6.4 Digital Bandpass Filters,606 11.6.5 Digital Bandstop Filters,611 11.6.6 Chebyshev Filter Design*,615 11.7 Problems,628 12 Interpolation,Decimation,and Oversampling 632 12.1 Interpolation and Oversampling,632 12.2 Interpolation Filter Design*,638 12.2.1 Direct Form,638 12.2.2 Polyphase Form,640 12.2.3 Frequency Domain Characteristics,645 12.2.4 Kaiser Window Designs,647 12.2.5 Multistage Designs,649 12.3 Linear and Hold Interpolators*,657 12.4 Design Examples*,661 12.4.1 4-fold Interpolators,661 12.4.2 Multistage 4-fold Interpolators,667 12.4.3 DAC Equalization,671 12.4.4 Postfilter Design and Equalization,674 12.4.5 Multistage Equalization,678 12.5 Decimation and Oversampling*,686 12.6 Sampling Rate Converters*,691 12.7 Noise Shaping Quantizers*,698 12.8 Problems,705
x CONTENTS 10 FIR Digital Filter Design 532 10.1 Window Method, 532 10.1.1 Ideal Filters, 532 10.1.2 Rectangular Window, 535 10.1.3 Hamming Window, 540 10.2 Kaiser Window, 541 10.2.1 Kaiser Window for Filter Design, 541 10.2.2 Kaiser Window for Spectral Analysis, 555 10.3 Frequency Sampling Method, 558 10.4 Other FIR Design Methods, 558 10.5 Problems, 559 11 IIR Digital Filter Design 563 11.1 Bilinear Transformation, 563 11.2 First-Order Lowpass and Highpass Filters, 566 11.3 Second-Order Peaking and Notching Filters, 573 11.4 Parametric Equalizer Filters, 581 11.5 Comb Filters, 590 11.6 Higher-Order Filters, 592 11.6.1 Analog Lowpass Butterworth Filters, 594 11.6.2 Digital Lowpass Filters, 599 11.6.3 Digital Highpass Filters, 603 11.6.4 Digital Bandpass Filters, 606 11.6.5 Digital Bandstop Filters, 611 11.6.6 Chebyshev Filter Design∗, 615 11.7 Problems, 628 12 Interpolation, Decimation, and Oversampling 632 12.1 Interpolation and Oversampling, 632 12.2 Interpolation Filter Design∗, 638 12.2.1 Direct Form, 638 12.2.2 Polyphase Form, 640 12.2.3 Frequency Domain Characteristics, 645 12.2.4 Kaiser Window Designs, 647 12.2.5 Multistage Designs, 649 12.3 Linear and Hold Interpolators∗, 657 12.4 Design Examples∗, 661 12.4.1 4-fold Interpolators, 661 12.4.2 Multistage 4-fold Interpolators, 667 12.4.3 DAC Equalization, 671 12.4.4 Postfilter Design and Equalization, 674 12.4.5 Multistage Equalization, 678 12.5 Decimation and Oversampling∗, 686 12.6 Sampling Rate Converters∗, 691 12.7 Noise Shaping Quantizers∗, 698 12.8 Problems, 705
CONTENTS 发 13 Appendices 713 A Random Signals*,713 A.1 Autocorrelation Functions and Power Spectra,713 A.2 Filtering of Random Signals,717 B Random Number Generators,719 B.1 Uniform and Gaussian Generators,719 B.2 Low-Frequency Noise Generators*,724 B.3 1/f Noise Generators*,729 B.4 Problems,733 C Complex Arithmetic in C,736 D MATLAB Functions,739 References 758 Index 775
CONTENTS xi 13 Appendices 713 A Random Signals∗, 713 A.1 Autocorrelation Functions and Power Spectra, 713 A.2 Filtering of Random Signals, 717 B Random Number Generators, 719 B.1 Uniform and Gaussian Generators, 719 B.2 Low-Frequency Noise Generators∗, 724 B.3 1/f Noise Generators∗, 729 B.4 Problems, 733 C Complex Arithmetic in C, 736 D MATLAB Functions, 739 References 758 Index 775
Preface This book provides an applications-oriented introduction to digital signal processing written primarily for electrical engineering undergraduates.Practicing engineers and graduate students may also find it useful as a first text on the subject. Digital signal processing is everywhere.Today's college students hear "DSp"all the time in their everyday life-from their CD players,to their electronic music synthesizers, to the sound cards in their PCs.They hear all about "DSP chips","oversampling digital filters","1-bit A/D and D/A converters","wavetable sound synthesis","audio effects processors","all-digital audio studios".By the time they reach their junior year,they are already very eager to learn more about DSP. Approach The learning of DSP can be made into a rewarding,interesting,and fun experience for the student by weaving into the material several applications,such as the above,that serve as vehicles for teaching the basic DSP concepts,while generating and maintaining student interest.This has been the guiding philosophy and objective in writing this text. As a result,the book's emphasis is more on signal processing than discrete-time system theory,although the basic principles of the latter are adequately covered. The book teaches by example and takes a hands-on practical approach that empha- sizes the algorithmic,computational,and programming aspects of DSP.It contains a large number of worked examples,computer simulations and applications,and several C and MATLAB functions for implementing various DSP operations.The practical slant of the book makes the concepts more concrete. Use The book may be used at the junior or senior level.It is based on a junior-level DSP course that I have taught at Rutgers since 1988.The assumed background is only a first course on linear systems.Sections marked with an asterisk(*)are more appropriate for a second or senior elective course on DSP.The rest can be covered at the junior level. The included computer experiments can form the basis of an accompanying DSP lab course,as is done at Rutgers. A solutions manual,which also contains the results of the computer experiments, is available from the publisher.The C and MATLAB functions may be obtained via anonymous FTP from the Internet site ece.rutgers.edu in the directory /pub/sjo or xiii
Preface This book provides an applications-oriented introduction to digital signal processing written primarily for electrical engineering undergraduates. Practicing engineers and graduate students may also find it useful as a first text on the subject. Digital signal processing is everywhere. Today’s college students hear “DSP” all the time in their everyday life—from their CD players, to their electronic music synthesizers, to the sound cards in their PCs. They hear all about “DSP chips”, “oversampling digital filters”, “1-bit A/D and D/A converters”, “wavetable sound synthesis”, “audio effects processors”, “all-digital audio studios”. By the time they reach their junior year, they are already very eager to learn more about DSP. Approach The learning of DSP can be made into a rewarding, interesting, and fun experience for the student by weaving into the material several applications, such as the above, that serve as vehicles for teaching the basic DSP concepts, while generating and maintaining student interest. This has been the guiding philosophy and objective in writing this text. As a result, the book’s emphasis is more on signal processing than discrete-time system theory, although the basic principles of the latter are adequately covered. The book teaches by example and takes a hands-on practical approach that emphasizes the algorithmic, computational, and programming aspects of DSP. It contains a large number of worked examples, computer simulations and applications, and several C and MATLAB functions for implementing various DSP operations. The practical slant of the book makes the concepts more concrete. Use The book may be used at the junior or senior level. It is based on a junior-level DSP course that I have taught at Rutgers since 1988. The assumed background is only a first course on linear systems. Sections marked with an asterisk (∗) are more appropriate for a second or senior elective course on DSP. The rest can be covered at the junior level. The included computer experiments can form the basis of an accompanying DSP lab course, as is done at Rutgers. A solutions manual, which also contains the results of the computer experiments, is available from the publisher. The C and MATLAB functions may be obtained via anonymous FTP from the Internet site ece.rutgers.edu in the directory /pub/sjo or xiii
xiv PREFACE by pointing a Web browser to the book's wWW home page at the URL: http://www.ece.rutgers.edu/~orfanidi/intro2sp Contents and Highlights Chapters 1 and 2 contain a discussion of the two key DSP concepts of sampling and quantization.The first part of Chapter 1 covers the basic issues of sampling,aliasing, and analog reconstruction at a level appropriate for juniors.The second part is more advanced and discusses the practical issues of choosing and defining specifications for antialiasing prefilters and anti-image postfilters. Chapter 2 discusses the quantization process and some practical implementations of A/D and D/A converters,such as the conversion algorithm for bipolar two's comple- ment successive approximation converters.The standard model of quantization noise is presented,as well as the techniques of oversampling,noise shaping,and dithering The tradeoff between oversampling ratio and savings in bits is derived.This material is continued in Section 12.7 where the implementation and operation of delta-sigma noise shaping quantizers is considered. Chapter 3 serves as a review of basic discrete-time systems concepts,such as linear- ity,time-invariance,impulse response,convolution,FIR and IIR filters,causality,and stability.It can be covered quickly as most of this material is assumed known from a prerequisite linear systems course. Chapter 4 focuses on FIR filters and its purpose is to introduce two basic signal processing methods:block-by-block processing and sample-by-sample processing.In the block processing part,we discuss various approaches to convolution,transient and steady-state behavior of filters,and real-time processing on a block-by-block basis using the overlap-add method and its software implementation.This is further discussed in Section 9.9 using the FFT. In the sample processing part,we introduce the basic building blocks of filters: adders,multipliers,and delays.We discuss block diagrams for FIR filters and their time-domain operation on a sample-by-sample basis.We put a lot of emphasis on the concept of sample processing algorithm,which is the repetitive series of computations that must be carried out on each input sample. We discuss the concept of circular buffers and their use in implementing delays and FIR filters.We present a systematic treatment of the subject and carry it on to the remainder of the book.The use of circular delay-line buffers is old,dating back at least 25 years with its application to computer music.However,it has not been treated systematically in DSP texts.It has acquired a new relevance because all modern DSP chips use it to minimize the number of hardware instructions. Chapter 5 covers the basics of z-transforms.We emphasize the z-domain view of causality,stability,and frequency spectrum.Much of this material may be known from an earlier linear system course. Chapter 6 shows the equivalence of various ways of characterizing a linear filter and illustrates their use by example.It also discusses topics such as sinusoidal and steady-state responses,time constants of filters,simple pole/zero designs of first-and second-order filters as well as comb and notch filters.The issues of inverse filtering and causality are also considered
xiv PREFACE by pointing a Web browser to the book’s WWW home page at the URL: http://www.ece.rutgers.edu/~orfanidi/intro2sp Contents and Highlights Chapters 1 and 2 contain a discussion of the two key DSP concepts of sampling and quantization. The first part of Chapter 1 covers the basic issues of sampling, aliasing, and analog reconstruction at a level appropriate for juniors. The second part is more advanced and discusses the practical issues of choosing and defining specifications for antialiasing prefilters and anti-image postfilters. Chapter 2 discusses the quantization process and some practical implementations of A/D and D/A converters, such as the conversion algorithm for bipolar two’s complement successive approximation converters. The standard model of quantization noise is presented, as well as the techniques of oversampling, noise shaping, and dithering. The tradeoff between oversampling ratio and savings in bits is derived. This material is continued in Section 12.7 where the implementation and operation of delta-sigma noise shaping quantizers is considered. Chapter 3 serves as a review of basic discrete-time systems concepts, such as linearity, time-invariance, impulse response, convolution, FIR and IIR filters, causality, and stability. It can be covered quickly as most of this material is assumed known from a prerequisite linear systems course. Chapter 4 focuses on FIR filters and its purpose is to introduce two basic signal processing methods: block-by-block processing and sample-by-sample processing. In the block processing part, we discuss various approaches to convolution, transient and steady-state behavior of filters, and real-time processing on a block-by-block basis using the overlap-add method and its software implementation. This is further discussed in Section 9.9 using the FFT. In the sample processing part, we introduce the basic building blocks of filters: adders, multipliers, and delays. We discuss block diagrams for FIR filters and their time-domain operation on a sample-by-sample basis. We put a lot of emphasis on the concept of sample processing algorithm, which is the repetitive series of computations that must be carried out on each input sample. We discuss the concept of circular buffers and their use in implementing delays and FIR filters. We present a systematic treatment of the subject and carry it on to the remainder of the book. The use of circular delay-line buffers is old, dating back at least 25 years with its application to computer music. However, it has not been treated systematically in DSP texts. It has acquired a new relevance because all modern DSP chips use it to minimize the number of hardware instructions. Chapter 5 covers the basics of z-transforms. We emphasize the z-domain view of causality, stability, and frequency spectrum. Much of this material may be known from an earlier linear system course. Chapter 6 shows the equivalence of various ways of characterizing a linear filter and illustrates their use by example. It also discusses topics such as sinusoidal and steady-state responses, time constants of filters, simple pole/zero designs of first- and second-order filters as well as comb and notch filters. The issues of inverse filtering and causality are also considered
