Declaration of Rachel J. Watters on Authentication of Publication
`
`1, Rachel J. Watters, am a librarian, and the Head of Resource Sharing for the
`
`General Library System, Memorial Library, located at 728 State Street, Madison,
`
`Wisconsin, 53706. Part of my job responsibilities include oversight of Wisconsin
`
`TechSearch (“WTS”), an interlibrary loan departmentat the University of Wisconsin-
`
`Madison.
`
`I have workedasa librarian at the University of Wisconsin library system
`
`since 1998, starting as a graduate student employee in the Kurt F. Wendt Engineering
`
`Library and WTS, then asa librarian in Interlibrary Loan at Memorial Library.
`
`I began
`
`professional employment at WTS in 2002 and became WTSDirector in 2011. In 2019,
`
`I became of Head of Resource Sharing forUW-Madison’s General Library System.
`
`|
`
`have a master’s degree in Library and Information Studies from the University of
`
`Wisconsin-Madison. Through the course of my studies and employment, I have
`
`becomewell informed about the operations of the University of Wisconsin library
`
`system, which followsstandard library practices.
`
`This Declaration relates to the dates of receipt and availability of the following:
`
`Widrow, B. and Stearns, S.D. (1985). Chapter 1: Adaptive
`Systems, p. 3-14; Chapter 2: The Adaptive Linear Combiner,p.
`15-29; and Chapter 6: The LMS Algorithm, p. 99-116. Adaptive
`Signal Processing. Englewood Cliffs, NJ: Prentice-Hall.
`
`Standard operating procedures for materials at the University of Wisconsin-
`
`Madison Libraries, When a volume wasreceived by the Library, it would be checked
`
`Page 1 of 63
`
`,
`
`Amazon v. Jawbone
`U.S. Patent 10,779,080
`Amazon Ex. 1030
`
`Page 1 of 63
`
`Amazon v. Jawbone
`U.S. Patent 10,779,080
`Amazon Ex. 1030
`
`

`

`Declaration of Rachel J. Watters on Authentication of Publication
`
`in, addedto library holdings records, and made available to readers as soon afterits
`arrival as possible, The procedure normally took a few days or at most 2 to 3 weeks.
`
`Exhibit A to this Declaration is true and accurate copy of the front matter of the
`
`Adaptive Signal Processing (1985) publication, which includes stamps onthe inside
`
`front cover and verso pages showing that this bookis the property of the K.F. Wendt
`
`Library at the University of Wisconsin-Madison.
`
`Exhibit A also includesan excerpt of pages 3 to 14 of that book, showing the
`
`chapterentitled Chapter 1: Adaptive Systems (1985); pages 15 to 29 of that book,
`
`showing the chapter entitled Chapter 2: The Adaptive Linear Combiner (1985); and
`
`pages 99 to 116 of that book, showing the chapter entitled Chapter 3: The LMS
`
`Algorithm (1985).
`
`Attached as Exhibit B is the cataloging system record of the University of
`
`Wisconsin-Madison Libraries forits copy of the Adaptive Signal Processing (1985)
`
`publication. As shownin the “Receiving date” field of this Exhibit, the University of
`
`Wisconsin-Madison Libraries owned this bookand hadit cataloged in the system as of
`
`June 6, 1999.
`
`Membersofthe interested public could locate the Adaptive Signal Processing
`
`(1985) publication after it was cataloged by searchingthe public library catalog or
`
`requesting a search through WTS. Thesearch could be donebytitle, author, and/or
`
`Page 2 of 63
`
`Page 2 of 63
`
`

`

`Declaration of Rachel J. Watters on Authentication of Publication
`
`subject key words. Membersofthe interested public could access the publication by
`
`locating it on the library’s shelves or requesting it from WTS.
`
`I declare that all statements made herein of my own knowledgeare true andthat
`
`all statements made on information andbelief are believed to be true; and further that
`
`these statements were made with the knowledgethat willful false statements and the like
`
`so made are punishable by fine or imprisonment, or both, under Section 1001 of Title 18
`
`of the United States Code.
`
`Date: May 13, 2022
`
`Memorial Library
`728 State Street
`Madison, Wisconsin 53706
`
`J. Watters
`R
`Head of Resource Sharing
`
`Page 3 of 63
`
`Page 3 of 63
`
`

`

`o
`p=
`“oO
`rant
`mad
`|a|
`<)
`G>
`
`~”
`
`>O
`
`—>p
`
`eas
`
`©|
`2)
`an)
`oP)
`rm
`Cf)
`<2)
`
`=q
`
`@ =7
`
`]|o
`
`n)
`
`= Q
`
`o Yo
`
`od
`
`>=
`
`<)
`Pa
`
`Page 4 of 63
`
`

`

`KF. WENDT LIBRARY
`UW COLLEGE OF ENGR.
`215 N. RANDALL AVENUE
`MADISON, WI. 53706
`
`Page 5 of 63
`
`K.F. WENDT LIBRARY
`UW COLLEGE OF ENGR.
`215 N. RANDALL AVENUE
`MADISON, WI 53706
`
`Page 5 of 63
`
`

`

`
`
`___ ADAPTIVE
`SIGNAL
`- PROCESSING
`
`
`
`
`
`Page 6 of 63
`
`
`
`Page 6 of 63
`
`

`

`AOESERENEern
`=<aCTuyETeCAEQ
`
`PRENTICE-HALL SIGNAL PROCESSING SERIES
`
`Alan V. Oppenheim, Editor
`
`
`
`ANDREWS AND HUNT Digital Image Restoration
`BRIGHAM The Fast Fourier Transform
`BURDIC—Underwater Acoustic System Analysis
`CASTLEMAN_Digital Image Processing
`COWAN AND GRANT Adaptive Filters
`CROCHIERE AND RABINER
` Multirate Digital Signal Processing
`DUDGEON AND MERSEREAU Multi-Dimensional Digital Signal Processing
`HAMMING_Digital Filters, 2e
`HAYKIN, ET AL.
`Array Signal Processing
`JAYANT AND NOLL Digital Coding of Waveforms
`LEA, ED.
`Trends in Speech Recognition
`Lim—Speech Enhancement
`MCCLELLAN AND RADER
`Number Theory in Digital Signal Processing
`OPPENHEIM, ED.
`Applications of Digital Signal Processing
`OPPENHEIM AND SCHAFER Digital Signal Processing
`OPPENHEIM, WILLSKY, WITH YOUNG
`Signals and Systems
`RABINER AND GOLD
`Theory and Application of Digital Signal Processing
`RABINER AND SCHAFER Digital Processing of Speech Signals
`ROBINSON AND TREITEL
`Geophysical Signal Analysis
`TRIBOLET
`Seismic Applications of Homomorphic Signal Processing
`WIDROW AND STEARNS’
`Adaptive Signal Processing
`
`
`
`Page 7 of 63
`
`Page 7 of 63
`
`

`

`ADAPTIVE
`SIGNAL
`PROCESSING
`
`Bernard Widrow
`Stanford University
`
`Samuel D. Stearns
`Sandia National Laboratories
`
`Prentice-Hall, Inc.
`Englewood Cliffs, N.J. 07632
`
`Page 8 of 63
`
`
`
`Page 8 of 63
`
`

`

` H
`
`
`
`Roaneaseleroseers
`
`intoNgant
`
`Library of Congress Cataloging in Publication Data
`Widrow, Bernard, (date)
`Adaptivesignal processing.
`(Prentice-Hall signal processingseries)
`Includes index.
`1. Adaptivesignal processing.
`Samuel D.
`II. Title.
`III. Series.
`TKS5102.5.W537
`1985
`621.38'043
`ISBN 0-13-004029-0
`
`I. Stearns,
`
`84-18057
`
`Editorial/production supervision and
`interior design: Tracey L. Orbine
`Cover design: Sue Behnke
`Manufacturing buyer: Anthony Caruso
`
`© 1985 by Prentice-Hall, Inc., EnglewoodCliffs, New Jersey 07632
`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.
`
`Printed in the United States of America
`
`109876543241
`
`ISBN O-13-004029
`
`O1
`
`Prentice-Hall International, Inc., London
`Prentice-Hall of Australia Pty. Limited, Sydney
`Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro
`Prentice-Hall Canada Inc., Toronto
`Prentice-Hall Hispanoamericana, S. A., Mexico
`Prentice-Hall of India Private Limited, New Delhi
`Prentice-Hall of Japan, Inc., Tokyo
`Prentice-Hall of Southeast Asia Pte. Ltd., Singapore
`Whitehall Books Limited, Wellington, New Zealand
`
`
`
`Page 9 of 63
`
`
`
`
`Page 9 of 63
`
`

`

`
`
`This book is dedicated to the memory of Moses Widrow, William
`K. Linvill, and Thomas J. Flanagan. It is also dedicated to the
`cause of peace on earth. We hope andtrust that its contents will be
`used to improve the lot of mankind everywhere.
`
` aaSSSSAAa
`
`Page 10 of 63
`
`Page 10 of 63
`
`

`

`Contents
`
`PREFACE
`
`LIST OF SYMBOLS
`
`part I
`
`GENERAL INTRODUCTION
`Objectives of Part |
`1
`
`1 ADAPTIVE SYSTEMS
`
`xiii
`
`XV
`
`1
`
`3
`
`Definition and Characteristics
`Areas of Application
`4
`5
`General Properties
`6
`Open- and Closed-Loop Adaptation
`Applications of Closed-Loop Adaptation
`Example of an Adaptive System
`11
`The Chapters Ahead=13
`
`9
`
`3
`
`2 THE ADAPTIVE LINEAR COMBINER
`
`15
`
`'
`
`,
`
`
`
`16
`
`15
`General Description
`Input Signal and Weight Vectors
`Desired Response and Error
`18
`The Performance Function
`19
`I Gradient and Minimum Mean-Square Error=21
`Example of a Performance Surface
`22
`
`Page 11 of 63
`
`
`
`vii
`
`Page 11 of 63
`
`

`

`
`
`viii
`
`Contents
`
`24
`Alternative Expression of the Gradient
`Decorrelation of Error and Input Components
`Exercises
`26
`
`26
`
`part I|_
`
`THEORY OF ADAPTATION WITH
`STATIONARY SIGNALS
`Objectives of Part Il
`31
`
`3 PROPERTIES OF THE QUADRATIC PERFORMANCE
`SURFACE
`Normal Form of the Input Correlation Matrix
`Eigenvalues and Eigenvectors of the Input
`Correlation Matrix
`34
`36
`An Example with Two Weights
`Geometrical Significance of Eigenvectors
`and Eigenvalues
`38
`A Second Example
`41
`Exercises
`43
`
`34
`
`46
`
`4 SEARCHING THE PERFORMANCE SURFACE
`Methods of Searching the Performance Surface
`Basic Ideas of Gradient Search Methods
`47
`A Simple Gradient Search Algorithm andIts Solution
`Stability and Rate of Convergence
`49
`The Learning Curve
`51
`52
`Gradient Search by Newton’s Method
`54
`Newton’s Method in Multidimensional Space
`Gradient Search by the Method of Steepest Descent
`Comparison of Learning Curves
`61
`Exercises
`63
`
`5 GRADIENT ESTIMATION AND ITS EFFECTS ON
`ADAPTATION
`Gradient ComponentEstimation by Derivative
`Measurement
`66
`
`31
`
`33
`
`46
`
`48
`
`56
`
`66
`
`Page12 of 63
`
`Page 12 of 63
`
`

`

`Contents
`
`ix
`
`68
`‘ The Performance Penalty
`Derivative Measurement and Performance Penalties
`with Multiple Weights
`69
`71
`Variance of the Gradient Estimate
`Effects on the Weight-Vector Solution=75
`Excess Mean-Square Error and Time Constants
`80
`Misadjustment
`87
`Comparative Performance of Newton’s and
`Steepest-Descent Methods
`89
`Total Misadjustment and Other Practical Considerations
`Exercises
`93
`
`91
`
`part lil
`
`ADAPTIVE ALGORITHMS AND STRUCTURES
`
`98
`
`Objectives of Part Ill
`
`98
`
`6 THE LMS ALGORITHM
`
`99
`
`Derivation of the LMS Algorithm
`Convergence of the Weight Vector
`An Example of Convergence
`103
`Learning Curve
`107
`Noise in the Weight-Vector Solution
`Misadjustment
`110
`Performance
`112
`Exercises
`
`114
`
`99
`101
`
`109
`
`7 THE z-TRANSFORM IN ADAPTIVE SIGNAL
`PROCESSING
`
`117
`
`117
`The z-Transform
`Right- and Left-Handed Sequences
`Transfer Functions
`120
`Frequency Response
`122
`Impulse Response and Stability
`The Inverse z-Transform
`126
`Correlation Functions and Power Spectra
`The Performance Function
`131
`Examples of Performance Surfaces
`Exercises
`137
`
`119
`
`124
`
`128
`
`134
`
`Page 13 of 63
`
`a a reRR
`
`Page 13 of 63
`
`

`

`Contents
`
`141
`
`182
`
`partlV) APPLICATIONS
`Objectives of Part IV
`
`193
`
`193
`
`
`
`8 OTHER ADAPTIVE ALGORITHMS AND STRUCTURES
`An Ideal: The LMS/Newton Algorithm
`142
`Properties of the LMS/Newton Algorithm
`145
`The Sequential Regression Algorithm=147
`Adaptive Recursive Filters
`154
`Random-Search Algorithms
`161
`Lattice Structures
`164
`173
`The Adaptive Lattice Predictor
`Adaptive Filters with Orthogonal Signals
`Exercises
`186
`
`9 ADAPTIVE MODELING AND SYSTEM
`IDENTIFICATION
`195
`General Description
`Adaptive Modeling of a Multipath Communication
`Channel=200
`Adaptive Modeling in Geophysical Exploration
`209
`Adaptive Modeling in FIR Digital Filter Synthesis
`212
`Exercises
`225
`
`195
`
`10
`
`INVERSE ADAPTIVE MODELING, DECONVOLUTION,
`AND EQUALIZATION
`General Description of Inverse Modeling
`Some Theoretical Examples
`236
`Adaptive Equalization of Telephone Channels
`Adapting Poles and Zeros for IIR Digital
`Filter Synthesis
`250
`Exercises
`264
`
`232
`
`244
`
`11. ADAPTIVE CONTROL SYSTEMS
`Adaptive Model Control
`271
`Adaptive Inverse Control
`280
`
`Page 14 of 63
`
`231
`
`270
`
`Page 14 of 63
`
`

`

`Contents
`
`285
`Examples of Adaptive Inverse Control
`288
`Plant Noise and the Filtered-X LMS Algorithm
`Inverse Control Using the Filtered-X LMS Algorithm
`Model Reference Control
`294
`Exercises
`298
`
`xi
`
`292
`
`12 ADAPTIVE INTERFERENCE CANCELING
`
`302
`
`303
`
`330
`
`311
`316
`
`329
`
`351
`354
`
`
`
`Early Work in Adaptive Interference Canceling
`The Concept of Adaptive Noise Canceling
`303
`Stationary Noise-Canceling Solutions
`306
`Effects of Signal Components in the Reference Input
`The Adaptive Interference Canceler as a Notch Filter
`The Adaptive Interference Canceler as a
`High-Pass Filter
`323
`324
`Effects of Finite Length and Causality
`327
`Multiple-Reference Noise Canceling
`Canceling 60-Hz Interference in Electrocardiography
`Canceling Donor-Heart Interference in
`Heart-Transplant Electrocardiography
`Canceling the Maternal ECG in Fetal
`Electrocardiography
`334
`Canceling Noise in Speech Signals=337
`Canceling Echoes in Long-Distance Telephone Circuits
`339
`Canceling Antenna Sidelobe Interference
`347
`Canceling Periodic Interference with an
`Adaptive Predictor
`349
`The Adaptive Self-Tuning Filter
`The Adaptive Line Enhancer
`Conclusion
`361
`Exercises
`361
`
`13.
`
`INTRODUCTION TO ADAPTIVE ARRAYS AND
`ADAPTIVE BEAMFORMING
`
`368
`
`369
`Sidelobe Cancellation
`Beamforming with a Pilot Signal©383
`Spatial Configurations
`388
`Adaptive Algorithms
`391
`Narrowband Experiments
`Broadband Experiments
`Exercises
`404
`
`394
`399
`
`Page 15 of 63
`
`Page 15 of 63
`
`

`

`
`
`14 ANALYSIS OF ADAPTIVE BEAMFORMERS
`Performance Characteristics of Receiving Arrays
`The Griffiths LMS Beamformer
`412
`The Frost Adaptive Beamformer
`415
`An Adaptive Beamformer with Poles and Zeros
`Signal Cancellation and Distortion
`429
`Frequency-Hop Spread-Spectrum Techniques
`Beamformers with Superresolution
`445
`Exercises
`456
`
`Contents
`
`409
`
`409
`
`420
`
`442
`
`APPENDIX A
`
`A Portable Random Number Generator
`
`459
`
`INDEX
`
`469
`
`Page16 of 63
`
`
`
`RPetaoemecTceeCNCPRRECReRCARRORRRERRNReTeECETtnreesememes
`
`Page 16 of 63
`
`

`

`chapter 1
`
`Adaptive Systems
`
`DEFINITION AND CHARACTERISTICS
`
`adapt, v.t., 1. to make suitable to requirements or conditions; adjust or modifyfittingly;
`. v.i., 2. to adjust oneself to different conditions, environments, etc. (Random House
`Dictionary, 1971)
`
`In recent years, a growing field of research in “adaptive systems” has resulted
`in a variety of adaptive automatons whose characteristics in limited ways resemble
`certain characteristics of living systems and biological adaptive processes. According
`to the Random House Dictionary, some of the meanings of “adaptation”are:
`
`the state of being adapted; adjustment. 3. Biol. a. any
`the act of adapting. 2.
`1.
`alteration in the structure or function of an organism or anyofits parts that results
`from natural selection and by which the organism becomesbetterfitted to survive and
`multiply in its environment. b. a form orstructure modified to fit changed environ-
`ment. 5. Physiol.
`the decrease in response of sensory receptor organs, as those of
`vision, touch, temperature, olfaction, audition, and pain, to changed, constantly ap-
`plied, environmental conditions. 6. Ophthalm.
`the regulating by the pupil of the
`quantity oflight entering the eye. 7. Sociol. a slow, usually unconscious modification of
`individual andsocial activity in adjustment to cultural surroundings.
`
`It will be noted that the definition above is expressed primarily in terms of
`biological adaptation to environment. The same definitions serve at least to some
`extent for “artificial” or human-made adaptive systems, which are the central
`concern of this book.
`An adaptive automatonis a system whosestructureis alterable or adjustable in
`such a way that its behavior or performance (according to some desired criterion)
`improves through contact with its environment. A simple example of an automaton
`or automatic adaptive system is the automatic gain control (AGC) used in radio and
`television receivers. The function of this circuit is to adjust the sensitivity of the
`
`Page 17 of 63
`
`3
`
`Page 17 of 63
`
`

`

`following characteristics:
`
`1. They can automatically adapt (self-optimize) in the face of changing (nonsta-
`tionary) environments and changing system requirements.
`2. They can betrained to perform specific filtering and decision-makingtasks.
`Synthesis of systems having these capabilities can be accomplished automati-
`cally through training. In a sense, adaptive systems can be “programmed” by
`a training process.
`dase elt Les deege ptt 7?
`3. Because of the above, adaptive systems do not require the elaborate synthesis
`procedures usually needed for nonadaptive systems. Instead, they tend to be
`“self-designing.”
`4. They can extrapolate a model of behavior to deal with newsituations after
`having been trained ona finite and often small number of training signals or
`patterns.
`5. To a limited extent, they can repair themselves; that is, they can adapt around
`certain kinds of internal defects.
`6. They can usually be described as nonlinear systems with time-varying parame-
`ters.
`they are more complex and difficult to analyze than nonadaptive
`tes 7, Usually,
`systems, but they offer the possibility of substantially increased system perfor-
`mance when inputsignal characteristics are unknown or time varying.
`
`+,+«
`
`AREAS OF APPLICATION
`
`Recentprogress in microcircuit design and production hasresulted in very compact,
`economical, and reliable signal processors thatrival biological nervous systems in
`size andare clearly superior to biological systemsin speed. The gesult has been a
`very fast-growing field of applications for all
`types of digital signal processing,
`including adaptive processing. Current applications for adaptive systems are in such
`fields as communications, radar, sonar, seismology, mechanical design, navigation
`systems, and biomedical electronics.
`Part IV of this book concernscertain classes of applications, and the chapter
`headings provide a rough picture of the application areas. Chapter 9 covers adaptive
`modeling and system identification, in which an adaptive system models an un-
`
`Page 18 of 63
`
`Page 18 of 63
`
`

`

`that is, control systems whose
`Chapter 11 is on adaptive control systems,
`characteristics change with time and adapt to the environment. An example is the
`flight control system whose gain and response times change with air density.
`Adaptive noise canceling, discussed in Chapter 12, has been applied to areas such as
`speech communications, electrocardiography, and seismic signal processing. Adap-
`tive noise canceling is in fact applicable to a wide variety of signal-enhancement
`situations, because noise characteristics are not often stationary in real-world
`situations. Chapters 13 and 14, on adaptive arrays, describe an area where adaptive
`signal processing concepts have proved to beespecially useful.
`
`GENERAL PROPERTIES
`
`The essential and principal property of the adaptive system is its time-varying,
`self-adjusting performance. The need for such performance mayreadily be seen by
`realizing that if a designer develops a system of fixed design which he or she
`considers optimal, the implications are that the designer has foreseen all possible
`input conditions, at least statistically, and knows what he or she would like the
`system to do undereach of these conditions. The designer has then chosena specific
`criterion whereby performanceis to be judged, such as the amountoferror between
`the output of the actual system and that of some selected model or “ideal” system.
`Finally,
`the designer has chosen the system that appears best according to the
`performancecriterion selected, generally choosing this system from anapriori
`restricted class of designs (such as linear systems).
`In many instances, however, the complete range of input conditions may not
`be known exactly, or even statistically; or the conditions may change from time to
`time. In such circumstances, an adaptive system that continually seeks the optimum
`within an allowed class of possibilities, using an orderly search process, would give
`superior performance compared with a system of fixed design.
`By their very nature, adaptive systems must be time varying and nonlinear.
`Their characteristics depend, among other things, on their inputsignals. If an input
`signal x, is applied, an adaptive system will adapt to it and produce an output—let
`us call it y,. If another input signal, x, is applied, the system will adapt to this
`second signal and will again produce an output—let us call it,
`this time, y).
`Renerally the form or the structure or the adjustments of the adaptive system will
`be
`slifferensforr(Be two different inputs. If the sum of the two inputs is applied to
`age
`3
`
`Page 19 of 63
`
`

`

`GeneralIntroduction
`
`Part|
`
`v1 + ¥2
`Yt ya: X2@
`
`x
`
`Figure 1.1 The loweroutput, y,, is equal
`to y + y if H is a linear system. If H
`is adaptive, y, is generally different from
`
`the adaptive system, the latter will adapt to this new input—butit will produce an
`output that will generally not be the same as y, + y,, the sum of the outputs that
`would have corresponded to inputs x, and x,. In such a case,
`asillustrated in
`Figure 1.1,
`the principle of superposition does not work as it does with linear
`systems. If a signal is applied to the input of an adaptive system to test its response
`characteristics, the system adaptsto this specific input and thereby changes its own
`form. Thusthe adaptive system is inherently difficult to characterize in conventional
`terms.
`Within the realm of nonlinear systems, adaptive systems cannot be dis-
`tinguished as belonging to an absolutely clear subset. However,
`they have two
`features that generally distinguish them from other forms of nonlinear systems.
`First,adaptive systems are adjustable, and their adjustments usually depend on
`nite-time average, signal characteristics rather than on instantaneous values of
`signals or instantaneous values of the internal system states. Second, the adjust-
`ments of adaptive systems are changed purposefully in order to optimize specified
`performance measures.
`Certain formsofadaptivesystems.become.linear,systems .when-their-adjyst-
`ments, areheld.constant,afteradaptation..These may becalled ‘elinear_adaptive
`systems.” ‘They are very useful; they tend to be mathematically tractable; and they
`“dré"penerally easier to design than other forms of adaptive systems.
`
`OPEN- AND CLOSED-LOOP ADAPTATION
`
`Several waysto classify adaptive schemes have been proposed in theliterature. It is
`most convenient here to begin by thinking in terms of open-loop and closed-loop
`adaptation. The open-loop adaptive process involves making measurementsof input
`or environmental characteristics, applying this information to a formula or to a
`computational algorithm, and using the results to set the adjustments of the adaptive
`system. Closed-loop adaptation, on the other hand, involves automatic experimen-
`
`Page 20 of 63
`
`Page 20 of 63
`
`

`

`Chap. 1
`
`Adaptive Systems
`
`7
`
`tation with these adjustments and knowledge of their outcome in order to optimize a
`measured system performance. The latter process may be called adaptation by
`“performance feedback.”
`The principles of open- and closed-loop adaptation are illustrated in Figures
`1.2 and 1.3. In both casesit is helpful to envisage the adaptive processas it might be
`performed manually by a human operator or “supervisor.” In Figures 1.2(a) and
`1.3(a) the supervisor is shown adjusting the controls of the processor by reading a
`display that registers measurementsof the preselected performancecriterion. In the
`epenclopp.system.this.criterion.is.a.chasacteristic.of.thesinput-signalandperhaps,
`_other,datazand in.the-closed-loop.systemitis_also,a-functionofthe.outpulsignals
`‘The adjustments in Figure 1.3 are made even though the operator may have no
`knowledge of what is inside the processor or of the functions performed by the
`controls. The operator does not process the input signal; he or she only controls
`the adjustments of the processor to keep its performance optimized according to the
`preselected criterion. Thus the operator’s function is purely supervisory, and in real
`automatic adaptive systems the operator is replaced by computational or “adaptive”
`algorithms, as suggested by Figures 1.2(b) and 1.3(b). The “other data” in these
`figures may be data about
`the environment of the adaptive system, or in the
`closed-loop case, it may be a desired version of the outputsignal.
`
`Processor
`
`Input
`signal
`
`Other
`data
`
`Output
`
`signal
`
`
`
`
`Signal
`processor
`
`Display
`
`(a)
`
` Input
`
`
`Processor
`
`Adaptation
`algorithm
`
`signal
`
`Other
`data
`
`Output
`signal
`
`(b)
`
`Figure 1.2 Open-loop adaptation:(a) concept; (b) equivalent system.
`
`Page 21 of 63
`
`Page 21 of 63
`
`

`

`GeneralIntroduction
`
`Part |
`
`ae
`
`Processor
`
`signal
`
`Output
`
`Other
`
`calculation
`
`signal
` Input
`| Performance
`data N
`
` Performance
`display
`
`
`Input
`signal
`
`(a)
`
`
`
`
`
`
`Performance
`calculation
`
`Adaptation
`algorithm
`
`Output
`signal
`
`Other
`data
`
`(b}
`
`Figure 1.3. Closed-loop adaptation.
`
`When designing an adaptive process, many factors determine the choice of
`closed-loop versus open-loop adaptation. che availabilityof,input Signalsand |
`-berformance-indicatingSignals.is Amajor.consideration, Also, the amount of ‘com-
`puting capacity and the type of computer required to implement the open-loop and
`closed-loop adaptation algorithms will generally differ. Certain algorithms require
`the use of a general-purpose digital computer, whereas other algorithms could be
`implemented far more economically with special-purpose chips or other apparatus.
`Someof these structural considerations are discussedin later chapters. It is difficult
`to develop general principles to guide all choices, but several advantages and a few
`disadvantages of closed-loop adaptation, which is the main subject of this book, can
`be pointed out here.
`Closed-loop adaptation has the advantage of being workable in many applica-
`tions where no analytic synthesis procedure either exists or is known; for example,
`whereerrorcriteria other than mean-square are used, where systems are nonlinear or
`time variable, where signals are nonstationary, and so on. Closed-loop adaptation
`
`Page 22 of 63
`
`Page 22 of 63
`
`

`

`Chap. 1
`
`Adaptive Systems
`
`9
`
`can also be used effectively in situations where physical system componentvaluesare
`variable or inaccurately known. Closed-loop adaptation will find the best choice of
`componentvalues. In the eventof partial system failure, an adaptation mechanism
`that continually monitors performance will optimize this performance by adjusting
`and reoptimizing the intact parts. As a result, system reliability can often be
`improved by the use of performance feedback.
`The closed-loop adaptation process is not always free of difficulties, however.
`In certain situations, performance functions do not have unique optima. Automatic
`optimization is an uncertain process in such situations. In other situations,
`the
`closed-loop adaptation process, like a closed-loop control system, could be unstable.
`The adaptation process could diverge rather than converge. In spite of these
`possibilities, performance feedback is a powerful, widely applicable technique for
`implementing adaptation. Most of the adaptive processes described in this book will
`be closed-loop processes utilizing performance feedback.
`
`APPLICATIONS OF CLOSED-LOOP ADAPTATION
`
`Let us now consider briefly some applications of the closed-loop, performance
`feedback concept. These will anticipate the applications chapters in Part IV, begin-
`ning with Chapter 9.
`We begin by representing the performance feedback process [Figure 1.3(b)]
`more specifically in Figure 1.4. We call the input signal x and define a “desired
`fesponse””signal_d,.which is.assumed to.representthe. desiredoutputofthe.adaptive,,
`(system. The Signald‘is,forourpurposehere, the “otherdata’in Figure 1.3(b).
`Theerror signal, ¢, is the difference between the desired output signal and the
`actual output signal, y, of the adaptive system. Using the error signal, an adaptive
`algorithm adjusts the structure of the adaptive system, thus altering its response
`characteristics by minimizing some measureoftheerror, thereby closing the perform-
`ance loop.
`Different structures are possible for the adaptive system, and these are dis-
`cussed later, beginning in Chapter 2. Adaptive algorithms for adjusting these
`structures are also discussed later, beginning in Chapter 4. Here we wish only to
`show in a general way how the schemein Figure 1.4 is applied in practical situations.
`
`d (desired output)
`
`
` y (output)
`é (error)
`
`Processor
`
`
`x (input)
`
`
` Adaptive
`algorithm
`
`Page 23 of 63
`
`Figure 1.4 Signals in closed-loop
`adaptation.
`
`Page 23 of 63
`
`

`

`
`
`General Introduction
`
`Part |
`
`5
`
`d
`
`
`
`Adaptive
`(2)
`processor
`
`
`
` x
`
`s
`
`
`
`
`
`(a)
`
`
`
`
`
`
`
`
`x
`processor vO
`
`d
`
`@)
`
`
`
`
`
`
`
`wee
`
`Figure 1.5 Examples showing how the
`configuration in Figure 1.4 may be
`applied: (a) prediction; (b) system
`identification (modeling); (c) equalization
`(deconvolution,inversefiltering, inverse
`modeling); (d) interference canceling.
`
`d A
`
`daptive
`processor
`
`stn
`
`(d)
`
`Page 24 of 63
`
`Page 24 of 63
`
`€
`

`

`Chap.1
`
`Adaptive Systems
`
`11
`
`Some examplesof applications are given in Figure 1.5. Notice that Figure 1.4,
`which illustrates the basic closed-loop adaptive process, is simplified slightly and
`embeddedin each part of this figure, and that the application determines how the
`desired signal, d, is obtained.
`The prediction application in Figure 1.5(a) is perhaps the simplestof the four.
`The desired signal is the input signal, s, and a delayed version of the latter is sent to
`the adaptive processor, which must therefore try to ¢predict’-the-gureentanput
`Signal.in,order,tohaye_y,cancel.d_.anddrive.s-toward.zerg,Predictionis .used.in,
`signalencodingandnoise,reduction,and is discussed in Chapters8,9, and 12.
`The system identification application in Figure 1.5(b) is also easy to under-
`stand. Here a broadbandsignal, s, is the input to the adaptive processor as well as
`to an unknown “plant” (a term originating in the control literature). To reducee,
`the adaptive processor tries to emulate the plant’s transfer characteristic. After
`adaptation the plant is “identified” in the sense that its transfer function can be
`specified as essentially the same as that of the adaptive processor. Adaptive system
`identification or modeling can be used as such, to model a slowly varying plant
`whose input and output signals are available, for example, in vibration studies of
`mechanical systems. It can also be used in many other ways, some of which are
`described in Chapters 9 and 11.
`The inverse modeling application [Figure 1.5(c)] is discussed primarily in
`Chapter10, andits uses in control are discussed in Chapter 11. In this application
`theadaptiveprocessor attempts.torecoveradelayedversion.ofthe-signal, s, which
`is assumed to have been altered by the slowly varying plant and to contain additive
`noise. Thedelay in thefigure is to allow for the delay, or propagation time, through
`the plant and the adaptive processor. Adaptive equalization could be used to undo
`(deconvolve) the effects of a transducer, a communication channel, or some other
`system, or to produce an inverse model of an unknownplant. It is also applicable in
`the design of digital filters, as well as in adaptive control problems, and so on.
`Finally, Figure 1.5(d) showsthe adaptive processor in an interference-canceling
`configuration. Herethesignal, s, is corrupted by additive noise, n, and a distorted
`but correlated version of the noise, n’, is also available. The.goal-of-theadaptaye
`~Processor,inthisfase istoproduce.an.output,. athat.closelyresembles.n,sQthat,the
`overalloutput,:¢-will-closely_resemble_s., Wewill show, under certain very broad
`conditions, that the optimal adaptive processor is that which minimizes the mean-
`square value of e. The subject of adaptive interference canceling is discussed in
`Chapters 12 through 14.
`.
`
`EXAMPLE OF AN ADAPTIVE SYSTEM
`By now wehave seen that adaptive signal processingis really a very general and
`basic term which implies the.use.of,time-varying_-self-adiusting-sisnal-processors.
`We think of the performance of these’ systems as being purposeful, useful, and
`
`Page 25 of 63
`
`)
`
`Page 25 of 63
`
`

`

`12
`
`GeneralIntroduction
`
`Part|
`
`
` mw
`
`sometimeseven “intelligent” in a limited sense. Before concluding this introductory
`chapter we introduce just one specific example of such a system, to provide a more
`concreteillustration of adaptation in general and closed-loop adaptation in particu-
`lar. We will use the “prediction” application in Figure 1.5(a), keeping in mindthat
`in doing so we have a very restricted and specific example of a very broad and
`general class of systems.
`
`x*3a£
`
`100
`
`200
`
`300
`
`400
`
`100
`
`200
`
`300
`
`400
`
`Sample number, k
`
`0.0
`
`-0.1
`
`0.02
`
`0.00
`
`-0,02
`
`0
`
`0
`
`x 2
`
`a
`oO
`
`co
`S
`uw
`
`Figure 1.7 Signals in the adaptive predictor in Figure 1.6. The error (2) becomes
`nearly zero as the system learns to predict
`the input (x) and the output (y)
`approaches x.
`
`Page 26 of 63
`
`Page 26 of 63
`
`

`

`’-oy
`
`|
`
`|
`
`|
`:
`
`Chap.1
`
`Adaptive Systems
`
`13
`
`The adaptive predictor diagram in Figure 1.5(a) is redrawn in Figure 1.6, with
`examples of several conventionsof notation that are used throughoutthis text. The
`symbols x,, y,, and e, represent the kth elementsin the time series represented by
`x, y, and e. Usually, the time series may be assumed to be obtained by sampling
`continuous signals. Thus x, = x(kT), and so on, where T is the time step or
`interval between samples. The symbol z~™ standsfor a fixed delay of M timesteps,
`so that in Figure 1.6 the output of the z~™ blockis labeled x,_,,. The symbol H,
`represents the transfer characteristic of the adaptive processor or “adaptivefilter.”
`Weleave a detailed de