Steven W. Smith
`
`Physics
`
`Earth Science
`
`The Scientist and Engineer’s Guide to
`Digital Signal Processing
`
`sakeanalasutere Page 1 of 38
`
`Medicine
`
`GOOGLEEXHIBIT 1010
`
`Page 1 of 38
`
`GOOGLE EXHIBIT 1010
`
`

`

`The Scientist and Engineer’s Guide to
`Digital Signal Processing
`
`Page 2 of 38
`
`Page 2 of 38
`
`

`

`v v v v v v v
`
`Be sure to visit our web site:
`
`www.DSPguide.com
`
`Jf
`
`free DSP software- easy to use
`homework and computer exercises
`references and suggested reading
`information about the author
`contacting the author or publisher
`links to other DSP sites
`suggestions and corrections
`ordering information
`
`Pictures on the cover
`
`Physics
`A rare and spectacular collision is seen in the Cartwheel galaxy, located 500 million light-years away
`in the constellation Sculptor. Thestriking ring-like feature was formed when a smaller intruder
`galaxy careened throughthe core of the host galaxy about 200 million years ago, sending gas and
`dust into space at 200,000 miles per hour. The intruder is not known, but is thought to be one of
`the two galaxies at the right of the image. This picture was taken with the Hubble Space Telescope
`on October 16, 1994.
`
`Earth Science ©
`Water surface height measurementof the Pacific Ocean, acquired with microwave imaging from
`the TOPEX/Poseidonsatellite on August 21, 1997. The oblong mass near the equatoris the
`weather-disrupting phenomenon known as El Nino. Green represents the normal sea level; white
`indicates that the sea surface is greater than 18 cm (7 inches) higher than normal; purple indicates
`it is more than 18 cm below normal. The excess water contained in this El Ninois about 30 times
`the volume of all the U.S. great lakes combined.
`
`Medicine
`Magnetic Resonance Image (MRI) ofa living human’s head, using pseudo color to delineate the
`brain from othersoft tissue and bone. MRI has revolutionized medical diagnosis with its ability
`to visualize the body’s internal anatomy. Digital Signal Processing has been at the forefront of
`MRIand other medical imaging techniques.
`
`Engineering
`Cut away view of a turbine engine, such as used on commercial and military aircraft. Air enters
`the engine on theleft and is compressed by a multistage turbine.
`In the center, fuel is injected
`into the air flow and ignited. The hot expanding gases exit the engine toward theright, passing
`through another turbine that extracts power from the high-velocity gas flow. Large turbine engines
`can generate more than 100,000 poundsofthrust.
`
`Page 3 of 38
`
`Page 3 of 38
`
`

`

`The Scientist and Engineer’s Guide to
`Digital Signal Processing
`
`by
`Steven W. Smith
`
`California Technical Publishing
`San Diego, California
`
`rrr
`Page 4 of 38
`
`Page 4 of 38
`
`

`

`The Scientist and Engineer’s Guide to
`Digital Signal Processing
`
`by
`Steven W. Smith
`
`copyright © 1997 by California Technical Publishing
`All rights reserved. Noportion of this book may be reproduced or
`transmitted in any form or by any means, electronic or mechanical,
`without written permission of the publisher.
`
`ISBN 0-9660176-3-3
`LCCN 97-80293
`
`California Technical Publishing
`P.O. Box 502407
`San Diego, CA 92150-2407
`
`To contact the author or publisher through the internet:
`website: DSPguide.com
`e-mail:
`Smith@DSPguide.com
`
`Printed in the United States of America
`First Edition
`First printing 1997
`
`Important Legal Information: Warning and Disclaimer
`This book presents the fundamentals of Digital Signal Processing using examples from common science
`and engineering problems. While the author believes that the concepts and data contained in this book
`are accurate and correct, they should not be used in any application without proper verification by the
`person making the application. Extensive and detailed testing is essential where incorrect functioning
`could result in personal injury or damage to property. The material in this book is intended solely as a
`teaching aid, and is not represented to be an appropriate or safe solution to any particular problem. For
`this reason, the author and publisher make no warranties, express or implied, that the concepts, examples,
`data, algorithms, techniques, or programs contained in this book are free from error, conform to any
`industry standard, or are suitable for any application. The author and publisher disclaim all liability and
`responsibility to any person or entity with respect to any loss or damage caused, or alleged to be caused,
`directly or indirectly, by the information contained in this book.
`If you do not wish to be bound by the
`
`above, you may return this book to the publisher for a full refund.
`
`Page 5 of 38
`
`Page 5 of 38
`
`

`

`Contents at a Glance
`
`FOUNDATIONS
`
`The Breadth and Depth of DSP ............. 1
`Chapter 1.
`Statistics, Probability and Noise ............. 11
`Chapter 2.
`Chapter 3. ADCand DAC ...................0... ,. 35
`Chapter 4. DSP Software ........ 0.0.0.0... 00000 67
`
`FUNDAMENTALS
`
`Linear Systems ................0.0..00005 87
`Chapter 5.
`Chapter 6. Convolution .............. 000.0020 ee eee 107
`Chapter 7.
`Properties of Convolution .................. 123
`Chapter 8.
`The Discrete Fourier Transform ............. 141
`Chapter 9. Applications of the DFT................... 169
`Chapter 10. Fourier Transform Properties ............... 185
`Chapter 11. Fourier Transform Pairs ................... 209
`Chapter 12. The Fast Fourier Transform ................ 225
`Chapter 13. Continuous Signal Processing ............... 243
`
`DIGITAL FILTERS
`
`Introduction to Digital Filters............... 261
`' Chapter 14.
`Chapter 15.. Moving Average Filters ................... 277
`Chapter 16. Windowed-Sinc Filters ................004. 285
`Chapter 17. Custom Filters ............... ce eee ee 297
`Chapter 18. FFT Convolution .................--22--0. 311
`Chapter 19. Recursive Filters .................-.00--00- 319
`Chapter 20. Chebyshev Filters .................002-00- 333
`Chapter 21. Filter Comparison ................-...0., 343
`
`APPLICATIONS
`
`Chapter 22. Audio Processing ......... 0.0.0 0c eee eeee 351
`Chapter 23.
`Image Formation and Display ............... 373
`Chapter 24. Linear Image Processing ................-. 397
`Chapter 25. Special Imaging Techniques ................ 423
`Chapter 26. Neural Networks (and more!) ............... 451
`Chapter 27. Data Compression ................00000-5 481
`
`COMPLEX TECHNIQUES
`Chapter 28. Complex Numbers ...................005- 503
`Chapter 29. The Complex Fourier Transform ............. 519
`Chapter 30. The Laplace Transform ................... 533
`Chapter 31. The z-Transform ................-..2--0- 557
`
`Study Guide... 00. eee ee ee 583
`Glossary 2.6... ee et ee eee 607
`Index 2... eee eee eee 619
`
`Page 6 of 38
`
`Page 6 of 38
`
`

`

`Table of Contents
`
`FOUNDATIONS
`
`Chapter 1. The Breadth and Depth of DSP .......... 1
`The Roots of DSP
`1
`Telecommunications
`Audio Processing 5
`Echo Location 7
`Imaging Processing 9
`
`4
`
`Chapter 2. Statistics, Probability and Noise ......... 11
`Signal and Graph Terminology 11
`Meanand Standard Deviation
`13
`Signal vs. Underlying Process
`17
`The Histogram, Pmf and Pdf
`19
`The Normal Distribution 26
`Digital Noise Generation 29
`Precision and Accuracy 32
`
`Chapter 3. ADC and DAC ...................... 35
`Quantization 35
`The Sampling Theorem 39
`Digital-to-Analog Conversion 44
`Analog Filters for Data Conversion 48
`Selecting the Antialias Filter
`55
`Multirate Data Conversion 58
`Single Bit Data Conversion 60
`
`70
`
`Chapter 4. DSP Software ...................000. 67
`Computer Numbers
`67
`68
`Fixed Point (Integers)
`Floating Point (Real Numbers)
`Number Precision 72
`Execution Speed: Program Language
`Execution Speed: Hardware
`80
`Execution Speed: Programming Tips
`
`76
`
`84
`
`
`Page 7 of 38
`
`vi
`
`Page 7 of 38
`
`

`

`FUNDAMENTALS
`
`Chapter 5. Linear Systems ..........----- eee ees 87
`Signals and Systems
`87
`Requirements for Linearity 89
`Static Linearity and Sinusoidal Fidelity 92
`Examples of Linear and Nonlinear Systems
`Special Properties of Linearity 96
`Superposition: the Foundation of DSP 98
`CommonDecompositions
`100
`Alternatives to Linearity 104
`
`94
`
`Chapter 6. Convolution ..........6- +++ eee eeeees 107
`The Delta Function and Impulse Response
`107
`Convolution
`108
`The Input Side Algorithm 112
`The Output Side Algorithm 116
`The Sum of Weighted Inputs
`122
`
`Chapter 7. Properties of Convolution..............
`Common Impulse Responses
`123
`Mathematical Properties
`132
`Correlation 136
`Speed 140
`
`123
`
`141
`
`Chapter 8. The Discrete Fourier Transform ....... ..
`The Family of Fourier Transforms
`141
`Notation and Format of the real DFT 146
`The Frequency Domain’s Independent Variable
`DFTBasis Functions
`150
`Synthesis, Calculating the Inverse DFT 152
`Analysis, Calculating the DFT 156
`Duality
`160
`Polar Notation 160
`Polar Nuisances
`163
`
`148
`
`Chapter 9. Applications of the DFT ...........---- 169
`Spectral Analysis of Signals
`169
`176
`Frequency Response of Systems
`Convolution via the Frequency Domain
`
`179
`
`Chapter 10. Fourier Transform Properties ........-. 185
`Linearity of the Fourier Transform 185
`Characteristics of the Phase
`188
`
`vii
`
`Page 8 of 38
`
`Page 8 of 38
`
`

`

`Periodic Nature of the DFT 194
`Compression and Expansion, Multirate methods
`Multiplying Signals (Amplitude Modulation)
`204
`The Discrete Time Fourier Transform 206
`Parseval’s Relation 208
`
`200
`
`Chapter 11. Fourier Transform Pairs .............. 209
`Delta Function Pairs
`209
`The Sinc Function 212
`Other Transform Pairs
`Gibbs Effect
`218
`Harmonics 220
`Chirp Signals
`222
`
`215
`
`Chapter 12. The Fast Fourier Transform ........... 225
`Real DFT Using the Complex DFT 225
`How the FFT Works
`228
`FFT Programs
`233
`Speed and Precision Comparisons
`Further Speed Increases
`238
`
`237
`
`Chapter 13. Continuous Signal Processing .......... 243
`The Delta Function 243
`Convolution 246
`The Fourier Transform 252
`The Fourier Series
`255
`
`DIGITAL FILTERS
`
`Introduction to Digital Filters .......... 261
`Chapter 14.
`Filter Basics
`261
`How Information is Represented in Signals
`Time Domain Parameters
`266
`268
`Frequency Domain Parameters
`High-Pass, Band-Pass and Band-Reject Filters
`Filter Classification 274
`
`271
`
`265
`
`Chapter 15. Moving Average Filters ............... 277
`Implementation by Convolution 277
`Noise Reduction vs. Step Response
`Frequency Response
`280
`Relatives of the Moving Average Filter
`Recursive Implementation 282
`
`280
`
`278
`
`vill
`
`Page 9 of 38
`
`Page 9 of 38
`
`

`

`Chapter 16. Windowed-Sinc Filters ............... 285
`Strategy of the Windowed-Sinc
`285
`Designing the Filter
`288
`Examples of Windowed-Sinc Filters
`Pushing it to the Limit
`293
`
`292
`
`Chapter 17. Custom Filters ..................... 297
`Arbitrary Frequency Response
`297
`Deconvolution 300
`Optimal Filters
`307
`
`Chapter 18. FFT Convolution ................... 311
`The Overlap-Add Method 311
`FFT Convolution 312
`Speed Improvements
`
`316
`
`Chapter 19. Recursive Filters ................... 319
`The Recursive Method 319
`Single Pole Recursive Filters
`Narrow-bandFilters 326
`Phase Response
`328
`Using Integers
`332
`
`322
`
`Chapter 20. Chebyshev Filters ................... 333
`The Chebyshev and Butterworth Responses
`333
`Designing the Filter
`334
`Step Response Overshoot
`Stability 339
`
`338
`
`Chapter 21. Filter Comparison .................. 343
`Match #1: Analog vs. Digital Filters
`343
`Match #2: Windowed-Sinc vs. Chebyshev
`Match #3: Moving Average vs. Single Pole
`
`346
`348
`
`APPLICATIONS
`
`Chapter 22. Audio Processing ................... 351
`Human Hearing 351
`Timbre
`355
`Sound Quality vs. Data Rate
`High Fidelity Audio
`359
`Companding 362
`
`358
`
`
`
`Page 10 of 38
`
`Page 10 of 38
`
`

`

`Speech Synthesis and Recognition 364
`Nonlinear Audio Processing 368
`
`Image Formation and Display .........- 373
`Chapter 23.
`Digital Image Structure
`373
`Cameras and Eyes
`376
`384
`Television Video Signals
`Other Image Acquisition and Display 386
`Brightness and Contrast Adjustments
`387
`Grayscale Transforms
`390
`Warping 394
`
`Chapter 24. Linear Image Processing .............. 397
`Convolution 397
`3x3 Edge Modification 402
`Convolution by Separability 404
`Example of a Large PSF: Illumination Flattening 407
`Fourier Image Analysis
`410
`FFT Convolution 416
`A Closer Look at Image Convolution 418
`
`Chapter 25. Special Imaging Techniques ............ 423
`Spatial Resolution 423
`Sample Spacing and Sampling Aperture
`Signal-to-Noise Ratio 432
`Morphological Image Processing 436
`Computed Tomography 442
`
`430
`
`Chapter 26. Neural Networks (and more!) .......... 451
`Target Detection 451
`Neural Network Architecture
`Why Does it Work?
`463
`Training the Neural Network 465
`Evaluating the Results
`473
`Recursive Filter Design 476
`
`458
`
`Chapter 27. Data Compression .........--..-5++5- 481
`Data Compression Strategies
`481
`Run-Length Encoding 483
`Huffman Encoding 484
`Delta Encoding 486
`LZW Compression 488
`JPEG (Transform Compression)
`MPEG 501
`
`494
`
`Page 11 of 38
`
`Page 11 of 38
`
`

`

`COMPLEX TECHNIQUES
`
`Chapter 28. Complex Numbers .....-.-----++-+-: 503
`The Complex Number System 503
`Polar Notation 507
`Using Complex Numbersby Substitution 509
`Complex Representation of Sinusoids
`511
`Complex Representation of Systems
`513
`Electrical Circuit Analysis
`515
`
`Chapter 29. The Complex Fourier Transform........ 519
`The Real DFT 517
`Mathematical Equivalence
`The Complex DFT 523
`528
`The Family of Fourier Transforms
`Why the Complex Fourier Transform is Used 532
`
`521
`
`Chapter 30. The Laplace Transform .......-..---- 533
`The Nature of the s-Domain 533
`Strategy of the Laplace Transform 540
`Analysis of Electric Circuits
`544
`The Importance of Poles and Zeros
`Filter Design in the s-Domain 552
`
`549
`
`Chapter 31. The z-Transform ......--------++++> 557
`The Nature of the z-Domain 557
`Analysis of Recursive Systems
`562
`Cascade and Parallel Stages
`568
`Spectral Inversion 571
`Gain Changes
`573
`Chebyshev-Butterworth Filter Design 575
`The Best and Worst of DSP 582
`
`Study Guide... 0.60.6... eee eee tee 583
`
`Glossary ..... 0-0 cee eee eet tees 607
`
`Index oo.ee eee eee eee 619
`
`
`
`Visit our website at www.DSPguide.com for free software, homework problems,
`
`suggested reading, biography of the author, and other up-to-date DSP information.
`
`
`
`xi
`
`Page 12 of 38
`
`Page 12 of 38
`
`

`

`Preface
`
`How this book is different
`
`In only 15 years, the power of
`The technical world is changing very rapidly.
`personal computers has increased by a factor of nearly one-thousand.
`Byall
`accounts, it will increase by another factor of one-thousand in the next 15 years.
`This tremendous powerhas changed the way science and engineering is done,
`and there is no better example of this than Digital Signal Processing.
`
`In the early 1980s, DSP was taught as a graduate level course in electrical
`engineering. A decade later, DSP had becomea standardpart of the
`undergraduate curriculum. Today, DSPis a basic skill neededby scientists and
`engineers in many fields. Unfortunately, DSP education has been slow to
`adapt to this change. Nearly all DSP textbooks arestill written in the
`traditional electrical engineering style of detailed and rigorous mathematics.
`DSPis incredibly powerful, but if you can’t understandit, you can’t use it!
`
`This book was written for scientists and engineers in a wide variety of fields:
`physics, bioengineering, geology, oceanography, mechanical andelectrical
`engineering, to name just a few. The goal is to present practical techniques
`while avoiding the barriers of detailed mathematics and abstract theory. To
`achieve this goal, three strategies were employed in writing this book:
`
`First, the techniques are explained, not simply proven to be true through
`mathematical derivations. While much of the mathematics is included, it is not
`used as the primary meansof conveying the information. Nothing beats a few
`_ well written paragraphs supported by goodillustrations!
`
`Second, complex numbers are treated as an advanced topic, something to be
`learned after the fundamental principles are understood. Chapters 1-27 explain
`all the basic techniques using only algebra, and in rare cases, a small amount
`of elementary calculus. Chapters 28-31 show how complex math extends the
`power of DSP, presenting techniques that cannot be implemented with real
`numbers alone. Many would view this approach as heresy! Traditional DSP
`textbooks are full of complex math, often starting right from thefirst chapter.
`
`|
`
`xi
`
`SSSSSS
`Page 13 of 38
`
`Page 13 of 38
`
`

`

`Third, very simple computer programs are used. Most DSP programsare written
`in C, Fortran, or a similar language. However, learning DSP has different
`requirements than using DSP. Thestudent needs to concentrate on the
`algorithms and techniques, without being distracted by the quirks of a particular
`language. Power andflexibility aren’t important; simplicity is critical. The
`programsin this book are written to teach DSP in the most straightforward way,
`with all other factors being treated as secondary. Good programmingstyle is
`disregarded if it makes the program logic more clear. For instance:
`
`= a simplified version of BASIC is used
`= line numbers are included
`=
`the only control structure used is the FOR-NEXT loop
`=
`there are no J/O statements
`
`This is the simplest programmingstyle I could find. Some may think that this
`book would be betterif the programs had been written in C.
`I couldn’t disagree
`more.
`
`The Intended Audience
`
`This book is primarily intended for a one year course in practical DSP, with the
`students being drawn from a wide variety of science and engineering fields. The
`suggested prerequisites are:
`
`= A course in practical electronics: (op amps, RC circuits, etc.)
`s A course in computer programming (Fortran or similar)
`=» Oneyear of calculus
`
`This book was also written with the practicing professional in mind. Many
`everyday DSP applications are discussed: digital filters, neural networks, data
`compression, audio and image processing, etc. As much as possible, these
`chaptersstand on their own, not requiring the reader to review the entire book
`to solve a specific problem.
`
`Be sure to visit our Website!
`
`Anything you see in a bookwill be at least two years out-of-date, and usually
`much more. For this reason, we have placed much of the supplementary
`material you would expect in a textbook on our website. This includes:
`homework problems, computer exercises, references, suggested reading,
`information about the author, etc. We have also included free computer
`programs and links to other DSP sites. Visit this site often for up-to-date
`information about Digital Signal Processing.
`
`Xili
`
`[Milne
`Page 14 of 38
`
`Page 14 of 38
`
`

`

`Acknowledgements
`
`
`
`A special thanks to the many reviewers who provided comments and suggestions
`on this book. Their generous donation of time andskill has madethis a better
`work: Magnus Aronsson (Department of Electrical Engineering, University of
`Utah); Vernon L. Chi (Department of Computer Science, University of North
`Carolina); Manohar Das, Ph.D. (Department of Electrical and Systems
`Engineering, Oakland University); Fred DePiero, Ph.D. (Department of
`Electrical Engineering, CalPoly State University); Kenneth H. Jacker,
`(Department of Computer Science, Appalachian State University); Rajiv
`Kapadia, Ph.D. (Department of Electrical Engineering, Mankato State
`University); A. Dale Magoun, Ph.D. (Department of Computer Science,
`Northeast Louisiana University); Bernard J. Maxum, Ph.D. (Department of
`Electrical Engineering, Lamar University); Paul Morgan, Ph.D. (Department
`of Geology, Northern Arizona University); Dale H. Mugler, Ph.D. (Department
`of Mathematical Science, University of Akron); Christopher L. Mullen, Ph.D.
`(Department of Civil Engineering, University of Mississippi); Cynthia L.
`Nelson, Ph.D. (Sandia National Laboratories); Branislava Perunicic-
`Drazenovic, Ph.D. (Departmentof Electrical Engineering, Lamar University);
`John Schmeelk, Ph.D. (Department of Mathematical Science, Virginia
`Commonwealth University); Richard R. Schultz, Ph.D. (Department of
`Electrical Engineering, University of North Dakota);
`Jay L. Smith, Ph.D.
`(Center for Aerospace Technology, Weber State University); Jeffrey Smith,
`Ph.D. (Department of Computer Science, University of Georgia); Oscar Yanez
`Suarez, Ph.D. (Department of Electrical Engineering, Metropolitan University,
`Iztapalapa campus, Mexico City), and other reviewers who wish to remain
`anonymous.
`
`This book is now in the hands of the final reviewer, you. Please take the time
`to give me your commentsand suggestions. This will allow future reprints and
`editions to serve your needs even better. All it takes is a two minute e-mail
`message to: Smith@DSPguide.com. Thanks; I hope you enjoy the book.
`
`Steve Smith .
`October 1997
`
`xiv
`
`Page 15 of 38
`
`Page 15 of 38
`
`

`

`CHAPTER
`
`15
`
`Moving Average Filters
`
`The moving average is the most common filter in DSP, mainly because it is the easiest digital
`filter to understand and use. In spite of its simplicity, the moving average filter is optimal for
`a common task: reducing random noise while retaining a sharp step response. This makes it the
`premier filter for time domain encoded signals. However, the moving average is the worst filter
`for frequency domain encoded signals, with little ability to separate one band of frequencies from
`another. Relatives of the moving average filter include the Gaussian, Blackman, and multiple-
`pass moving average. These have slightly better performance in the frequency domain, at the
`expense of increased computation time.
`
`Implementation by Convolution
`
`As the name implies, the moving average filter operates by averaging a number
`of points from the input signal to produce each point in the output signal. In
`equation form, this is written:
`
`x [ i
`
`j ]
`
`M 1
`
`j 0
`
`1 M
`
`y [i ]
`
`EQUATION 15-1
`Equation of the moving average filter. In
`this equation,
` is the input signal,
`is
`x[ ]
`y[ ]
`the output signal, and M is the number of
`points used in the moving average. This
`equation only uses points on one side of the
`output sample being calculated.
`
` is the output signal, and M is the number
` is the input signal,
`Where
`y [ ]
`x [ ]
`of points in the average. For example, in a 5 point moving average filter, point
`80 in the output signal is given by:
`
`y [80]
`
`x [80]
`
`x [81]
`
`x [82]
`5
`
`x [83]
`
`x [84]
`
`277
`
`Page 16 of 38
`
`

`

`278
`
`The Scientist and Engineer's Guide to Digital Signal Processing
`
`As an alternative, the group of points from the input signal can be chosen
`symmetrically around the output point:
`
`y [80]
`
`x [78]
`
`x [79]
`
`x [81]
`
`x [82]
`
`x [80]
`5
`
`,
`This corresponds to changing the summation in Eq. 15-1 from:
`0 to M 1
`j
`to:
`. For instance, in a 10 point moving average
`j
`(M 1) /2 to (M 1) /2
`filter, the index, j, can run from 0 to 11 (one side averaging) or -5 to 5
`(symmetrical averaging). Symmetrical averaging requires that M be an odd
`number. Programming is slightly easier with the points on only one side;
`however, this produces a relative shift between the input and output signals.
`
`You should recognize that the moving average filter is a convolution using a
`very simple filter kernel. For example, a 5 point filter has the filter kernel:
` . That is, the moving average filter is a
`0, 0, 1/5, 1/5, 1/5, 1/5, 1/5, 0, 0
`convolution of the input signal with a rectangular pulse having an area of one.
`Table 15-1 shows a program to implement the moving average filter.
`
`'X[ ] holds the input signal
`'Y[ ] holds the output signal
`
`'Mythical subroutine to load X[ ]
`
`'Loop for each point in the output signal
`'Zero, so it can be used as an accumulator
`'Calculate the summation
`
`'Complete the average by dividing
`
`100 'MOVING AVERAGE FILTER
`110 'This program filters 5000 samples with a 101 point moving
`120 'average filter, resulting in 4900 samples of filtered data.
`130 '
`140 DIM X[4999]
`150 DIM Y[4999]
`160 '
`170 GOSUB XXXX
`180 '
`190 FOR I% = 50 TO 4949
`200 Y[I%] = 0
`210 FOR J% = -50 TO 50
`220 Y[I%] = Y[I%] + X(I%+J%]
`230 NEXT J%
`240 Y[I%] = Y[I%]/101
`250 NEXT I%
`260 '
`270 END
`
`TABLE 15-1
`
`Noise Reduction vs. Step Response
`
`Many scientists and engineers feel guilty about using the moving average filter.
`Because it is so very simple, the moving average filter is often the first thing
`tried when faced with a problem. Even if the problem is completely solved,
`there is still the feeling that something more should be done. This situation is
`truly ironic. Not only is the moving average filter very good for many
`applications, it is optimal for a common problem, reducing random white noise
`while keeping the sharpest step response.
`
`Page 17 of 38
`
`

`

`Chapter 15- Moving Average Filters
`
`279
`
`b. 11 point moving average
`
`100
`
`200
`300
`Sample number
`
`400
`
`500
`
`c. 51 point moving average
`
`100
`
`200
`300
`Sample number
`
`400
`
`500
`
`2
`
`1
`
`0
`
`Amplitude
`
`-1
`
`0
`
`2
`
`1
`
`0
`
`Amplitude
`
`-1
`
`0
`
`a. Original signal
`
`100
`
`200
`300
`Sample number
`
`400
`
`500
`
`2
`
`1
`
`0
`
`Amplitude
`
`-1
`
`0
`
`FIGURE 15-1
`Example of a moving average filter. In (a), a
`rectangular pulse is buried in random noise. In
`(b) and (c), this signal is filtered with 11 and 51
`point moving average filters, respectively. As
`the number of points in the filter increases, the
`noise becomes lower; however, the edges
`becoming less sharp. The moving average filter
`is the optimal solution for this problem,
`providing the lowest noise possible for a given
`edge sharpness.
`
`Figure 15-1 shows an example of how this works. The signal in (a) is a pulse
`buried in random noise. In (b) and (c), the smoothing action of the moving
`average filter decreases the amplitude of the random noise (good), but also
`reduces the sharpness of the edges (bad). Of all the possible linear filters that
`could be used, the moving average produces the lowest noise for a given edge
`sharpness. The amount of noise reduction is equal to the square-root of the
`number of points in the average. For example, a 100 point moving average
`filter reduces the noise by a factor of 10.
`
`To understand why the moving average if the best solution, imagine we want
`to design a filter with a fixed edge sharpness. For example, let's assume we fix
`the edge sharpness by specifying that there are eleven points in the rise of the
`step response. This requires that the filter kernel have eleven points. The
`optimization question is: how do we choose the eleven values in the filter
`kernel to minimize the noise on the output signal? Since the noise we are
`trying to reduce is random, none of the input points is special; each is just as
`noisy as its neighbor. Therefore, it is useless to give preferential treatment to
`any one of the input points by assigning it a larger coefficient in the filter
`kernel. The lowest noise is obtained when all the input samples are treated
`equally, i.e., the moving average filter. (Later in this chapter we show that
`other filters are essentially as good. The point is, no filter is better than the
`simple moving average).
`
`Page 18 of 38
`
`

`

`280
`
`The Scientist and Engineer's Guide to Digital Signal Processing
`
`Frequency Response
`
`Figure 15-2 shows the frequency response of the moving average filter. It is
`mathematically described by the Fourier transform of the rectangular pulse, as
`discussed in Chapter 11:
`
`EQUATION 15-2
`Frequency response of an M point moving
`average filter. The frequency, f, runs between
`0 and 0.5. For
`, use:
`0
`H [ f ]
`1
`f
`
`H [ f ]
`
`f M )
`sin(
`M sin(
`f )
`
`The roll-off is very slow and the stopband attenuation is ghastly. Clearly, the
`moving average filter cannot separate one band of frequencies from another.
`Remember, good performance in the time domain results in poor performance
`in the frequency domain, and vice versa. In short, the moving average is an
`exceptionally good smoothing filter (the action in the time domain), but an
`exceptionally bad low-pass filter (the action in the frequency domain).
`
`3 point
`
`11 point
`
`31 point
`
`1.2
`
`1.0
`
`0.8
`
`0.6
`
`0.4
`
`0.2
`
`0.0
`
`Amplitude
`
`0
`
`0.1
`
`0.2
`0.3
`Frequency
`
`0.4
`
`0.5
`
`FIGURE 15-2
`Frequency response of the moving average
`filter. The moving average is a very poor
`low-pass filter, due to its slow roll-off and
`poor stopband attenuation. These curves are
`generated by Eq. 15-2.
`
`Relatives of the Moving Average Filter
`
`In a perfect world, filter designers would only have to deal with time
`domain or frequency domain encoded information, but never a mixture of
`the two in the same signal. Unfortunately, there are some applications
`where both domains are simultaneously important. For instance, television
`signals fall into this nasty category. Video information is encoded in the
`time domain, that is, the shape of the waveform corresponds to the patterns
`of brightness in the image. However, during transmission the video signal
`is treated according to its frequency composition, such as its total
`bandwidth, how the carrier waves for sound & color are added, elimination
`& restoration of the DC component, etc. As another example, electro-
`magnetic interference is best understood in the frequency domain, even if
`
`Page 19 of 38
`
`

`

`Chapter 15- Moving Average Filters
`
`281
`
`c. Frequency response
`
`1 pass
`
`2 pass
`
`4 pass
`
`1.25
`
`1.00
`
`0.75
`
`0.50
`
`0.25
`
`0.00
`
`Amplitude
`
`FFT
`
`4 pass
`
`a. Filter kernel
`
`2 pass
`
`1 pass
`
`6
`
`12
`Sample number
`
`18
`
`24
`
`0
`
`0.1
`
`0.2
`0.3
`Frequency
`
`0.4
`
`0.5
`
`Integrate
`
`20 Log( )
`
`d. Frequency response (dB)
`
`1 pass
`
`2 pass
`
`4 pass
`
`40
`
`20
`
`0
`
`-20
`
`-40
`
`-60
`
`-80
`
`-100
`
`-120
`
`Amplitude (dB)
`
`b. Step response
`
`1 pass
`
`4 pass
`
`2 pass
`
`0.2
`
`0.1
`
`Amplitude
`
`0.0
`
`0
`
`1.2
`
`1.0
`
`0.8
`
`0.6
`
`0.4
`
`0.2
`
`0.0
`
`Amplitude
`
`0
`
`6
`
`12
`Sample number
`
`18
`
`24
`
`0
`
`0.1
`
`0.2
`0.3
`Frequency
`
`0.4
`
`0.5
`
`FIGURE 15-3
`Characteristics of multiple-pass moving average filters. Figure (a) shows the filter kernels resulting from
`passing a seven point moving average filter over the data once, twice and four times. Figure (b) shows the
`corresponding step responses, while (c) and (d) show the corresponding frequency responses.
`
`the signal's information is encoded in the time domain. For instance, the
`temperature monitor in a scientific experiment might be contaminated with 60
`hertz from the power lines, 30 kHz from a switching power supply, or 1320
`kHz from a local AM radio station. Relatives of the moving average filter
`have better frequency domain performance, and can be useful in these mixed
`domain applications.
`
`Multiple-pass moving average filters involve passing the input signal
`through a moving average filter two or more times. Figure 15-3a shows the
`overall filter kernel resulting from one, two and four passes. Two passes are
`equivalent to using a triangular filter kernel (a rectangular filter kernel
`convolved with itself). After four or more passes, the equivalent filter kernel
`looks like a Gaussian (recall the Central Limit Theorem). As shown in (b),
`multiple passes produce an "s" shaped step response, as compared to the
`straight line of the single pass. The frequency responses in (c) and (d) are
`given by Eq. 15-2 multiplied by itself for each pass. That is, each time domain
`convolution results in a multiplication of the frequency spectra.
`
`Page 20 of 38
`
`

`

`282
`
`The Scientist and Engineer's Guide to Digital Signal Processing
`
`Figure 15-4 shows the frequency response of two other relatives of the moving
`average filter. When a pure Gaussian is used as a filter kernel, the frequency
`response is also a Gaussian, as discussed in Chapter 11. The Gaussian is
`important because it is the impulse response of many natural and manmade
`systems. For example, a brief pulse of light entering a long fiber optic
`transmission line will exit as a Gaussian pulse, due to the different paths taken
`by the photons within the fiber. The Gaussian filter kernel is also used
`extensively in image processing because it has unique properties that allow
`fast two-dimensional convolutions (see Chapter 24). The second frequency
`response in Fig. 15-4 corresponds to using a Blackman window as a filter
`kernel. (The term window has no meaning here; it is simply part of the
`accepted name of this curve). The exact shape of the Blackman window is
`given in Chapter 16 (Eq. 16-2, Fig. 16-2); however, it looks much like a
`Gaussian.
`
`How are these relatives of the moving average filter better than the moving
`average filter itself? Three ways: First, and most important, these filters have
`better stopband attenuation than the moving average filter. Second, the filter
`kernels taper to a smaller amplitude near the ends. Recall that each point in
`the output signal is a weighted sum of a group of samples from the input. If the
`filter kernel tapers, samples in the input signal that are farther away are given
`less weight than those close by. Third, the step responses are smooth curves,
`rather than the abrupt straight line of the moving average. These last two are
`usually of limited benefit, although you might find applications where they are
`genuine advantages.
`
`The moving average filter and its relatives are all about the same at reducing
`random noise while maintaining a sharp step response. The ambiguity lies in
`how the risetime of the step response is