digital_signal_processing_principles_algorithms_and_applications_third_edition.pdf
Document Details
Uploaded by SportyHilbert
Tags
Related
- Mastering The Fourier Transform: From Theory To Application PDF
- Digitale Signalverarbeitung - Studienbrief PDF
- Fast Fourier Transform PDF
- Prentice-HallDigital-Signal-Processing-Principles-Algorithms-ApplicationsJohn-G.-Proakis-Dimitris-G.-Manolakis3rd-.pdf
- UNIT-2 DSP PDF
- Lecture 5 Computer Graphics PDF
Full Transcript
77un/ Edition DIGITAL SIGNAL PROCESSING Principles, Algorithms, m l Applications J o h n G. Proakis Dimitris G. M anolakis Digital Signal Processing Principles, Algorithms, and Applications Third E dition John G. Proakis Northeastern U niversity Dimitr...
77un/ Edition DIGITAL SIGNAL PROCESSING Principles, Algorithms, m l Applications J o h n G. Proakis Dimitris G. M anolakis Digital Signal Processing Principles, Algorithms, and Applications Third E dition John G. Proakis Northeastern U niversity Dimitris G. Manolakis Boston C ollege PRENTICE-HALL INTERNATIONAL, INC. This edition may be sold only in those countries to which it is consigned by Prentice-Hall International. It is not to be reexported and it is not for sale in the U.S.A., Mexico, or Canada. © 1996 by Prentice-Hall, Inc. Simon & Schuster/A Viacom Company U pper Saddle River, New Jersey 07458 All rights reserved. No part of this book may be reproduced, in any form or by any means, without permission in writing from the publisher. The author and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The author and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this book. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of. the furnishing, performance, or use of these programs. Printed in the United States of America 10 9 8 7 6 5 ISBN 0-13-3TM33fl-cl Prentice-Hall International (U K ) Limited. L ondon Prentice-Hall of Australia Pty. Limited, Sydney Prentice-Hall Canada, Inc., Toronto Prentice-Hall Hispanoamericana. S.A., M exico Prentice-Hall of India Private Limited, N ew D elhi Prentice-Hall of Japan, Inc., T okyo Simon & Schuster Asia Pie, Ltd., Singapore Editora Prentice-Hall do Brasil, Ltda., R io de Janeiro Prentice-Hall, Inc, Upper Saddle River, N ew Jersey Contents PREFACE xiii 1 INTRODUCTION 1 1.1 S ignals, S ystem s, and S ignal P ro cessin g 2 1.1.1 Basic Elements of a Digital Signal Processing System. 4 1.1.2 A dvantages of Digital over Analog Signal Processing, 5 1.2 C lassificatio n o f Signals 6 1.2.1 Multichannel and Multidimensional Signals. 7 1.2.2 Continuous-Time Versus Discrete-Time Signals. 8 1.2.3 Continuous-Valued Versus Discrete-Valued Signals. 10 1.2.4 Determ inistic Versus Random Signals, 11 1.3 T h e C o n c e p t o f F re q u e n c y in C o n tin u o u s -T im e an d D isc re te -T im e S ignals 14 1.3.1 Continuous-Time Sinusoidal Signals, 14 1.3.2 Discrete-Time Sinusoidal Signals. 16 1.3.3 Harmonically Related Complex Exponentials, 19 1.4 A n a lo g -to -D ig ita l an d D ig ita l-to -A n a lo g C o n v e rs io n 21 1.4.1 Sampling of Analog Signals, 23 1.4.2 The Sampling Theorem , 29 1.4.3 Q uantization of Continuous-Am plitude Signals, 33 1.4.4 Quantization of Sinusoidal Signals, 36 1.4.5 Coding of Quantized Samples, 38 1.4.6 Digital-to-Analog Conversion, 38 1.4.7 Analysis of Digital Signals and Systems Versus Discrete-Time Signals and Systems, 39 S u m m a ry a n d R e fe re n c e s 39 Problems 40 iii iv Contents 2 DISCRETE-TIME SIGNALS AND SYSTEMS 43 2.1 D isc rete-T im e S ignals 43 2.1.1 Some Elem entary Discrete-Time Signals, 45 2.1.2 Classification of Discrete-Time Signals, 47 2.1.3 Simple Manipulations of Discrete-Time Signals, 52 2.2 D isc re te -T im e S ystem s 56 2.2.1 Input-O utput Description of Systems, 56 2.2.2 Block Diagram Representation of Discrete-Time Systems, 59 2.2.3 Classification of Discrete-Time Systems, 62 2.2.4 Interconnection of Discrete-Tim e Systems, 70 2.3 A n alysis o f D isc re te -T im e L in e a r T im e -In v a ria n t S ystem s 72 2.3.1 Techniques for the Analysis of Linear Systems, 72 2.3.2 Resolution of a Discrete-Time Signal into Impulses, 74 2.3.3 Response of LTI Systems to A rbitrary Inputs: The Convolution Sum, 75 2.3.4 Properties of Convolution and the Interconnection of LTI Systems, 82 2.3.5 Causal Linear Tim e-Invariant Systems. 86 2.3.6 Stability of Linear Tim e-Invariant Systems, 87 2.3.7 Systems with Fim te-D uration and Infinite-Duration Impulse Response. 90 2.4 D isc rete-T im e System s D e s c rib e d by D iffe re n c e E q u a tio n s 91 2.4.1 Recursive and Nonrecursive Discrete-Tim e Systems, 92 2.4.2 Linear Time-Invariant Systems Characterized by Constant-Coefficient Difference Equations, 95 2.4.3 Solution of Linear Constant-Coefficient Difference Equations. 100 2.4.4 The Impulse Response of a Linear Tim e-Invariant Recursive System, 108 2.5 Im p le m e n ta tio n o f D isc re te -T im e S ystem s 111 2.5.1 Structures for the Realization of Linear Tim e-Invariant Systems, 111 2.5.2 Recursive and Nonrecursive Realizations of FIR Systems, 116 2.6 C o rre la tio n of D isc re te -T im e S ignals 118 2.6.1 Crosscorrelation and A utocorrelation Sequences, 120 2.6.2 Properties of the A utocorrelation and Crosscorrelation Sequences, 122 2.6.3 Correlation of Periodic Sequences, 124 2.6.4 Com putation of Correlation Sequences, 130 2.6.5 Input-O utput Correlation Sequences, 131 2.7 S u m m ary a n d R e fe re n c e s 134 Problems 135 Contents 3 THE Z-TRANSFORM AND ITS APPLICATION TO THE ANALYSIS OF LTI SYSTEMS 151 3.1 T h e r-T ra n sfo rm 151 3.1.1 The Direct ^-Transform. 152 3.1.2 The inverse : -Transform, 160 3.2 P ro p e rtie s o f th e ; -T ra n sfo rm 161 3.3 R a tio n a l c-T ran sfo rm s 172 3.3.1 Poles and Zeros, 172 3.3.2 Pole Location and Time-Domain Behavior for Causal Signals. 178 3.3.3 The System Function of a Linear Tim e-Invariant System. 181 3.4 In v e rs io n o f th e ^ -T ra n sfo rm 184 3.4.1 The Inverse ; -Transform by Contour Integration. 184 3.4.2 The Inverse ;-Transform by Power Series Expansion. 186 3.4.3 The Inverse c-Transform by Partial-Fraction Expansion. 188 3.4.4 Decomposition of Rational c-Transforms. 195 3.5 T h e O n e -sid e d ^ -T ra n sfo rm 197 3.5.1 Definition and Properties, 197 3.5.2 Solution of Difference Equations. 201 3.6 A n aly sis o f L in e a r T im e -In v a ria n t S ystem s in th e --D o m a in 203 3.6.1 Response of Systems with Rational System Functions. 203 3.6.2 Response of P ole-Z ero Systems with Nonzero Initial Conditions. 204 3.6.3 Transient and Steady-State Responses, 206 3.6.4 Causality and Stability. 208 3.6.5 P ole-Z ero Cancellations. 210 3.6.6 M ultiple-Order Poles and Stability. 211 3.6.7 The Schur-C ohn Stability Test, 213 3.6.8 Stability of Second-Order Systems. 215 3.7 S u m m ary an d R e fe re n c e s 219 P ro b le m s 220 4 FREQUENCY ANALYSIS OF SIGNALS AND SYSTEMS 230 4.1 F re q u e n c y A n aly sis o f C o n tin u o u s-T im e Signals 230 4.1.1 The Fourier Series for Continuous-Time Periodic Signals. 232 4.1.2 Power Density Spectrum of Periodic Signals. 235 4.1.3 The Fourier Transform for Continuous-Time Aperiodic Signals, 240 4.1.4 Energy Density Spectrum of Aperiodic Signals. 243 4.2 F re q u e n c y A n aly sis o f D isc re te -T im e Signals 247 4.2.1 The Fourier Series for Discrete-Time Periodic Signals, 247 V) Contents 4.2.2 Power Density Spectrum of Periodic Signals. 250 4.2.3 The Fourier Transform of Discrete-Time Aperiodic Signals. 253 4.2.4 Convergence of the Fourier Transform. 256 4.2.5 Energy Density Spectrum of Aperiodic Signals, 260 4.2.6 Relationship of the Fourier Transform to the i-Transform , 264 4.2.7 The Cepstrum, 265 4.2.8 The Fourier Transform of Signals with Poles on the Unit Circle, 267 4.2.9 The Sampling Theorem Revisited, 269 4.2.10 Frequency-Domain Classification of Signals: The Concept of Bandwidth, 279 4.2.11 The Frequency Ranges of Some N atural Signals. 282 4.2.12 Physical and M athematical Dualities. 282 4.3 P ro p e rtie s of th e F o u rie r T ra n s fo rm fo r D isc re te -T im e S ignals 286 4.3.1 Symmetry Properties of the Fourier Transform, 287 4.3.2 Fourier Transform Theorems and Properties, 294 4.4 F re q u e n c y -D o m a in C h a ra c te ristic s of L in e a r T im e -In v a ria n t S ystem s 305 4.4.1 Response to Complex Exponential and Sinusoidal Signals: The Frequency Response Function. 306 44.2 Steady-State and Transient Response to Sinusoidal Input Signals. 314 4.4.3 Steady-State Response to Periodic Input Signals, 315 4.4.4 Response to Aperiodic Input Signals. 316 4.4.5 Relationships Between the System Function and the Frequency Response Function. 319 4.4.6 Com putation of the Frequency Response Function. 321 4.4.7 Input-O utput Correlation Functions and Spectra, 325 4.4.8 Correlation Functions and Power Spectra for Random Input Signals. 327 4.5 L in e a r T im e -In v a ria n t S ystem s as F re q u e n c y -S e le c tiv e F ilters 330 4.5.1 Ideal Filter Characteristics, 331 4.5.2 Lowpass, Highpass, and Bandpass Filters, 333 4,5.3 Digital Resonators, 340 4.5.4 Notch Filters, 343 4.5.5 Comb Filters. 345 4.5.6 All-Pass Filters. 350 4.5.7 Digital Sinusoidal Oscillators, 352 4.6 In v e rse S y stem s an d D e c o n v o lu tio n 355 4.6.1 Invertibility of Linear Tim e-Invariant Systems, 356 4.6.2 Minimum-Phase. Maximum-Phase, and Mixed-Phase Systems. 359 4.6.3 System Identification and Deconvolution, 363 4.6.4 Hom om orphic Deconvolution. 365 Contents vii 4.7 S u m m ary a n d R e fe re n c e s 367 P ro b le m s 368 5 THE DISCRETE FOURIER TRANSFORM: ITS PROPERTIES AND APPLICATIONS 394 5.1 F re q u e n c y D o m a in Sam pling: T h e D isc re te F o u rie r T ra n s fo rm 394 5.1.1 Frequency-Dom ain Sampling and Reconstruction of Discrete-Time Signals. 394 5.1.2 The Discrete Fourier Transform (DFT). 399 5.1.3 The D FT as a Linear Transform ation. 403 5.1.4 Relationship of the DFT to O ther Transforms, 407 5.2 P ro p e rtie s o f th e D F T 409 5.2.1 Periodicity. Linearity, and Symmetry Properties, 410 5.2.2 Multiplication of Two DFTs and Circular Convolution. 415 5.2.3 Additional DFT Properties, 421 5.3 L in e a r F ilte rin g M e th o d s B ased on th e D F T 425 5.3.1 Use of the DFT in Linear Filtering. 426 5.3.2 Filtering of Long Data Sequences. 430 5.4 F re q u e n c y A n aly sis o f S ignals U sing th e D F T 433 5.5 S u m m ary an d R e fe re n c e s 440 P ro b le m s 440 6 EFFICIENT COMPUTATION OF THE DFT: FAST FOURIER TRANSFORM ALGORITHMS 448 6.1 E fficien t C o m p u ta tio n of th e D F T : F F T A lg o rith m s 448 6.1.1 Direct Com putation of the DFT, 449 6.1.2 D ivide-and-Conquer Approach to Com putation of the DFT. 450 6.1.3 Radix-2 FFT Algorithms. 456 6.1.4 Radix-4 FFT Algorithms. 465 6.1.5 Split-Radix FFT Algorithms, 470 6.1.6 Im plem entation of FFT Algorithms. 473 6.2 A p p lic a tio n s o f F F T A lg o rith m s 475 6.2.1 Efficient Com putation of the D FT of Two Real Sequences. 475 6.2.2 Efficient Com putation of the D FT of a Z N -Point Real Sequence, 476 6.2.3 Use of the FFT Algorithm in Linear Filtering and Correlation, 477 6.3 A L in e a r F ilte rin g A p p ro a c h to C o m p u ta tio n o f th e D F T 479 6.3.1 The Goertzel Algorithm, 480 6.3.2 The Chirp-z Transform Algorithm, 482 viii Contents 6.4 Q u a n tiz a tio n E ffects in the C o m p u ta tio n o f th e D F T 486 6.4.1 Quantization Errors in the Direct Com putation of the DFT. 487 6.4.2 Quantization Errors in FFT Algorithms. 489 6.5 S u m m ary an d R e fe re n c e s 493 P ro b le m s 494 7 IMPLEMENTATION OF DISCRETE-TIME SYSTEMS 500 7.1 S tru c tu res fo r th e R e a liz a tio n o f D isc re te -T im e S ystem s 500 7.2 S tru c tu res fo r F IR System s 502 7.2.1 Direcl-Form Structure, 503 7.2.2 Cascade-Form Structures. 504 7.2.3 Frequency-Sampling S tructures1. 506 7.2.4 Lattice Structure. 511 S tru c tu re s for IIR S ystem s 519 7.3.1 Direct-Form Structures. 519 7.3.2 Signal Flow Graphs and Transposed Structures. 521 7.3.3 Cascade-Form Structures, 526 7.3.4 Parallel-Form Structures. 529 7.3.5 Lattice and Lattice-Ladder Structures for IIR Systems, 531 S tate-S p a ce System A n aly sis a n d S tru c tu re s 539 7.4.1 State-Space Descriptions of Systems Characterized by Difference Equations. 540 7.4.2 Solution of the State-Space Equations. 543 7.4.3 Relationships Between Input-O utput and State-Space Descriptions, 545 7.4.4 State-Space Analysis in the z-Domain, 550 7.4.5 Additional State-Space Structures. 554 R e p re s e n ta tio n of N u m b e rs 556 7.5.1 Fixed-Point Representation of Numbers. 557 7.5.2 Binary Floating-Point R epresentation of Numbers. 561 7.5.3 E rrors Resulting from R ounding and Truncation. 564 Q u a n tiz a tio n of F ilte r C o e fficien ts 569 7.6.1 Analysis of Sensitivity to Quantization of Filter Coefficients. 569 7.6.2 Q uantization of Coefficients in FIR Filters. 578 7.7 R o u n d -O ff E ffects in D igital F ilte rs 582 7.7.1 Limit-Cycle Oscillations in Recursive Systems. 583 7.7.2 Scaling to Prevent Overflow, 588 7.7.3 Statistical Characterization of Q uantization Effects in Fixed-Point Realizations of Digital Filters. 590 7.8 S u m m ary a n d R e fe re n c e s 598 P ro b le m s 600 Contents ix 8 DESIGN OF DIGITAL FILTERS 614 8.1 G e n e ra l C o n s id e ra tio n s 614 8.1.1 Causality and Its Implications. 615 8.1.2 Characteristics of Practical Frequency-Selective Filters. 619 8.2 D e sig n o f F IR F ilters 620 8.2.1 Symmetric and Antisym m eiric FIR Filters, 620 8.2.2 Design of Linear-Phase FIR Filters Using Windows, 623 8.2.3 Design of Linear-Phase FIR Filters by the Frequency-Sampling M ethod, 630 8.2.4 Design of Optimum Equiripple Linear-Phase FIR Filters, 637 8.2.5 Design of FIR Differentiators, 652 8.2.6 Design of Hilbert Transformers, 657 8.2.7 Comparison of Design M ethods for Linear-Phase FIR Filters, 662 8.3 D esig n o f I I R F ilters F ro m A n a lo g F iiters 666 8.3.1 IIR Filter Design by Approxim ation of Derivatives. 667 8.3.2 IIR Filter Design by Impulse Invariance. 671 8.3.3 IIR Filter Design by the Bilinear Transform ation, 676 8.3.4 The M atched-; Transform ation, 681 8.3.5 Characteristics of Commonly Used Analog Filters. 681 8.3.6 Some Examples of Digital Filter Designs Based on the Bilinear Transform ation. 692 8.4 F re q u e n c y T ra n s fo rm a tio n s 692 8.4.1 Frequency Transform ations in the Analog Dom ain, 693 8.4.2 Frequency Transform ations in the Digital Dom ain. 698 8.5 D esig n o f D ig ital F ilters B a sed on L e a st-S q u a re s M e th o d 701 8.5.1 Pade Approxim ation Method, 701 8.5.2 Least-Squares Design Methods, 706 8.5.3 FIR Least-Squares Inverse (W iener) Filters, 711 8.5.4 Design of IIR Filters in the Frequency Dom ain, 719 8.6 S u m m ary an d R e fe re n c e s 724 P ro b le m s 726 9 SAMPLING AND RECONSTRUCTION OF SIGNALS 738 9.1 S am p lin g o f B a n d p a ss S ignals 738 9.1.1 R epresentation of Bandpass Signals, 738 9.1.2 Sampling of Bandpass Signals, 742 9.1.3 Discrete-Time Processing of Continuous-Time Signals, 746 9.2 A n a lo g -to -D ig ita l C o n v e rsio n 748 9.2.1 Sample-and-Hold. 748 9.2.2 Quantization and Coding, 750 9.2.3 Analysis of Q uantization Errors, 753 9.2.4 Oversampling A /D Converters, 756 X Contents 9.3 D ig ita l-to -A n a lo g C o n v e rsio n 763 9.3.1 Sample and Hold, 765 9.3.2 First-Order Hold. 768 9.3.3 Linear Interpolation with Delay, 771 9.3.4 Oversampling D/A Converters, 774 9.4 S u m m ary an d R e fe re n c e s 774 P ro b le m s 775 10 MULTIRATE DIGITAL SIGNAL PROCESSING 782 10.1 In tro d u c tio n 783 10.2 D e c im a tio n by a F a c to r D 784 10.3 In te rp o la tio n by a F a c to r / 787 10.4 S am p lin g R a te C o n v e rsio n by a R a tio n a l F a c to r I ID 790 10.5 F iite r D esig n an d Im p le m e n ta tio n for S a m p lin g -R ate C o n v e rsio n 792 10.5.1 Direct-Form FIR Filter Structures, 793 10.5.2 Polyphase Filter Structures, 794 10.5.3 Time-Variant Filter Structures. 800 10.6 M u ltistag e Im p le m e n ta tio n o f S a m p lin g -R a te C o n v e rs io n 806 10.7 S a m p lin g -R a te C o n v e rsio n o f B a n d p a ss S ignals 810 10.7.1 Decim ation and Interpolation by Frequency Conversion, 812 10.7.2 M odulation-Free Method for Decimation and Interpolation. 814 10.8 S a m p lin g -R a te C o n v e rsio n by an A rb itra ry F a c to r 815 10.8.1 First-O rder Approxim ation, 816 10.8.2 Second-Order Approximation (Linear Interpolation). 819 10.9 A p p lic a tio n s o f M u ltira te Signal P ro c essin g 821 10.9.1 Design of Phase Shifters. 821 10.9.2 Interfacing of Digital Systems with Different Sampling Rates, 823 10.9.3 Im plem entation of Narrowband Lowpass Filters, 824 10.9.4 Im plem entation of Digital Filter Banks. 825 10.9.5 Subband Coding of Speech Signals, 831 10.9.6 Q uadrature M irror Filters. 833 10.9.7 Transmultiplexers. 841 10.9.8 Oversampling A/D and D /A Conversion, 843 10.10 S u m m ary an d R e fe re n c e s 844 P ro b le m s 846 Contents xi 11 LINEAR PREDICTION AND OPTIMUM LINEAR FILTERS 852 11.1 In n o v a tio n s R e p re s e n ta tio n o f a S ta tio n a ry R a n d o m P ro c e ss 852 11.1.1 Rational Power Spectra. 854 11.1.2 Relationships Between the Filter Param eters and the Autocorrelation Sequence, 855 11.2 F o rw a rd an d B a ck w ard L in e a r P re d ictio n 857 11.2.1 Forw ard Linear Prediction, 857 11.2.2 Backward Linear Prediction, 860 11.2.3 The Optimum Reflection Coefficients for the Lattice Forward and Backward Predictors, 863 11.2.4 Relationship of an A R Process to Linear Prediction. 864 11.3 S o lu tio n o f th e N o rm al E q u a tio n s 864 11.3.1 The Levinson-Durbin Algorithm. 865 11.3.2 The Schiir Algorithm. 868 11.4 P ro p e rtie s o f th e L in e a r P re d ic tio n -E rro r F ilte rs 873 11.5 A R L attice an d A R M A L a ttic e -L a d d e r F ilters 876 11.5.1 AR LaLtice Structure. 877 11.5.2 A RM A Processes and Lattice-Ladder Filters. 878 11.6 W ie n e r F ilters fo r F ilterin g a n d P re d ictio n 880 11.6.1 FIR W iener Filter, 881 11.6.2 Orthogonality Principle in Linear M ean-Square Estimation, 884 11.6.3 IIR W iener Filter. 885 11.6.4 Noncausal Wiener Filter. 889 11.7 S u m m ary an d R e fe re n c e s 890 P ro b le m s 892 12 POWER SPECTRUM ESTIMATION 896 12.1 E stim a tio n o f S p e c tra from F in ite -D u ra tio n O b s e rv a tio n s o f Signals 896 12.1.1 Com putation of the Energy Density Spectrum. 897 12.1.2 Estim ation of the Autocorrelation and Power Spectrum of Random Signals: The Periodogram. 902 12.1.3 The Use of the DFT in Power Spectrum Estim ation, 906 12.2 N o n p a ra m e tric M e th o d s fo r P o w er S p ectru m E s tim a tio n 908 12.2.1 The B artlett Method: Averaging Periodograms, 910 12.2.2 The Welch Method: Averaging Modified Periodogram s, 911 12.2.3 The Blackman and Tukey Method: Smoothing the Periodogram, 913 12.2.4 Perform ance Characteristics of N onparam etric Power Spectrum Estim ators, 916 xii Contents 12.2.5 Com putational Requirem ents of Nonparam etric Power Spectrum Estimates, 919 12.3 P a ra m e tric M e th o d s fo r P o w er S p e c tru m E stim a tio n 920 12.3.1 Relationships Between the A utocorrelation and the Model Param eters, 923 12.3.2 The Y ule-W alker M ethod for the A R Model Param eters, 925 12.3.3 The Burg M ethod for the A R Model Param eters, 925 12.3.4 Unconstrained Least-Squares M ethod for the A R Model Param eters, 929 12.3.5 Sequential Estim ation M ethods for the A R Model Param eters, 930 12.3.6 Selection of A R Model O rder, 931 12.3.7 MA Model for Power Spectrum Estim ation, 933 12.3.8 A R M A Model for Power Spectrum Estim ation, 934 12.3.9 Some Experim ental Results, 936 12.4 M in im u m V a rian ce S p ectral E stim a tio n 942 12.5 E ig e n an aly sis A lg o rith m s fo r S p e c tru m E stim a tio n 946 12.5.1 Pisarenko Harm onic Decom position M ethod, 948 12.5.2 Eigen-decomposition of the A utocorrelation Matrix for Sinusoids in White Noise, 950 12.5.3 MUSIC Algorithm. 952 12.5.4 ESPR IT Algorithm, 953 12.5.5 O rder Selection Criteria. 955 12.5.6 Experim ental Results, 956 12.6 S u m m ary an d R e fe re n c e s 959 P ro b le m s 960 SPECTRA , A RANDOM SIGNALS CORRELATION FUNCTIONS, AND POWER A1 B RANDOM NUMBER GENERATORS B1 C TABLES OF TRANSITION COEFFICIENTS FOR THE DESIGN OF LINEAR-PHASE FIR FILTERS C1 D LIST OF MATLAB FUNCTIONS D1 REFERENCES AND BIBLIOGRAPHY R1 INDEX 11 Lj_ Preface T h is b o o k w as d e v e lo p e d b ased on o u r te ach in g o f u n d e rg ra d u a te and g ra d u a te level co u rse s in d ig ital signal p ro cessin g o v er th e p a s t several y ears. In this b o o k w e p re se n t th e fu n d a m e n ta ls o f d isc re te -tim e signals, system s, and m o d e rn d ig ital p ro cessin g a lg o rith m s an d a p p lic a tio n s fo r stu d e n ts in electrical e n g in e e r ing. c o m p u te r en g in eerin g , a n d c o m p u te r science. T h e b o o k is su itab le fo r e ith e r a o n e -se m e s te r o r a tw o -se m e ste r u n d e rg ra d u a te level c o u rse in d isc re te system s a n d dig ital signal p ro cessin g. It is also in te n d e d fo r use in a o n e -se m e s te r first-year g ra d u a te -le v e l co u rse in digital signal processing. It is a ssu m ed th a t th e s tu d e n t in electrical and c o m p u te r e n g in e e rin g has h ad u n d e rg ra d u a te c o u rses in a d v an ce d calculus (in clu d in g o rd in a ry d iffe re n tia l e q u a tio n s). an d lin ear sy stem s fo r c o n tin u o u s-tim e signals, including an in tro d u c tio n to th e L ap lace tran sfo rm. A lth o u g h the F o u rie r se ries a n d F o u rie r tra n sfo rm s of p e rio d ic an d a p e rio d ic signals a re d escrib ed in C h a p te r 4, we ex p ect th a t m any s tu d e n ts m ay have h ad th is m a te ria l in a p rio r course. A b ala n c e d co v erag e is p ro v id e d of b o th th e o ry an d p ra c tic a l ap p licatio n s. A larg e n u m b e r o f w ell d esigned p ro b le m s a re p ro v id e d to h e lp th e s tu d e n t in m a ste rin g th e su b ject m a tte r. A so lu tio n s m a n u a l is av ailab le fo r th e b en efit o f th e in stru c to r an d can be o b ta in e d fro m th e p u b lish er. T h e th ird e d itio n o f th e b o o k covers basically th e sa m e m a te ria l as th e se c o n d e d itio n , b u t is o rg an ized d ifferen tly. T h e m a jo r d ifferen ce is in th e o rd e r in w hich th e D F T a n d F F T alg o rith m s are co v ered. B a sed o n su g g estio n s m a d e by se v era l rev iew ers, w e n o w in tro d u c e th e D F T a n d d esc rib e its efficient c o m p u ta tio n im m e d ia te ly fo llo w ing o u r tr e a tm e n t of F o u rie r analysis. T his re o rg a n iz a tio n h as also allo w ed us to elim in a te re p e titio n o f so m e to p ics c o n cern in g th e D F T and its ap p licatio n s. In C h a p te r 1 w e d escrib e th e o p e ra tio n s in v o lv ed in th e an alo g -to -d ig ital c o n v ersio n o f an alo g signals. T h e p ro cess o f sa m p lin g a sin u so id is d escrib ed in so m e d e ta il an d th e p ro b le m o f aliasing is ex p lain ed. Signal q u a n tiz a tio n an d d ig ita l-to -a n a lo g co n v ersio n a re also d escrib ed in g e n e ra l term s, b u t th e analysis is p re s e n te d in su b s e q u e n t c h a p te rs. C h a p te r 2 is d e v o te d e n tire ly to th e c h a ra c te riz a tio n a n d analysis o f lin e a r tim e -in v a ria n t (sh ift-in v arian t) d isc re te -tim e system s a n d d isc re te -tim e signals in th e tim e d o m a in. T h e co n v o lu tio n sum is d e riv e d a n d system s a re categ o rized a c co rd in g to th e d u ra tio n of th e ir im p u lse re sp o n s e as a fin ite -d u ra tio n im p u lse xiii xiv Preface re sp o n se (F IR ) an d as an in fin ite -d u ra tio n im pulse re sp o n se ( II R ). L in e a r tim e- in v a ria n t sy stem s c h a ra c te riz e d by d ifferen ce e q u a tio n s are p r e s e n te d an d th e so lu tio n o f d ifferen ce e q u a tio n s w ith initial c o n d itio n s is o b ta in e d. T h e c h a p te r co n clu d es w ith a tre a tm e n t o f d isc re te -tim e c o rre la tio n. T h e z -tra n sfo rm is in tro d u c e d in C h a p te r 3. B o th th e b ila te ra l an d th e u n ila te ra l z -tra n sfo rm s are p re se n te d , a n d m e th o d s fo r d e te rm in in g th e in v erse z -tra n sfo rm are d esc rib e d. U se o f the z -tra n s fo rm in the analysis o f lin ear tim e- in v a ria n t sy stem s is illu stra te d , an d im p o rta n t p ro p e rtie s o f system s, su c h as c a u s a l ity a n d stab ility , a re re la te d to z-d o m ain ch aracteristics. C h a p te r 4 tr e a ts th e analysis o f signals and sy stem s in th e fre q u e n c y d o m ain. F o u rie r se ries an d th e F o u rie r tra n sfo rm a re p re s e n te d fo r b o th co n tin u o u s-tim e an d d isc rete-tim e signals. L in e a r tim e -in v a ria n t (L T I) d isc rete sy stem s are c h a r a c terized in th e fre q u e n c y d o m a in by th e ir freq u e n c y resp o n se fu n c tio n an d th e ir re sp o n se to p e rio d ic an d a p e rio d ic signals is d e te rm in e d. A n u m b e r of im p o rta n t ty p es o f d isc re te -tim e system s are d esc rib e d , in clu d in g re s o n a to rs , n o tc h filters, co m b filters, all-p ass filters, a n d o scillato rs. T h e desig n of a n u m b e r of sim ple F IR a n d IIR filters is also co n sid ered. In a d d itio n , th e stu d e n t is in tro d u c e d to th e co n c e p ts o f m in im u m -p h a se , m ix ed -p h ase, an d m a x im u m -p h a se system s an d to th e p ro b le m o f d e c o n v o lu tio n. T h e D F T. its p ro p e rtie s an d its a p p licatio n s, a re th e topics c o v e re d in C h a p te r 5. T w o m e th o d s a re d e sc rib e d fo r using th e D F T to p e rfo rm lin e a r filtering. T h e use o f th e D F T to p e rfo rm fre q u e n c y analysis o f signals is also d escrib ed. C h a p te r 6 co v ers th e efficient c o m p u ta tio n o f th e D F T. In c lu d e d in this c h a p te r are d e sc rip tio n s o f radix-2, ra d ix -4, a n d sp lit-ra d ix fast F o u rie r tra n sfo rm (F F T ) alg o rith m s, a n d a p p lic a tio n s o f th e F F T a lg o rith m s to th e c o m p u ta tio n o f c o n v o lu tio n a n d c o rre la tio n. T h e G o e rtz e l alg o rith m a n d the ch irp -z tra n sfo rm are in tro d u c e d as tw o m e th o d s fo r c o m p u tin g th e D F T using lin e a r filtering. C h a p te r 7 tre a ts th e re a liz a tio n o f I I R an d F IR system s. T h is tre a tm e n t in clu d es d irect-fo rm , cascad e, p a ra lle l, lattice, a n d la ttic e -la d d e r re a liz a tio n s. T h e c h a p te r in clu d es a tr e a tm e n t o f sta te -sp a c e analysis an d s tru c tu re s fo r d isc rete-tim e system s, an d ex am in es q u a n tiz a tio n effects in a d igital im p le m e n ta tio n o f F IR and I IR system s. T e c h n iq u e s fo r d esign o f digital F IR a n d IIR filters are p r e s e n te d in C h a p te r 8. T h e d esign te c h n iq u e s in clu d e b o th d irect design m e th o d s in d isc re te tim e an d m e th o d s involv in g th e co n v ersio n o f an a lo g filters in to digital filters by v ario u s tra n sfo rm a tio n s. A lso tre a te d in this c h a p te r is th e d esig n o f F I R a n d IIR filters by le a st-sq u a re s m e th o d s. C h a p te r 9 fo cu ses o n th e sam pling o f c o n tin u o u s-tim e sig n a ls a n d th e r e c o n s tru c tio n o f such signals fro m th e ir sam ples. In th is c h a p te r, w e d eriv e th e sam p lin g th e o re m fo r b a n d p a ss co n tin u o u s-tim e -sig n a ls an d th e n co v e r th e A /D an d D /A co n v ersio n te c h n iq u e s, including o v e rsam p lin g A /D a n d D /A co n v erters. C h a p te r 10 p ro v id e s an in d e p th tre a tm e n t o f sa m p lin g -ra te c o n v ersio n and its a p p lic a tio n s to m u ltira le d ig ital signal p ro cessin g. In a d d itio n to d escrib in g d e c im atio n a n d in te rp o la tio n by in te g e r facto rs, we p re s e n t a m e th o d o f sa m p lin g -rate Preface xv co n v e rsio n by an a rb itra ry facto r. S ev eral a p p licatio n s to m u ltira te signal p ro c e ss ing a re p re s e n te d , in clu d in g th e im p le m e n ta tio n o f d igital filters, su b b a n d cod in g o f sp e ech sig n als, tra n sm u ltip le x in g , an d o v ersam p lin g A /D a n d D /A c o n v e rte rs. L in e a r p re d ic tio n an d o p tim u m lin e a r (W ien er) filters a re tr e a te d in C h a p te r 11. A lso in clu d ed in this c h a p te r are d escrip tio n s o f th e L e v in s o n -D u rb in alg o rith m a n d Schiir a lg o rith m fo r solving th e n o rm a l e q u a tio n s , as w ell as th e A R la ttic e a n d A R M A la ttic e -la d d e r filters. P o w e r sp e c tru m e stim a tio n is th e m ain to p ic of C h a p te r 12. O u r co v erag e in clu d es a d e s c rip tio n o f n o n p a ra m e tric an d m o d el-b ased (p a ra m e tric ) m e th o d s. A lso d e s c rib e d a re e ig e n -d e c o m p o sitio n -b a se d m e th o d s, in clu d in g M U S IC an d E S P R IT. A t N o r th e a s te r n U n iv ersity , w e h av e u se d th e first six c h a p te rs o f this b o o k fo r a o n e -se m e s te r (ju n io r level) c o u rse in d isc rete sy stem s a n d d ig ital signal p r o cessing. A o n e -s e m e s te r se n io r level c o u rse fo r stu d e n ts w h o h av e h a d p rio r e x p o su re to d isc rete sy stem s can u se th e m a te ria l in C h a p te rs 1 th ro u g h 4 for a q u ick rev iew a n d th e n p ro c e e d to co v er C h a p te r 5 th ro u g h 8. In a first-v ear g ra d u a te level c o u rse in digital signal p ro cessin g , th e first five c h a p te rs p ro v id e th e s tu d e n t w ith a goo d rev iew of d isc re te -tim e system s. T h e in stru c to r can m o v e q u ick ly th ro u g h m o st o f th is m aterial a n d th e n co v e r C h a p te rs 6 th ro u g h 9, fo llo w ed by e ith e r C h a p te rs 10 and 11 o r by C h a p te rs 11 an d 12. W e h a v e in c lu d e d m an y ex am p les th ro u g h o u t th e b o o k an d a p p ro x im a te ly 500 h o m e w o rk p ro b le m s. M an y o f th e h o m ew o rk p ro b le m s can b e so lv ed n u m e r ically on a c o m p u te r, using a so ftw are p ack ag e such as M A T L A B ©. T h e se p r o b lem s a re id e n tifie d by an asterisk. A p p e n d ix D co n tain s a list o f M A T L A B fu n c tio n s th a t th e s tu d e n t can use in solving th e se p ro b lem s. T h e in s tru c to r m ay also w ish to c o n s id e r th e u se o f a s u p p le m e n ta ry b o o k th a t c o n ta in s c o m p u te r b ased exercises, su c h as th e b o o k s Digilal Signal Processing Us ing M A T L A B (P.W.S. K e n t, 1996) by V. K. In g le a n d J. G. P ro a k is a n d C o m p u te r- B a s e d Exercises f o r S ignal P ro cessing Using M A T L A B (P re n tic e H all, 1994) by C. S. B u rru s e t al. T h e a u th o rs a re in d e b te d to th e ir m an y facu lty c o lleag u es w ho h av e p ro v id e d v alu ab le su g g e stio n s th ro u g h review s o f the first an d se co n d ed itio n s o f this b o o k. T h e se in clu d e D rs. W. E. A le x a n d e r, Y. B re sle r, J. D e lle r, V. Ingle, C. K eller, H. L e v -A ri, L. M e ra k o s , W. M ik h a e l, P. M o n ticcio lo , C. N ikias, M. S ch etzen , H. T ru ssell, S. W ilso n , a n d M. Z o lto w sk i. W e a re also in d e b te d to D r. R , P ric e fo r re c o m m e n d in g th e in clu sion o f sp lit-ra d ix F F T alg o rith m s a n d re la te d su g g estio n s. F in ally , w e w ish to ac k n o w le d g e th e su g g e stio n s an d c o m m e n ts o f m an y fo rm e r g ra d u a te s tu d e n ts , a n d especially th o se by A. L. K ok, J. L in an d S. S rin id h i w ho assisted in th e p r e p a r a tio n o f several illu stra tio n s an d th e so lu tio n s m an u al. J o h n G. P ro a k is D im itris G , M a n o lak is Introduction D ig ital signal p ro cessin g is an are a o f science a n d e n g in e e rin g th a t h a s d ev e lo p e d rap id ly o v e r th e p ast 30 y ears. T his rap id d e v e lo p m e n t is a resu lt o f th e signif ican t ad v an ce s in digital c o m p u te r tech n o lo g y an d in te g ra te d -c irc u it fab rica tio n. T h e digital c o m p u te rs an d asso ciated digital h ard w are of th re e d e c a d e s ago w ere relativ ely larg e an d ex p en siv e and, as a co n seq u en ce, th e ir use w as lim ited to g e n e ra l-p u rp o s e n o n -re a l-tim e (o ff-line) scientific c o m p u ta tio n s an d business a p p licatio n s. T h e ra p id d ev e lo p m e n ts in in te g ra te d -c irc u it te c h n o lo g y , sta rtin g with m ed iu m -scale in te g ra tio n (M S I) an d p ro g ressin g to large-scale in te g ra tio n (L S I), a n d now , v ery -larg e-scale in te g ra tio n (V L S I) of e le c tro n ic circuits has sp u rre d th e d e v e lo p m e n t o f p o w erfu l, sm a ller, faster, an d c h e a p e r digital c o m p u te rs an d sp e cial-p u rp o se d igital h a rd w a re. T h e se in ex p en siv e an d re lativ ely fast digital c ir cuits h av e m a d e it p o ssib le to co n stru c t highly so p h istic a te d digital system s cap ab le o f p e rfo rm in g co m p lex digital signal p ro cessin g fu n ctio n s a n d tasks, w hich are u su ally to o difficult a n d /o r to o expensive to be p e rfo rm e d by an a lo g circuitry or a n alo g signal p ro cessin g system s. H e n c e m an y of th e signal p ro cessin g task s th a t w ere c o n v en tio n ally p e rfo rm e d by an alo g m e a n s a re realized to d a y by less ex p en siv e an d o fte n m o re re lia b le digital h a rd w a re. W e do n o t w ish to im ply th a t digital signal p ro cessin g is th e p ro p e r so lu tio n fo r all signal p ro cessin g p ro b lem s. In d e e d , fo r m a n y signals w ith e x tre m e ly w ide b a n d w id th s, real-tim e p ro cessin g is a re q u ire m e n t. F o r such signals, a n a log o r, p e rh a p s, o p tical signal p ro cessin g is th e only p o ssib le so lu tio n. H o w ev er, w h ere dig ital circuits are av ailab le an d h av e sufficient sp e e d to p e rfo rm th e signal p ro cessin g , th ey a re usually p re fe ra b le. N o t only d o d igital circuits yield c h e a p e r an d m o re re lia b le system s fo r signal p ro cessin g , th e y h av e o th e r a d v an tag es as w ell. In p a rtic u la r, digital pro cessin g h a rd w a re allow s p ro g ra m m a b le o p e ra tio n s. T h ro u g h so ftw are, on e can m o re easily m o d ify th e sig n al p ro cessin g fu n ctio n s to b e p e rfo rm e d by th e h a rd w a re. T h u s dig ital h a rd w a re a n d a s so ciated so ftw are p ro v id e a g re a te r d eg re e o f flexibility in sy stem d esign. A lso , th e re is o ften a h ig h e r o rd e r of p re c isio n ach iev ab le w ith d ig ital h a rd w a re an d so ftw are c o m p a re d w ith an alo g circu its a n d an alo g signal p ro cessin g system s. F o r all th e se re a so n s, th e re h as b e e n an explosive grow th in d ig ital signal p ro cessin g th e o ry a n d a p p licatio n s o v e r th e p ast th re e decades. 2 Introduction Chap. 1 In this b o o k o u r o b jectiv e is to p re se n t an in tro d u c tio n o f th e basic analysis to ols an d te c h n iq u e s fo r d igital p ro cessin g o f signals. W e b eg in by in tro d u c in g so m e o f th e n ecessa ry term in o lo g y an d by d escrib in g th e im p o rta n t o p e ra tio n s asso ciated w ith th e p ro cess of c o n v ertin g an an alo g signal to d ig ital fo rm su itab le fo r d igital p ro cessin g. A s we shall se e, digital p ro cessin g o f a n a lo g signals has som e d raw b ack s. F irst, an d fo re m o st, c o n v ersio n o f an a n a lo g signal to digital fo rm , acco m p lish ed by sa m p lin g th e signal an d q u a n tiz in g th e sa m p le s, resu lts in a d isto rtio n th a t p re v e n ts us fro m re c o n stru c tin g th e o rig in a l a n a lo g signal fro m the q u a n tiz e d sam p les. C o n tro l o f th e a m o u n t o f th is d isto rtio n is ach ie v e d by p ro p e r choice o f th e sam p lin g ra te a n d th e p recisio n in th e q u a n tiz a tio n p ro cess. S eco n d , th e re a re finite p re c isio n effects th a t m u st be c o n s id e re d in th e d igital pro cessin g o f th e q u a n tiz e d sam p les. W hile th e se im p o rta n t issues are c o n s id e re d in som e d etail in this b o o k , th e em p h asis is on th e analysis a n d d esig n o f digital signal p ro cessin g sy stem s a n d c o m p u ta tio n a l te ch n iq u es. 1.1 SIGNALS, SYSTEMS, AND SIGNAL PROCESSING A signal is d efin ed as any physical q u a n tity th a t varies w ith tim e, sp ace, o r any o th e r in d e p e n d e n t v ariab le o r variables. M a th em atic ally , we d e sc rib e a signal as a fu n ctio n o f o n e o r m o re in d e p e n d e n t variab les. F o r e x am p le, th e fu n ctio n s * i( r ) = 5/ (1.1.1) S2(t) = 20 r d escrib e tw o signals, o n e th a t varies lin early w ith the in d e p e n d e n t v ariab le t (tim e) an d a seco n d th a t v aries q u a d ra tic a lly w ith t. A s a n o th e r ex a m p le , co n sid e r the fu n ctio n v) = 3x + 2 x y + 1 0 y 2 (1.1.2) T his fu n ctio n d escrib es a signal o f tw o in d e p e n d e n t v a riab les x a n d y th a t could r e p re s e n t th e tw o sp a tia l c o o rd in a te s in a p lan e. T h e signals d e sc rib e d by (1.1.1) an d (1.1.2) b e lo n g to a class o f signals th a t are p recisely d efin ed by specifying th e fu n c tio n a l d e p e n d e n c e on th e in d e p e n d e n t v ariab le. H o w ev er, th e re are cases w h ere such a fu n c tio n a l re la tio n sh ip is u n k n o w n o r to o highly c o m p licated to be o f any p ractical use. F o r ex am p le, a sp e ech signal (see Fig. 1.1) c a n n o t be d e s c rib e d fu n ctio n ally by ex p ressio n s such as (1.1.1). In g e n eral, a se g m e n t o f sp e ech m ay be re p re se n te d to a high d eg re e o f accu racy as a sum of se v era l sin u so id s o f d iffe re n t am p litu d e s a n d freq u e n cies, th a t is, as N A j ( t ) s i n [ 2 ; r f } ( r ) f + #,(/)] (1.1.3) i=i w h ere {/!,(/)}, {F ,(r)j, a n d {t9,(r)} a re th e se ts of (p o ssib ly tim e -v a ry in g ) a m p litu d es, freq u e n cies, an d p h a se s, resp ectiv ely , o f th e sinusoids. In fact, o n e w ay to in te rp re t th e in fo rm a tio n c o n te n t o r m essag e co n v ey ed by an y sh o rt tim e se g m e n t o f th e Sec. 1.1 Signals, Systems, and Signal Processing 3 — # I Th... ‘ ^ ft S A N D ^ # i j ^ ---------- ,|* y y y > v y y m w ' 'r r m w m 1 ' W W W ’...................... Figure 1.1 Example of a speech signal. sp e e c h signal is to m e a s u re the a m p litu d es, freq u e n cies, a n d p h a se s c o n ta in e d in th e sh o rt tim e se g m e n t o f the signal. A n o th e r ex am p le o f a n a tu ra l signal is an e le c tro c a rd io g ra m (E C G ). Such a signal p ro v id e s a d o c to r w ith in fo rm a tio n a b o u t th e co n d itio n o f the p a tie n t's h e a rt. S im ilarly, an e le c tro e n c e p h a lo g ra m (E E G ) signal p ro v id es in fo rm a tio n a b o u t th e activ ity o f th e b rain. S p eech , e le c tro c a rd io g ra m , a n d e le c tro e n c e p h a lo g ra m signals a re ex am p les o f in fo rm a tio n -b e a rin g signals th a t evolve as fu n ctio n s o f a single in d e p e n d e n t v ariab le, n am elv , tim e. A n ex am p le o f a signal th at is a fu n ctio n o f tw o in d e p e n d e n t v ariab les is an im age signal. T h e in d e p e n d e n t v ariab les in th is case are th e sp atial c o o rd in a te s. T h e se a re b u t a few ex am p les o f th e co u n tless n u m b e r of n a tu ra l signals e n c o u n te re d in practice. A s so c ia te d w ith n a tu ra l signals are the m ean s by w hich such signals are g e n e ra te d. F o r ex am p le, sp e ech signals are g e n e ra te d by fo rcin g air th ro u g h th e vocal co rd s. Im ag es a re o b ta in e d by ex p o sin g a p h o to g ra p h ic film to a scene o r an o b ject. T h u s signal g e n e ra tio n is usually asso ciated w ith a sy stem th a t re sp o n d s to a stim u lu s o r fo rce. In a sp e ech signal, th e system consists o f th e vocal cords a n d th e vocal tra c t, also called th e vocal cavity. T h e stim ulus in c o m b in a tio n w ith th e sy stem is called a signal source. T h u s w e have sp eech so u rces, im ag es so u rces, an d v ario u s o th e r ty p es o f signal sources. A sy stem m ay also be defin ed as a physical device th a t p e rfo rm s an o p e r a tio n on a signal. F o r e x am p le, a filter u sed to red u c e th e n o ise an d in te rfe re n c e co rru p tin g a d e s ire d in fo rm a tio n -b e a rin g signal is called a system. In this case th e filter p e rfo rm s so m e o p e ra tio n (s ) on th e signal, w hich h as th e effect o f red u cin g (filterin g ) th e n o ise a n d in te rfe re n c e from th e d e sire d in fo rm a tio n -b e a rin g signal. W h en w e pass a signal th ro u g h a system , as in filterin g , w e say th a t we h av e p ro c e sse d th e signal. In this case th e p ro cessin g of th e signal involves filtering th e n o ise an d in te rfe re n c e fro m th e d e s ire d signal. In g e n e ra l, th e system is c h a ra c te riz e d by th e ty p e o f o p e ra tio n th a t it p e rfo rm s on th e signal. F o r ex am p le, if th e o p e ra tio n is lin ear, th e system is called linear. If th e o p e ra tio n o n th e signal is n o n lin e a r, th e system is said to be n o n lin e a r, a n d so fo rth. S uch o p e ra tio n s a re u su a lly re fe rre d to as signal processing. 4 Introduction Chap. 1 F o r o u r p u rp o se s, it is c o n v en ien t to b r o a d e n th e d efin itio n o f a system to include n o t o n ly physical devices, b u t also so ftw are re a liz a tio n s o f o p e ra tio n s on a signal. In d igital p ro cessin g o f signals on a digital c o m p u te r, th e o p e ra tio n s p e r fo rm e d on a signal co n sist of a n u m b e r of m a th e m a tic a l o p e ra tio n s as specified by a so ftw are p ro g ram. In this case, th e p ro g ra m r e p re s e n ts an im p le m e n ta tio n o f the system in software. T h u s we h ave a system th a t is re a liz e d on a d igital c o m p u te r by m ean s o f a se q u en ce o f m a th e m a tic a l o p e ra tio n s; th a t is, w e h av e a digital signal p ro cessin g system realized in so ftw are. F o r e x am p le, a d ig ital c o m p u te r can be p ro g ra m m e d to p e rfo rm digital filtering. A lte rn a tiv e ly , th e d igital processing o n th e signal m ay be p e rfo rm e d by digital h ard w a re (logic circu its) co nfigured to p e rfo rm th e d e sire d specified o p e ra tio n s. In such a re a liz a tio n , w e h av e a physical d ev ice th a t p e rfo rm s th e specified o p e ra tio n s. In a b r o a d e r se n se, a digital system can be im p le m e n te d as a c o m b in a tio n o f digital h a rd w a re an d so ftw are, each of w hich p e rfo rm s its ow n set of specified o p e ra tio n s. T h is b o o k d eals w ith th e p ro cessin g o f signals by digital m e a n s, e ith e r in so ft w are o r in h a rd w a re. Since m an y of the signals e n c o u n te re d in p ra c tic e are analog, w e will also co n sid er th e p ro b lem of c o n v ertin g an a n a lo g signal in to a digital sig n al fo r pro cessin g. T h u s we will be d ealin g p rim a rily w ith d ig ital system s. T he o p e ra tio n s p e rfo rm e d by such a system can u su ally be specified m ath em atically. T h e m e th o d o r set o f ru les for im p le m e n tin g th e sy stem by a p ro g ra m th a t p e r fo rm s th e c o rre sp o n d in g m a th e m a tic a l o p e ra tio n s is called an algorithm. U sually, th e re are m an y w ays o r alg o rith m s by w hich a system can be im p le m e n te d , e ith e r in so ftw are o r in h a rd w a re , to p e rfo rm th e d e sire d o p e ra tio n s a n d c o m p u tatio n s. In p ra c tic e , we h av e an in te re st in devising a lg o rith m s th a t are c o m p u ta tio n a lly efficient, fast, an d easily im p lem en ted. T h u s a m a jo r to p ic in o u r stu d y o f digi tal signal p ro cessin g is th e discussion o f efficient a lg o rith m s fo r p e rfo rm in g such o p e ra tio n s as filterin g , c o rre la tio n , an d sp e c tra l analysis. 1.1.1 Basic Elements of a Digital Signal Processing System M o st o f th e signals e n c o u n te re d in science an d e n g in e e rin g a re a n a lo g in n a tu re. T h a t is. th e signals a re fu n ctio n s of a c o n tin u o u s v a ria b le , such as tim e o r space, an d u su ally ta k e o n v alues in a co n tin u o u s ran g e. S uch signals m ay be p ro cessed directly by a p p ro p ria te an alo g system s (such as filters o r fre q u e n c y an aly zers) or fre q u e n c y m u ltip lie rs for th e p u rp o se of ch an g in g th e ir c h a ra c te ristic s o r ex tractin g so m e d esired in fo rm a tio n. In such a case w e say th a t th e signal h as b e e n p ro cessed d irectly in its an alo g fo rm , as illu strated in Fig. 1.2. B o th th e in p u t signal a n d the o u tp u t signal a re in an a lo g form. Analog Analog Analog input signal output signal processor signal Figure 1.2 A nalog signal processing. Sec. 1.1 Signals, Systems, and Signal Processing 5 Analog Analog input output signal signal Digital Digital input output signal signal Figure 1.3 Block diagram of a digital signal processing system. D ig ital signal p ro cessin g p ro v id e s an a lte rn a tiv e m e th o d fo r p ro cessin g th e a n a lo g signal, as illu stra te d in Fig. 1.3. T o p e rfo rm th e p ro cessin g digitally, th e re is a n e e d fo r an in te rfa c e b e tw e e n th e an a lo g signal a n d th e digital p ro cesso r. T h is in te rfa c e is called an analog-to-digital ( A / D ) converter. T h e o u tp u t of th e A /D c o n v e rte r is a d ig ital signal th a t is a p p ro p ria te as an in p u t to th e d igital p ro cesso r. T h e dig ital signal p ro c e ss o r m ay be a larg e p ro g ra m m a b le digital c o m p u te r o r a sm all m ic ro p ro c e s so r p ro g ra m m e d to p e rfo rm th e d e s ire d o p e ra tio n s on th e in p u t signal. It m ay also be a h a rd w ire d digital p ro c e ss o r co n fig u red to p e rfo rm a specified se t o f o p e ra tio n s on th e in p u t signal. P ro g ra m m a b le m ach in es p r o v id e th e flexibility to ch an g e th e signal p ro cessin g o p e ra tio n s th ro u g h a ch an g e in th e so ftw are, w h e re a s h a rd w ire d m ach in es a re difficult to reco n fig u re. C o n s e q u e n tly , p ro g ra m m a b le signal p ro c e ss o rs a re in very c o m m o n use. O n th e o th e r h an d , w h en signal p ro cessin g o p e ra tio n s are w ell d efin ed , a h a rd w ire d im p le m e n ta tio n o f th e o p e ra tio n s can be o p tim ized , re su ltin g in a c h e a p e r signal p ro c e sso r a n d , u su ally , o n e th a t ru n s fa ste r th a n its p ro g ra m m a b le c o u n te rp a rt. In a p p li c atio n s w h e re th e d ig ital o u tp u t fro m th e d igital signal p ro c e sso r is to be given to th e u se r in an alo g form , such as in sp e ech co m m u n icatio n s, w e m ust p r o vid e a n o th e r in te rfa c e fro m th e digital d o m a in to th e a n a lo g d o m ain. S uch an in te rfa c e is called a digital-to-analog ( D / A ) converter. T h u s th e signal is p r o v id ed to th e u se r in an a lo g form , as illu stra te d in th e b lo ck d iag ram o f Fig. 1.3. H o w e v e r, th e re a re o th e r p ractical a p p lic a tio n s involving signal analysis, w h ere th e d e s ire d in fo rm a tio n is co n v ey ed in digital form a n d n o D /A c o n v e rte r is re q u ire d. F o r ex am p le, in th e d igital p ro cessin g o f r a d a r signals, th e in fo rm a tio n e x tra c te d fro m th e ra d a r signal, such as th e p o sitio n o f th e aircra ft a n d its sp e ed , m ay sim ply b e p rin te d on p a p e r. T h e re is n o n e e d fo r a D /A c o n v e rte r in th is case. 1.1.2 Advantages of Digital over Analog Signal Processing T h e re a re m an y re a so n s w hy d ig ital signal p ro cessin g o f an an alo g signal m ay be p re fe ra b le to p ro cessin g th e signal directly in th e an a lo g d o m ain , as m e n tio n e d briefly e a rlie r. F irst, a digital p ro g ra m m a b le sy stem allow s flexibility in r e c o n figuring th e digital signal p ro cessin g o p e ra tio n s sim ply by ch anging th e p ro g ra m. 6 Introduction Chap. 1 R e c o n fig u ra tio n o f an an a lo g system usually im plies a re d e sig n o f th e h a rd w a re follow ed by te stin g a n d v erification to see th a t it o p e ra te s p ro p e rly. A ccu racy c o n s id e ra tio n s also p lay an im p o rta n t role in d e te rm in in g th e fo rm o f th e signal p ro cesso r. T o le ra n c e s in an alo g c ircu it c o m p o n e n ts m a k e it e x tre m e ly difficult fo r th e system d esig n er to co n tro l th e accu racy o f an an a lo g signal p r o cessing system. O n th e o th e r h an d , a digital system p ro v id e s m uch b e tte r c o n tro l o f accu racy re q u ire m e n ts. Such re q u ire m e n ts , in tu rn , re s u lt in specifying th e a c cu racy r e q u ire m e n ts in th e A /D c o n v e rte r a n d th e d igital sig n a l p ro c e sso r, in te rm s o f w ord le n g th , flo atin g -p o in t v ersu s fix ed -p o in t arith m e tic , a n d sim ilar facto rs. D ig ita l signals are easily sto re d o n m a g n e tic m ed ia (ta p e o r disk) w ith o u t d e te rio ra tio n o r loss o f signal fidelity b e y o n d th a t in tro d u c e d in th e A /D co n v ersio n. A s a c o n se q u e n c e , th e signals b e c o m e tra n s p o rta b le an d can b e p ro cessed off-line in a re m o te la b o ra to ry. T h e digital signal p ro cessin g m e th o d also allow s for th e im p le m e n ta tio n o f m o re so p h istic a te d signal p ro cessin g alg o rith m s. It is usually very difficult to p e rfo rm p recise m a th e m a tic a l o p e ra tio n s on signals in a n a lo g fo rm b u t th ese sam e o p e ra tio n s can b e ro u tin e ly im p le m e n te d on a d ig ital c o m p u te r using so ftw are. In so m e cases a d igital im p le m e n ta tio n of th e signal p ro cessin g system is c h e a p e r th a n its an a lo g c o u n te rp a rt. T h e lo w er cost m ay be d u e to th e fact th a t th e dig ital h a rd w a re is c h e a p e r, o r p e rh a p s it is a re su lt o f th e flexibility fo r m o d ifications p ro v id e d by th e digital im p le m e n ta tio n. A s a c o n se q u e n c e o f th ese ad v a n ta g e s, d igital signal p ro c e ssin g has b e e n a p p lied in p ractical sy stem s co v erin g a b ro a d ra n g e of d iscip lin es. W e cite, fo r ex am p le, th e a p p licatio n o f d igital signal p ro cessin g te c h n iq u e s in sp e ech p ro cessin g an d signal tran sm issio n o n te le p h o n e ch an n els, in im age p ro c e ssin g an d tra n sm is sio n , in seism o lo g y an d geophysics, in oil e x p lo ra tio n , in th e d e te c tio n of n u c le a r ex p lo sio n s, in th e p ro cessin g of signals receiv ed fro m o u te r sp a ce, an d in a vast v ariety o f o th e r a p p licatio n s. S om e o f th e se a p p lic a tio n s a re cited in su b s e q u e n t ch ap ters. A s a lre a d y in d icated , h o w ev er, digital im p le m e n ta tio n has its lim itatio n s. O n e p ractical lim ita tio n is th e sp e ed o f o p e ra tio n o f A /D c o n v e rte rs a n d digital signal p ro cesso rs. W e shall see th a t signals hav in g e x tre m e ly w id e b a n d w id th s re q u ire fa st-sam p lin g -rate A /D c o n v e rte rs an d fast d igital signal p ro cesso rs. H e n c e th e re a re an alo g signals w ith larg e b a n d w id th s fo r w hich a digital p ro cessin g a p p ro a c h is b ey o n d th e s ta te of th e a rt o f digital h a rd w a re. 1.2 CLASSIFICATION OF SIGNALS T h e m e th o d s we use in p ro cessin g a signal o r in an aly zin g th e re s p o n s e o f a system to a sig n al d e p e n d h eavily on th e ch a ra c te ristic a ttr ib u te s o f th e specific signal. T h e re a re te c h n iq u e s th a t ap p ly only to specific fam ilies o f signals. C o n seq u en tly , an y in v estig atio n in signal p ro cessin g sh o u ld sta rt w ith a classification o f th e signals in v o lv ed in th e specific ap p licatio n. Sec. 1.2 Classification of Signals 7 1.2.1 Multichannel and Multidimensional Signals A s e x p lain ed in S ectio n 1.1, a signal is d escrib ed by a fu n c tio n o f o n e o r m o re in d e p e n d e n t v ariab les. T h e v alue of th e fu n ctio n (i.e., th e d e p e n d e n t v ariab le) can be a re a l-v a lu e d sc alar q u a n tity , a co m p lex -v alu ed q u a n tity , o r p e rh a p s a v ecto r. F o r e x am p le, th e signal si( r ) = A sin37rr is a re a l-v a lu e d signal. H o w e v e r, th e signal s2(f) = A e ji7Tt = A cos 37t t j'A sin 3:r r is co m p lex v alu ed. In so m e a p p lic a tio n s, signals a re g e n e ra te d by m u ltip le so u rces or m u ltip le sen so rs. Such signals, in tu rn , can be re p re s e n te d in v e c to r fo rm. F ig u re 1.4 show s th e th re e c o m p o n e n ts of a v e c to r signal th a t re p re se n ts th e g ro u n d a c c e le ra tio n d u e to an e a r th q u a k e. T h is a c c e le ra tio n is the re su lt of th re e basic ty p es of elastic w aves. T h e p rim a ry (P ) w aves an d th e se co n d a ry (S) w aves p ro p a g a te w'ithin th e b o d y o f rock a n d a re lo n g itu d in al a n d tra n sv e rsa l, resp ec tiv ely. T h e th ird ty p e o f elastic w ave is called th e su rface w ave, b e c a u se it p ro p a g a te s n e a r th e g ro u n d su rface. If $*(/). k = 1. 2. 3. d e n o te s th e electrical signal from th e £ th se n so r as a fu n ctio n o f tim e, th e se t of p = 3 signals can be re p re se n te d by a v e c to r S?(f )< w h ere r si (O ' S;,(r) = Si(t) -Sl(t) J W e re fe r to such a v e c to r o f signals as a m u ltich a n n el signal. In e le c tro c a rd io g ra p hy. for ex am p le, 3 -lead an d 12-lead e le c tro c a rd io g ra m s (E C G ) are o ften used in p ractice, w hich resu lt in 3 -ch an n el a n d 12-channel signals. L e t us n o w tu rn o u r a tte n tio n to th e in d e p e n d e n t v a ria b le (s). If the signal is a fu n ctio n o f a single in d e p e n d e n t v ariab le, th e signal is called a o ne-d im en sio n a l signal. O n th e o th e r h a n d , a signal is called M -d i m e n s i o n a l if its v alu e is a fu n ctio n of M in d e p e n d e n t v ariab les. T h e p ic tu re sh o w n in Fig. 1.5 is an ex am p le of a tw o -d im e n sio n al signal, since th e in ten sity o r b rig h tn e ss I ( x. y) a t each p o in t is a fu n ctio n of tw o in d e p e n d e n t v ariab les. O n th e o th e r h a n d , a b la c k -a n d -w h ite telev isio n p ic tu re m ay be r e p r e se n te d as I ( x. y. t ) since th e b rig h tn e ss is a fu n ctio n of tim e. H e n c e th e T V p ic tu re m ay b e tr e a te d as a th re e -d im e n s io n a l signal. In c o n tra st, a co lo r T V p ic tu re m ay b e d e sc rib e d by th re e in te n sity fu n ctio n s of th e fo rm Ir (x, y. ?), Is (x. y. t ), a n d I i , ( x. y , t ) , c o rre sp o n d in g to th e b rig h tn e ss of the th re e p rin cip al colors (red. g re e n , b lu e) as fu n ctio n s o f tim e. H e n c e th e co lo r T V p ic tu re is a th re e -c h a n n e l, th re e -d im e n s io n a l signal, w hich can b e re p re s e n te d by th e v e c to r -/,(* ,>. O ' I U , y. t) —. l b(x, v ,r ) _ In this b o o k we d e a l m ainly w ith sin g le-ch an n el, o n e -d im e n sio n a l real- or co m p lex -v alu ed signals a n d w e re fe r to th e m sim ply as signals. In m a th e m a tic a l Introduction Chap. 1 Up / % East 7jJL______ South bouth I____ i 1 ]____ I. 1____ 1____ I f S waves t Surface waves _4 P waves r1 -2 I I i i i_______ I , I____ _ J _______I_______ I----------- 1-----------1----------- 1-----------1----------- 1-----------1 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 Time (seconds) (b) Figure 1.4 Three components of ground acceleration measured a few kilometers from the epicenter of an earthquake. (From Earthquakes, by B. A. Bold. © 1988 by W. H. Freeman and Company. Reprinted with permission of the publisher.) te rm s th ese signals are d escrib ed by a fu n ctio n o f a single in d e p e n d e n t v ariable. A lth o u g h th e in d e p e n d e n t variab le n e e d n o t be tim e, it is c o m m o n p ractice to use t as th e in d e p e n d e n t v ariab le. In m an y cases th e signal p ro c e ssin g o p e ra tio n s and a lg o rith m s d e v e lo p e d in this tex t for o n e -d im e n sio n a l, sin g le-ch an n el signals can b e e x te n d e d to m u ltic h a n n e l an d m u ltid im e n sio n a l signals. 1.2.2 Continuous-Time Versus Discrete-Time Signals Signals can b e fu rth e r classified in to fo u r d iffe re n t c a te g o rie s d e p e n d in g on the ch a ra c te ristic s o f th e tim e (in d e p e n d e n t) v a ria b le an d th e v alu es th ey tak e. Con tin u o u s -tim e signals o r a nalog signals a re d e fin ed for ev e ry value o f tim e an d Sec. 1.2 Classification of Signals 9 Figure 1.5 Example of a two-dimensional signal. th ey ta k e on v alu es in the co n tin u o u s in terv al (a. b ). w h e re a can be —oc a n d b can be oc. M a th em atic ally , th ese signals can be d e sc rib e d by fu n ctio n s o f a c o n tin u o u s v ariab le. T h e sp eech w av efo rm in Fig. 1.1 an d th e signals x i(r) = c o s 7i t , x j { t ) = e ^ 1' 1, —oc < t < oq are ex am p les o f an alo g signals. Discrete-time signals a re d efin ed o n ly at c e rta in specific v alu es o f tim e. T h e se tim e in sta n ts n eed n o t be e q u id ista n t, b u t in p ractice th ey are usually ta k e n a t e q u a lly sp a ced in terv als fo r c o m p u ta tio n a l c o n v en ien ce an d m a th e m a tic a l tra c ta b ility. T h e signal x(t„) = n = 0, ± 1 , ± 2 ,... p ro v id es an ex am p le o f a d isc re te -tim e signal. If we use th e in d ex n o f th e d isc rete-tim e in sta n ts as th e in d e p e n d e n t v ariab le, th e signal v alu e b eco m es a fu n ctio n o f an in te g e r v ariab le (i.e., a se q u e n c e of n u m b e rs). T h u s a d isc re te -tim e signal can be re p re s e n te d m a th e m a tic a lly by a se q u e n c e of real o r c o m p lex n u m b ers. T o em p h asize the d isc rete-tim e n a tu r e o f a signal, w e sh all d e n o te such a signal as x{n) in ste a d o f x ( t ). If th e tim e in stan ts t„ are e q u ally sp a ced (i.e., t„ = n T ), th e n o ta tio n x ( n T ) is also used. F o r ex am p le, th e se q u e n c e if n > 0 x(n) ( 1.2. 1 ) o th erw ise is a d isc re te -tim e signal, w hich is r e p re s e n te d g rap h ically as in Fig. 1.6. In ap p licatio n s, d isc rete-tim e signals m ay arise in tw o ways: 1. B y se lectin g v alu es o f an an alo g signal a t d isc re te -tim e in stan ts. T his p ro c e ss is called s am plin g an d is discussed in m o re d etail in S ectio n 1.4. A ll m e a s u r ing in stru m e n ts th a t ta k e m e a s u re m e n ts at a re g u la r in te rv a l o f tim e p ro v id e d isc rete-tim e signals. F o r ex am p le, th e signal x ( n ) in Fig. 1.6 can be o b ta in e d 10 Introduction Chap. 1 x{n) I I T Figure 1.6 Graphical representation of the discrete time signal x[n) = 0.8" for n > 0 and x(n) = 0 for n < 0. bv sa m p lin g th e an a lo g signal x ( t ) — 0.8 ', t > 0 an d x ( t ) = 0. t < 0 once ev ery seco n d. 2. By accu m u latin g a v a ria b le o v e r a p e rio d o f tim e. F o r e x a m p le , c o u n tin g th e n u m b e r o f cars using a given s tre e t every h o u r, o r re c o rd in g th e v alu e of gold ev ery day, resu lts in d isc re te -tim e signals. F ig u re 1.7 show s a g rap h o f the W o lfer su n sp o t n u m b e rs. E a c h sam ple o f this d isc re te -tim e signal p ro v id es th e n u m b e r o f su n s p o ts o b se rv e d d u rin g an in te rv a l o f 1 y e a r. 1.2.3 Continuous-Valued Versus Discrete-Valued Signals T h e v alu es o f a c o n tin u o u s-tim e or d isc re te -tim e signal can be c o n tin u o u s or d is crete. If a signal ta k e s on all po ssib le values on a finite or an infinite ran g e, it Year Figure 1.7 W olfer annual sunspot num bers (1770-1869). Sec. 1.2 Classification of Signals 11 is said to b e c o n tin u o u s-v a lu e d signal. A lte rn a tiv e ly , if th e signal ta k e s on v alu es fro m a finite se t o f p o ssib le values, it is said to be a d isc re te -v a lu e d signal. U su ally , th e s e v alu es a re e q u id ista n t a n d h en ce can be e x p ressed as an in te g e r m u ltip le of th e d istan c e b e tw e e n tw o successive values. A d isc re te -tim e signal hav in g a set of d isc rete v alu es is called a digital signal. F ig u re 1,8 show s a d igital signal th a t ta k e s o n o n e o f fo u r p o ssib le values. In o r d e r fo r a signal to be p ro c e sse d digitally, it m u st be d isc rete in tim e a n d its v alu es m u st b e d isc re te (i.e., it m ust b e a digital sig n al). If th e signal to b e p ro c e sse d is in an a lo g fo rm , it is c o n v e rte d to a digital signal by sam pling th e an alo g signal at d isc rete in stan ts in tim e, o b ta in in g a d isc re te -tim e signal, and th e n by q ua n tizin g its v alu es to a set o f d isc re te v alu es, as d e sc rib e d la te r in th e c h a p te r. T h e p ro cess o f co n v e rtin g a c o n tin u o u s-v a lu e d signal in to a d isc re te -v a lu e d signal, called quan tizatio n, is basically an a p p ro x im a tio n p ro cess. It m ay be acco m p lish ed sim ply bv ro u n d in g o r tru n c a tio n. F o r ex am p le, if th e allo w ab le signal v alu es in th e d ig ital signal are in teg ers, say 0 th ro u g h 15, the c o n tin u o u s-v a lu e signal is q u a n tiz e d in to th ese in te g e r values. T h u s th e signal v alue 8.58 will be a p p ro x im a te d by th e v alu e 8 if th e q u a n tiz a tio n p ro cess is p e rfo rm e d by tru n c a tio n o r by 9 if th e q u a n tiz a tio n p ro c e ss is p e rfo rm e d by ro u n d in g to th e n e a re s t in teg er. A n ex p la n a tio n o f th e a n a lo g -to -d ig ita l co n v ersio n p ro cess is given la te r in th e c h a p te r. Figure 1.8 Digital signal with four different amplitude values. 1.2.4 Deterministic Versus Random Signals T h e m a th e m a tic a l an aly sis an d p ro cessin g o f signals re q u ire s th e availability o f a m a th e m a tic a l d e sc rip tio n fo r th e signal itself. T h is m a th e m a tic a l d e scrip tio n , o fte n re fe rre d to as th e signal m o d e l, lead s to a n o th e r im p o rta n t classification of signals. A n y signal th a t can b e u n iq u ely d esc rib e d by an explicit m a th e m a tic a l ex p ressio n , a tab le o f d a ta , o r a w ell-defined ru le is called deterministic. T his te rm is used to em p h asize th e fact th a t all p ast, p re se n t, an d fu tu re values o f th e signal are kno w n precisely , w ith o u t an y u n c e rta in ty. In m a n y p ractical ap p lic a tio n s, h o w ev er, th e re are sig n a ls th a t e ith e r c a n n o t b e d esc rib e d to an y re a so n a b le d e g re e o f accu racy by explicit m a th e m a tic a l fo r m u las, o r such a d e sc rip tio n is to o c o m p licated to b e of any p ractical use. T h e lack 12 Introduction Chap. 1 o f such a re la tio n sh ip im plies th a t such signals ev o lv e in tim e in an u n p re d ic ta b le m a n n e r. W e re fe r to th ese signals as ra n d o m. T h e o u tp u t o f a n oise g e n e ra to r, th e seism ic signal o f Fig. 1.4, an d th e sp e ech signal in Fig. 1.1 are ex am p les of ra n d o m signals. F ig u re 1.9 show s tw o signals o b ta in e d fro m th e sa m e n o ise g e n e ra to r an d th e ir asso ciated h isto g ram s. A lth o u g h th e tw o signals do n o t re s e m b le each o th e r visually, th e ir h isto g ra m s re v e a l som e sim ilarities. T his p ro v id e s m o tiv a tio n fo r —3>- —4 1 ---------------------------------------------------------- 1 -------*------------------- — ----- ------ --------------------------------------- 0 200 400 600 800 1000 1200 1400 1600 (a) 400 f ----------------- ------------------- — - — -------------------------- ------------------- ------------------- 1 1 350 r i 300 - 250 2 Fmax (1.4.19) 30 Introduction Chap. 1 w h ere Fmax is th e larg est fre q u e n c y c o m p o n e n t in the a n a lo g signal. W ith the sa m p lin g ra te se le c te d in this m a n n e r, any fre q u e n c y c o m p o n e n t, say |F ;| < Fmax, in th e an alo g signal is m a p p e d in to a d isc re te -tim e sinusoid w ith a freq u e n cy 1 F 1 (1.4.20) 2 Fs ~ 2 o r, eq u iv alen tly , — tt < a)j = 2n f < 7r (1.4.21) S ince, | / | = \ o r \co\ = n is th e h ig h est (u n iq u e ) freq u e n c y in a d isc re te -tim e signal, th e choice o f sam p lin g ra te acco rd in g to (1.4.19) avoids th e p ro b le m of aliasing. In o th e r w o rd s, th e co n d itio n Fs > 2 Fmax e n s u re s th a t all th e sin u so id al c o m p o n e n ts in th e a n a lo g signal are m a p p e d in to c o rre sp o n d in g d isc re te -tim e freq u e n cy c o m p o n e n ts w ith fre q u e n c ie s in th e fu n d a m e n ta l in terv al. T h u s all the freq u e n cy c o m p o n e n ts o f th e a n alo g signal a re re p re s e n te d in sa m p le d fo rm w ith o u t am b i guity, a n d h en ce th e an alo g signal can be re c o n stru c te d w ith o u t d isto rtio n from th e sa m p le v alu es u sing an “ a p p r o p ria te ” in te rp o la tio n (d ig ita l-to -a n a lo g c o n v e r sio n ) m e th o d. T h e ‘ ap p ro p riate” o r ideal in te rp o la tio n fo rm u la is specified by the s a m p ling theorem. Sam pling T h eorem. If the h ig h est fre q u e n c y c o n ta in e d in an an alo g signal x a (t) is Fmax = B a n d th e signal is sa m p le d at a ra te F, > 2 F max = 2 B. th e n A.u(r) can b e exactly re c o v e re d fro m its sa m p le values using th e in te rp o la tio n fu n ctio n s i n 2 jr B / _ , 8(t) = 2n B t ( } T h u s jcfl(f) m ay be e x p ressed as *. ( £ ) * ( ' - £ ) (1-4.23) w h ere x a(n / F s ) = x a( n T ) = Jt(rc) a re th e sa m p les o f x a(t). W h en th e sa m p lin g of x a(t) is p e rfo rm e d at the m in im u m sam p lin g ra te Fs = 2 B , th e re c o n stru c tio n fo rm u la in (1.4.23) b eco m es ^ / n \ sin2nB (t — n flB ) , , , = ( zb) (1'4 2 4 ) T h e sa m p lin g r a te F ^ = 2 B = 2 Fmax is called th e N y q u is t rate. F ig u re 1.19 illus tra te s th e ideal D /A c o n v ersio n p ro cess using th e in te rp o la tio n fu n c tio n in (1.4.22). A s can b e o b se rv e d from e ith e r (1.4.23) o r (1.4.24), th e re c o n stru c tio n o f x a(t) fro m th e se q u e n c e x ( n ) is a c o m p lic a te d p ro cess, involving a w e ig h te d sum o f the in te rp o la tio n fu n ctio n g (t) an d its tim e -sh ifte d v ersio n s g ( t —n T ) fo r —oo < n < oo, w h ere th e w eig h tin g facto rs a re th e sa m p le s x ( n ). B e c a u se o f th e co m p lex ity an d th e infinite n u m b e r o f sa m p les re q u ire d in (1.4.23) o r (1.4.24), th e s e re c o n stru c tio n Sec. 1.4 Analog-to-Digital and Digital-to-Analog Conversion 31 sample of ,v„(n Figure 1.19 Ideal D /A conversion (/[ —^ / {ri — l )l fll \’t -r l 11 (interpolation). fo rm u ias are p rim a rily o f th e o re tic a l in te re st. P ra ctical in te rp o la tio n m e th o d s are given in C h a p te r 9. Example 1.4.3 Consider the analog signal xu(r) = 3cos50;rz 10sin300;n —cos 100tt? What is the Nvquist rate for this signal? Solution The frequencies present in the signal above are F = 25 Hz. F: = 150 Hz. F, = 50 Hz Thus Fnm = 150 Hz and according to (1.4.19), F > 2 Fmax = 300 Hz The Nvquist rale is FA = 2 Fm;„. Hence Fs = 300 Hz Discussion It should be observed that the signal component 10sin300;r/. sampled at the Nvquist raie FA- = 300, results in the samples 10 sin 7r/j. which are identically zero. In other words, we are sampling the analog sinusoid at its zero-crossing points, and hence we miss this signal component completely. This situation would not occur if the sinusoid is offset in phase by some am ount 8. In such a case we have lOsinGOOin -ffl) sampled at the Nvquist rate FA- = 300 samples per second, which yields the samples 10 sin(7rn+ ^) = 10(sin n n cos & -+ -c o stth sin f>) = lOsin 6 cos nn Thus if 6 ^ 0 or tt, the samples of the sinusoid taken at the Nvquist rate are not all zero. However, we still cannot obtain the correct amplitude from the samples when the phase 9 is unknown. A simple rem edy that avoids this potentially troublesome situation is to sample the analog signal at a rate higher than the Nvquist rate. Example 1.4.4 Consider the analog signal *a(t) = 3cos2000irf + 5 sin6000;rr + lOcos 12.000;?; Introduction Chap. 1 (a) What is the Nvquist rate for this signal? (b) Assume now that we sample this signal using a sampling rate Fs = 5000 samples/s. What is the discrete-time signal obtained after sampling? (c) What is the analog signal y„(r) we can reconstruct from the samples if we use ideal interpolation? — = 2.5 kHz 2 and this is the maximum frequency that can be represented uniquely by the sampled signal. By making use of (1.4.2) we obtain = 3 cos 2jt( j )h + 5 sin 2n- (^ )« + 10 cos 2n(^)n = 3 c o s2 ;r(|)n + 5 sin 2 7 r(l — §)« 4- 10cos2,t(1 4- ^)u = 3cos2jr({)n 4- 5sin27r(—1)« 4- 1 0 c o s 2 ^ (|)« Finally, we obtain x(n) = 13 cos2^({)/i - 5sin27r( = )fl The same result can be obtained using Fig. 1.17. Indeed, since F, = 5 kHz. the folding frequency is FJ2 = 2.5 kHz. This is the maximum frequency that can be represented uniquely by the sampled signal. From (1.4.17) we have Fti = Fk — kFs. Thus Fo can be obtained by subtracting from Fk an integer m ultiple of Fs such that —F t/2 < F0 < F J 2. The frequency F: is less than Fsf2 and thus it is not affected by aliasing. However, the other two frequencies are above the folding frequency and they will be changed by the aliasing effect. Indeed. F'2 = Fj ~ Fs = - 2 kHz f; = Fj — Fs = 1 kHz From (1.4.5) it follows that /] = h — and h = ^ which are in agreem ent with the result above. Sec. 1.4 A nalog-toD igital and Digital-to-Analog Conversion 33 (c) Since only the frequency components at 1 kHz and 2 kHz are present in the sampled signal, the analog signal we can recover is x„(t) = 13 cos 2000^r - 5sin400()-Tf which is obviously different from the original signal x„U). This distortion of the original analog signal was caused by the aliasing effect, due to the low sampling rate used. A lth o u g h aliasin g is a pitfall to be av o id ed , th e re are tw o useful p ractical a p p licatio n s b ased on th e ex p lo itatio n of the aliasing effect. T h e se a p p licatio n s are th e stro b o sc o p e an d the sam pling oscilloscope. B o th in stru m e n ts are d esigned to o p e ra te as aliasin g devices in o rd e r to re p re se n t high fre q u e n c ie s as low f re q u en cies. T o e la b o ra te , co n sid er a signal w ith h ig h -freq u en cy c o m p o n e n ts confined to a given fre q u e n c y b an d B\ < F < B2. w h ere Bz — B\ = B is d efined as the b a n d w id th o f th e signal. W e assum e th a t B < < B\ < B 2. T h is co n d itio n m ean s th a t th e fre q u e n c y c o m p o n e n ts in the signal are m uch larg er th an th e b an d w id th B of th e signal. Such signals are usually called p a ssb a n d or n a rro w b a n d signals. N ow. if this signal is sa m p le d at a rate Fs > 2B. b u t F^ 2 B. w h ere B is th e b an d w id th. T h is s ta te m e n t c o n stitu te s a n o th e r fo rm o f th e sam pling th e o re m , w hich we call the p a s s b a n d f o r m in o rd e r to d istin g u ish it fro m th e p rev io u s form o f the sa m p lin g th e o re m , w hich ap p lies in g en eral to all ty p es of signals. T he la tte r is so m e tim es called th e bas e ban d f or m. T h e p a s s b a n d f o r m o f th e sam pling th e o re m is d escrib ed in d e ta il in S ectio n 9.1.2. 1.4.3 Quantization of Continuous-Amplitude Signals A s w e h av e se en , a dig ital signal is a se q u en ce of n u m b e rs (sa m p le s) in w hich each n u m b e r is re p re s e n te d by a finite n u m b e r of digits (finite p recisio n ). T h e p ro c e ss o f co n v ertin g a d isc rete-tim e c o n tin u o u s-a m p litu d e signal in to a dig ital signal by ex p ressin g each sa m p le value as a finite (in ste a d of an infinite) n u m b e r o f d igits, is called quant izati on. T he e rro r in tro d u c e d in re p re se n tin g th e c o n tin u o u s-v a lu e d signal by a finite set o f d isc rete v alu e levels is called quant i zat i on error o r quant i zat i on noise. W e d e n o te th e q u a n tiz e r o p e ra tio n o n th e sa m p le s x ( n ) as Q[x{n)] an d let x q{n) d e n o te th e se q u en ce o f q u a n tiz e d sam ples a t th e o u tp u t o f th e q u a n tiz e r. H e n ce Xq(n) = Q[x(n)] 34 Introduction Chap. 1 T h e n th e q u a n tiz a tio n e r ro r is a se q u e n c e eq (n) d efin ed as th e d iffe re n c e b etw e e n th e q u a n tiz e d v alu e a n d th e actu al sa m p le value. T h u s eq (n) = x q {n) - x ( n ) (1.4.25) W e illu strate th e q u a n tiz a tio n p ro cess w ith a n ex am p le. L e t us co n sid e r the d isc rete-tim e signal o b ta in e d by sa m p lin g th e an a lo g e x p o n e n tia l signal x a( t) = 0.9 ', t > 0 w ith a sam p lin g freq u e n cy f , = 1 H z (see Fig. 1.20(a)). O b se rv a tio n o f T a b le 1.2, w hich show s th e v alu es o f th e first 10 sa m p les o f x ( n ) , rev eals th a t th e d e sc rip tio n o f the sam p le v alu e x{n) re q u ire s n significant digits. It is o b v io u s th a t th is signal can n o t (a) Figure 1.20 Illustration of quantization. Sec. 1.4 Analog-to-Digital and Digital-to-Analog Conversion 35 TA B LE 1.2 NU M ER IC A L ILLU S TR A TIO N O F Q U A N TIZA TIO N W ITH ONE S IG N IF IC A N T D IG IT USING T R U N C A T IO N O R R O UN DING x ( n) x,(n ).voi) n D iscrete-tim e signal (Truncation) (Rounding) (Rounding) 0 1 1.0 1.0 0.0 1 0.9 0.9 0.9 0.0 2 0.81 0.8 0.8 - 0.01 3 0.729 0.7 0.7 - 0.029 4 0.6561 0.6 0.7 0.0439 5 0.59049 0.5 0.6 0.00951 6 0.531441 0.5 0.5 - 0.031441 7 0.4782969 0.4 0.5 0.0217031 8 0.43046721 0.4 0.4 - 0.03046721 9 0.387420489 0.3 0.4 0.012579511 be p ro cessed by u sing a c a lcu lato r o r a digital c o m p u te r since only the first few sam p les can be sto re d an d m a n ip u la te d. F o r ex am p le, m ost c alcu lato rs process n u m b e rs w ith only eig h t significant digits. H o w e v e r, let us assum e th a t w e w an t to use only o n e significant digit. To elim in ate th e excess digits, w e can e ith e r sim ply d iscard th em (tru n ca tion ) o r dis card th e m bv ro u n d in g th e resu ltin g n u m b e r (ro un din g). T h e resu ltin g q u an tized signals x q (n) a re show n in T ab le 1.2. W e discuss only q u a n tiz a tio n by ro u n d in g , alth o u g h it is ju st as easy to tr e a t tru n c a tio n. T h e ro u n d in g p ro c e ss is g raphically illu stra te d in Fig. 1.20b. T h e values allo w ed in th e digital signal are called the quan tizatio n levels, w h ereas the d istan c e A b etw een tw o successive q u a n tiz a tio n levels is called th e q uantization step siz e o r resolution. T h e ro u n d in g q u a n tiz e r assigns each sa m p le of x ( n ) to th e n e a re s t q u a n tiz a tio n level. In c o n tra st, a q u a n tizer th a t p e rfo rm s tru n c a tio n w ould have assigned each sa m p le of jc(/z) to the q u a n tiz a tio n level b elo w it. T h e q u a n tiz a tio n e r ro r eq (n) in ro u n d in g is lim ited to th e ra n g e of —A /2 to A /2 , th a t is, A A - y
