Contents xi 11 LINEAR PREDICTION AND OPTIMUM LINEAR FILTERS 852 111 Innovations Representation of a Stationary Random Process 852 ]1.1.1 Rational Power Spectra.854 11.1.2 Relationships Between the Filter Parameters and the Autocorrelation Sequence.855 11.2 Forward and Backward Linear Prediction 857 11.2.1 Forward Linear Prediction.857 11.2.2 Backward Linear Prediction.860 11.2.3 The Optimum Refection Coefficients for the Lattice Forward and Backward Predictors.863 11.2.4 Relationship of an AR Process to Linear Prediction.864 11.3 Solution of the Normal Equations 864 11.3.1 The Levinson-Durbin Algorithm.865 11.3.2 The Schur Algorithm.868 11.4 Properties of the Linear Prediction-Error Filters 873 11.5 AR Lattice and ARMA Lattice-Ladder Filters 876 11.5.1 AR Lattice Structure.877 11.5.2 ARMA Processes and Lattice-Ladder Filters.878 11.6 Wiener Filters for Filtering and Prediction 880 11.6.1 FIR Wiener Filter.881 11.6.2 Orthogonality Principle in Linear Mean-Square Estimation.884 11.6.3 JIR Wiener Filter.885 11.6.4 Noncausal Wiener Filter,889 11.7 Summary and References 890 Problems 892 12 POWER SPECTRUM ESTIMATION 896 12.1 Estimation of Spectra from Finite-Duration Observations of Signals 896 12.1.1 Computation of the Energy Density Spectrum.897 12.].2 Estimation of the Autocorrelation and Power Spectrum of Random Signals:The Periodogram.902 12.1.3 The Use of the DFT in Power Spectrum Estimation.906 12.2 Nonparametric Methods for Power Spectrum Estimation 908 12.2.1 The Bartlet:Method:Averaging Periodograms.910 12.2.2 The Welch Method:Averaging Modifed Periodograms.911 12.2.3 The Blackman and Tukey Method:Smoothing the Periodogram.913 12.2.4 Performance Characteristics of Nonparametric Power Spectrum Estimators.916
xii Contents 12.2.5 Computational Requirements of Nonparametric Power Spectrum Estimates,919 12.3 Parametric Methods for Power Spectrum Estimation 920 12.3.1 Relationships Between the Autocorrelation and the Model Parameters,923 12.3.2 The Yule-Walker Method for the AR Model Parameters.925 12.3.3 The Burg Method for the AR Model Parameters.925 12.3.4 Unconstrained Least-Squares Method for the AR Model Parameters.929 12.3.5 Sequential Estimation Methods for the AR Model Parameters.930 12.3.6 Selection of AR Model Order.931 12.3.7 MA Model for Power Spectrum Estimation.933 12.3.8 ARMA Model for Power Spectrum Estimation.934 12.3.9 Some Experimental Results.936 12.4 Minimum Variance Spectral Estimation 942 12.5 Eigenanalysis Algorithms for Spectrum Estimation 946 12.5.1 Pisarenko Harmonic Decomposition Method,948 12.5.2 Eigen-decomposition of the Autocorrelation Matrix for Sinusoids in White Noise.950 12.5.3 MUSIC Algorithm.952 12.5.4 ESPRIT Algorithm.953 12.5.5 Order Selection Criteria.955 12.5.6 Experimental Results.956 12.6 Summary and References 959 Problems 960 A RANDOM SIGNALS,CORRELATION FUNCTIONS,AND POWER SPECTRA 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
Preface This book was developed based on our teaching of undergraduate and gradu- ate level courses in digital signal processing over the past several years.In this book we present the fundamentals of discrete-time signals.systems,and modern digital processing algorithms and applications for students in electrical engineer- ing.computer engineering.and computer science.The book is suitable for either a one-semester or a two-semester undergraduate level course in discrete systems and digital signal processing.It is also intended for use in a one-semester first-vear graduate-level course in digital signal processing. It is assumed that the student in electrical and computer engineering has had undergraduate courses in advanced calculus (including ordinary differential equa- tions).and linear systems for continuous-time signals.including an introduction to the Laplace transform.Although the Fourier series and Fourier transforms of periodic and aperiodic signals are described in Chapter 4,we expect that many students may have had this material in a prior course. A balanced coverage is provided of both theory and practical applications. A large number of well designed problems are provided to help the student in mastering the subject matter.A solutions manual is available for the benefit of the instructor and can be obtained from the publisher. The third edition of the book covers basically the same material as the sec- ond edition.but is organized differently.The major difference is in the order in which the DFT and FFT algorithms are covered.Based on suggestions made by several reviewers.we now introduce the DFT and describe its efficient computa- tion immediately following our treatment of Fourier analysis.This reorganization has also allowed us to eliminate repetition of some topics concerning the DFT and its applications. In Chapter 1 we describe the operations involved in the analog-to-digital conversion of analog signais.The process of sampling a sinusoid is described in some detail and the problem of aliasing is explained.Signal quantization and digital-to-analog conversion are also described in general terms.but the analysis is presented in subsequent chapters. Chapter 2 is devoted entirely to the characterization and analysis of linear time-invariant (shift-invariant)discrete-time systems and discrete-time signals in the time domain.The convolution sum is derived and systems are categorized according to the duration of their impulse response as a finite-duration impulse xiii
xiv Preface response (FIR)and as an infinite-duration impulse response (IIR).Linear time- invariant systems characterized by difference equations are presented and the so- lution of difference equations with initial conditions is obtained.The chapter concludes with a treatment of discrete-time correlation. The =-transform is introduced in Chapter 3.Both the bilateral and the unilateral z-transforms are presented,and methods for determining the inverse z-transform are described.Use of the z-transform in the analysis of linear time- invariant systems is illustrated,and important properties of systems.such as causal- ity and stability.are related to z-domain characteristics. Chapter 4 treats the analysis of signals and systems in the frequency domain. Fourier series and the Fourier transform are presented for both continuous-time and discrete-time signals.Linear time-invariant (LTI)discrete systems are char- acterized in the frequency domain by their frequency response function and their response to periodic and aperiodic signals is determined.A number of important types of discrete-time systems are described.including resonators.notch filters. comb filters,all-pass filters,and osciliators.The design of a number of simple FIR and IIR filters is also considered.In addition.the student is introduced to the concepts of minimum-phase,mixed-phase,and maximum-phase systems and to the problem of deconvolution. The DFT.its properties and its applications.are the topics covered in Chap- ter 5.Two methods are described for using the DFT to perform linear filtering. The use of the DFT to perform frequency analysis of signals is also described. Chapter 6 covers the efficient computation of the DFT.Included in this chap- ter are descriptions of radix-2,radix-4,and split-radix fast Fourier transform(FFT) algorithms,and applications of the FFT algorithms to the computation of convo- lution and correlation.The Goertzel algorithm and the chirp-z transform are introduced as two methods for computing the DFT using linear filtering. Chapter 7 treats the realization of IIR and FIR systems.This treatment includes direct-form.cascade,parallel,lattice,and lattice-ladder realizations.The chapter includes a treatment of state-space analysis and structures for discrete-time systems.and examines quantization effects in a digital implementation of FIR and IIR systems. Techniques for design of digital FIR and IIR filters are presented in Chap- ter 8.The design techniques include both direct design methods in discrete time and methods invoiving the conversion of analog filters into digital filters by various transformations.Also treated in this chapter is the design of FIR and IIR filters by least-squares methods. Chapter 9 focuses on the sampling of continuous-time signais and the re- construction of such signals from their samples.In this chapter.we derive the sampling theorem for bandpass continuous-time-signals and then cover the A/D and D/A conversion techniques,including oversampling A/D and D/A converters. Chapter 10 provides an indepth treatment of sampling-rate conversion and its applications to multirate digital signal processing.In addition to describing dec- imation and interpolation by integer factors,we present a method of sampling-rate
Preface v conversion by an arbitrary factor.Several applications to multirate signal process- ing are presented.including the implementation of digital filters.subband coding of speech signals,transmultiplexing.and oversampling A/D and D/A converters. Linear prediction and optimum linear (Wiener)filters are treated in Chap- ter 11.Also included in this chapter are descriptions of the Levinson-Durbin algorithm and Schur algorithm for solving the normal equations,as well as the AR lattice and ARMA lattice-ladder filters. Power spectrum estimation is the main topic of Chapter 12.Our coverage includes a description of nonparametric and model-based (parametric)methods. Also described are eigen-decomposition-based methods,including MUSIC and ESPRIT. At Northeastern University,we have used the first six chapters of this book for a one-semester (junior level)course in discrete systems and digital signal pro- cessing. A one-semester senior level course for students who have had prior exposure to discrete systems can use the material in Chapters 1 through 4 for a quick review and then proceed to cover Chapter 5 through 8. In a first-vear graduate level course in digital signal processing,the first five chapters provide the student with a good review of discrete-time systems.The instructor can move quickly through most of this material and then cover Chapters 6 through 9.followed by either Chapters 10 and 11 or by Chapters 11 and 12. We have included many examples throughout the book and approximately 500 homework problems.Many of the homework problems can be solved numer- ically on a computer,using a software package such as MATLABO.These prob- lems are identified by an asterisk.Appendix D contains a list of MATLAB func- tions that the student can use in solving these problems.The instructor may also wish to consider the use of a supplementary book that contains computer based exercises.such as the books Digital Signal Processing Using MATLAB (P.W.S. Kent.1996)by V.K.Ingle and J.G.Proakis and Computer-Based Exercises for Signal Processing Using MATLAB (Prentice Hall,1994)by C.S.Burrus et al. The authors are indebted to their many faculty colleagues who have provided valuable suggestions through reviews of the first and second editions of this book. These include Drs.W.E.Alexander,Y.Bresler.J.Deller,V.Ingle,C.Keller. H.Lev-Ari,L.Merakos,W.Mikhael,P.Monticciolo,C.Nikias,M.Schetzen, H.Trussell,S.Wilson,and M.Zoltowski.We are also indebted to Dr.R.Price for recommending the inclusion of split-radix FFT algorithms and related suggestions. Finally,we wish to acknowledge the suggestions and comments of many former graduate students.and especially those by A.L.Kok,J.Lin and S.Srinidhi who assisted in the preparation of several illustrations and the solutions manual. John G.Proakis Dimitris G.Manolakis