`
`
`
` Sony v. Jawbone
`
`
`
`
`
`
`
`-1-
`
`U.S. Patent No. 8,019,091
`Sony Ex. 1011
`
`- 1 -
`
`Sony v. Jawbone
`
`U.S. Patent No. 8,019,091
`
`Sony Ex. 1011
`
`

`

`PRENTICE-HALL S IGNAL l>ROCE..'!SING SERIES
`
`A /on V. Opptmheu14 Editor
`
`ANDREWS 1\ND Hum bigua/ Image Re.\lorai/0/1
`Thi!' Fast Foun~r Trattsform
`BRJOIIA-\t
`BURDJC U111:hmmter Acoustic System A•ralvsis
`CAS1'U:M.I\N Digital ]mag'! Pmu:.st11g
`·
`COWAN M-Il> GAANT Adaptiue Ftltets
`CP.OCHIEilE AND RAilii'IEI\ Multirate Digilul S(<l?lal Proce.•,,•ing
`DuoGF-Ot-r 1\ND MEII-SE!lEAU Multi-Dimen.t!ona/ Digitul Signal Prlll.'ess{ng
`lfA~!MrNO D•xital Filters, 2e
`lli'I'KIN, I!T AL. Array Signal Procey;ing
`JAY 1\ ,..-, AND No!.L Digtlal C odillg ol Wllt'Pforms
`LE,\, w .
`}rends 111 Speech Recognition
`Speech E11hancemenr
`LIM
`McCLE~UN ANb R.Av<.ll. Number Theory tn Digital Signal Processlitg
`0PPEN.HEJM, ED. App /;C(11/r>m of Dtg£tal Stgnul Proressing
`0PPCNllEI.M AND SCHAFER Digttal Signal PriJC<'.<Sing
`Stgnals and Systems
`Or·P.ENtiEJM. W!LI.SKY, WITH YOUNG
`RAsr!'ltR AND Gou> Thron• mrd Appliration of Digiw/ Signal Proce~~"ng
`RABI!ftR AND SCHAFER Digtfal PrO('essmg of Spt!edt Srgnals
`ROBINSON AND TREttEl Geopltysilal Signa/ A.lla(vsis
`ScL1mic Applicattc/ltf of Hnmomorpltic Srgnal Proce.v.vmg
`TRIBOI.£T
`.4daptil'e Stgna/ Prth'I!Mmg
`WIOI<OW ANO STEIIRNS
`
`ADAPTIVE
`SIGNAL
`PROCESSING
`
`Bernard Wldrow
`StanfMi Urttfii;si(r•
`
`Samuel D. Stearns
`Sundia 11/atil)l(al [.Qboratr>rie.~
`
`- 2 -
`
`

`

`Uhrury uf CMgr<ss Catu/ogi~g in l'u~(ica(ion Datu
`
`Wldrow, llcrnnrd, (dale I
`Adaptj,e,~ignal pr<)l.~$'"1\·
`
`(Ptenlicc· Hall 5ignal pro.:t~o>lllS ~rlrs)
`l nclud<S lnd<x.
`I. Adapti" sig~~al prt'<.~s~ing J. Steam~.
`II! Stri.:s
`I f. Tille
`Spmud D.
`6~1 3M'041
`TK.5102.5.W537
`tQS5
`ISfiN O·l3·00402q..(J
`
`M ·ll\057
`
`Editorial/production supe1V1;1.,n and
`mtcmor dtstgn: Ttat"lfl' L. Orlmre
`Cover d~ign: S11t 8&huAe
`Manuracturing ~uycr: Auth<Ml· Cur,tJo
`
`@ 1985 by PrtnttCC:· H~ll PTR.
`l'rcnbcc·llull, Inc.
`Upptr Soddlc River. ,"'ew Jcr.;cy 0745ll
`
`AU rights reserved. No part of lhit book mll.y be
`reprod uced, in any form or by an)' means,
`without permission in writing from the publisb~>r,
`
`Printed in the United Slate$ of America
`
`20 19 18 17 16
`
`ISBN 0-13-004029 -0
`
`PRf:>.'TICe·H,ur I:>~TER.\illfi0:-.11\L (UK) I iMltEP, LONDON
`PRThTICE-HAI~~ OF AUSTRALIA £->r.·. l.lMITEO, SYPN£'1'
`PRE.~"Jln-1-!ALL CANAOA r:-.c., TOII.ON'f(f
`PR:tNUCE-HI\1 L Htsi'ANOMI-lliRJCANA. S,A., MC:l\'KO
`l'REf\."JlC'E-H/11 LOF l N'(llA PRJV AT!': LIM !TELl, NFW' Det HI
`f'RE:>!TICF.-H/IU .OF }AI'I\\I, Jl\(;,, TOk\'0
`PFMSON .F.DUC/ITION A SIA Pn;, L'tD., 51NCA('0R£
`f.OITORA PRENTIC'l'-f.ii\Ll. DO BRA!,lll.. l.JilA., RIP or j /.Nt;IRO
`
`This book is dedicated to the memory of Moses Widrow. William
`K. T..invill. and Thomas J. Flanagan. £t is also dedicated to the
`cause of peace on earth. We hope and trust Lhat its contents will be
`used to improve the lot of mankind everywhere.
`
`- 3 -
`
`

`

`Contents
`
`PREFACE
`
`LIST OF SYMBOLS
`
`part I
`
`GENERAL INTRODUCTION
`Objectives of Part I
`1
`
`ADAPTIVE SYSTEMS
`
`3
`
`Definition a nd Characteristics
`Areas of Application
`4
`5
`General Properties
`6
`Open- and Closed-Loop Adapta ti(ln
`Applications of Closed-Loop Adaptation
`Example of an Adapuve System
`I l
`The Chapters Ahead
`13
`
`9
`
`xlii
`
`XV
`
`1
`
`3
`
`2 THE ADAPTIVE LINEAR COMBINER
`
`15
`
`15
`General D escription
`lnput Signal and Weight Vectors
`Desi red Re~ponse and Error
`lS
`The Performance Function
`19
`Omdient and Minimum Mean-Square Error
`Example or a Pcr[ormance Surface
`22
`
`16
`
`21
`
`vii
`
`- 4 -
`
`

`

`viii
`
`Conlents
`
`Contepts
`
`24
`Alternative Expression- of thtl Gradient
`Decor relation or Error nnd Input Co mponents
`26
`E:~Cercises
`
`26
`
`part 11
`
`THEORY OF ADAPTATION WITH
`SiTATIONARY SIGNALS
`Objectives of Part II
`31
`
`31
`
`68
`The Performance Penalty
`Derivative Measurement and Performance Pen;rlties
`with Multiple Weights
`69
`Variance o r the Gradient Estimate
`71
`Effects on the Weight-Vector Solution
`75
`E.x.cess Mean,Square Error and Time Constants
`Misa<ljustment
`87
`Camparative Perfonnance of Newton's and
`89
`Steepest-Descent Methods
`Total Misadjustment and Other Practical Considerations
`93
`Exercises
`
`80
`
`,3 PROPERTIES OF THE QUADRATIC PERFORMANCE
`SURFACE
`
`J4
`
`Normal Form of the Input Correlation Matrix
`Eigenvalues and Eigenvectors o r the Input
`34
`Correlation Matrix
`36
`An E.umple with Two Weights
`Geometrical Significance o r Eigenvectors
`and Eigenvalues
`38
`A Second Example
`41
`43
`Exercises
`
`4 SEARCHING THE PERFORMANCE SURFACE
`
`46
`
`Methods of Searchtng the Performance Surface
`Basic Ideas of Gradient Sea.rch Methods
`47
`A Simple Gradient Search Algorithm and lts Solution
`49
`Stability and Rate of Convergence
`The Learning Curve
`51
`Gradient Searc"h by Newton's Method
`52
`Newlon's Method in Multidimensional Space
`54
`GTad1ent Search by the Method of Steepest Descen t
`61
`Comparison of Learning Curves
`Exercises
`63
`
`5 GRADJENT ESTIMATION AND ITS EFFECTS ON
`ADAPTATION
`
`Gradient Component Estimation by Derivative
`Measurement
`66
`
`~~
`
`91
`
`98
`
`99
`
`Tl7
`
`- 5 -
`
`

`

`Cof)tents
`
`Contents
`
`a OTHER ADAPTIVE ALGORITHMS AND STRUCTURE$
`142
`An ldc::ll: Th;;, LMS/Newtoo Algorithm
`Propenit:.'l of the LMSjNewton Algorithm H5
`The Sequential Regression Algorithm
`147
`154
`Adaptive Recui~ve Filters
`Random-Search Algorithms
`161
`Lauice Structures
`164
`173
`The Adaptive Lauice Predictor
`Adaptive FIJtcrs with Orthogonal Signals
`Exercises
`186
`
`182
`
`part IV
`
`APPLICATIONS
`Objectives of Par/ IV
`
`193
`
`9 ADAPTIVE MODELING AND SYSTEM
`IDENTIFICATION
`
`141
`
`193
`
`195
`
`1'95
`CeneraJ Description
`Adaptive Modeling of n Muhipath Communication
`Chtutnel
`200
`Adaptive Modeling i.n Geophysical Exploration
`209
`212
`Ad:~ptive Modeling in Fl R D(gital Filter Synthesis
`Exercises
`225
`
`10 INVERSE ADAPTIVE MODELiNG, DECONVOLUTION,
`AND EQUALIZATION
`
`231
`
`General Description of Inverse Modeling
`Some Theoretical Examples
`236
`Adaptive EqualiZ!lUOn of Telephone Channels
`AdaptiJJg Poles and Zeros for fiR Digital
`250
`Filter Synthesis
`Exerci.ses
`264
`
`232
`
`244
`
`11 ADAPTIVE CONTROL SYSTEMS
`
`270
`
`Adaptive Model Control
`Adaptive Jnvcrse Control
`
`271
`280
`
`285
`Examples of Adaptive Inverse Con trol
`Plant Noise and the Filtered-X LMS Algorithm
`188
`Inverse Control Using the F'iltcred-X LMS Algorithm
`194
`Mode l Reference Control
`Exercises
`29R
`
`xl
`
`292
`
`12 ADAPTIVE INTERFERENCE CANCELING
`
`302
`
`303
`
`3'1 \
`~16
`
`329
`
`339
`
`Early Work in Adaptive Interference Canceling
`The Concept of Adaptive Noise Cancd.ing
`303
`306
`Stationary Noise-Canceling Solutions
`Effects o! Signal Components in the Reference Jnput
`The Adaptive Interference Canceler li S n Notch Filter
`The Adaptive Interference Canceler us n
`High-Pass Filter
`323
`Elfects of Finite Length and Causality
`32.4
`Multiple-Reference Noise Canceling
`327
`Canceling 60-Hz. Interferenc-e in Ele~trocardiograpby
`Canceling Donor-Heart Interference i.n
`Heart-Transplant Electrocaidiography
`C9nceling the Matemal ECG in Fetal
`Electroc.ardiograpby
`334
`Canceling Noise in Speech Signals
`337
`Canceling Echoes in Long-Distance Telephone. Circuits
`Canceling Antenna Sidclobe lnterference
`347
`Canceling Periodic Interference with an
`Adaptive Predic.tor
`349
`The Adaptive Self-Tuning Filter
`The Adaptive line Enhancer
`Conclusion
`361
`Exercises
`361
`
`330
`
`351
`354
`
`·13
`
`INTRODUCTION TO ADAPTIVE ARRAYS AND
`ADAPTIVE BEAMFORMING
`
`368
`
`369
`Sidclobe Cancellation
`Beam forming with a Pilot Sig,nal
`Spatial umfigurations
`388
`Adaptive Algorithms
`391
`Nauowband Experiments
`Broadband Experiments
`404
`Exercises
`
`394
`399
`
`JS3
`
`- 6 -
`
`

`

`xll
`
`14 ANALYSIS OF ADAPTIVE BEAMFORMERS
`
`Contents
`
`409
`
`Performance Characteristics of Re.:eiving Arrays
`The Griffiths LMS .Beamformer
`412
`The Frost Adaptive Beam!ormer
`415
`An Adaptive Bcaroformcr with Poles and Zeros
`429
`Signal Cancellation and Distortion
`Frequency-Hop Spread-Spectrum Techniques
`445
`.Beamformers with Superresolution
`456
`Exercises
`
`409
`
`420
`
`442
`
`APPENDIX A
`
`A Portable Random Number Generator
`
`459
`
`INDEX
`
`469
`
`Preface
`
`This book bas grown out of nearly three de.cades of research and teaching m the field
`o£ adaptive slgnal processing. It is d11signcd primarily to be a basic text on adaptive
`signal processing and, at the time of its publication. it is believed to be the only basic
`te>tt on the subject, or at least the only te ... tbook coven.og the breadth l)f subject
`matter shown an the table of contents.
`Tlte book is based on class notes for a one- or two- semester seruor or
`graduate Jevcl course in adaptive signal processing taught at Stanford Universlly, the
`University or Nc" Mexico, and Sandia NauonaJ Laboratooe.-.. Every chapter except
`Chapter 1 hns exercises at the end, and these arc considc:red to be unessential part of
`any course using the text. The exercises are often used to complete the reader·~
`understanding of a concept or tO present dillerenl applications of ideas in the texl.
`Referring to the table oi contents, the reader can sec that the book is dtvided
`into fo11r main parts. The fust three: pans- General In troduction, Theory o r
`Adaptataon with Stationary Signals, and Adaptive Algonthm~ and Structures- make
`up a little les~ than half of the teAl. The material io these parts as oonsidered baloiC
`theory and would normally be included in any first course on adaptive sagnal
`processing. The fourth pan- Applicallons- consists of six chapters on vamtus
`engineering appUca.taons of adaptive Signal processing. ln this part the instructor
`may wish to concentr,ate on subjects of special interest. However. even in a
`one- semcste( course. the instruclOr will probably wish to includ..: at least the first
`portion or each chapter.
`For prerequisites, weas:.ume that the studeo1 has at least senior-level academic
`experience in engineering and mathematics. and has the ability to write and run
`computer programs. The latter is essenl13l for do10g m.:1ny of the exercises. A course
`io line:u systems analysis. particularly in dist.Tete systems with the use of the
`z-transform, would provide a very useful (if not essential) background. Also. a
`cour~e in engineering st<ttistics or pcobability, or the equivalent. provides u helpful
`background.
`In the lirst pan of the text, Chapter I introduces the con~:ept of adaptation as a
`property or characteristic of certain systems in engjneering. Chapter 2 introduces the
`
`sill
`
`I
`I
`I
`
`- 7 -
`
`

`

`xiv
`
`Preface
`
`adaptive Linear combiner, whicb is the simplest and most widely used adaptive
`structure. Chapter 2 also describes a geometric "performance s urface'' which is
`useful in the analysis or all adaptive systems.
`Part !L Theory or Adaptation with Stationary Signals. contains an analysis of
`the performance surface and its properties. The analysis begin'> in Ch~ptcr 3. and in
`Chapter 4 adaptation is viewed as the process of searching the performance surface
`for its minimum. Chapter 5 contains a statistit,al ann lysis or gradient estima tion on
`the performance surface and a comparison o r seaN:h methods.
`In Part III. Adaptive Algorithms and Structur.:s. the least mean squares (LMS)
`algorithm is introduced and discussed in Chapter 6. In Chapter 7 basic signal
`pro..:essing concepts that are required for the rest of the book ure introduced. These
`illclude primarily the z-transform relationships linking the time and frequency
`domains. To conc:.ludc Pan Ill, Chapter 8 introduces adaptive algorithms other than
`the LMS algorithm and adaptive structures other than the adaptive linear combiner,
`including the adapt:ivc. lattrce structure. The latter is considered, at the time of thi s
`writing. to be a rapidly devclopmg area, and our introduction to it is therefore less
`comprehensive than we would wish it to be.
`Finally, Part IV covers the major applicatie>n areas or adaptive signal process(cid:173)
`ing. Once the basic-s in Chapters 1- 8 have been teamed. subjects can be chosen
`selectively from Part lV. In Chapters 9 and 10. forward and inverse adaptive
`modeling are introduced and applied to areas sucb as multipath communication,
`geophysical ex.ploration, digital filter design, and telephone channel equalization.
`Adaptive control systems are introduced in Cbapter 11. and Chapter 12 introduces
`adaptive interference ,-anccling, with several examples of application. Chapters 13
`and 14 cover adaptive arrays and beamformers.
`While writing this text. t.he authors have had the benefit of critiq ues, eom(cid:173)
`mems, and suggestions from many talemed colleaguc.s. We are very gratefu l for the
`reviews and ideas we have received, and thankful for the friendships engendered ~nd
`increased through this work. We especially wish to acknowledge tbe belp of Robert
`D . Fraser, Dennis R. Morgan, Dae H. Youn. Eugene Walach, Richard Gooch, Ruth
`A. David. Sharoo K. Fletcher, Claude S. Lindquist, Dakshce.sb Parikh, D elores M.
`Etter. 8dward S. Angel, Lloyd J. Griffiths, Nasir Ahmed, John R. Treichler. C.
`Richard Jobnsor., Jr .. Michad G , Larimore. Glenn R. EI.Hott, John M. McCool. John
`M. Ciofli, and 1 . C. Hsia_ The book would not be .in i~s present form without the
`contributions or these special friends.
`We also wish to thank all of the students who took the adaptive signal
`processtng courses menliont!d above. In effect, they haw edited and corrected tbe
`text far beyond our ability to do so. We thank all of these students for t.heir palience,
`interest, and cntbusiasm.
`The only ones with more patience and persevemnce tha:n our students have
`been the talented ladic~ wbo have typed and retyped this text, Debra Shepperd at
`Sandia a nd Micka Parke.r at. Stanford, We also acknowledge their help with
`gratitude.
`
`Bernard w ·idrow
`Samuel D. S teams
`
`List of Symbols
`
`SYMBOL
`
`USE(S) IN THJS .BOOK
`
`a
`
`b.
`
`c
`
`d
`
`j( )
`g
`h
`j
`k
`I
`
`t)
`
`p
`r
`
`(1) forward weight in a line:J.r filter
`(2) bit in g~netir algorithm
`(1) recursive weight in a linear filter
`(2) bit in genet-Ic algorithm
`(1) plant outp~•t signal
`(2) signa l propagarion vclocit y
`(1) desired response
`(2) antenna element sparing
`natural logarithmic base. 2.71828 -·.
`continuous function of
`plant output signal
`impulse response
`0
`s:l.mple number
`(1) weight number
`(2) elemen t spacing
`(I) general indclt
`(2) noise sample value
`1ota l white input noise power
`(1) converge-nce ratio in gradient sea rch algorithms
`(2) unif<Jrm random number in (0, I)
`(3) reference input signal
`(1) signal in lattic.e niter
`(2) input signal
`continuous Lime
`
`)lV
`
`- 8 -
`
`

`

`

`

`l(V111
`
`List of Symbols
`
`A
`e
`0
`A
`<t•
`t/1
`
`time c{)nstnnt of weight cnnvcrgcncc
`(l ) average random signal power
`(2) ~orrelation funcuo n
`angular frequency in rod (~mpUng freq. = 2~)
`delay value
`phase angle (rad)
`signal arnval angle
`eigenvalue mMnx, dtog I A 0 A t . . . A 1 }
`power density (z-lransfo rm of !f>)
`(1) input signal
`(2) signal arrival angle
`angular frequency in rad/ s (sampling frcq = 2"7/T)
`deno tts an optimal vnlue. as in W •
`gradient vector of the performance function
`esnmale of V
`
`part I
`
`GENERAL INTRODUCTION
`
`(Chapters 1 and 2)
`
`OBJECTIVES OF PART I
`
`In the first two chapters of this book we have three maJor objectives. The first
`is to introduce the baslc meaning of " adaptation" (or ''adaption") ln the
`engineering sense, and to set adaptive signal processing Into the general
`signal processing context.
`The second oblective Is to describe the adaptive linear combiner, which
`Is the slmplest and most Widely appffcable adaptive processor It is the basic
`adaptive device that will be used exclusively through Chapter 6. as well as in
`much ot the rest of the text
`The third objective Is to persuade the reader to lhil')k of the overall
`process of adaptation In geometrical terms. We wish to think of adaptation as
`a procedure for moving generally downhill on a " performance surface" like
`the one shown on page 2, which is the L-dimensional surface in (L +
`1)-dimensional space formed by plotting the mean-square error versus the
`adaptive parameters. These geometrical concepts and terms are described in
`Chapter 2.
`
`- 10 -
`
`

`

`

`

`4
`
`General Introduction
`
`Part I
`
`Chap. 1
`
`Adaphve Systems
`
`5
`
`receiver inve!'M'ly a~ the d\erage incoming signal stn:ngth. The receiver is thus 3blc
`to adapl 10 a wide range of input le\el!'. and to produce a much n.1rrowec range of
`ou tput inttm~ities.
`The purpose of thts book is lo present certain basic pnnciple.~ of adaptation; lo
`explain th~: design. operating characteristics. tl nd appli~1Hions of the ~impler forms o f
`adaptive systems: and lt.> describe means for their physical realization. The types of
`system!> di~~d include those designed primarily for the purJl(oSCl> of adapllvc
`control and udo~ptive signal processing. Such system~ usually ha,·e some or all of the
`following .:haracteristi.:~·
`
`1. They can automatically adapt (~elf-optimize) in the fac.e of changing (nonsta·
`uonary) Cll' ironment!i and changif11, system r.:quirc:ments.
`2. Thq can be tratned to perform spectfic filtcnng and dtc1sion-maldng ta.~ks.
`Synth~sis o f systems h~ving these cupabi litie~ t<ln be accompli!'.hed automati(cid:173)
`cally through lratning. In a sense. adaptive systi:lrnS can be " progr;unrned'' by
`a tratning process.
`3. Be<:Qu.se of the above. adaptive syMems do not require the elaborate synthc:sis
`procedwes u~ually needed for nonadaptive ~ysttm~. Instead, they tend to be
`"self·designing."
`4. They can exlrapolate J mode) o f hehavror to dc:al with new situations aflc.:r
`louvinr. bo<:n trained on a finite tmd often small number of tnaining signals or
`pauc:ms
`5. T o a limited ext~nt, they can repatr themselveS: that is. they can adapt around
`certain kinds or internal dt:rwt~.
`6. They ca n usually bo: described as nonlinear syRtems with tim~:-varyi.ngparnmc·
`ters.
`7. Usually, they aJC more eomple.>. nnd difficult to analyu thun nonadaptive
`system~. but they otTer lhe possibility of substantially incrl"ased system perfor(cid:173)
`mance when input signal cbaracLcristic~ are unknown or time varying.
`
`AREAS OF APPLICATION
`
`Recen t progt."es~ in !1Ucrocircuit design and production hu> resulted in very compact.
`economicnJ, und reliable signal processors that rival biological nervous systems in
`size and aJe clearly superior to biological systems in speed. The rt.:5ult has been a
`very iast-gro"ing field ()( applications for all types of digital si&nal processing.
`including adaptive proce~ing. Current applications for adapuve sy~tem1o are in ~uch
`fields as communications, radar, sonar. setsmology, mechanical design. navigation
`~'Ystems, &nu biomedical electronirs.
`Pare IV of this book concerns certain classes of 01pplications, and the chapter
`h12dings pro'·•de a rou!h picture of the application areas. Chaptu 9 covers adaptive
`modehng 11nd system idenuticauon. tn wluch an adaptive. sy~tcm modeb an un-
`
`known ~ystem or "plant." which may be slowly varymg with ttme. l·or a given input
`s•gnal. the adaptive system tries to match the planL out.puL Adapu"e modelong is
`used In ~lc~:tricaJ and mechanical dtl$i&n and tesung.
`Chapter 10 os on inverse modehfll!-- deconvoluuon, and cquahzntion. All pf
`the~e terms, a~ well as the term "inverse filtering,'' refer to rhe process of removtng
`the elfect of some deVJce o r medium on a signal. For example, we may wi~h: to make
`an audio \y~tem respond lvtth equnlgJm to all speech frequenctes, or to remove the
`eiTects of a transmi.,..s.on line on a radar puhe.
`Chupter ll is on adapthe control system,, that 1S. comrol systems who~e
`charactcd~t tCS change "'lth time and adilpt w the cn~1ronm.:nt ·\n I.!Mmple ,~ fht:
`Hight control system whose gain anu n:~pon$.: lrmto.~ change: wtth alr dcn~tty.
`Adaptive notse cancd•ng. discussed to Chapter 12. hus be.."' applt.:d to dfeas such a>
`speech communicatio~. c:lecuocardiograpby. and s.:llimic signal processing. Adap(cid:173)
`tive noise canceling IS tn fact applic:~bt.: to a wide van.:t~ of SJgnal-enhaocement
`situations. hccause noise chara.cteri~Hcs are not orten stationary m real-world
`situations. Chapters U and 14, on adaptive arrays, d~:Scribe an areu wher.: adaptive
`SJgna] proct:S~ing concc:pts have proved to be especoally useful.
`
`GENERAL PROPERTIES
`
`The ~o::nuaJ aml priuc1pal propcmy .,( the audptivt' syM.:m i~ i~ t.irru:.-varying.
`self-adj\1.\ting performance. The nt:ed for such performance may r.:ndtly be ~een by
`realizmg lhat if a designer develops a sy~tem of jiud detign which he or ~he
`considers Optimal, the implic"-tions are that the designer has fore~ecn all pos~thle
`input conditions, at least statistically, and knows whal be <;>r she would like the
`system LO do under each of these conditions. Tht: de.•<igner has lhen chosen a spectlic
`criterion "'hereby performMce is to be Judged, such a~ the amount of error betv.cc:n
`the output o f the actual ystem 31ld thut or some !.elected model or •·idc!al'" system.
`finally, ihe d esigner has chosen the system that oppears hest according to the
`performance criterion selected, generally choosing thi~ system from M a prion
`restricted class of d<!$igns (such as linear system.~).
`In many insl31lce~. bo,\·ever, the complete range or input condiuons may not
`be known exnctly, or l!ven Matistically; or the coodiLi11oS may change (rom timt: to
`time. In such circum~tnnc~s. an ndapthe system that contmually seeks the optimum
`within llll allowed class of pussibililie~. usiug an Clrdc:rly ~earch p rocess, would giv~
`superior perfotmnnce compared with a system of lhed design.
`By their very nature, adapthc: systl!ms must be ume Vaf)tng .1od nonline:~r
`Their charactc:ristics depend, &mong ott.er things. on their mput signals 1£ an input
`let
`signaJ r 1 is apptied,an lldaptive system IJ.tll adapt to it ond produce: on output-
`us tall it y1• lf anothet· input signal, r 2, is applied. the system wiU adapt to this
`second signnl and will again product an output-
`let us call it, this time.
`t·l·
`Generally, the form or the structure or the ;,dJustm.:nts of the udapth.: system \\ill
`be diOerent ror the two dt.ffcrent inpuU U the sum of tbe IIJ.O inputs IS appiJed tO
`
`- 12 -
`
`

`

`

`

`

`

`

`

`

`

`14
`
`General tntroductron
`
`Part 1
`
`Some areas of adaptive signal processing. including recursive ndnptive filters.
`cannot be analyzed cooveruently without refecence to the frequency domain, so
`Chapter 7 is concerned mainly with developing foundations for this type of analysis.
`Then in Chapter 8 we introduce other types of algorithms that require frequen<..'Y·
`domain analysis. In Chapter 8 we also introduce tbe adaptive lauice . a structure
`different frorn the adaptive linear cDmbiner of Chapter 2. Finally, Chapters 9
`through 14 deal with some of the important appticalions of adaptive signal processing,
`us described above.
`
`chapter 2
`
`The Adaptive
`Linear Combiner
`
`GENERAL DESCRIPTION
`
`The adaptive linC".:Lr combiner, or nonrecursivc adaptive filter. is rundamental to
`adaptive signal processiTig. lt appears, ln one fom1 or another. In most adaptive
`filters and systeQlS, and it is the single most important element in" learning" systems
`and adaptive p.roces~es in general. Thus a primary purpose of thi~ book is to
`develop a thorough exposition of the properties, behavior, means of adaptation. rate
`of adaptation, and useful appl ications of the adaptive linear combiner.
`Because of irs non recursive stru.cture. the adaptive linear combiner is relatively
`easy to understand and annlyze. In es:;ence il is a time-varying, non recursive digital
`filter. and as such its performance is quite simple. lis behavior and the means of
`adapting i l, as we ll as its implementation in dilferent forms. are well understood.
`Furthermore, we know of specilic applicat ions where iL~ performance is "best" in
`some sen~e.
`A diagram of the geneml form of the adaptive linear combiner is shown in
`Figure 2.1. l·h~e is an input signal vector with elements x0 • x 1 .... , xL• a corr~
`spending set of adjustable weights, w0, wt •... , w1_, a summing unit, and a single
`output signal, y. A procedure for adjusting or adapting the weights is called a
`" weight adjustment," ·•~rain adjustment," or '·adaptation" procedure. The combiner
`is called " linear" because for 11. f1xe.d selling of the weights its outpul is a linear
`combination of the input components. However, when the weights are in the process
`of being adjusted, they, too, are a function of tbe input components, and -the output
`af the combiner is no longer ~ linear function of the input That is, its operation
`becomes nonlinear in accordance with the general principle set forth in Chapler1.
`
`15
`
`- 17 -
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`part II
`
`THEORY OF
`ADAPTATION WITti
`STATIONARY SIGNIALS
`
`(Chapters 3 - 5)
`
`OBJECTIVES OF PART II
`
`If we have satisfied the objectives of Part I. the reader now understands the
`idea ot the performance or error surface and how 11 represents the adaptive
`environment. An important property or the performance surface in adaptive
`signal processing is the following· II the si9nals are stationary and have
`invariant statistical propert1es, the performance surface remains fixed and
`rigid in its coordinate system The adaptive process then consists or starting
`at some point on the surface. proceeding downhill to the neighborhood of the
`minimum, and staying there.
`On the other hand. if the signals are nonstaltonary and have s1atistical
`properties that slowly change, we can view thEl performance surface as being
`"fuzzy," or undulating, or moving In Its coordinate system The adaptive
`process then consis1s not only or moving downhill to the minimum. but also or
`trackmg the minimum as It moves about in thE! coordinate system
`Chapters 3 through 5 concern the stationary situation where the perfor(cid:173)
`mance surface is rigid, which is ol course the ~>implest situation to discuss. In
`Chapter 3 our objective is to introduce oertaln mathematical properties of the
`fixed performance surface. These properties ·will be useful In later chapters,
`in comparing the performance of adaptive systems.
`The primary objective in Chapter 4 Is to understand two basic methods
`fof searching the performance surlace - Newton's method and the method of
`
`- 25 -
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`Tt>eory of Adaptation with S tationary Slgnals
`
`Part II
`
`Chap. 3
`
`Properties ot the Quadratic Performance SUrface
`
`45
`
`J. J . H. Wilkinson, The AlgebFuk £igerwalue Problem . London : Oxford University Pre~s.
`19'65.
`4, L. G. Kelly, Handbook of Numerccal Methuds and Appllcatron,t _ Reading. Mass.: Addi~on­
`Wesley. 1967. Cbap. 9.
`5. H. Anton, Eli!mPnlary Ltnear Algebr<J. New York~ WUey.1973. Chap. 6.
`6. D . K .. Faddeev and V. N. Faddeeva, Computational Methods of Lin.-ar Algebra, San
`FranCI)CO! w_ H. Freeman. 1963
`
`12. Find the normalized eigenvectOr>:
`(b) In Exerci.~ 5.
`(Q) In EKcrdsc 4.
`(d) In Exercise 9.
`(c) In Exercise 8.
`(f) Jo Exercise H .
`(e) In Exercise IQ.
`U. Demonstrate thal the eigenvectors are mutually orthogonal:
`(a) In Ex~rcise 12(a).
`(b) In EKercise 12(c).
`(e) (n Exercise 12(f).
`14. Considet an adaptive linear combiner m r.he form of Figure 2.4 wttb two weir,llts (i.e ..
`I). rhc signals X uod d have the following properties: Et.cak J ... 2. £[Xf; 1- ~~.
`L -
`El x0~x1 d= I, El 'u•d, I= 6, £[x~4 dd ~ 4, £(dlJ .. 36.
`(u) Write an expression for the mean·squart> error.
`(b) What is the optunal weight vector, W• ?
`(c) What is the minimum meM·square ~rror?
`( d) Find the e tgcovalues and eigenvectors.
`(e) Make a plQt similar to Figure 3.2.
`IS. Show that the eigenvectors of any single-input adaptive linear combiner wl.tb two weig.h.lls
`arc given by Equation (3.50).
`
`ANSWERS TO SELECTED EXERCISES
`
`c~)>. - a 1 + 2b2(a- <! I+ ul'2 = 0
`
`1. (a) mnr: The general quadratic lorm. Ax:1 + Bxy + Cy 2 + Dx + Ey + F= 0, repr•:(cid:173)
`scnts an ellipse i.f B 1
`- 4AC < 0.
`- b1
`J. (a) ).Z- 2aA. • a1
`- 0
`(b) )..3 - Ja~' + (3a' - 2bl -
`4. >..g.>.,= 1,5
`S. >.0 .>. 1 = 2, 4
`6. (o) >.a -(a+'' )>..+ ac - b~ = 0
`(h) >..3 + (a + d + j)'A1 + ( b2 + c 2 + e2 - ad - af - df)>. + adf-! 2/x:e - ae2
`- cltf .. 0
`7. Singlc4nput: 3a, b (also 6a i! a= c; 6b ir a - d - r. b = ~1 Multiplc·input: 6a, b
`(3a, b could also apply)
`8. >.0 , 1.1 - 1.382. 3.618
`10. >. 0 • >.. 1, >.. 1 = 2.1716, 4 , 7,82&4
`12. (a) Same as Equation (3,50)
`(b) Same a_s Equation (3,50)
`(.:) Ob ~ !0.851
`- 0.526]; Of = (0.526 0.8511
`
`- h~/
`
`REFERENCES AND ADDITIONAL READINGS
`
`1. F. R. Gantmacher, The 7'heory of Mauices, vol. 1. New Yoilc: Cbefsea. 1960. p. )08.
`2. 1. N. Franklin, Matrix: Theory. Englewood ctifls. N.J.: Prentice-Ball, 1968, Sec. 4.6.
`
`- 32 -
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`64
`
`Theory ol Adaptalton wrth Statronary Stgnals
`
`Part II
`
`cnap. 4
`
`Search•ng lhe Per1ormance Surface
`
`65
`
`8. "h = 0, ... , - 1.7143, " '! = ).()J47.
`. '"'· = " ' - 0 4484
`9. 0.4484, 0.44R4, 1 3335. - l.JISJ. - 1.3333
`II. W:!ll -12 0346
`.2.9885]T
`14. W!q = 12.0231 2.9769}T
`ts. t, ... 4 + 31!(0.9)"
`17 t, = 4 ~ 0. 51(0.9)'~ + 75(0. 7)1 ' }
`
`REFERENCES AND ADDITIONAL READING S
`
`I. B. Gold and C. M. Rader. Dtgilu/ PrOI.'i'Ssmg of Stljnul.r. New York: McGraw-Hill. l %9.
`Chap. 2.
`2. G. B. TI1omas. Jr., Ca/('U/us ami Atra/yrlc Gcomem•. 4th ed. Reading.. Mass.: Addison·
`We~ley, 1968, Sec. 10.3.
`:l D. G. Luenbergtlr, lntroduwon lo Lweor wt,J Von/iii(Or Pru,r;rollumllf!.. R~ding, Mass":
`Addisoo-Wc.\ley. 1973, S.:c. 7 7.
`4 P. EykhoiT, S)'ltcm fdantlfitr:ttull New York: Wiley. 1974, Chap 5
`
`9. rn Figure ~ 5. flnd "t 10 four decimal placo:s when .... - o.
`008. -0.14, - I 20. and
`- l.30. El!,_pla.in the resuhs and $how wbv Ncwton'5 method may not 3pply to non(cid:173)
`quadratic error surface:..
`10. Writ~ an algorithm 111 the form ol Equation t4.31) s~ciflcallv for the ~rformance surfaGe
`10 Figure 3.2. Oemoru.tratc onc·stcp Nn•ergence lrom any Marung poia1.
`1 I. Using the modtficd Ncv.·ton method in Equation (4.32) wnh convergence p.ll'amcter It set
`at 0.1, wbat :ut• the lirst 1\"e we~ght Vt>Ctors b.:~g from W0 = (S. 2) tn FlguJC .3.2?
`Wh:ll ;, W111'1
`12. Suppo!.C that the inverse matrix, a-•. Jnd thi! gradient vcctc.r. 'V ' are ~pccllicd in the
`foli('Jwing form:
`"' .. l8l
`
`R 1 • [AI Pt J
`Pt
`Pu
`Wnte explicit weight-adJustmeot formul~r, {oY Newton\ method and Cor the .tec-pest·
`descent algorithm.
`13. Suppose that we h:wc the following sp~citkations :
`R -[~ ~]
`Wn1e explicit wctghHidJUStmcnt formul3s for the Newton und stocpat·dc.sccnt a!·
`gorithms, umt, t!qu3Uoru. (4.34) and (43MI Use \he result$ to aplam the nouon ot cross
`coupling.
`14. Using the SteCJ)CM·dCS('ent method wi th iJo = OJ, what ~ r~ the first J\ve wci&ht vectors
`(5,2) .in Figure 3.2'! What is W20!
`beginning from W0 -
`IS. Oivt:n the error burfat-e in Equation tl 44), plot the learning curve for Newton'" method
`when lhe iruttal wcigbts ar~ uro and tbe convergcoce parameter ~ !l = 0.05.
`16. Write 1b" dill'ereo<:c "'luations tlutl dc3Cn1><: the Jeo.rnin& curves for NCW1oo's method und
`the steq>est·de!iC<nt method in term.• of natural coordinate>.
`17. Given the error surfac:e in EQu<1tioo (3.44), plot the lcaming t,.rve for the stccpest·descen1
`mcllJod when the initial weigh~ arc l'.~ro nnd fl = 0.05.
`18. Derive Equation (4 .59) rrorn Equation (4.5~) by carrying out the matnx productS. elemenl
`b) clement.
`19. Explain why I' i.\ dimeiiSlonles~ in (4.32) und has dimeostOilli or reciprocal signal l")Wt:r m
`(4.36).
`
`ANSWERS T O SELECTED EXERCISES
`
`1 1.999)6
`
`1. £ - 0.1(1 .. - 2)1
`2. "1•- 0. '"1 •
`).{), ~ •1.92, .. ., ll'j
`4, 0 < II < 1.25
`s. ,, - l + 10( - 0 2) l '
`"{l_~>_,_4_T_4...;)""( 6_w..:.·!_+_4...:"'•~-_,;..t.3)
`-
`S4wf + 1lw, + 7
`
`7 "'I -I =
`
`.... -
`
`- 42 -
`
`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`~ .. -------------------·
`
`138
`
`Adaptive Algorithms and Structures
`
`Part Ill
`
`lit de •ai.n ver~uS frequency for
`I
`'1. For the uansve.rsal filter sbowo be l?w· plot t te_ am~ u
`.,
`' .
`.. , .. 0 1 and 10 to show how the gaJO changes With "t·
`,
`..,.,
`
`8. Plot tbe three. ph:\SC·Sbift curves for Exercise 7.
`9. A recursive linear system bas the Lransfer function
`
`(a} Draw a filter diagram similar to Figure 7.1.
`(b) P!ot tn~ gain and pbase sbilt versus. frequency.
`(c} Expi::Uo the ploLs in terms of a pok->.ero ploL
`.
`th )j ar (;Q'mbtocr tn EJ<e.tCJSC 7 Wllh wl -
`[
`10. Plot the power gain versus [rcquem:y or e nc
`1 l. Express the impulse r