Digital Signal Processing: Signals, Systems, and Filters The great advancements in the design of microchips, digital systems, and computer hardware over the past 40 years have given birth to digital signal processing (DSP) which has grown over the years into a ubiquitous, multifaceted, and indispensable subject of study. As such DSP has been applied in most disciplines ranging from engineering to economics and from astronomy to molecular biology. Consequently, it would take a multivolume encyclopedia to cover all the facets, aspects, and ramifications of DSP, and such a treatise would require many authors. This textbook focuses instead on the fundamentals of DSP, namely, on the representation of signals by mathematical models and on the processing of signals by discretetime systems. Various types of processing are possible for signals but the processing of interest in this volume is almost always linear and it typically involves reshaping, transforming, or manipulating the frequency spectrum of the signal of interest. Discretetime systems that can reshape, transform, or manipulate the spectrum of a signal are known as digital filters, and these systems will receive very special attention as they did in the author’s previous textbook Digital Filters: Analysis, Design, and Applications, McGrawHill, 1993. This author considers the processing of continuous and discretetime signals to be different facets of one and the same subject of study without a clear demarcation where the processing of continuoustime signals by analog systems ends and the processing of discretetime signals by digital systems begins. Discretetime signals sometimes exist as distinct entities that are not derived from or related to corresponding continuoustime signals. The processing of such a signal would result in a transformed discretetime signal, which would be, presumably, an enhanced or in some way more desirable version of the original signal. Obviously, reference to an underlying continuoustime signal would be irrelevant in such a case. However, more often than not discretetime signals are derived from corresponding continuoustime signals and, as a result, they inherit the spectral characteristics of the latter. Discretetime signals of this type are often processed by digital systems and after that they are converted back to continuoustime signals. A case in point can be found in the recording industry where music is first sampled to generate a discretetime signal which is then recorded on a CD. When the CD is played back, the discretetime signal is converted into a continuoustime signal. In order to preserve the spectrum of the underlying continuoustime signal, e.g., that delightful piece of music, through this series of signal manipulations, special attention must be paid to the spectral relationships that exist between continuous and discretetime signals. These relationships are examined in great detail in Chapters 6 and 7. In the application just described, part of the processing must be performed by analog filters. As will be shown in Chapter 6, there is often a need to use a bandlimiting analog filter before sampling and, on the other hand, the continuoustime signal we hear through our stereo systems is produced by yet another analog filter. Therefore, knowledge of analog filters is prerequisite if we are called upon to design DSP systems that involve continuoustime signals in some way. Knowledge of analog filters is crucial in another respect: some of the better recursive digital filters can be designed only by converting analog into digital filters, as will be shown in Chapters 10–12 and 17. The prerequisite knowledge for the book is a typical undergraduate mathematics background of calculus, complex analysis, and simple differential equations. At certain universities, complex analysis may not be included in the curriculum. To overcome this difficulty, the basics of complex analysis are summarized in Appendix A which can also serve as a quick reference or refresher. The derivation of the elliptic approximation in Section 10.6 requires a basic understanding of elliptic functions but it can be skipped by most readers. Since elliptic functions are not normally included in undergraduate curricula, a brief but adequate treatment of these functions is included in Appendix B for the sake of completeness. Chapter 14 requires a basic understanding of random variables and processes which may not be part of the curriculum at certain universities. To circumvent this difficulty, the prerequisite knowledge on random variables and processes is summarized in Chapter 13. Chapter 1 provides an overview of DSP. It starts with a classification of the types of signals encountered in DSP. It then introduces in a heuristic way the characterization of signals in terms of frequency spectrums. The filtering process as a means of transforming or altering the spectrum of a signal is then described. The second half of the chapter provides a historical perspective of the evolution of analog and digital filters and their applications. The chapter concludes with two specific applications that illustrate the scope, diversity, and usefulness of DSP. Chapter 2 describes the Fourier series and Fourier transform as the principal mathematical entities for the spectral characterization of continuoustime signals. The Fourier transform is deduced from the Fourier series through a limiting process whereby the period of a periodic signal is stretched to infinity. The most important mathematical tool for the representation of discretetime signals is the z transform and this forms the subject matter of Chapter 3. The z transform is viewed as a Laurent series and that immediately causes the z transform to inherit the mathematical properties of the Laurent series. By this means, the convergence properties of the z transform are more clearly understood and, furthermore, a host of algebraic techniques become immediately applicable in the inversion of the z transform. The chapter also deals with the use of the z transform as a tool for the spectral representation of discretetime signals. Chapter 4 deals with the fundamentals of discretetime systems. Topics considered include basic system properties such as linearity, time invariance, causality, and stability; characterization of discretetime systems by difference equations; representation by networks and signal flowgraphs and analysis by nodeelimination techniques. Timedomain analysis is introduced at an elementary level. The analysis is accomplished by solving the difference equation of the system by using induction. Although induction is not known for its efficiency, it is an intuitive technique that provides the newcomer with a clear understanding of the basics of discretetime systems and how they operate, e.g., what are initial conditions, what is a transient or steadystate response, what is an impulse response, and so on. The chapter continues with the representation of discretetime systems by convolution summations on the one hand and by statespace characterizations on the other. The application of the z transform to discretetime systems is covered in Chapter 5.Byapplying the z transform to the convolution summation, a discretetime system can be represented by a transfer function that encapsulates all the linear properties of the system, e.g., timedomain response, stability, steadystate sinusoidal response, and frequency response. The chapter also includes stability criteria and algorithms that can be used to decide with minimal computational effort whether a discretetime system is stable or not. The concepts of amplitude and phase responses and their physical significance are illustrated by examples as well as by two and threedimensional MATLAB plots that show clearly the true nature of zeros and poles. Chapter 5 also delineates the standard first and secondorder transfer functions that can be used to design lowpass, highpass, bandpass, bandstop, and allpass digital filters. The chapter concludes with a discussion on the causes and elimination of signal distortion in discretetime systems such as amplitude distortion and delay distortion. Chapter 6 extends the application of the Fourier transform to impulse and periodic signals. It also introduces the class of impulsemodulated signals which are, in effect, both sampled and continuous in time. As such, they share characteristics with both continuous as well as discretetime signals. Therefore, these signals provide a bridge between the analog and digital worlds and thereby facilitate the DSP practitioner to interrelate the spectral characteristics of discretetime signals with those of the continuoustime signals from which they were derived. The chapter also deals with the sampling process, the use of digital filters for the processing of continuoustime signals, and the characterization and imperfections of analogtodigital and digitaltoanalog converters. Chapter 7 presents the discrete Fourier transform (DFT) and the associated fast Fouriertransform method as mathematical tools for the analysis of signals on the one hand and for the software implementation of digital filters on the other. The chapter starts with the definition and properties of the DFT and continues with the interrelations that exist between the DFT and (1) the z transform, (2) the continuous Fourier transform, and (3) the Fourier series. These interrelations must be thoroughly understood, otherwise the user of the fast Fouriertransform method is likely to end up with inaccurate spectral representations for the signals of interest. The chapter also deals with the window method in detail, which can facilitate the processing of signals of long or infinity duration. Chapters 1 to 7 deal, in effect, with the characterization and properties of continuous and discretetime, periodic and nonperiodic signals, and with the general properties of discretetime systems in general. Chapters 8 to 18, on the other hand, are concerned with the design of various types of digital filters. The design process is deemed to comprise four steps, namely, approximation, realization, implementation, and study of system imperfections brought about by the use of finite arithmetic. Approximation is the process of generating a transfer function that would satisfy the required specifications. Realization is the process of converting the transfer function or some other characterization of the digital filter into a digital network or structure. Implementation can take two forms, namely, software and hardware. In a software implementation, a difference equation or statespace representation is converted into a computer program that simulates the performance of the digital filter, whereas in a hardware implementation a digital network is converted into a piece of dedicated hardware. System imperfections are almost always related to the use of finiteprecision arithmetic and manifest themselves as numerical errors in filter parameters or the values of the signals being processed. Although the design process always starts with the solution of the approximation problem, the realization process is much easier to deal with and for this reason it is treated first in Chapter 8. As will be shown, several realization methods are available that lead to a great variety of digitalfilter structures. Chapter 8 also deals with a special class of structures known as systolic structures which happen to have some special properties that make them amenable to integratedcircuit implementation. Chapter 9 is concerned with closedform methods that can be used to design nonrecursive filters. The chapter starts by showing that constantdelay (linearphase) nonrecursive filters can be easily designed by forcing certain symmetries on the impulse response. The design of such filters through the use of the Fourier series in conjunction with the windowmethod is then described. Several of the standard window functions, including the DolphChebyshev and Kaiser window functions, and their interrelations are detailed. The chapter includes a stepbystep design procedure based on the Kaiser window function that can be used to design standard nonrecursive filters that would satisfy prescribed specifications. It concludes with a method based on the use of classical numerical analysis formulas which can be used to design specialized nonrecursive filters that can perform interpolation, differentiation, and integration. The approximation problem for recursive filters can be solved by using direct or indirect methods. In direct methods, the discretetime transfer function is obtained directly in the z domain usually through iterative optimization methods. In indirect methods, on the other hand, the discretetime transfer function is obtained by converting the continuoustime transfer function of an appropriate analog filter through a series of transformations. Thus the need arises for the solution of the approximation problem in analog filters. The basic concepts pertaining to the characterization of analog filters and the standard approximation methods used to design analog lowpass filters, i.e., the Butterworth, Chebyshev, inverseChebyshev, elliptic, and BesselThomson methods, are described in detail in Chapter 10. The chapter concludes with certain classical transformations that can be used to convert a given lowpass approximation into a corresponding highpass, bandpass, or bandstop approximation. Chapter 11 deals with the approximation problem for recursive digital filters. Methods are described by which a given continuoustime transfer function can be transformed into a corresponding discretetime transfer function, e.g., the invariant impulseresponse, matchedz transformation, and bilineartransformation methods. The chapter concludes with certain transformations that can be used to convert a given lowpass digital filter into a corresponding highpass, bandpass, or bandstop digital filter. A detailed procedure that can be used to design Butterworth, Chebyshev, inverseChebyshev, and elliptic filters that would satisfy prescribed specifications, with design examples, is found in Chapter 12. The basics of random variables and the extension of these principles to random processes as a means of representing random signals are introduced in Chapter 13. Random variables and signals arise naturally in digital filters because of the inevitable quantization of filter coefficients and signal values. The effects of finite word length in digital filters along with relevant uptodate methods of analysis are discussed in Chapter 14. The topics considered include coefficient quantization and methods to reduce its effects; signal scaling; product quantization and methods to reduce its effects; parasitic and overflow limitcycle oscillations and methods to eliminate them. Chapters 15 and 16 deal with the solution of the approximation problem using iterative optimization methods. Chapter 15 describes a number of efficient algorithms based on the Remez exchange algorithm that can be used to design nonrecursive filters of the standard types, e.g., lowpass, highpass, bandpass, and bandstop filters, and also specialized filters, e.g., filters with arbitrary amplitude responses, multiband filters, and digital differentiators. Chapter 16, on the other hand, considers the design of recursive digital filters by optimization. To render this material accessible to the reader who has not had the opportunity to study optimization before, a series of progressively improved but related algorithms is presented starting with the classical Newton algorithm for convex problems and culminating in a fairly sophisticated, practical, and efficient quasiNewton algorithm that can be used to design digital filters with arbitrary frequency responses. Chapter 16 also deals with the design of recursive equalizers which are often used to achieve a linear phase response in a recursive filter. Chapter 17 is in effect a continuation of Chapter 8 and it deals with the realization of digital filters in the form of wave digital filters. These structures are derived from classical analog filters and, in consequence, they have certain attractive features, such as lowsensitivity to numerical errors, which make them quite attractive for certain applications. The chapter includes stepbystep procedures by which wave digital filters satisfying prescribed specifications can be designed either in ladder or lattice form. The chapter concludes with a list of guidelines that can be used to choose a digitalfilter structure from the numerous possibilities described in Chapters 8 and 12. Chapter 18 deals with some of the numerous applications of digital filters to digital signal processing. The applications considered include downsampling and upsampling using decimators and interpolators, the design of quadraturemirrorimage filters and their application in timedivision to frequencydivision multiplex translation, Hilbert transformers and their application in singlesideband modulation, adaptive filters, and twodimensional digital filters. The purpose of Appendix A is twofold. First, it can be regarded as a brief review of complex analysis for readers who have not had the opportunity to take a course on this important subject. Second, it can serve as a reference monograph that brings together those principles of complex analysis that are required for DSP. Appendix B, on the other hand, presents the basic principles of elliptic integrals and functions and its principal purpose is to facilitate the derivation of the elliptic approximation in Chapter 10. The book can serve as a text for undergraduate or graduate courses and various scenarios are possible depending on the background preparation of the class and the curriculum of the institution. Some possibilities are as follows:
The book is supported by the author’s DSP software package DFilter which can be used to analyze, design, and realize digital filters, and to analyze discretetime signals. See DFilter page at the end of the book for more details. The software can be downloaded from DFilter’s website: www.dfilter.com or www.dfilter.ece.uvic.ca. In addition, a detailed Instructor’s Manual and PDF slides for classroom use are nowbeing prepared, which will be made available to instructors adopting the book through the author’s website: www.ece.uvic.ca/˜ andreas. I would like to thank Stuart Bergen, Rajeev Nongpiur, andWuSheng Lu for reviewing the reference lists of certain chapters and supplying more uptodate references;Tarek Nasser for checking certain parts of the manuscript; Randy K. Howell for constructing the plots in Figures 16.12 and 16.13; Majid Ahmadi for constructive suggestions; Tony Antoniou for suggesting improvements in the design of the cover and title page of the book and for designing the installation graphics and icons of DFilter; David Guindon for designing a new interface for DFilter; Catherine Chang for providing help in updating many of the illustrations; Lynne Barrett for helping with the proofreading; Michelle L. Flomenhoft, Development Editor, Higher Education Division, McGrawHill, for her many contributions to the development of the manuscript and for arranging the reviews; to the reviewers of the manuscript for providing useful suggestions and identifying errata, namely, Scott T. Acton, University of Virginia; Selim Awad, University of Michigan; Vijayakumar Bhagavatula, Carnegie Mellon University; Subra Ganesan, Oakland University; Martin Haenggi, University of Notre Dame; Donald Hummels, University of Maine; James S. Kang, California State Polytechnic University; Takis Kasparis, University of Central Florida; Preetham B. Kumar, California State University; Douglas E. Melton, Kettering University; Behrooz Nowrouzian, University of Alberta; Wayne T. Padgett, RoseHulman Institute of Technology; Roland Priemer, University of Illinois, Chicago; Stanley J. Reeves, Auburn University; Terry E. Riemer, University of New Orleans; A. David Salvia, Pennsylvania State University; Ravi Sankar, University of South Florida; Avtar Singh, San Jose State University; Andreas Spanias, Arizona State University; Javier VegaPineda, Instituto Tecnologico de Chihuahua; HsiaoChun Wu, Louisiana State University; Henry Yeh, California State University. Thanks are also due to Micronet, Networks of Centres of Excellence Program, Canada, the Natural Sciences and Engineering Research Council of Canada, and the University of Victoria, British Columbia, Canada, for supporting the research that led to many of the author’s contributions to DSP as described in Chapters 12 and 14 to 17. Last but not least, Iwould like to express my thanks and appreciation to Mona Tiwary, Project Manager, International Typesetting and Composition, and Stephen S. Chapman, Editorial Director, Professional Division, McGrawHill, for seeing the project through to a successful conclusion. Andreas Antoniou
