`
`- i -
`
`Amazon v. Jawbone
`U.S. Patent 11,122,357
`Amazon Ex. 1005
`
`
`
`—s EE”
`
`IN
`
`NUMBER 1
`
`(ISSN 0018-926X)
`
`IN SOCIETY
`
`UNIVERSITY OF CALIFORNIA
`LOS ANGELES
`|
`
`
`
`1AN 20 1982
`
`SCIENCES LIBRARY <g@
`
`
`EINGiNEEKMING &
`MATHEMATICAL
`
`ee ew ee 68 fe
`
`© os eae ee See ee
`
`H. Mieras and C. L. Bennett
`
`5 iia wicdalset ee Hee
`ite Signals iin the Gailfof MOMGO.
`use tale ww adigde eee D. J. Fang, F. T. Tseng, and T. QC. Calvit.
`G. Goubau, N. N. Puri, and F. K. Schwertag.
`giana
`- Pe reW an
`Ming. «a. eas ee L. J.
`Griff
`dé
`L. Grun and ®
`ee
`] Domain Analysis
`..-#++errr tee o tien ws
`ee wT Ko. V. Jamnejad, R. Mittra, and S. W. Lee
`
`,
`
`a
`
`eo
`
`@
`
`eo
`
`oe
`
`#
`
`eee
`
`Lie ee Se SSF
`
`eoweeseee ee
`
`ee
`
`40
`
`27
`35
`
`A
`
`2 of @.
`
`&
`
`- ii -
`
`
`
`> IEEE ANTENNAS AND PROPAGATION SOCIETY
`All membersof the IEEEareeligible for membershipin the Antennas and Propagation Society andwill receive this TRANSACTIONS upon Payment of
`annual Society membership fee of $10.00. For information on joining, write to the IEEEatthe address below.
`ADMINISTRATIVE COMMITTEE
`R. J. MAILLOUX,Vice President
`1983
`1984
`H. E. KING
`S. A. LONG
`C. E. RYAN,JR.
`A.C. NEWELL
`G. H. MILLMAN
`Y. RAHMAT-SAMII
`I. C. PEDEN
`D. H. SCHAUBERT
`Honorary Life Members: E. C. JORDAN, L. C. VAN ATTA
`Committee Chairmen and Representatives
`Committee on Man
`and Radiation: F. L. CAIN
`Council on Oceanic Engineering:
`D. E. WEISSMAN, H. S. HAYRE
`Geoscience and Remote Sensing:
`G.S. BROWN
`Meetings: S. A. LONG
`Membership: D. H. SCHAUBERT
`Newsletter Editor: R. E. MCINTOSH
`
`—,
`
`the
`
`R. E. MCINTOSH,Secretary-TreQS,
`Past Presidents
`A. C, SCHELL
`L. J. RICARDI
`R. C. JOHNSON
`R. C. HANSEN
`
`Nominations: R. C. JOHNSON
`Standards—Antennas. E. S. GILLESPIE
`Standards—Propagation: K. TOMAN
`Publications: J. P.
`SHELTON
`Standards Board: H. V. COTTONY
`PAC Coordinator: W. R. STONE
`Energy Committee:J. F. LINDSEY, R.S. Coup,
`TAB-USAB R&D Committee: W.T. PATTon
`USNC/URSI: A. W. LOVE
`U.S. Activities Board: W. A. IMBRIALE
`
`e
`
`G. A. THIELE, President
`1982
`A. ISHIMARU
`Y.T. Lo
`A. W. Love
`A. J. SIMMONS
`
`Awards and Fellows: A. J. SIMMONS
`Chapter Activities: W.G. SCOTT
`Constitution and Bylaws: R. 1. WOLFSON
`Distinguished Lecturers: R. L. FANTE
`Education and Tutorial: Y.T. Lo
`Finance: R. E. MCINTOSH
`Institutional Listings: G.S. BROWN
`Long Range Planning: R. 1. WOLFSON
`APS-EMCNuclear EMP: C. E. BAUM
`one: on ene implica
`of Technology: D. G. BODNAR
`Albuquerque
`Boston
`S. SINGARAJU
`D. FYE
`Atlanta
`Chicago
`G. SMITH
`B. LEVIN
`Baltimore
`Columbus
`S. STITZER
`P. H. PATHAK
`Benelux
`Dallas
`A. GUISSARD
`E. MCBRIDE
`
`Denver
`G. HUFFORD
`Houston
`S. A. LONG
`Los Angeles
`O. GRAHAM
`
`Chapter Chairmen
`Melbourne
`J. MARA
`Montreal
`R. BELANGER
`Philadelphia
`M.AFIFI
`
`Phoenix
`A. C. BROWN,JR.
`St. Louis
`J. BOGDANOR
`San Diego
`G. VANCE
`Santa Clara/SF
`G. AUGUST
`
`Seattle
`D. K. REYNOLDps
`S. E. Michigan
`V. LIEPA
`Tokyo
`S. ADACHI
`Washington, D¢
`A. CHEUNG
`
`TEEE TRANSACTIONS® ON ANTENNAS AND PROPAGATION
`is a publication devoted to theoretical and experimental advances in antennas including design and development,andin the propagationof electromagneti
`waves includingscattering, diffraction, and interaction with continuous media; and applicationspertinent to antennas and propagation,such as remote sensing
`applied optics, and millimeter and submillimeter wave techniques.
`.
`RAJ MITTRA,Editor
`(See inside back cover)
`Associate Editors
`H. E. KING,Application Notes
`G. H. KNITTEL, Phased Arrays
`C.H. Liv, Propagation
`A. W. LOVE, Reflector Antennas
`
`S. ADACHI, International Editor
`W-M. BOERNER,Inverse Scattering
`G.S. BROWN,Geophysical Scattering
`C.M. BUTLER, Tutorial
`—
`R. L. FANTE, Propagation
`
`L. W. PEARSON, Transients
`R. J. POGORZELSKI, EM Theory
`Y. RAHMAT-SAMII, Reflectors and HF Technique
`D. L. SENGUPTA, Numerical Methods
`D. R. WILTON, Analytical and Numerical Method.
`THE INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, INC.
`Officers
`ROBERT E. LARSON,President
`JAMES B. OWENS,President-Elect
`THELMAA.ESTRIN,Executive Vice President
`CHARLES A. ELDON,Treasurer
`Dick C. J. POORTVLIET, Secretary
`
`EDWARDW.ERNST,Vice President, Educational Activitie.
`EDWARDJ. DOYLE,Vice President, Professional Activities
`G. P. RODRIGUE,Vice President, Publication Activities
`HANSC. CHERNEY,Vice President, Regional Activities
`JOSE B. Cruz, JR., Vice President, Technical Activities
`ALLANC. SCHELL, Division IV Director
`
`Headquarters Staff
`ERIC HERZ, Executive Director and General Manager
`ELWoopK. GANNETT,Deputy General Manager
`THOMAS W.BARTLETT,Controller
`DONALDL. Suppers, StaffDirector, Field Services
`DONALD CHRISTIANSEN,Editor ofSpectrum
`SAVA SHERR, StaffDirector, Standards
`renee
`IRVING ENGELSON,StaffDirector, Technical Activities
`EMILYL. SIRJANE,StaffDirector, Corporate Services
`LEO FANNING,StaffDirector, Professional Activities
`CHARLES F. STEWART,JR., StaffDirector, Administration Service.
`ELWoopK. GANNETT,Acting StaffDirector, Publishing Services
`JOHN F. WILHELM,StaffDirector, EducationalServices
`Publications Department
`H. JAMES CARTER,Associate StaffDirector,
`Production Managers: ANN H. BURGMEYER*, CAROLYNE ELENOWITZ,GAILS. FERENC, ISABEL NAREA
`Associate Editors: MARY E. GRANGEIA, THOMAS R. GRECO, ELAINE A. MAROTTA,JEFFREY B. MARTIN, EVELYN C. NORMAN,
`BARBARAA. SOMOGYI
`* Responsible for this TRANSACTIONS
`IEEE TRANSACTIONS ON ANTENNAS ANDPROPAGATIONis published bimonthly by TheInstitute of Electrical and Electronics Engineers, Inc. Head
`quarters: 345 East 47 Street, New York, NY10017. Responsibility for the contents rests uponthe authors and not upon the IEEE,theSociety, or its members
`IEEEService Center (for orders, subscriptions, address changes, Region/Section/Student Services): 445 Hoes Lane, Piscataway, NJ 08854. Telephones:
`Headquarters 212-644 + extension; Information -7900, General Manager -7910, Controller -7748, Educational Services -7860, Publishing Services -7560
`Standards -7960, Technical Services -7890. IEEE Service Center 201-981-0060. Professional Services: Washington Office 202-758-0017. NY Telecopier
`212-752-4949. Telex: 236-411 (International messages only). Individual copies: IEEE members $6.00 (first copy only), nonmembers $12.00per copy. Annua
`subscription price IEEE members, dues plus Society fee. Price for nonmemberson request. Available in microfiche and microfilm. COPYRIGHT AND
`REPRINTPERMISSIONS: Abstractingis permittedwithcredit tothesource. Libraries are permitted to photocopy beyondthe limitsofU.S. Copyright
`Lawfor private use of patrons: (1) those post-1977 articles that carry a code at the bottom ofthe first page, provided the per copyfee indicated in the code
`is paid through the Copyright Clearance Center, 21 Congress Street, Salem, MA 01970;(2) pre-1978 articles withoutfee. Instructors are permitted to photocopy
`isolated articles for noncommercial classroom usewithoutfee. For other copying, eaor republication permission, write to Director, PublishingServices
`at IEEE Headquarters.All rights reserved.Copyright © 1981 by TheInstitute of Electrical and Electronics Engineers,Inc. Printed in U.S.A. Second-class
`postage paid at New York, NY andatadditional mailing offices.
`
`- iii -
`
`
`
`IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION,VOL. AP-30, NO. 1, JANUARY1982
`An Alternative Approach to Linearly Constrained Adaptive Beamforming
`
`27
`
`LLOYDJ. GRIFFITHS, senior MEMBER, IEEE, AND CHARLES W. JIM
`
`Abstract—A beamformingstructure is presented which can be used
`to implement a wide variety of linearly constrained adaptive array
`processors. The structure is designed for use with arrays which have
`been time-delay steered such that
`the desired signal of interest
`appears approximately in phase at the steered outputs. One major
`advantage of the new structure is the constraints can be implemented
`using simple hardware differencing amplifiers. The structure is shown
`to incorporate algorithms which have been suggested previously for
`use in adaptive beamforming as well as to include new approaches. It
`is also particularly useful for studying the effects of steering errors on
`array performance. Numerical examples illustrating the performance
`of the structure are presented.
`
`INTRODUCTION
`
`HIS PAPER describes a simple time-varying beamformer
`which can be used to combine the outputs of an array of
`sensors. The beamformeris constrainedtofilter the “‘desired”’
`signal with a filter having a prescribed gain and phase response.
`The ‘“‘desired” signal is identified by time-delay steering the
`sensor outputs so that any signal incident on the array from
`the direction of interest appears as an identical replica at the
`outputs of the steering delays. All other signals received by the
`array which do not have this property are considered to be
`noise and/or interference. The purpose of the beamformeris
`to minimize the effects of noise and interference at the array
`output while simultaneously maintaining the prescribed fre-
`quency responsein the direction of the desired signal.
`Beamformers of this type are termedlinearly constrained
`array processors and have been studied by several authors
`including Levin [1], Lacoss [2], Kobayashi [3], Booker and
`Ong [4], Frost [5], and Applebaum and Chapman [6]. The
`last
`five of these authors describe iterative or continuously
`adaptive beamformers in which the beamforming coefficients
`adjust to new values as each new set of samples of array sensor
`outputs are received. Adaptive methods are of particular
`interest in those problems in which the interference properties
`are either spatially or temporarily time varying.
`The purpose of this paper is to present the linearly con-
`strained adaptive algorithm, due to Frost [5], using an alter-
`native beamforming model. This presentation illustrates the
`fundamental properties of the algorithm in an exceedingly
`simple fashion. It also allows for generalizations not available
`with Frost’s method. The basic structure of the beamforming
`model has been suggested by Applebaum and Chapman[6].
`In this paper we describe the structure in detail and give exact
`algorithm comparisons for a variety of linearly constrained
`
`Manuscript received May 19, 1980; revised March 5, 1981. This
`work was supported in part by the Office of Naval Research, Washing-
`ton, DC, under Contract NO0014-77-C-0592 and by the Electronics
`System Division (AFSC), Hanscom AFB, MA under Subcontract
`14029 with SRI International, Menlo Park, CA.
`L. J. Griffiths and C. W. Jim are with the Departmentof Electrical
`Engineering, University of Colorado, Boulder, CO 80309.
`
`beamformers. The structure is shown to be a direct conse-
`quence of Frost’s method. One major advantage of our ap-
`proachis an assessment of the performance degradation caused
`by the steering and/or gain errors in the array sensors. In most
`practical situations the theoretically ideal requirement of an
`“identical replica” of the desired signal, at the output of each
`steering delay, is seldom met. The effects of these errors on
`overall beamformer performance is easily modeled using our
`approach. For example,
`it is shown that
`these effects are
`particularly detrimental under conditions of high signal-to-
`noise ratio (SNR).
`A second reason for this presentation is to enumerate cer-
`tain difficulties which may arise with the use of constrained
`adaptive array processors which do not
`incorporate Frost’s
`error-correction feature. Of
`the papers referenced above,
`four (see [2]-[4] and [7]) use an algorithm based on the
`gradient projection approach [8].
`(Levin’s approach was
`nonadaptive and utilized matrix inversion techniques.)
`In this paper wefirst review Frost’s algorithm whichis not
`susceptible to roundoff error and requires relatively few addi-
`tional computations per adaptive cycle. A simple geometric
`interpretation illustrating the effects of roundoff errors on his
`algorithm and on gradient projection is presented. The error-
`correcting properties of the approachare identified using this
`illustration.
`
`We then showthat the algorithm can be interpreted using a
`new beamforming model, termed the adaptive sidelobe cancel-
`ing beamformer. This structure illustrates the constraint fea-
`tures of the algorithm and shows how additional constraints
`can be added. Theerror-correcting features are also elucidated.
`Sidelobe canceling is shown to be closely related to the method
`of adaptive noise canceling described by Widrow et al. [9].
`As a consequenceresults derived in adaptive noise canceling
`can be applied directly to the linearly constrained adaptive
`beamformer.
`
`LINEARLY CONSTRAINED ADAPTIVE BEAMFORMING
`
`We denote the sampled output of the mth time-delayed
`sensor by x,,(k). A total of M sensors are assumed to be
`present in the assumptions of ideal steering:
`
`Xm(k) = 8(k) + nm(k).
`
`(1)
`
`In this expression s(k) is the desired signal and n,,(k) repre-
`sents the totality of noise and interference observed at the
`output of the mth steered sensor. A beamformed output
`signal y(k) is formed as the sum of delayed and weighted
`Xm(k). Specifically,if ay, ; is used to represent the weight used
`for the mth channel at delay /, then
`M
`K
`x)= DY D am,em(k—D.
`m=] -K
`
`(2)
`
`0018-926X/82/0100-0027$00.75 © 1981 IEEE
`
`-27 -
`
`- 27 -
`
`
`
`28
`
`IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION,VOL. AP-30, NO. 1, JANUARY1985
`
`Note that a total of 2K + 1 samples are used from each chan-
`nel and that the zero timereferenceis at the filter midpoint.
`Matrix notation can be used to simplify this notation. We
`let A; and X(k — J) represent the filter coefficient and signal
`vectors at the /th delay point, i.e.,
`(3)
`Ay” =[a1,1, 42,17" ¢m,1]
`(4)
`XT—D=[x1 (K-92 — 9, yxm(k — 2)
`where superscript T denotes transpose. The outputsignal of
`(2) then becomes
`
`K
`y= YY aOXK—D.
`ELK
`
`(5)
`
`Under the ideal steering assumption in (1), the signal vector
`x(k — 1) becomes
`
`X(k-—D)= s&-DL+NE—-D)
`
`(6)
`
`where 1 is a column vector of M ones and N(k — /)is a vector
`of noise and interference defined in a manner analogous to
`(4).
`Prescribed gain and phase response for the desired signal is
`ensured by constraining the sums of channel weights at each
`delay point to be specific values. Thusif f(I) is used to denote
`the sum for the set of weights at delay / then
`
`AT()1 =f.
`
`7
`
`Underthis constraint the portion of the output due to desired
`signal reduces to
`K
`Y= DY fOsk—D.
`EK
`
`(8)
`
`\
`
`} Thus the f(J) represent the impulse response of a finite-dura-
`tion impulse-response (FIR) filter having length 2K + 1. One
`commonly used constraint is that of zero distortion in which
`f@ = 5), where 6(J) is the discrete impulse function. The
`FIR filter constraint function is normalized such that
`
`F71=1,
`
`FT =(f(-k), -, (kD).
`
`(9a)
`
`(9b)
`
`The objective of linearly constrained adaptive beamforming
`is then to find filter coefficients A(/) which satisfy (7) and
`simultaneously reduce the average value of the square of the
`output noise component. This is equivalent to finding those
`coefficients which result
`in minimum output noise power
`subject
`to the constraint of the prescribed desired signal
`filtering.
`In adaptive beamforming the filter coefficients are time
`varying and change as each new set of samples of sensor out-
`puts is received. Thus if A,(k) is used to denote the values at
`time k the values at the next sampling instant k + 1 are com-
`puted as
`
`this paper we are concerned with Frost’s procedure [5], in
`which
`
`Aik) = wy) ax(k — D1 — Xk — 9)
`1
`— aa,i(k) + =AU)
`
`and
`
`1
`
`ax(k—D=OXME-DI
`
`(11)
`
`(12)
`
`1
`
`(13)
`da,i(k) = Atwl
`The adaptive step size u is a scalar which controls both the
`convergence rate and steady-state noise behavior of the algo-
`rithm [9] and is normalized by the total power contained in
`the beamformer. Thus
`
`Qa
`=
`P Pk)
`M
`K
`P= D Dy xm2k—D.
`m=1 1=-K
`
`(14)
`
`(15)
`
`Convergence of either algorithm is assured if 0 <a < 1.
`Other power estimates involving time averaging may be em-
`ployed without significantly affecting performance.
`Frost’s procedure differs from that used in gradient projec-
`tion [7] by the addition of the last two terms in (11). These
`terms involve a total number of additional (2K + 1)M adds
`and 2K + 1 multiples. They are necessary, however, in that
`they prevent the accumulation of computational errors which
`may occur on anyiteration of the algorithm.
`
`Error Effects in Linearly Constrained Beamforming
`The effects of errors may beillustrated by examining the
`constraints (7) for the adaptive algorithm in (10) and (11).
`We assume that in the algorithm implementation, the com-
`putation of the signal sum q,(k — J) and the weight sum
`aq (kK) in (13) introduced the followingerrors:
`
`1
`
`ax(k —I = we& —1N)1+ e,(k)
`
`9a,(k) =
`
`[Ai7(k)l + €a(K)]
`
`(16a)
`
`(16b)
`
`or equivalently, the current weight vector A,(k) is presumed
`to be slightly off the constraint,i.e.,
`
`A?(k)1= 0) + €4 (k).
`
`(16c)
`
`The degree to which the next weight vector fails to meet
`the constraint can then be computed bysolving for 4;’(k +
`1)1 in (10) and (11). Thus, using (16),
`
`Adk + 1) = Aik) + Ax)
`
`(10)
`
`AP(k +11 =f+ €a(k) + uM(Rex)
`
`where A,(k) is determined by the specific algorithm in use. In
`
`+ {902 - €4(k) + sO}.
`
`q7)
`
`- 28 -
`
`- 28 -
`
`
`
`The terms enclosed in {+} are produced by error correction
`position of Frost’s algorithm while the first three are due to
`the gradient projection operator. Thus if a gradient projection
`adaptation algorithm is employed—as wasthe case in [2]-[4]
`and [7]—theconstraint error at step k +1is
`
`29
`
` GRIFFITHS AND JIM: LINEARLY CONSTRAINED ADAPTIVE BEAMFORMING
`
`a (k + 1) = €4(k) + uMy(kKex(k)
`
`(18)
`
`and with Frost’s procedure
`
`€4(k + 1) = wMy(k)ex(k).
`
`(19)
`
`The cumulative error effects of gradient projection ob-
`served by Shen [7] are due to the first-order difference rela-
`tionship in (18). If we assume that the driving term uM,(k)
`€,(k)
`can be modeled as a zero-mean white random process
`with variance G,”, and that €,(0) = 0, then the gradient
`projection constraint error (18) is a Brownian motion [10] or
`random walk process. Although the mean of the error remains
`zero, its variance 047(k) grows linearly with the numberof
`steps,i.e.,
`
`047 (k) =ko,?
`
`(20a)
`
`for gradient projection. With the correction terms, however,
`the error at each step has constantvariance at each iteration,
`
`G47(k) =a".
`
`(20b)
`
`A simple geometric interpretation [5] can also be given for
`these effects. Consider
`the geometry associated with the
`gradient projection algorithm shown in Fig. 1. Coefficient
`vectors meeting the desired constraint mustlie on the planar
`subspace C defined by the vector F(9b). It is assumed that the
`coefficient vector Aj;(k) at
`time k is too long and that the
`gradient vector produced by the datais g,(k) given by
`
`Bik) = wy (K)X(K — 2).
`
`(21)
`
`In the gradient projection method the new coefficient vector
`Aj,(k) is obtained by finding the projection of g)(k) in the
`direction of the plane C, and then by adding this projection
`to the previous vector. As shown by Fig. 1 the resulting new
`coefficient vector will not lie on the constraint plane, even
`with an error-free projection operation.
`Fig. 2 illustrates the geometry for Frost’s approach. In
`this case the new coefficient vector is found by projecting the
`sum of the former vector and the gradient in the direction of
`the constraint plane C. The new coefficient vector Aj,(k) is
`then the sum of this projected vector and the vector F, which
`defines C. As shown in the diagram the new coefficients will
`lie on the constraint plane regardless of the previous error
`provided that the projection operation is error free. The net
`error induced by this methodis then restricted to the machine
`quantization error of a single projection operation and accu-
`mulation does not occur.
`
`GENERALIZED SIDELOBE CANCELING MODEL
`
`The linearly constrained adaptive algorithm defined by
`(10)}(13) may be implemented using the structure shown in
`Fig. 3. Time-delay steering elements 71 , 72, “*, Tag are used to
`point the array in the direction of interest. We will refer to
`this implementation as the direct form. Each coefficient in
`
`
`
`
`
`Fig. 1. Geometrical
`
`interpretation for gradient projection adaptive
`algorithm.
`
`linearly constrained error-
`interpretation for
`Fig. 2. Geometrical
`correcting adaptive algorithm.
`
`sensor
`number
`
`[LINEARLY -CONSTRAINED)
`ADAPTIVE ALGORITHM
`
`Fig. 3. Direct form implementation of linearly constrained adaptive
`array processing algorithm.
`
`the beamformer is updated by the adaptive processor, which
`computes new values using the algorithm. An alternative
`implementation which achieves precisely the same overall
`processor can be derived in a simple mannerdirectly from this
`algorithm. The resulting structure is termed the generalized
`sidelobe canceling form and is depicted in Fig. 4.
`This processor consists of two distinct substructures which
`are shownas the upper and lowerprocessing paths. The upper
`or conventional beamformer path consists of a set:of fixed
`amplitude weights w.1, We2,
`‘*; Wear which produce non-
`adaptive-beamformed signal y,(k),
`Yolk) = We"X(k)
`where
`
`(22)
`
`WwW." =[We1, We2,°, Wem).
`
`(23)
`
`This conventional array beamforming system is identical
`to that traditionally used to process sensor array outputs with
`
`- 29 -
`
`- 29 -
`
`
`
`30
`
`sensor
`number
`
`IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION,VOL. AP-30, NO. 1, JANUARY198)
`
`where X’ and A’ are the M — 1 dimensional signal and coeffj.
`cient vectors.
`The overall output of the generalized sidelobe canceling
`structure y (k)is
`
`Yo (*)
`
`¥(k) = ye'(k) — v4 &).
`
`(29)
`
`
`FIXED F(t)
`
`CONSTRAINTS
`VTapreo
`
`WWDAPTIVE ALGORITHM
`_ UNCONSTRAINED, _
`
`
`
`
`
`TAPPED
`DELAY
`
`TAPPED
`DELAY
`
`vq tk)
`
`Because y4(k) contains no desired signal terms, the response
`of the processor to the desired signal s(k)1 is that produced
`only by y,'(k). Thus from (22)-(25) the output due to the
`presence of only the desired signal satisfies the constraint
`defined by (9), regardless of W,. In addition, since y»4(k)
`contains only noise and interference terms, finding the set of
`filter coefficients A;(k) which minimize the power contained
`in y(k) is equivalent to finding the minimum variance,lin-
`early constrained beamformer. The unconstrained least-mean-
`square (LMS) algorithm [12] can be employed to adapt the
`filter coefficients to the desired solution,
`
`(30)
`Ay'(k) = Ark) + Bx(®)X'& — 2.
`The step size y is normalized by the total power containedin
`the X'(k — 2) using methods analogous to those described
`above.
`The algorithm in (30), together with conditions (24) and
`(27), completely defines the operation of the generalized side-
`lobe canceling structure. Although it
`is not obvious,
`this
`structure can provide exactly the samefiltering operation as
`the constrained beamformer in Fig. 3, which uses Frost’s
`algorithm. In addition, it can also provide filtering operations
`which are not the same as Frost’s procedure. The key lies
`with the structure of the blocking matrix W, and the conven-
`tional beamformer W,. If the rows of W, are orthogonal (in
`addition to satisfying (27)) and if all conventional beamformer
`weights equal 1/M,
`then Frost’s method is obtained. Non-
`orthogonal
`rows and/or other conventional beamformers
`produce a processor having the same steady-state performance
`in a stationary environment, but one which uses a different
`adaptive trajectory.
`the con-
`The generalizedsidelobe canceler separates out
`straint as element W, and an FIRfilter. In addition, it provides
`a conventional beamformer as an integral portion of its struc
`ture. Coefficient adaptation is reduced to its simplest possible
`form: the unconstrained LMS algorithm.
`
`Relationship with Linearly Constrained Beamforming
`The structure of the generalized sidelobe canceler can
`readily be related to the adaptive linearly constrained beam-
`former. We begin by defining an invertible M X M matrix T as
`
`—
`
`|W7=("e |—W,
`
`(31)
`
`The inverse of Tis guaranteed forWc and W; satisfying (24)
`and (27). In addition, the product 71 is a simple unit vector,
`
`(32)
`T1=[]1, 0, 0, --, 0]7.
`Multiplying Frost’s algorithm bythis invertible transformation
`yields
`
`By(k + 1) = Bk) + uve )Lax(k — DTI — TX(K — 1)
`
`1
`_
`—4a,4E)TI + =0071.
`
`(33)
`
`|
`
`
`
`|
`
`Fig. 4. Generalized sidelobe canceling form oflinearly constrained
`adaptive array processing algorithm.
`
`fixed nonadaptive coefficients. In typical applications the
`weights W, are chosen so as to trade off the relationship be-
`tween array beamwidth and average sidelobe level
`[11].
`(One widely used method employs Chebyshev polynomials
`to find the W,.) For the purpose of this paper, however, any
`method can be used to choose the weights as the performance
`of the overall beamformer will be characterized in terms
`of the specific values chosen. (All w,; are assumed nonzero.)
`In order to simplify notation the coefficients in W, are nor-
`malized to have a sum of unity. That is
`
`W.71=1.
`
`(24)
`
`The signal Ve'(k) is obtained by filtering y,(k) and the FIR
`operator containing the constraint values f(/),
`K
`y= DY sOvck—D.
`i=-K
`
`(25)
`
`\)
`
`The lower path in Fig, 4 is the sidelobe canceling path.
`It consists of a matrix preprocessor W, followed by a set of
`tapped-delay lines, each containing 2K + 1 weights. The pur-
`pose of W, is to block the desired signal s(k) from the lower
`path. Since s(k) is common to each of the steered sensor
`outputs (1) blocking is ensured if the rows of W, sum up to
`zero. Specificallyif X'(k) is used to denote theset of signals
`at the output of W,, then
`
`X'(k) = WsX(K).
`
`(26)
`
`In addition, if b,,7 is used to represent the mth row of Ws,
`werequire that the by? satisfy
`
`bn 1=0,
`
`for all m,
`
`(27)
`
`and that the b,, are linearly independent. As a result X'(k)
`can have at most M — 1 linearly independent components.
`Equivalently, the row dimension of W, must be M — 1 orless.
`The lower path of the generalized sidelobe canceler gen-
`erates a scalar output y,(X) as the sum of delayed and weighted
`elements of X'(k). Following the notation used to describe
`the linearly constrained beamformer,
`K
`yakk)= DY [Al@I7X'&—-9,
`m—K
`
`(28)
`
`- 30 -
`
`- 30 -
`
`
`
`f GRIFFITHS AND JIM: LINEARLY CONSTRAINED ADAPTIVE BEAMFORMING
`
`31
`
`The transformed weight vector B,(k) can be partitioned in a
`manner analogousto (31) as follows
`
`br (k
`
`Bxk)= EOT.
`
`B; (k)
`
`(34)
`
`With this partitioning, and (32), the transformed algorithm
`(33) is recognized as two algorithms: one in the scalar b;'(k)
`and onein the M — 1 dimensional vector B,'(k),
`
`br(k + 1)=5/'(k) + w(Kaxe —D—yeK—D]
`
`By(k + 1) = By(k) + wy()X'(k —D.
`
`(35a)
`
`(35b)
`
`These equations may be viewed as an alternative imple-
`mentation of Frost’s procedure. Since T is invertible, the out-
`put »(k) may be expressed as
`x
`y= DD [TBATXK 2.
`iB-K
`
`(36)
`
`Thus if-(35) is used to update the B,(k) and the outputis
`computed using (36), this procedure is indistinguishable from
`the original. Many more computations would be required,
`however, and the transformed system offers no advantages.
`We now consider the simplification which arises when T is
`an orthogonal transformation, i.e., when T~! = [7 The out-
`put equation (36) simplifies to
`
`that this is a sufficient condition only, and necessity has not
`been considered.
`Jim [13] has studied the comparison in detail and shown
`that steady-state performance of the twoprocessors is identi-
`cal regardless of the structure of W, and W,g, provided that the
`system operates at full rank. He has also shownthatdifferent
`eigenvalue spectra will be encounteredby the adaptive filters
`in the two systems unless W, and Ws, meet
`the sufficient
`equality conditions previously described. As a result the coeffi-
`cient trajectories and adaptive learning curves will differ.
`
`PROPERTIES AND EXTENSIONS OF ADAPTIVE
`CONSTRAINED BEAMFORMERS
`
`The previous section has presented a generalized sidelobe
`canceling structure which can be used to implementtheerror-
`correcting linearly constrained adaptive algorithm in (10)-(12).
`This structure can also be used to both analyze the perform-
`ance of the algorithm and to suggest generalizations. of con-
`strained beamforming. We begin by summarizing the perform-
`ance characteristics of the algorithm which are readily delin-
`eqted by the sidelobe canceling model. These properties are
`then used to extend the concept of linearly constrained adap-
`tive beamforming and to develop new methodsforuse in array
`processing.
`in the sidelobe canceler is the signal-
`One key element
`blocking matrix W,. As shown by (27), this matrix is required
`to have M — 1
`linearly independent rows which sum up to
`zero, Of the many matrices which can be generated with this
`property, two possibilities which involve only addition opera-
`tions are shown below for the case M = 4:
`
`K
`yk)= DP o/®yck-)
`eK
`
`K
`— D [8@)17X«—3.
`r-K
`
`Inspection of (35)-(37) shows that the transformed linearly
`constrained beamformerin this case is identical to the adap-
`tive-sidelobe canceling beamformer, provided that the b, (k)
`satisfy
`
`bk) = £0,
`
`(38)
`
`~
`
`for all values of k. Since the b;(k) must satisfy (35a), this
`will occur only if they are initialized to the values in (38) and
`if
`
`ax(k —1) = y-(k — 2).
`
`This condition is equivalent to the requirementthat
`
`1
`W. =~—1
`M
`
`(39)
`
`(40)
`
`that all beamformer weights have equal
`
`‘ or, equivalently,
`values of 1/M.
`In summary the above discussion has shown that the adap-
`' tive-sidelobe canceler will be identical to Frost’s algorithm
`provided that the conventional weights satisfy (40) and that
`T is an orthogonal transformation. (From (31) and (4), this
`: Jatter condition is equivalent to requiring that the rowsof Wy
`‘ sum up to zero and be mutually orthogonal.) It is to be noted
`
`WoO=]1 -1 -1
`1
`-l
`1
`
`(37)
`
`—1
`1
`1
`
`Wi Y=
`
`1
`]/o0
`0
`
`-l
`
`0
`
`0
`0
`-1 0
`1
`1
`
`(41)
`
`(42)
`
`In the first matrix the rows are mutually orthogonal and are
`elements of the binary-valued Walsh functions [14]. The
`second matrix involves fewer operations and consists of taking
`the difference between adjacent sensor outputs.
`One can interpret
`the rows of W, as fixed-weight beam-
`formers which are applied to the sensor outputs. The beam-
`formed signals are then the elements of X'(k) and the con-
`straints in (27) ensure the presence of a spatial null in the
`broadside direction for each beamformer. Note that w,? has
`a_ different spatial amplitude response for each row while
`W,) has identical patterns.
`The effects of imperfect sensor steering and/or gain varia-
`tions are easily modeled using the generalized sidelobe cancel-
`ing structure. For example, gain differences at the outputs
`of the time-delayed sensors result in a set of received signals
`Xm (t) given by
`
`Xm(t) = s(0)(1 + Em) + mm (t)
`
`(43)
`
`represents the gain departure from unity at the mth
`where €,,
`sensor output. Because of the nonzero e¢,,, the desired signal
`
`- 31 -
`
`- 31 -
`
`
`
`IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION, VOL. AP-30, NO. 1, JANUARY 1987
`sensor
`
`32
`
`appears in both the conventional beamformer output y(t) and
`in the sidelobe canceling path. The presence of desired signal
`in the adaptive filters has been termed “signal leak through”
`by Widrow et al. (9], and mayresult in signal distortion and/
`or reduction in output SNR. The distortion is due to the fact
`that the scalar y,4(k) contains a weighted sum of delayed-
`desired signal terms. It can be demonstrated, however, that
`these effects are negligible provided that the power level of
`the signal leak through is small compared with the power
`containedin thefiltered noise vector N'(k). Equivalently,if
`
`G,2 tr{WsReeWs?} <tr WsRynWs”
`
`(44)
`
`where Os is the power level of the desired signal observed at
`a sensor output, tr {-} denotes trace, and R,_ and Ryy are
`the autocorrelation matrices for the vector of gain errors €
`and the received noise vector N(K), respectively. For the case
`of uncorrelated, equal variance, gain errors, and white receiver
`noise, the result simplifies to
`
`number
`
`0
`
`200
`
`400
`sample number
`
`600
`
`800
`
`2
`Os
`Oe" a <€1
`On
`
`Fig. 5. Synthetic sensor outputs used to demonstrate algorithm per-
`formance.
`
`(45)
`
`where 6,2 and On? are the variance of the gain errors and
`white receiver noises. This result demonstrates a well-known
`property of constrained beamformers,i.e., that the system is
`much more sensitive to gain errors at high input signal-to-noise
`ratios.
`New methods of adaptive beamforming are suggested by
`the generalized sidelobe canceling structure illustrated in Fig.
`4. These include the following.
`1)Additional spatial constraitits can be incorporated into
`the W, matrix. For example, one can require both a spatial
`null in the desired direction (as in the system discussed above)
`and a zero derivative in that direction. The matrix Ww, for
`M = 4 achievesthis result:
`
`_
`Ww,
`
`12 100
`
`o 1-21
`
`.
`
`(46)
`
`Note that the row dimension in this case is M — 2 due to the
`additional spatial constraint. The system sensitivity to point-
`ing errors (time-delay steering errors), however, is markedly
`reduced.
`2) Combined spatial/temporal constraint beamformers are
`achieved by including delay-storage elements in the W, matrix.
`Equivalently,
`
`N
`X