United States Patent (19)
`Duttweiler
`
`USO05566167A
`(11) Patent Number:
`(45) Date of Patent:
`
`5,566,167
`Oct. 15, 1996
`
`(54) SUBBAND ECHO CANCELER
`75) Inventor: Donald L. Duttweiler, Rumson, N.J.
`73) Assignee: Lucent Technologies Inc., Murray Hill,
`N.J.
`
`"Adaptive Filtering in Subbands with Centical Sampling:
`Analysis, Experiments, and Application to Acoustic Echo
`Cancellation”, Gilloire et al., 1992, pp 1862-1875.
`"Numerical Recipes in C", Press et al. 1988, pp. 394-420.
`
`(21) Appl. No.: 368,687
`22 Filed:
`Jan. 4, 1995
`(51) Int. Cl. ........................ HO4B 3/21
`(52)
`370/32.1; 379/411; 379/410
`58) Field of Search ................................ 370/32.1, 100.1,
`370/32; 379/406, 410, 407,408,409, 411;
`333/18, 28 R; 364/724.01, 724.19, 728.03;
`381/71, 63, 64; 375/220, 229, 230, 232,
`227, 254, 354, 355, 356, 358, 349,350,
`209, 210
`
`56
`
`References Cited
`U.S. PATENT DOCUMENTS
`3,500,000 3/1970 Kelly, Jr. et al. ....................... 379/410
`5,136,577
`8/1992 Amano et al. ......
`370/32.1
`5,272,695 12/1993 Makino et al. ........................ 370/32.
`5,351,291
`9/1994 Menez et al. .......................... 370/32.1
`5,428,605 6/1995 André ..................................... 370/32.1
`OTHER PUBLICATIONS
`"A Twelve-Channel Digita Echo Canceler', Duttweiler,
`1978, pp 647–653.
`"A New Technique for the Design of Non-Recursive Digital
`Filter', Hofstetter et al. pp 64-72.
`
`
`
`Primary Examiner-Douglas W. Olms
`Assistant Examiner Dang Ton
`Attorney, Agent, or Firm Thomas Stafford
`
`ABSTRACT
`57
`Failure to cancel echos at frequencies in which the fre
`quency characteristics of sub-band filters in the X and Y
`analysis filter banks overlag in subband echo cancelers is
`overcome by employing an X-analysis filter bank in which
`the pass-band of the subband filters is wider than the
`pass-band of the corresponding subband filters in the
`Y-analysis filter bank. This insures that there is sufficient
`energy in the tap delay lines of the adaptive filters in the
`subband echo cancelers at all frequencies where echos are to
`be synthesized. More specifically, the keeping of sufficient
`energy in the tap delay lines of the adaptive filters in the
`subband echo cancelers avoids exciting eigenmodes associ
`ated with the small eigenvalues of the correlation matrix.
`
`19 Claims, 6 Drawing Sheets
`
`E
`SYNTHESIS
`FILTER
`
`107-m
`
`|
`
`x-(s
`TRANSYERS
`FILTER
`5-(s)
`
`SAMPNG
`
`DOWN
`SAMPLNG
`
`DOWN
`SAMPLING
`
`FILTER
`BANK
`
`LGE EXHIBIT NO. 1017
`
`- 1 -
`
`Amazon v. Jawbone
`U.S. Patent 8,467,543
`Amazon Ex. 1017
`
`

`

`SISATYNYA
`
`Yad
`
`yas
`
`Nx
`
`wai
`
`TEIN
`
`SIS3HINAS|()2
`
`TWSYIASNVUL
`TWSUSASNVULtT
`[Liavsnasur|
`
`U.S. Patent
`U.S. Patent
`
`
`
`Oct. 15, 1996
`
`Sheet 1 of 6
`
`5,566,167
`5,566,167
`
`LOld
`
`0-201
`
`
`
`_MATAONVOOHI3
`
`J
`
`NIGAVS
`
`valid
`
`9. ||
`
`- 2 -
`
`
`

`

`U.S. Patent
`
`Oct. 15, 1996
`FIC. 2
`
`Sheet 2 of 6
`
`5,566,167
`
`FREQUENCY
`
`FIC. 3
`
`113
`
`p
`
`S
`
`FREQUENCY
`
`
`
`- 3 -
`
`

`

`U.S. Patent
`
`Oct. 15, 1996
`
`Sheet 3 of 6
`
`5,566,167
`
`FIG. 5
`
`502-0
`
`50-0
`
`FIG. 6
`
`
`
`
`
`602
`
`
`
`603
`
`604
`
`605
`
`COMPUTE
`Zs = R(zp(N)
`FIND X MINIMIZING
`
`DID X CHANGE
`APPRECIABLY THIS PASS
`
`- 4 -
`
`

`

`5,566,167
`5,566,167
`
`U.S. Patent
`U.S. Patent
`
`
`
`Sheet 4 of 6
`Oct. 15, 1996
`Sheet 4 of 6
`Oct. 15, 1996
`FIG. 7
`
`FIG. 7
`
`- 5 -
`
`

`

`US. Patent
`U.S. Patent
`
`Oct. 15, 1996
`Oct. 15, 1996
`FIC. 9
`FIG. 9
`
`Sheet 5 of 6
`Sheet 5 of 6
`
`5,566,167
`5,566,167
`
`
`
`OOOODIO0000
`
`
`
`
`- 6 -
`
`

`

`U.S. Patent
`U.S. Patent
`
`Oct. 15, 1996
`Sheet 6 of 6
`Oct. 15, 1996
`Sheet 6 of 6
`FIC, 1 O
`FIG. 10
`
`5,566,167
`5,566,167
`
`
`
`O
`
`O
`Qo
`O
`O
`O
`O
`
`O ® O O O O O O
`
`O
`O
`CP
`on
`O
`
`- 7 -
`
`

`

`1
`SUBBAND ECHO CANCELER
`
`5,566,167
`
`TECHNICAL FIELD
`This invention relates to echo cancelers and, more par
`ticularly, to Subband echo cancelers.
`
`5
`
`2
`FIG. 3 is a graphical representation of more practical
`frequency characteristics of the X and Y filters used in the
`X and Y analysis filter banks of FIG. 1;
`FIG. 4 shows, in simplified block diagram form, details of
`the X analysis filter bank of FIG. 1;
`FIG. 5 shows, in simplified block diagram form, details of
`the E synthesis filter bank of FIG. 1;
`FIG. 6 is a flow chart illustrating the steps of the Z-plane
`alternation design procedures;
`FIG. 7 graphically illustrates a typical stopband zero
`pattern for a filter design with Zs even;
`FIG. 8 graphically illustrates a typical stopband zero
`pattern for a filter design with Zs odd;
`FIG.9 shows a small section of the Z complex plane unit
`circle illustrating zeros for the Y filters in the Yanalysis filter
`bank of FIG. 1; and
`FIG.10 shows a small section of the Z complex plane unit
`circle illustrating zeros for the X filters in the X analysis
`filter bank of FIG. 1.
`
`DETALED DESCRIPTION
`
`SUBBAND ECHO CANCELER
`FIG. 1 shows, in simplified block diagram form, details of
`a subband echo canceler 100 in which the invention can be
`employed. It is noted that the processing of the signals is in
`digital form and that any analog-to-digital and digital-to
`analog converters are not shown. Specifically, a received
`signal x(k) is supplied via received path 101 to echo path
`102 and Xanalysis filter bank 103. An outgoing voice signal
`v(k) is combined via summer 104 with an echo signal from
`echo path 102 to form outgoing near-end signal y(k). It is
`noted that echo path 102 maybe electrical or acoustical in
`nature. If the echo path is acoustical it is obvious that the
`summing is done at the microphone or the like rather than an
`electrical path. Summer 104 is merely illustrative that there
`is a combination of the voice signal and the echo path signal
`and is not a physical summer per say. The near-end signal is
`supplied to Yanalysis filter bank 105. The X and Yanalysis
`filter banks 103 and 105 are employed to decompose the
`received signal x(k) and the near-end signal y(k), respec
`tively, into a plurality of subbands. In this example, the
`number of subbands in the Xanalysis filter bank 103 and the
`Y analysis filter bank 105 are equal. The subband signals
`x(k), where m=0, . . . , M-1 and in a specific example
`M=32, from X analysis filter bank 103 are supplied to
`down-sampling units 106-0 through 106-M-1 where they
`are down-sampled as described below. In turn, the resulting
`down-sampled signals xo(s) through X
`(s) are supplied to
`echo cancelers 107-0 through 107-M-1 and, therein, to
`transversal filters 108-0 through 108-M-1, respectively.
`Echo cancelers 107-0 through 107-M-1 also include alge
`braic combining units 109-0 through 109-M-1, respectively,
`which are supplied with echo estimate signals So(s) through
`S (s), respectively. The subband signals y(k), where
`m=0,..., M-1 and in a specific example M=32, from Y
`analysis filter bank 105 are supplied to down-sampling units
`110-0 through 110-M-1 where they are down-sampled as
`described below. In turn, the resulting down-sampled signals
`yo(s) through y(s) are supplied to echo cancelers 107-0
`through 107-M-1 and, therein, to algebraic combiners 109-0
`through 109-M-1, respectively, where the echo estimates
`So(s) through S(s) are subtracted therefrom to cancel the
`echoes in the subbands. Such echo cancelers are well known
`in the art and adaptive filters 108 are typically adaptive
`
`BACKGROUND OF THE INVENTION
`In a subband implementation of an echo canceler, or more
`generally, any adaptive filter, the signals to be processed,
`i.e., a receive signal and a transmit signal, are first decom
`posed into an array of frequency bands and, then, processing
`is done on a per-band basis. To this end, an X-analysis filter
`bank is employed to decompose the receive signal x(k) into
`a predetermined number of frequency bands and a Y-analy
`sis filter bank is employed to decompose the transmit signal
`y(k) into a similar number of frequency bands. Then, the The
`X and Y subband signals are supplied to an echo canceler in
`each respective subband in order to cancel echos in the
`respective subbands. One such subband echo canceler is
`disclosed in U.S. Pat. No. 5,272,695 issued Dec. 21, 1993.
`In prior subband echo cancelers, the X and Y filters in the
`X and Yanalysis filter banks and were identical. That is, they
`had identical frequency characteristics and, consequently,
`there was overlap in the roll-off regions of the frequency
`characteristics. It has been observed that the prior subband
`echos cancelers using such filters in the X and Y analysis
`filter banks with identical frequency characteristics for the
`subbands suffer in convergence performance. Indeed, poor
`convergence at band edges, that is, at frequencies covered
`roughly equally by two adjacent subbands has been
`observed. An explanation for the poor band-edge conver
`gence is that the correlation matrices of subsampled per
`band reference signals (that is, the X subband signals
`running down the tap delay lines of the echo cancelers in
`each subband) are ill conditioned with small eigenvalues. If
`eigenmodes associated with these small eigenvalues are
`excited, there will inevitably be long time constants intro
`duced into the convergence of the echo cancelers in the
`subbands. The result is that there is practically no conver
`gence of the subband echo cancelers in the transition regions
`between subbands. This is extremely undesirable.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`SUMMARY OF THE INVENTION
`The problems associated with prior subband echo cancel
`ers are overcome by employing an X-analysis filter bank in
`which the pass-band of the subband filters is wider than the
`pass-band of the corresponding subband filters in the
`Y-analysis filter bank. This insures that there is sufficient
`energy in the tap delay lines of the adaptive filters in the
`subband echo cancelers at all frequencies where echos are to
`be synthesized. More specifically, the keeping of sufficient
`energy in the tap delay lines of the adaptive filters in the
`subband echo cancelers avoids exciting eigenmodes associ
`ated with the small eigenvalues of the correlation matrix.
`
`45
`
`50
`
`55
`
`BRIEF DESCRIPTION OF THE DRAWING
`FIG. 1 shows, in simplified block diagram form, details of
`a subband echo canceler in which the invention can be
`employed;
`FIG. 2 is a graphical representation of the ideal frequency
`characteristics of the X and Y filters used in the X and Y
`65
`analysis filter banks of FIG. 1 and their relationship to the
`prior art frequency characteristics;
`
`60
`
`- 8 -
`
`

`

`3
`transversal filters of a type broadly described in U.S. Pat.
`No. 3,500,000 and also, in an article authored by D. L.
`Duttweiler, entitled "A Twelve-Channel Digital Echo Can
`celer", IEEE Transactions on Communications, VOL.COM
`26, No. 5, May 1978, pages 647-653. The resulting sub
`Sampled error signals eo(s) through e-(s) from echo
`cancelers 107-0 through 107-M-1 are supplied to up-sam
`pling units 111-0 through 111-M-1, respectively. The up
`sampled error signals eo(k) through e-1(k) are supplied to
`E synthesis filter bank 112 where they are recombined to
`form error signal e(k). Such subband echo cancelers are
`known in the art, one of which is disclosed in U.S. Pat. No.
`5,272,695 issued Dec. 21, 1993.
`As indicated in more detail below, it is important that the
`signals in the tap delay lines in adaptive filters 108-0 through
`108-M-1 have strong spectral energy at any frequencies
`where there is even weak spectral energy in the signals
`y(k). Achieving this end requires careful design of the
`bandpass filters employed in the X and Y analysis filter
`banks 103 and 105. Referring to FIG. 2, there is shown
`frequency characteristics of low-pass prototype filters which
`can readily be expanded into bandpass filters. Shown is the
`ideal frequency characteristic for X filters employed in X
`analysis filter bank 103 and the ideal filter characteristic for
`Y filters employed in Y analysis filter bank 105 and their
`relationship to the frequency characteristics of prior X and
`Y filters. Note that the prior X and Y filters had identical
`frequency characteristics which led to the problem of not
`being able to cancel echoes at frequencies in the overlap
`region of the X and Y bandpass filters. The ideal solution
`30
`would be as shown in FIG. 2 to have the passband of the X
`filters be wider than the passband of the Y filters so that there
`would always be energy available in the tap delay lines of
`adaptive filters 108 in order to be able to synthesize the
`appropriate echo estimates in the subbands at frequencies in
`the overlap region of the bandpass filters. To this end, the
`frequency characteristics of the Y filters in Y analysis filter
`bank 105 start to roll off at approximately frequency f. and
`cut off at approximately frequency if
`while the frequency
`characteristics of the X filters in the X analysis filter bank
`103 start to roll off at approximately frequency f. and cut
`off at approximately frequency f. In this example, f is
`0.5/Mf is 0.5/S where S is the sub-sampling rate and if
`is mid-way between f, and f. Note that both of the X and
`Y filter frequency characteristics must be cut off by fre
`quency f. Such ideal frequency characteristics for the X and
`Y filters as shown in FIG. 2, however, come at an increased
`expense because of the length of the filters that are required.
`In order to reduce the length of the filters, i.e., the number
`of taps required and, hence, their cost, compromise fre
`quency characteristics are employed for the X and Y filters
`as shown in FIG. 3. As shown, the frequency characteristic
`of the Y filter begins to roll off at frequency f. and cuts off
`at a frequency approximately two thirds of the way between
`frequency f. and f. and the roll off of the X filter frequency
`characteristic begins at a frequency approximately one third
`of the way between f, and f, and cuts off at approximately
`frequency f. In practical filters it is noted that the roll off
`will be approximately 3 dB down at the roll off points.
`FIG. 4 shows, in simplified block diagram form, details of
`60
`X analysis filter bank 103 of FIG. 1. It is noted that the Y
`analysis filter bank will include essentially identical ele
`ments with the only difference being the frequency charac
`teristic of the filters 402. Shown, is received signal x(k)
`being supplied to multipliers 401-0 through 401-M-1 with
`the generalized multiplier being 401-m. Each of multipliers
`401 is supplied with a signal represented by ei'", again
`
`45
`
`4
`where m=0,..., M-1 to obtain the m" such heterodyned
`down signal. The heterodyned down output signals from
`multipliers 401-0 through 401-M-1 are supplied to bandpass
`filters 402-0 through 402-M-1, respectively, which yield the
`subband signals X(k) through X (k), respectively. The
`design procedure and details of the filters employed in the X
`and Y filters of X and Y analysis filter banks 103 and 105,
`respectively, are described in detail below.
`FIG. 5, shows in simplified block diagram form, details of
`E synthesis filter bank 112 of FIG.1. It should be noted that
`the E filter 501 employed in E synthesis filter bank 112 are
`typically identical to the Y filters in Y analysis filter bank
`105, the design of which is described below. Specifically, the
`up-sampled error signals eo(k) through e (k) are Supplied
`to E filters 501-0 through 501-M-1, respectively, with the
`generalized multiplier being 502-m. The filtered versions of
`the error signals e(k) through e_1(k) are supplied from
`multipliers 502-0 through 502-M-1, respectively, where
`they are heterodyned up by a signal supplied to each of the
`multipliers 502 which is represented by e?", where
`m=0,..., M-1 to obtain the m” such heterodyned up signal.
`The heterodyned up output signals from multipliers 502-0
`through 502-M-1 are supplied to algebraic summer 503
`where they are combined to yield the desired output error
`signal e(k) on transmit path 113.
`
`FILTER DESIGN
`None of the many existing techniques for designing finite
`impulse response (FIR) filters were capable of designing
`filters as described below. To meet this need, a new FIR
`design methodology was developed, which is called Z-plane
`alternation. It is general, powerful, and efficient. Both linear
`phase and minimum-phase filters can be designed. Addi
`tionally, it is possible to accommodate almost any reason
`able constraints on
`the shape of the time-domain impulse response,
`the shape of the frequency-domain transfer function, and
`the location or symmetry of zeros in the Z-plane.
`Z-plane alternation is computationally efficient and with
`reasonable care does not generally suffer from problems
`with local versus global minima or round-off due to finite
`precision arithmetic.
`The presentation here will assume the design of a filter
`basically low-pass in nature. There is, however, an obvious
`generalization for bandpass and high-pass filters.
`The key idea behind Z-plane alternation is to alternately
`optimize over the Z-plane locations of stopband zeros and
`the Z-plane locations of passband zeros. The stopband zeros
`are located via the now classic Remez-exchange-like algo
`rithm described in an article authored by Hofstetter et al.,
`entitled "A New Technique For The Design of Non-recur
`sive Digital Filters', The Fifth Annual Princeton Confer
`ence: Information Sciences and Systems, pp. 64-72, March
`1971. Thus, the resulting filters are optimal in the sense that
`the worst-case stopband rejection is the best possible for the
`specified number of stopband zeros.
`The passband zeros are located by minimizing a cost
`function. In our application we have found the Powell
`algorithm described in a book authored by W. H. Press, S.A.
`Teukolsky, W. T. Vetterling and B. P. Flannery and entitled
`"Numerical Recipes", second edition, Cambridge University
`Press, 1992, to be quite satisfactory despite its simplicity.
`Since, the cost function need not be linear and a Z-plane
`characterization can be transformed to a time-domain
`impulse response or a frequency-domain transfer function,
`
`5,566,167
`
`10
`
`15
`
`20
`
`25
`
`35
`
`40
`
`50
`
`55
`
`65
`
`- 9 -
`
`

`

`5,566,167
`
`5
`time-domain and frequency-domain requirements can be
`accommodated almost as readily as Z-plane requirements.
`Minimizations of nonlinear cost functions are notorious for
`often becoming stuck in local minima. With care, however,
`we have generally been able to avoid such problems in our
`applications to date. A desire to keep the 750" sample of a
`1000 sample impulse response small in magnitude would
`lead to a horrendously bumpy cost function parameterized in
`the Z-plane. Coming up with examples like this where the
`design goal is more reasonable is much more difficult,
`however, whereas many common objectives such as mini
`mizing passband ripple, insuring a smooth hand-off between
`bands in a filter bank, and minimizing delay can with care
`lead to comparatively smooth cost functions of zero loca
`tions.
`The fact that passband zeros are generally much less
`numerous than total zeros is also important in keeping run
`times reasonable. Numerical optimization algorithms have
`complexities and instruction counts increasing rapidly with
`the number of free parameters. Our experience suggests
`there is a practical limit of about 25 on this number.
`Since the passband zeros are in the complex plane, it takes
`two parameters to specify a location for one. However, if, it
`is assumed that the filter tap coefficients are all to be real,
`then any zeros off the real axis must come in complex
`conjugate pairs. This brings the number of free parameters
`down to roughly the number of passband zeros. A further
`reduction by a factor of two is realized in designs con
`strained to be linear in phase. No passband zeros would ever
`be located on the unit circle, and inlinear-phase designs, any
`zero off the unit circle at re'" must have a mating zero at
`(1/ref20.
`
`O
`
`15
`
`20
`
`25
`
`30
`
`6
`Experience has shown that it is only necessary to iterate
`in this fashion ten or fewer times before a stable point is
`reached. Alternatively, only one pass through the loop can be
`made but evaluating the cost function
`
`for each minimum candidate W. Computational time is likely
`to be substantially less, however, with the looped algorithm
`shown.
`
`Stopband Optimization
`Any given vectors z and Zs of passband and stopband
`Zeros define a transfer function H(f;z,z) where f is nor
`malized frequency. Let f denote the lower limit of the
`stopband for a low-pass filter and let
`
`(4)
`
`ax
`fefs,0.5
`In other words 8(zi,z) is the worst case stopband loss. For
`a given vector Z, of passband zero locations, there is a
`unique vector Zs minimizing 6(zi,z). We define R(z) as the
`function mapping Z to Zs in this way.
`The procedure we use to find z is similar to one first
`described by Hofstetter, Oppenheim, and Seigel, noted
`above.
`Using for conciseness the notation H(f) instead of H(f:z,
`Zs), we can write
`H(f)=H(f)H(f)
`
`(5)
`
`where
`
`n=0
`
`and
`
`Zs-l
`Hs(f) = II (ef-zs).
`
`(7)
`
`In these equations Ze and Zs, denote the nth components
`of the vectors z and Zs. Notice that we number the elements
`of an N dimensional vector from 0 to N-1, which is the C
`programming language convention, rather than the more
`customary 1 to N. In locating the stopband zeros, the
`passband zeros are fixed so that H(f) is a known function.
`It is assumed that optimally located stopband zeros
`always lie on the unit circle and the search is restricted to the
`unit circle. Intuitively this is entirely reasonable as for a
`frequency f near the frequency fo of a zero at re''",
`stopband rejection always improves as ro is driven towards
`1.
`Since it has been assumed that the desired impulse
`response is real valued, any stopband zeros with non-zero
`imaginary components must come in complex-conjugate
`pairs. In principle, there could be any multiplicity of stop
`band Zeros at -1, but again from geometric intuition it is
`clear that there would never be any advantage in having
`more than one.
`There is a fundamental distinction between designs with
`Zs even and Zs odd. Let
`Zs-20s-Rs
`(8)
`where Rs is 0 or 1 as Zsis even or odd. IfZ is even, optimal
`designs will have Qs pairs of complex-conjugate zeros as
`
`Z-PLANE OPTIMIZATION
`
`Alternating Between Stopband Zero and Passband
`Zero Optimization
`FIG. 6 shows a flow diagram for the Z-plane alternation
`design procedure. The routine is started via step 601. There
`after, in step 602 an initial guess
`is made of the N.
`dimensional vector of free parameters (vectors are shown in
`a bold typeface). The Z dimensional vector ze, () of
`passband Zeros specified by this particular in turn specifies
`a Zs dimensional vector
`
`35
`
`45
`
`(1)
`Zs-R(ze())
`of stopband zeros which is computed in step 603. The
`function R minimizes the worst-case stopband rejection. A
`Remez-exchange-like procedure is used to compute this
`50
`function for any given vector z of passband zeros. The cost
`function to be minimized is a function J(ze(),z) of the
`locations of the passband and stopband zeros. A new vector
`of free parameters is computed in step 604 by searching
`for the minimum, that is,
`(2)
`-WeR'J(zr(A),zs) is minimum.
`In this search, the vector zs is held constant rather than being
`reevaluated as z=R(Z()) each time a new candidate
`location W is tested. The return loop shown in FIG. 6
`compensates. Once a new free parameter vector is found
`in step 605, control is returned to step 603 and steps 603 to
`605 are iterated to compute a new vector of stopband zeros
`via Remez exchange. This process is iterated until step 605
`indicates that there is no appreciable change in . It, in turn,
`enters as a constant in another cost function optimization.
`
`60
`
`65
`
`55
`
`- 10 -
`
`

`

`7
`shown in FIG. 7. IfZ is odd, there will be one real zero in
`addition to the Qs complex-conjugate pairs as shown in FIG.
`
`8.
`
`Let
`
`.-
`
`(9)
`0<fs.<eog6.3. . . <eos0.5
`denote the stopband zero frequencies. Considering first the
`case where Z is even, we have
`
`(10)
`
`OS-1
`Hp(f) 20s II
`n=0
`
`where a superscript asterisk denotes complex-conjugation
`and
`
`(cos(2Tf)-cos(27c6)).
`
`OS-1
`E(f) = Hip(f) 20s II
`n=0
`The product on the right hand side of equation (11) defines
`a Qs order polynomial in cos(2Tcf). Hence, we can rewrite
`equation (11) as
`
`(11)
`
`E(f) = IHp(f)
`
`OS-1
`20scos0s(2rtf)- f p'cos(27tf)
`
`(12)
`
`where the weights pn=0,1, ... Os-1 could if desired be
`computed from the Zero frequencies 00,0,..., 0. There
`is no need for this mapping, however, so we need not be
`concerned with its precise functional form. Trigonometric
`identities allow rewriting
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`Os-1
`20s.cosos(21f) = 2cos(2ncCsf) +
`acos"(2f)
`where again the weights a could be calculated but are of no
`consequence for what follows. Using the expansion (13), we
`40
`finally obtain
`
`(13)
`
`re
`
`E(f) = Hp(f)
`
`OS-1
`2cos(2EOsf) - i. picos(21f)
`
`(14)
`
`OI
`
`(15)
`E(f) = W(f)(D(f) - P(f))
`with the obvious definitions for the weighting function
`W(f), the desired function D (f), and the polynomial P (f).
`IfZ is odd, we can again reach the general function form
`(15). The only difference is that the weighting W(f) is now
`given by
`
`The reason for expressing E(f) in the form (15) is that the
`problem is now within the framework of the Hofstetter et al.
`procedure noted above and their Remez-exchange like tech
`nique can be used. The application here is even slightly
`simpler than theirs, because the region over which the
`maximum is taken in the equation defining 8, that is,
`equation (4), is one continuous interval on the real line,
`whereas in the Hofstetter et al. application, it is composed of
`two or more disjoint intervals, which introduces complica
`tion.
`For filters with less than about 500 taps we were able to
`successfully use either the barycentric or the standard forms
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,566,167
`
`8
`of the Lagrange interpolating polynomial. However, for
`larger filters we frequently encountered difficulties when
`using the barycentric form recommended by Hofstetter et al.
`
`Passband Zero Location
`Passband zeros are located by finding the free parameter
`vector , minimizing J(Z(),Z) where Zs is fixed for the
`optimization. The best way to search for this minimizing
`vector is necessarily highly dependent on the particular cost
`function of interest. For the cost function of the example
`given below, it has been found that the Powell algorithm
`noted above performs satisfactorily. This particular algo
`rithm does not require any gradient information.
`
`Application to Subband Echo Canceler
`Our particular application of Z-plane alternation has been
`to the design of the X and Y filters in X and Yanalysis filter
`banks 103 and 105 and the E filters in E synthesis filter bank
`112 for subband echo canceling.
`As indicated above, FIG. 1 is a block diagram of an
`M-band subband echo canceler 100. The signal x(k) is
`tapped on its way to some unknown echo path ha(k) 102.
`This tapped signal is decomposed into M subband signals
`x(k),k=0,1,... M-1 in Xanalysis filter bank 103. The m'
`such signal is created by first heterodyning down by e?"
`and then filtering with the low-pass filter g(k), that is,
`
`where the raised * denotes convolution.
`The signal y(k) is the sum of the echo from echo path 102
`and any desired speech v(k) from the local end. The signal
`y(k) is also decomposed into M subband signals, but impor
`tantly, the prototype low-pass filter g(k) used in the Y
`analysis filter bank 105 need not be the same as the proto
`type low-pass filter used in the X analysis filter bank 103.
`In each band m the signals X(k) and y(k) are sub
`sampled by SCM. Critical rate sampling, that is, S=M, is in
`principle possible, but in practice a poor idea. An article
`authored by A. Gilloire and M. Vetterli, entitled "Adaptive
`filtering in subbands with critical sampling: Analysis,
`experiments, and application to acoustic echo cancellation',
`IEEE Transactions Signal Processing, vol. 40, pp.
`1862-1875, August 1992. Also, because there is a subtrac
`tion of an echo estimate S(s) from the echo y(s), quadra
`ture-mirror filtering in which aliasing in one band cancels
`that from another is not possible. Thus, the filters g(k) and
`g(k) must cutoff by at least the frequency 0.5/S.
`In each of the M bands the subsampled signals X(s) and
`y(s) drive an adaptive filter (echo canceler) to produce a
`subsampled error signal e(s). This signal is interpolated
`with zeros to forme(k), which is then filtered by a low-pass
`filter g(k) and heterodyned up by e'". All Msuch signals
`are then added to form the full-band signal e(k). Thus
`
`Let G.(f) denote the Fourier transform of g(k), that is,
`(19)
`
`and similarly define G(f) and G(f). If the echo estimates
`S(s) are all zero, the lower half of the echo canceler
`structure of FIG. 1 becomes simply an analysis/synthesis
`subband filter bank. Assuming the filters g(k) (not shown)
`
`- 11 -
`
`

`

`5,566,167
`
`9
`and filters g(k) 501 (FIG. 5) to have reasonable stopband
`attenuation so that aliasing is negligible, the transfer func
`tion T(f) from y(k) to e(k) is expressible by
`M
`
`(20)
`
`We have always chosen the E filters in E synthesis filterbank
`112 to be identical to the Y filters in Y analysis filter bank
`105, in which case, equation (20) becomes
`
`5
`
`O
`
`10
`limit of the passband and lower limit of the stopband for this
`Y filter. A plot of the passband zeros as well as some of the
`closer-in stopband zeros appears in FIG. 9. The stopband
`Zeros not shown continue around the unit circle with increas
`ingly regular spacing as -1 is approached. The worst case
`rejection is 59.89 dB and the peak-to-peak ripple in T(f) is
`0.20 dB. The delay of the Y filter is 109.30 samples. Note
`that this is only about one third the 340 sample delay of a
`680 tap linear phase filter.
`In designing the Y filter, we seeded the passband zeros to
`be equally spaced in frequency over-fief, and to be in
`from the unit circle a distance equal to the angular spacing.
`The initial guess for the Remez-exchange extremals spaced
`them uniformly over f0.5).
`The cutoff frequency fs=0.01169 in the above design of
`the Y filters in Yanalysis filter bank 105 is not equal to 0.5/S
`as might be expected. Rather it has been chosen as of the
`way out to 0.5/S from 0.5/M. The reason for moving the
`cutoff frequency in like this is because of the importance of
`making the pass-band of filter G(f) somewhat narrower
`than G(f) as indicated above. For this to be possible, G(f)
`must roll off faster than a simple consideration of aliasing
`alone would dictate. It is also noted that it is extremely
`important to have the passband zeros of g(k) duplicate as
`much as possible the passband zeros of g(k). We force this
`by allowing the passband Zero structure of g(k) to differ
`from that of g(k) by only the addition of one extra pair of
`complex-conjugate Zeros.
`The X filters in X analysis filter bank 103 are designed to
`mate with the above Y filters in Y analysis filter bank 105
`and has the Zero locations shown in FIG.10. The worst case
`rejection is 59.06 dB and the filter delay is 102.16 samples.
`In designing this X filter there were only two degrees of
`freedom: the radius and angle of the additional complex
`conjugate pair of zeros. Because there is no requirement for
`a smooth folded response as in equation (21), the cost
`function was changed to
`
`15
`
`In echo canceling it is desirable that there be as little delay
`as possible in the y(k) to e(k) path. For filter banks as large
`as about M=32 the best filters seem to be minimum phase
`filters, since, they have the least possible delay and the
`human ear is insensitive to the phase distortion they intro
`duce (Ohm's Law). However, when M is greater than 32, we
`have found experimentally that the phase distortion of
`minimum phase filters starts to become noticeable. Hence,
`20
`linear phase filters are more desirable in certain applications.
`if M is to be a very large number. The description here will
`continue under the assumption that m is no larger than 32
`and minimum phase filters are desired. It is noted that linear
`phase filter design is similar and in fact, somewhat simpler
`than the minimum phase filter design.
`The function T(f) is periodic every 1/M Hertz. A cost
`function
`
`25
`
`(22)
`
`max
`J(zp(A),zs) = min
`o, fe (0,0.5IM)
`is probably the most natural to use. The cost it assigns is the
`error at the worst frequency with the best possible scaling.
`Unfortunately, this particular cost function is bumpy (on a
`very small scale) when parameterized in the Z-plane. The
`optimization procedure quickly