An Introduction To The Mathematics Of Digital Signal Processing Pdf

Introduction to
Signal Processing

Sophocles J. Orfanidis

Copyright Notice

The book's copyrights were transferred from Prentice Hall to Sophocles J. Orfanidis in 2009. A new version of the book, that includes corrections of all the typos, is now freely available in PDF format, and in a 2-up form. A solutions manual is available. A printed version is also available as a size-6x9 paperback.

Links to the book's web page, http://www.ece. rutgers.edu/~orfanidi/intro2sp/ , may be placed on any web site. Any part of this book may be downloaded and printed for personal or educational use only, as long as the printed or photocopied pages are not altered in any way from the original PDF file posted on the book's web page.

No part of this book may be reproduced, altered in any way, or transmitted in any form for commercial, profit, sale, or marketing purposes.

Preface
Table of Contents
Highlights
C and MATLAB Functions
Errata and Feedback
Publication Data
Typesetting Notes
About the Cover
About the Author

ADSP-2181 Experiments

Preface

This book provides an applications-oriented introduction to digital signal processing written primarily for electrical engineering undergraduates. Practicing engineers and graduate students may also find it useful as a first text on the subject.

Digital signal processing is everywhere. Today's college students hear "DSP" all the time in their everyday life - from their CD players, to their electronic music synthesizers, to the sound cards in their PCs. They hear all about "DSP chips", "oversampling digital filters", "1-bit A/D and D/A converters", "wavetable sound synthesis", "audio effects processors", "all-digital audio studios". By the time they reach their junior year, they are already very eager to learn more about DSP.

Approach

The learning of DSP can be made into a rewarding, interesting, and fun experience for the student by weaving into the material several applications, such as the above, that serve as vehicles for teaching the basic DSP concepts, while generating and maintaining student interest. This has been the guiding philosophy and objective in writing this text. As a result, the book's emphasis is more on signal processing than discrete-time system theory, although the basic principles of the latter are adequately covered.

The book teaches by example and takes a hands-on practical approach that emphasizes the algorithmic, computational, and programming aspects of DSP. It contains a large number of worked examples, computer simulations and applications, and includes several C and MATLAB functions for implementing various DSP operations. The practical slant of the book makes the concepts more concrete.

Use

The book may be used at the junior or senior level. It is based on a junior-level DSP course that I have taught at Rutgers since 1988. The assumed background is only a first course on linear systems. Sections marked with an asterisk (*) are more appropriate for a second or senior elective course on DSP. The rest can be covered at the junior level. The included computer experiments can form the basis of an accompanying DSP lab course, as is done at Rutgers.

A solutions manual, which also contains the results of the computer experiments, is available from the publisher. The C and MATLAB functions may be obtained via anonymous FTP from the Internet site ece.rutgers.edu in the directory /pub/sjo or by pointing a Web browser to the book's WWW home page on ftp://ece.rutgers.edu/pub/sjo/intro2sp.html.

Contents and Highlights

Chapters 1 and 2 contain a discussion of the two key DSP concepts of sampling and quantization. The first part of Chapter 1 covers the basic issues of sampling, aliasing, and analog reconstruction at a level appropriate for juniors. The second part is more advanced and discusses the practical issues of choosing and defining specifications for antialiasing prefilters and anti-image postfilters.

Chapter 2 discusses the quantization process and some practical implementations of A/D and D/A converters, such as the conversion algorithm for bipolar two's complement successive approximation converters. The standard model of quantization noise is presented, as well as the techniques of oversampling, noise shaping, and dithering. The tradeoff between oversampling ratio and savings in bits is derived. This material is continued in Section 12.7 where the implementation and operation of delta-sigma noise shaping quantizers is considered.

Chapter 3 serves as a review of basic discrete-time systems concepts, such as linearity, time-invariance, impulse response, convolution, FIR and IIR filters, causality, and stability. It can be covered quickly as most of this material is assumed known from a prerequisite linear systems course.

Chapter 4 focuses on FIR filters and its purpose is to introduce two basic signal processing methods: block-by-block processing and sample-by-sample processing. In the block processing part, we discuss convolution and several ways of thinking about it, transient and steady-state behavior, and real-time processing on a block-by-block basis using the overlap-add method and its software implementation. This is further discussed in Section 9.9 using the FFT.

In the sample processing part, we introduce the basic building blocks of filters: adders, multipliers, and delays. We discuss block diagrams for FIR filters and their time-domain operation on a sample by sample basis. We put a lot of emphasis on the concept of sample processing algorithm, which is the repetitive series of computations that must be carried out on each input sample.

We discuss the concept of circular buffers and their use in implementing delays and FIR filters. We present a systematic treatment of the subject and carry it on to the remainder of the book. The use of circular delay-line buffers is old, dating back at least 25 years with its application to computer music. However, it has not been treated systematically in DSP texts. It has acquired a new relevance because all modern DSP chips use it to minimize the number of hardware instructions.

Chapter 5 covers the basics of z-transforms. We emphasize the z-domain view of causality, stability, and frequency spectrum. Much of this material may be known from an earlier linear system course.

Chapter 6 shows the equivalence of various ways of characterizing a linear filter and illustrates their relevance by example. It discusses also topics such as, sinusoidal and steady-state responses, time constants of filters, simple pole/zero designs of first and second order filters as well as comb and notch filters. The issues of inverse filtering and causality are also considered.

Chapter 7 develops the standard filter realizations of canonical, direct, and cascade forms, and their implementation with circular buffers. Quantization effects are briefly discussed.

Chapter 8 presents three DSP application areas. The first is on digital waveform generation, with particular emphasis on wavetable generators. The second is on digital audio effects, such as flanging, chorusing, reverberation, multitap delays, and dynamics processors, such as compressors and expanders. These two areas were chosen because of their appeal to undergraduates and because they provide concrete illustrations of the use of delays, circular buffers, and filtering concepts in the context of audio signal processing.

The third area is on noise reduction/signal enhancement, which is one of the most important applications of DSP and is of interest to practicing engineers and scientists who remove noise from data on a routine basis. Here, we develop the basic principles for designing noise reduction and signal enhancement filters both in the frequency and time domains. We discuss the design and circular buffer implementation of notch and comb filters for removing periodic interference, enhancing periodic signals, signal averaging, and for separating the luminance and chrominance components in digital color TV systems. We also discuss Savitzky-Golay filters for data smoothing and differentiation.

Chapter 9 covers DFT/FFT algorithms. The first part emphasizes the issues of spectral analysis, frequency resolution, windowing, and leakage. The second part discusses the computational aspects of the DFT and some of its pitfalls, the difference between physical and computational frequency resolution, the FFT, and fast convolution.

Chapter 10 covers FIR filter design using the window method, with particular emphasis on the Kaiser window. We also discuss the use of the Kaiser window in spectral analysis.

Chapter 11 discusses IIR filter design using the bilinear transformation based on Butterworth and Chebyshev filters. By way of introducing the bilinear transformation, we show how to design practical 2nd order digital audio parametric equalizer filters having prescribed widths, center frequencies, and gains. We also discuss the design of periodic notch and comb filters with prescribed widths.

In these two filter design chapters, we have chosen to present only a few design methods that are simple enough for our intended level of presentation and effective enough to be of practical use.

Chapter 12 discusses interpolation, decimation, oversampling DSP systems, sample rate converters, and delta-sigma quantizers. We discuss the use of oversampling for alleviating the need for high quality analog prefilters and postfilters. We present several practical design examples of interpolation filters, including polyphase and multistage designs. We consider the design of sample rate converters and study the operation of oversampled delta-sigma quantizers by simulation. This material is too advanced for juniors but not for seniors. All undergraduates, however, have a strong interest in it because of its use in digital audio systems such as CD and DAT players.

The Appendix has four parts: (a) a review section on random signals; (b) a discussion of random number generators, including uniform, gaussian, low frequency, and 1/f noise generators used in the simulations; (c) C functions for performing the complex arithmetic in the DFT routines; (d) listings of MATLAB functions.

Paths

Several course paths are possible through the text depending on the desired level of presentation. For example, in the 14-week junior course at Rutgers we cover sections 1.1-1.4, 2.1-2.4, chapters 3-7, section 8.1-8.2, chapter 9, and sections 10.1-10.2 and 11.1-11.4. One may omit certain of these sections and/or add others depending on the available time and student interest and background. In a second DSP course at the senior year, one may add sections 1.5-1.7, 2.5, 8.1, 8.3, 11.5, 11.6, and chapter 12. In a graduate course, the entire text can be covered comfortably in one semester.

Acknowledgments

I am indebted to the many generations of students who tried earlier versions of the book and helped me refine it. In particular, I would like to thank Mr. Cem Saraydar for his thorough proofreading of the manuscript. I would like to thank my colleagues Drs. Zoran Gajic, Mark Kahrs, James Kaiser, Dino Lelic, Tom Marshall, Peter Meer, and Nader Moayeri for their feedback and encouragement. I am especially indebted to Dr. James Kaiser for enriching my classes over the past eight years with his inspiring yearly lectures on the Kaiser window. I would like to thank the book reviewers Drs. A. V. Oppenheim, J. A. Fleming, Y-C Jenq, W. B. Mikhael, S. J. Reeves, A. Sekey, and J. Weitzen, whose comments helped improve the book. And I would like to thank Rutgers for providing me with a sabbatical leave to finish up the project. I welcome any feedback from readers - it may be sent to orfanidi@ece.rutgers.edu.

Finally, I would like to thank my wife Monica and son John for their love, patience, encouragement, and support.

Sophocles J. Orfanidis

Return to menu .

Sampling and Reconstruction

1.1 Introduction

1.2 Review of Analog Signals

1.3 Sampling Theorem

1.3.1 Sampling Theorem

1.3.2 Antialiasing Prefilters

1.3.3 Hardware Limits

1.4 Sampling of Sinusoids

1.4.1 Analog Reconstruction and Aliasing

1.4.2 Rotational Motion

1.4.3 DSP Frequency Units

1.5 Spectra of Sampled Signals*

1.5.1 Discrete-Time Fourier Transform

1.5.2 Spectrum Replication

1.5.3 Practical Antialiasing Prefilters

1.6 Analog Reconstructors*

1.6.1 Ideal Reconstructors

1.6.2 Staircase Reconstructors

1.6.3 Anti-Image Postfilters

1.7 Basic Components of DSP Systems

1.8 Problems
Quantization

2.1 Quantization Process

2.2 Oversampling and Noise Shaping*

2.3 D/A Converters

2.4 A/D Converters

2.5 Analog and Digital Dither*

2.6 Problems
Discrete-Time Systems

3.1 Input/Output Rules

3.2 Linearity and Time Invariance

3.3 Impulse Response

3.4 FIR and IIR Filters

3.5 Causality and Stability

3.6 Problems
FIR Filtering and Convolution

4.1 Block Processing Methods

4.1.1 Convolution

4.1.2 Direct Form

4.1.3 Convolution Table

4.1.4 LTI Form

4.1.5 Matrix Form

4.1.6 Flip-and-Slide Form

4.1.7 Transient and Steady-State Behavior

4.1.8 Convolution of Infinite Sequences

4.1.9 Programming Considerations

4.1.10 Overlap-Add Block Convolution Method

4.2 Sample Processing Methods

4.2.1 Pure Delays

4.2.2 FIR Filtering in Direct Form

4.2.3 Programming Considerations

4.2.4 Hardware Realizations and Circular Buffers

4.3 Problems
z-Transforms

5.1 Basic Properties

5.2 Region of Convergence

5.3 Causality and Stability

5.4 Frequency Spectrum

5.5 Inverse z-Transforms

5.6 Problems
Transfer Functions

6.1 Equivalent Descriptions of Digital Filters

6.2 Transfer Functions

6.3 Sinusoidal Response

6.3.1 Steady-State Response

6.3.2 Transient Response

6.4 Pole/Zero Designs

6.4.1 First-Order Filters

6.4.2 Parametric Resonators and Equalizers

6.4.3 Notch and Comb Filters

6.5 Deconvolution, Inverse Filters, and Stability

6.6 Problems
Digital Filter Realizations

7.1 Direct Form

7.2 Canonical Form

7.3 Cascade Form

7.4 Cascade to Canonical

7.5 Hardware Realizations and Circular Buffers

7.6 Quantization Effects in Digital Filters

7.7 Problems
Signal Processing Applications

8.1 Digital Waveform Generators

8.1.1 Sinusoidal Generators

8.1.2 Periodic Waveform Generators

8.1.3 Wavetable Generators

8.2 Digital Audio Effects

8.2.1 Delays, Echoes, and Comb Filters

8.2.2 Flanging, Chorusing, and Phasing

8.2.3 Digital Reverberation

8.2.4 Multitap Delays

8.2.5 Compressors, Limiters, Expanders, and Gates

8.3 Noise Reduction and Signal Enhancement

8.3.1 Noise Reduction Filters

8.3.2 Notch and Comb Filters

8.3.4 Line and Frame Combs for Digital TV

8.3.5 Signal Averaging

8.3.6 Savitzky-Golay Smoothing Filters*

8.4 Problems
DFT/FFT Algorithms

9.1 Frequency Resolution and Windowing

9.2 DTFT Computation

9.2.1 DTFT at a Single Frequency

9.2.2 DTFT over a Frequency Range

9.2.3 DFT

9.2.4 Zero Padding

9.3 Physical versus Computational Resolution

9.4 Matrix Form of DFT

9.5 Modulo-N Reduction

9.6 Inverse DFT

9.7 Sampling of Periodic Signals and the DFT

9.8 FFT

9.9 Fast Convolution

9.9.1 Circular Convolution

9.9.2 Overlap-Add and Overlap-Save Methods

9.10 Problems
FIR Digital Filter Design

10.1 Window Method

10.1.1 Ideal Filters

10.1.2 Rectangular Window

10.1.3 Hamming Window

10.2 Kaiser Window

10.2.1 Kaiser Window for Filter Design

10.2.2 Kaiser Window for Spectral Analysis

10.3 Frequency Sampling Method

10.4 Other FIR Design Methods

10.5 Problems
IIR Digital Filter Design

11.1 Bilinear Transformation

11.2 First Order Lowpass and Highpass Filters

11.3 Second Order Peaking and Notching Filters

11.4 Parametric Equalizer Filters

11.5 Comb Filters

11.6 Higher Order Filters

11.6.1 Analog Lowpass Butterworth Filters

11.6.2 Digital Lowpass Filters

11.6.3 Digital Highpass Filters

11.6.4 Digital Bandpass Filters

11.6.5 Digital Bandstop Filters

11.6.6 Chebyshev Filter Design*

11.7 Problems
Interpolation, Decimation, and Oversampling

12.1 Interpolation and Oversampling

12.2 Interpolation Filter Design*

12.2.1 Direct Form

12.2.2 Polyphase Form

12.2.3 Frequency-Domain Characteristics

12.2.4 Kaiser Window Designs

12.2.5 Multistage Designs

12.3 Design Examples*

12.3.1 4-fold Interpolators

12.3.2 Multistage 4-fold Interpolators

12.3.3 DAC Equalization

12.3.4 Postfilter Design and Equalization

12.3.5 Multistage Equalization

12.4 Decimation and Oversampling*

12.5 Sampling Rate Converters*

12.6 Noise Shaping Quantizers*

12.8 Problems
Appendix

A Random Signals*

A.1 Autocorrelation Functions and Power Spectra

A.2 Filtering of Random Signals

B Random Number Generators

B.1 Uniform and Gaussian Generators

B.2 Low-Frequency Noise Generators*

B.3 1/f Noise Generators*

B.4 Problems

C Complex Arithmetic in C

D MATLAB Functions

Return to menu .

Highlights

Sampling and reconstruction. Practical antialiasing prefilters and anti-image postfilters.
Quantization. A/D & D/A converters. Noise shaping, oversampling DSP systems, dither.
Block processing and sample processing methods. Convolution.
Circular buffer implementations of delays, FIR, and IIR filters.
Discrete-time systems. Z-transforms. Transfer functions. Digital filter realizations.
Wavetable generators. Digital audio effects and dynamics processors.
Noise reduction and signal enhancement principles.
Notch filters for canceling periodic interference.
Comb filters for periodic signal enhancement and digital TV.
Signal averaging. Savitzky-Golay smoothing filters.
DFT/FFT. Spectral analysis. Frequency resolution and windowing. Fast convolution.
FIR filter design using the Kaiser window.
IIR filter design using the bilinear transformation. Butterworth and Chebyshev designs.
Parametric equalizer filter design for digital audio. Parametric comb filters.
Interpolation, decimation, and oversampling. Multistage and polyphase designs.
Sample rate converters. Noise shaping delta-sigma quantizers.
Random signals. Random noise generators: uniform, gaussian, white, low-frequency, 1/f.

Return to menu .

C and MATLAB Functions

All the C functions are contained in the compressed zip file c.zip, and the MATLAB functions in m.zip. The files c.tar.Z, m.tar.Z are in tar-compressed format. Individual listings can be obtained as follows:

C functions
MATLAB Functions

If you download and use the programs, please acknowledge their source. The legal disclaimers contained in the book regarding the use of the programs apply also to these on-line versions.

To improve the readability of the C functions, we use the old K&R way of declaring function arguments. The functions may be easily edited to conform with ANSI C. For example, the K&R declaration:

double fir(M, h, w, x) int M; double *h, *w, x; { /* body of function */ } may be replaced by the ANSI version: double fir(int M, double *h, double *w, double x) { /* body of function */ }

Return to menu .

C Function Listings

blockcon.c - block convolution
can.c - canonical realization
can2.c - canonical realization
can3.c - canonical realization
cas2can.c - cascade to canonical
cas.c - cascade realization
ccan.c - circular-buffer canonical realization
ccan2.c - circular-buffer canonical realization
ccas.c - circular-buffer cascade realization
ccas2.c - circular-buffer cascade realization
cdelay.c - circular delay line
cdelay2.c - circular delay line
cfir.c - circular-buffer FIR filter
cfir1.c - circular-buffer FIR filter
cfir2.c - circular-buffer FIR filter
conv.c - convolution
csos.c - circular-buffer second-order section
csos2.c - circular-buffer second-order section
delay.c - delay line
dir.c - direct form realization
dir2.c - direct form realization
fir.c - FIR filter in direct form
fir2.c - FIR filter in direct form
fir3.c - FIR filter in direct form
sos.c - second-order section
tap.c - circular delay-line tap outputs
tap2.c - circular delay-line tap outputs
wrap.c - circular-buffer pointer wrapping
wrap2.c - circular-buffer index wrapping

adc.c - A/D converter
dac.c - D/A converter

allpass.c - allpass reverberator
lowpass.c - lowpass reverberator
plain.c - plain reverberator
tapi.c - interpolated circular delay-line tap outputs
tapi2.c - interpolated circular delay-line tap outputs

gdelay2.c - generalized circular delay
sine.c - sinusoidal wavetable
square.c - square wavetable
trapez.c - trapezoidal wavetable
wavgen.c - wavetable generator (truncation)
wavgenr.c - wavetable generator (rounding)
wavgeni.c - wavetable generator (interpolation)

bitrev.c - bit reversed index
complex.c - complex arithmetic in C
cmplx.h - header file for complex.c
dft.c - DFT
dftmerge.c - DFT merging
dtft.c - DTFT at single frequency
dtftr.c - DTFT over frequency range
fft.c - FFT
ifft.c - inverse FFT
modwrap.c - modulo-N reduction
shuffle.c - shuffling in FFT
swap.c - swapping in FFT

gran.c - gaussian random number generator
ran.c - uniform random number generator
ran1f.c - 1/f noise generator
ranh.c - low-frequency hold generator
ranl.c - linearly interpolated generator

cheby.c - Chebyshev polynomial evaluator
corr.c - correlation
delta.c - unit impulse
dot.c - dot product
I0.c - modified Bessel function
u.c - unit step

Return to C and MATLAB Functions . Return to menu .

MATLAB Function Listings

cas.m - cascade realization
cas2can.m - cascade to canonical
cdelay2.m - delay (circular buffer)
cfir2.m - FIR filter in direct form (circular buffer)
delay.m - delay (linear buffer)
fir.m - FIR filter in direct form (linear buffer)
sos.m - second order section
wrap2.m - circular delay-line wrapping

dtft.m - DTFT computation

dbp.m - ideal bandpass filter impulse response
ddiff.m - ideal differentiator impulse response
dhilb.m - ideal Hilbert transformer impulse response
dlh.m - ideal lowpass/highpass filter impulse response
I0.m - Modified Bessel function
kbp.m - Kaiser bandpass design
kdiff.m - Kaiser differentiator design
khilb.m - Kaiser Hilbert transformer design
klh.m - Kaiser lowpass/highpass design
kparm2.m - Kaiser window parameters for spectral analysis
kparm.m - Kaiser window parameters for filter design
kwind.m - Kaiser window

bpcheb2.m - bandpass Chebyshev type 2 design
bpsbutt.m - bandpass/bandstop Butterworth design
bscheb2.m - bandstop Chebyshev type 2 design
lhbutt.m - lowpass/highpass Butterworth design
lhcheb1.m - lowpass/highpass Chebyshev type 1 design
lhcheb2.m - lowpass/highpass Chebyshev type 2 design

combeq.m - parametric comb/notch equalizer design
parmeq.m - parametric equalizer design
peq.m - J. Audio Eng. Soc., vol.45, 444 (1997).

sg.m - Savitzky-Golay filter design
sgfilt.m - Savitzky-Golay filtering
sigav.m - signal averaging
ecg.m - simulated ECG waveform generator

Return to C and MATLAB Functions . Return to menu .

Errata and Feedback

Any feedback from readers is welcome - such as reporting errors, suggestions for improvement, omitted references - and may be sent to the author at orfanidi@ece.rutgers.edu. The LaTeX file errata.tex contains an updated list of known errata; the file errsol.tex contains the errata in the Solutions Manual (ISBN 0-13-230293-4). PDF versions of the errata files are also available: errata.pdf, errsol.pdf.

Return to menu .

Publication Data

Published in August 1995.

College Division
Prentice Hall, Upper Saddle River, NJ 07458
ISBN: 0-13-209172-0

Return to menu .

Typesetting Notes

The book was typeset by the author using emtex386, LaTeX2.09, nfss2, psnfss, and Y&Y's Lucida Bright postscript font family, including Lucida New Math, Euler, and some CM math fonts. The dvi file was converted to postscript by Y&Y's dvipsone and printed by Prentice Hall at 1200 dpi.

The dvi previewers were Y&Y's dviwindo and emtex's dvidrv. Several LaTeX style files from the CTAN collection were used: equation.sty, jeep.sty, aip.sty, psfig.sty, alltt.sty, amslatex.sty. The table.tex macros from PCTeX and the ps2pk conversion utility were also used.

The data graphs were plotted by the Scientific Endeavors GraphiC package, exported to EPS postscript format, and inserted into the dvi file by psfig.sty. The illustrations were prepared by the author using CorelDraw and exported to EPS; they were also inserted with psfig.

Return to menu .

About the Cover

The book cover was initially designed by the author using CorelDraw and finally redesigned by Prentice-Hall. The block diagram on the cover represents Schroeder's digital reverberator; see Section 8.2.3.

Return to menu .

About the Author

Sophocles J. Orfanidis is an Associate Professor of Electrical and Computer Engineering at Rutgers University. He has been teaching undergraduate and graduate DSP courses at Rutgers since 1978. He received the Rutgers College Parents Association Outstanding Teacher of the Year Award in 1990 and 1996. He is also the author of the graduate DSP text Optimum Signal Processing, 2nd edition, McGraw Hill, New York, 1988. He may be contacted at:

e-mail: orfanidi@ece.rutgers.edu, or, orfanidi@rci.rutgers.edu

Sophocles J. Orfanidis
Department of Electrical and Computer Engineering
Rutgers University
P. O. Box 909
Piscataway, NJ 08855-0909

Return to menu .