United States Patent [19J
`Marash et al.
`
`111111111111111111111111111111111111111111111111111111111111111111111111111
`US006049607 A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,049,607
`Apr. 11, 2000
`
`[54]
`
`[75]
`
`INTERFERENCE CANCELING METHOD
`AND APPARATUS
`
`Inventors: Joseph Marash, Haifa; Baruch
`Berdugo, Kiriat-Ata, both of Israel
`
`[73] Assignee: Lamar Signal Processing, Yokneam,
`Israel
`
`[21] Appl. No.: 09/157,035
`
`[22] Filed:
`
`Sep. 18, 1998
`
`Int. CI? ............................... H04M 9/08; H03R 3/00
`[51]
`[52] U.S. Cl . ............................ 379/410; 379/407; 381!92;
`381!94.1; 367/121
`[58] Field of Search ..................................... 379/407, 406,
`379/408, 409, 410, 411, 416; 381!92, 94.1,
`91.2, 94.7, 155; 367/116, 117, 118, 119-127;
`708/322
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,965,834 10/1990 Miller ..................................... 381/94.1
`5,226,016
`7/1993 Christman ............................... 367/135
`5,627,799
`5/1997 Hoshuyama ............................ 367/121
`5,825,898 10/1998 Marash ...................................... 381!92
`
`Primary Examiner--Forester W. Isen
`Assistant Examiner-Jacques Saint-Surin
`Attorney, Agent, or Firm--Frommer Lawrence & Haug
`LLP; Thomas J. Kowalski
`
`[57]
`
`ABSTRACT
`
`Interference canceling is provided for canceling, from a
`target signal generated from a target source, an interference
`signal generated by an interference source. The beam splitter
`beam-splits the target signal into a plurality of band-limited
`target signals band-limited frequency bands and beam-splits
`the interference signal into corresponding band-limited fre(cid:173)
`quency bands. The adaptive filter adaptively filters each
`band-limited interference signal from each corresponding
`band-limited target signal. The inhibitor can permit the
`adaptive filter to adapt or change coefficients when a signal(cid:173)
`to-noise ratio of the reference signal exceeds a predeter(cid:173)
`mined threshold, to be determined periodically, over a
`signal-to-noise ratio of the main signal. The beam selector
`selects at least one of a plurality of beams for adaptive
`filtering by the adaptive filter representing a direction from
`which the main signal is received. The beam selector selects
`beams simultaneously to improve accuracy and, in
`particular, selects a beam having a fixed direction and a
`beam which rotates in direction. The noise gate gates the
`main signal adaptively filtered by the adaptive filter by
`opening the noise gate when a signal-to-noise ratio at the
`near end is above a predetermined threshold and closing the
`noise gate when the signal-to-noise ratio at the near end is
`below the predetermined threshold. When the target signal
`represents speech generated at a near end of a
`teleconference, the adaptive filter cancels an echo present in
`the reference signal broadcast to a far end of the telecon(cid:173)
`ference.
`
`37 Claims, 7 Drawing Sheets
`
`~ ~ 102
`a:
`~··>-----1
`L!J zee>-----1
`0 B:••>-----1
`~··>------1
`
`(.)
`~.---~
`
`Required Direction
`
`122
`
`124
`
`126
`
`128
`
`Far end
`
`Signal
`
`0.
`(j)
`
`Band 15
`
`Petitioner Apple Inc.
`Ex. 1001, p. 1
`
`

`
`U.S. Patent
`
`Apr. 11, 2000
`
`Sheet 1 of 7
`
`6,049,607
`
`5
`0
`
`9lB8 9S!ON
`
`qwooat:J
`
`0
`C\J
`v
`
`.....r
`
`_j_
`
`...--
`
`..--
`(.0
`
`v_,--
`
`•••
`
`~,-----
`
`0
`"0
`c
`<tl co
`
`p....;;....-,:-
`.£2
`Qi
`-oU
`cc
`(ti<tl
`.oU
`(1)0
`c..c
`0~
`~
`"0 c
`crl co
`
`c
`(.0
`..--..--
`
`mds
`
`§I
`
`v
`
`C\J
`
`..-(cid:173)..--
`v
`
`0
`
`.....r
`
`co
`0
`.....r
`
`(.0
`
`0 ..--
`v
`
`v
`
`pa1as weas
`
`t
`
`UO!lBW!:)90
`
`t
`
`JaWJO.::J weas
`
`t
`
`ONDU!IdWBS
`
`t
`
`t
`
`t
`
`t
`
`t
`
`DU!UO!l!PUO:) IBUD!S
`
`~J 1 4~ 1 1 1
`
`AV't:lt:IV' 3N0Hd0t:I:JIV'J
`
`r--"c:;'"
`"6>
`0
`_J
`
`Et5
`<ti2
`Q) Q)
`CO (f)
`- -
`
`c
`0
`:;:::::;
`()
`Q)
`,__
`i:S
`"0
`Q)
`,__
`::I
`0""
`Q)
`a:
`
`1.!)
`...-
`"0
`c
`<tl
`co
`
`l!lds
`
`0
`"0
`c
`<tl
`co
`
`co~
`C\J
`..--
`
`.,._
`.
`(!)
`0::
`
`(.0
`C\J
`T""",_f
`
`UO!lBW!:)90
`
`ON DU!idWBS
`
`"<t
`~.....r
`
`C\J
`C\J
`..-..._r
`
`DU!UO!l!PUO:)
`IBUD!S
`
`"0
`c
`Q)
`en
`
`Cil
`c
`0)
`U5
`
`LL 1
`
`Petitioner Apple Inc.
`Ex. 1001, p. 2
`
`

`
`U.S. Patent
`
`Apr. 11, 2000
`
`Sheet 2 of 7
`
`6,049,607
`
`2041
`
`2021
`
`2042
`
`2022
`
`204n
`
`Mic Signal
`1
`
`Mic Signal
`2
`
`202~
`
`Mic Signal
`n
`
`Steering Vector
`
`2061
`
`Tap Delay Line
`
`Steering Vector
`
`2062
`
`Tap Delay Line
`
`•
`•
`•
`
`Steering Vector
`
`206n
`
`+
`
`Tap Delay Line
`
`206
`
`FIG. 2
`
`Petitioner Apple Inc.
`Ex. 1001, p. 3
`
`

`
`U.S. Patent
`
`Apr. 11, 2000
`
`Sheet 3 of 7
`
`6,049,607
`
`306-..r
`
`Low Pass
`Filter Coefficient
`
`30~ n
`New
`Samples
`
`Older Samples
`
`Tap Delay Line
`
`Decimation by n
`
`FIG. 3
`
`Petitioner Apple Inc.
`Ex. 1001, p. 4
`
`

`
`U.S. Patent
`
`! In
`
`Apr. 11, 2000
`
`Sheet 4 of 7
`
`6,049,607
`
`400
`
`Collect 8
`Points
`
`402
`
`128 Points Delay Line
`
`404
`
`Complex filter
`Coefficient (128 points)
`
`408
`
`Complex Multiply
`
`128 Points Buffer
`
`16
`Points
`
`16
`Points
`
`410
`
`16 point time
`aliasing sequence
`
`420 Modulation coefficients
`c clic buffer
`
`FFT
`
`416
`
`8
`
`16
`
`Complex Multiply
`
`418
`
`Real(*)
`
`16 point output
`
`422
`
`424
`
`FIG. 4
`
`Petitioner Apple Inc.
`Ex. 1001, p. 5
`
`

`
`U.S. Patent
`
`Apr. 11, 2000
`
`Sheet 5 of 7
`
`6,049,607
`
`500
`
`Near End
`
`5s6
`
`' - - -
`
`SNR
`Estimation
`
`SNR near
`
`+
`-
`
`508
`
`error
`
`(out)
`
`Beam
`
`Select
`
`Adaptive Filters Bank
`
`(beam 0 - beam 5)
`
`VSo6
`
`AW-
`coefficient
`update
`
`j
`
`Multiply
`Accumulate
`
`--'504
`
`r51o
`
`NLMS
`Algorithm
`
`Far
`
`End
`
`I
`
`Tap delay line
`
`jso2
`
`Power
`Estimation
`
`SNR
`Estimation
`
`SNR Far
`
`IJ'518
`
`Inhibit
`update
`logic
`
`SNR Near
`
`FIG. 5
`
`Petitioner Apple Inc.
`Ex. 1001, p. 6
`
`

`
`U.S. Patent
`
`Apr. 11, 2000
`
`Demodulation coefficients
`(cyclic buffer)
`
`Sheet 6 of 7
`
`! Input (t)
`
`16
`Points
`
`602
`
`6,049,607
`
`8
`
`606
`Complex Multiply
`
`(t)
`
`16
`
`IFFT
`
`Periodic extraction
`
`16
`Points
`
`16
`Points
`
`Complex Filter
`(128 coefficients)
`
`616
`
`618
`
`Real{*}
`
`8 points
`
`8 zeros
`
`8 point output ~604
`(t)
`
`FIG. 6
`
`Petitioner Apple Inc.
`Ex. 1001, p. 7
`
`

`
`U.S. Patent
`U.S. Patent
`
`Apr. 11,2000
`Apr. 11, 2000
`
`Sheet 7 of 7
`Sheet 7 of 7
`
`6,049,607
`6,049,607
`
`"5
`0
`
`.....,.
`
`NK
`
`$30
`
`50new:82
`
`"0 c w ....
`
`co
`Q)
`z
`
`0 .,....
`\"
`
`()
`
`·o,
`0
`_J
`
`~I
`o|E
`
`I
`
`t
`
`"0
`o-
`.c ()
`swam
`(/) Q)
`Q) Q)
`..CCI)
`I-
`
`_o_9_$::
`
`NGE
`
`co
`won
`0
`I'-
`
`.o..m:mdEoO
`
`....
`0
`"i ....
`+
`co
`c..
`E L
`0
`u
`
`oKco_..mE=wm_m
`23mzm
`
`<D
`0
`,...........,.
`
`c
`0
`a: ·.;:::::;
`z ~
`(/):.;::;
`(/)
`w
`
`oo:;t
`
`0 "v
`
`C\.1
`0
`
`"v
`
`c
`0
`a::.;:;
`mzm
`z ~
`(/):.;::;
`(/)
`w
`
`co:mE=wm
`
`....
`co
`En.
`
`"0
`Em.
`c
`
`Petitioner Apple Inc.
`Petitioner Apple Inc.
`Ex. 1001, p. 8
`Ex. 1001, p. 8
`
`
`
`
`
`

`
`6,049,607
`
`1
`INTERFERENCE CANCELING METHOD
`AND APPARATUS
`
`RELATED APPLICATIONS
`
`Reference is made to co-pending U.S. application Ser.
`Nos. 08/672,899 (allowed), 09/130,923, 08/840,159,
`09!059,503 and 09/055,709, each of which is hereby incor(cid:173)
`porated herein by reference; and each and every document
`cited in those applications, as well as each and every
`document cited herein, is hereby incorporated herein by
`reference.
`
`FIELD OF THE INVENTION
`
`The present invention relates to an interference canceling
`method and apparatus and, for instance, to an echo canceling
`method and apparatus which provides echo-canceling in full
`duplex communication, especially teleconferencing commu(cid:173)
`nications.
`
`BACKGROUND OF THE INVENTION
`
`30
`
`2
`signals. The echo-free signals are then transmitted back to
`the far-end system.
`In order to reduce the echo from the near-end microphone
`signal, it is required to obtain the transfer function that
`expresses the relationship between the near-end loudspeaker
`signal and the reverberations as they actually appear at the
`near-end microphone. This transfer function depends on the
`relative position of the near-end loudspeaker to the near-end
`microphone, the room structure, position of the system and
`10 even the presence of people in the room. Since it is impos(cid:173)
`sible to predict these parameters a priori, it is preferred that
`the echo-canceling system updates the transfer function
`continuously in real time.
`The adaptation process by which the echo-canceling
`15 system is updated in real time may be an LMS (least means
`square) adaptive filter (Widrow, et al., Proc. IEEE, vol. 63,
`pp. 1692-1716, Proc. IEEE, vol. 55, No. 12, December
`1967) with the far-end signal used as the reference signal.
`The LMS filter estimates the interference elements (echoes)
`20 present in the interfered channel by multiplying the refer(cid:173)
`ence channel by a filter and subtracting the estimated
`elements from the interfered signal. The resulting output is
`used for updating the filter coefficients. The adaptation
`process will converge when the resulting output energy is at
`25 a minimum, leaving an echo-free signal.
`Important to the adaptation process is the selection of the
`size of the adaptation step of the filter coefficients. In the
`standard LMS algorithm the step size is controlled by a
`predetermined adaptation coefficient, the level of the refer(cid:173)
`ence channel and the output level. In other words, the
`adaptation process will have bigger steps for strong signals
`and smaller steps for weaker signals.
`A better behaved system is one in which its adaptation
`steps are independent of the reference channel levels. This is
`accomplished by normalizing the adaptation coefficient by
`the reference channel energy, this method is called the
`Normalized Least Mean Square (NLMS) as, for example,
`described in see for example "A Family of Normalized LMS
`Algorithms", Scott C. Douglas, IEEE Signal Processing
`Letters, Vol. 1, No. 3, March 1994. It should be noted that
`the energy estimator, if not designed properly, may fail to
`track when large and fast changes in the level of the
`reference channel occur. Thus, the normalized coefficient
`may be too big during the transition period, and the filter
`coefficient may diverge.
`Another problem is that the adaptive process feeds the
`output back to determine the new filter coefficients. When
`the interfering elements in the signal are less pronounced
`50 than the non-interfering signal, there is not much to reduce
`and the filter may diverge or converge to a wrong value
`which results in signal distortions.
`When properly converged, the adaptive filter actually
`estimates the transfer function between the far-end loud(cid:173)
`speaker signal and the echo elements in the main channel.
`However, changes in the room will effect a change in the
`transfer function and the adaptive process will adapt itself to
`the new conditions. Sudden or quick changes, in particular,
`will take the adaptive filter time to adjust for and an echo
`will be present until the filter adapts itself to the new
`conditions.
`In order to improve the audio quality, sometimes a num(cid:173)
`ber of microphones are used instead of a single one. This
`system either selects a different microphone each time
`someone is speaking in the room or creates a directional
`beam using a linear combination of microphones. By mul(cid:173)
`tiplexing the microphones or steering the directional audio
`
`Tele-conferencing plays an extremely important role in
`communications today. The teleconference, particularly the
`telephone conference call, has become routine in business,
`in part because teleconferencing provides a convenient and
`inexpensive forum by which distant business interests com(cid:173)
`municate. Internet conferencing, which provides a personal
`forum by which the speakers can see one another, is enor(cid:173)
`mously popular on the home front, in part because it brings
`together distant family and friends without the need for
`expensive travel.
`In a teleconferencing system, the sounds present in a
`room, hereinafter referred to as the "near-end room" such as
`those of a near-end speaker are received by a microphone, 35
`transmitted to a "far end system" and broadcast by a far-end
`loudspeaker. Similarly, the far-end speaker is received by the
`far-end microphones and transmitted to the near-end system,
`and broadcast by the near-end loudspeaker. The near-end
`microphone receives the broadcasted sounds along with 40
`their reverberations and transmits them back to the far-end,
`together with the desired signals generated by, for example,
`speakers at the near-end, thereby resulting in a disturbing
`echo heard by the speaker at the far-end. The far-end speaker
`will hear himself after the sound has traveled to the near-end 45
`system and back, thereby resulting in a delayed echo which
`will annoy and confuse the far-end speaker. The problem is
`compounded in video and internet conferencing systems
`where the delay is more extremely pronounced.
`The simplest way to overcome the problem of echo is by
`blocking the near-end microphone while the far-end signal is
`broadcast by the near-end loudspeaker. Sometimes referred
`to as "ducking", the technique of blocking the microphone
`is effectively a half-duplex communication. Problematically,
`if the microphone is blocked for a prolonged period to avoid 55
`transmission of the reverberations, the half-duplex commu(cid:173)
`nication becomes a significant drawback because the far-end
`speaker will lose too much of the near-end speaker. In the
`video or Internet conferencing system, where the delay
`created by the communication lines is extreme, ducking 60
`becomes quite annoying.
`A more complex method to avoid echo is to employ an
`echo canceling system which measures the signals send
`from the far-end and broadcast it the near-end loudspeaker,
`estimates the resulting signal present at the near-end micro- 65
`phone (including the reverberations) and subtracts those
`signals representing the echo from the near-end microphone
`
`Petitioner Apple Inc.
`Ex. 1001, p. 9
`
`

`
`6,049,607
`
`3
`beam, the relationship between the loudspeaker signal and
`the audio signal obtained by the microphones can be
`changed. Problematically, each time such a transition takes
`place, an echo will "leak" into the system until the new
`condition has been studied by the adaptive filter. To allow
`the use of a steerable directional beam and prevent the
`transient echo, one can either perform continuous echo
`canceling on each of the microphones separately or on each
`of the microphone combinations (the combinations of
`microphones could be infinite). However, the increase in the 10
`computation load required to perform numerous echo(cid:173)
`canceling systems concurrently on each of the microphones
`or allowable beams is not realistic.
`An efficient echo-canceling system is needed which will
`reduce the echo drastically. However, because of the large 15
`dynamic ranges required by the microphone to be able to
`pick up very low voices, the microphone will most likely
`pick up some of the residual echo as well. The residual echo
`is most disturbing when no other signal is present but less
`noticed when a full duplex discussion is taking place.
`Another problem typical to multi-user conferencing sys(cid:173)
`tems is that the background noise from several systems is
`transmitted to all the participating systems and it is preferred
`that this noise be reduced to a minimum. The beam forming
`process reduces the background noise but not enough to
`account for the plurality of systems.
`
`OBJECTS AND SUMMARY OF THE
`INVENTION
`
`4
`broadcast from a far end of the teleconference. It is preferred
`that the adaptive filter is an adaptive filter array with each
`adaptive filter in the array filtering a different frequency
`band. In the exemplary embodiment the adaptive filter
`estimates a transfer function of the reference signal broad(cid:173)
`cast from the far end.
`The adaptive filter of the present invention may further
`comprise an inhibitor. The inhibitor permits the adaptive
`filter to adapt (change coefficients) when a signal-to-noise
`ratio of the reference signal exceeds a predetermined thresh(cid:173)
`old over a signal-to-noise ratio of the main signal.
`Preferably, the inhibitor determines the predetermined
`threshold periodically.
`The beam splitter of the exemplary embodiment of the
`present invention is a DFT filter bank using single side band
`modulation. Additionally, the present invention may com(cid:173)
`prise a beam selector for selecting at least one of a plurality
`of beams for adaptive filtering by the adaptive filter repre(cid:173)
`senting a direction from which the main signal is received.
`20 In this case, the adaptive filter updates coefficients repre(cid:173)
`senting the transform function and comprehensively stores
`the coefficients for each beam selected by the beam selector.
`In the exemplary embodiment, the beam selector selects the
`plurality of the beams for simultaneous adaptive filtering by
`25 the adaptive filter. Further, the beam selector may select a
`beam having a fixed direction and a beam which rotates in
`direction.
`The present invention may further comprise a noise gate
`30 for gating the main signal adaptively filtered by the adaptive
`filter by opening the noise gate when a signal-to-noise ratio
`at the near end is above a predetermined threshold and
`closing the noise gate when the signal-to-noise ratio at the
`near end is below the predetermined threshold. In this case,
`35 the noise gate determines the predetermined threshold by
`selecting a low threshold when a signal-to-noise ratio of the
`reference signal of the far end is low, updating the prede(cid:173)
`termined threshold upwards when the signal-to-noise ratio
`of the reference signal of the far end goes up and gradually
`40 reducing the predetermined threshold when the signal-to(cid:173)
`noise ratio of the reference signal of the far end goes down.
`
`It is therefore an object of the invention to provide an
`interference canceling system.
`It is another object of the invention to provide an inter(cid:173)
`ference canceling system to cancel interference while pro(cid:173)
`viding full duplex communication.
`It is yet another object of the invention to provide an
`interference canceling system to cancel an echo present in a
`teleconference.
`It is still another object of the present invention to provide
`an interference canceling system to cancel an echo present
`in video teleconferencing.
`It is further an object of the invention to allow a steerable
`directional audio beam to function with the interference
`canceling system of the present invention.
`It is yet a further object of the invention to overcome
`background noise in the conferencing system and reduce the
`residual echo to a minimum.
`In accordance with the foregoing objectives, the present
`invention provides an interference canceling system, method 50
`and apparatus for canceling, from a target signal generated
`from a target source, an interference signal generated by an
`interference source. A main input inputs the target signal
`generated by the target source. A reference input inputs the
`interference signal generated by the interference source. A
`beam splitter beam-splits the target signal into a plurality of
`band-limited target signals and beam-splits the interference
`signal into band-limited interference signals. Preferably, the
`amount and frequency of band-limited target signals equals
`the amount and frequency of band-limited interference 60
`signals, whereby for each band-limited target signal there is
`a corresponding band-limited interference signal. An adap(cid:173)
`tive filter adaptively filters, each band-limited interference
`signal from each corresponding band-limited target signal.
`When the target signal represents speech generated at a 65
`near end of a teleconference, the adaptive filter of the present
`invention cancels an echo present in the reference signal
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`A more complete appreciation of the present invention
`45 and many of its attendant advantages will be readily
`obtained by reference to the following detailed description
`considered in connection with the accompanying drawings,
`in which:
`FIG. 1 illustrates the interference canceling system of the
`present invention.
`FIG. 2 illustrates the beamforming unit of the present
`invention.
`FIG. 3 illustrates the decimation unit of the present
`55 invention.
`FIG. 4 illustrates the beam splitting unit of the present
`invention.
`FIG. 5 illustrates the adaptive filter of the present inven(cid:173)
`tion.
`FIG. 6 illustrates the recombining unit of the present
`invention.
`FIG. 7 illustrates the noise gate of the present invention.
`
`DETAILED DESCRIPTION
`
`FIG. 1 illustrates the exemplary echo canceling system of
`the present invention. An array of microphone elements 102
`
`Petitioner Apple Inc.
`Ex. 1001, p. 10
`
`

`
`6,049,607
`
`10
`
`5
`receive and convert acoustic sound in a room into an analog
`signal which is amplified by the signal conditioning block
`104 and converted into digital form by the ND converter
`106. While FIG. 1 appears to depict the microphone ele(cid:173)
`ments 102 as an array, it will be appreciated by those skilled
`in the art that other configurations are readily applicable to
`the present invention. The microphone elements, for
`example, may be arranged in a circular array, a linear, or any
`other type of array. The ND converter 106 may be an array
`of Delta Sigma converters set to, for example, a sampling
`frequency of 64 KHz per channel but, of course, may be
`substituted with other types of converters and sampling
`frequencies which are suitable as those skilled in the art will
`readily understand.
`The sampled signals of each microphone are stored in a 15
`tap delay line (not shown) and multiplied by a steering
`matrix in the beam forming unit 108 to form a number of
`directional beams. As an example, 6 beams are formed
`which are aimed in directions evenly spread over 360
`degrees (60 degrees apart). Of course, the present invention 20
`is not limited to any specific number of beams as one skilled
`in the art will readily understand. The beam signals are then
`low pass filtered to, for example, 8 KHz and decimated by
`decimating unit 110 to reduce the sampling rate and hence
`the computational load on the system. In this manner, the 25
`sampling rate is reduced to 16KHz for each channel. It shall
`be appreciated that the decimation process may be per(cid:173)
`formed prior to the beamforming process to further reduce
`the processing burden.
`The system receives an indication as to the direction of the 30
`speaker either through a direction finding system or through
`a manual steering process. In the exemplary embodiment,
`the beam select logic unit 112 selects the beam with the
`closest direction to that actual and performs echo can cella(cid:173)
`tion processing on the selected beam.
`A particular aspect of the present invention is that the
`selected beam is split into a number of frequency bands,
`preferably 16 evenly spaced bands, by the beam splitter 114
`such that echo cancellation processing is performed on each
`frequency band separately. Without this arrangement, an 40
`echo which typically lasts for more than 100 msec would
`require an adaptive filter, assuming that the filter samples the
`100 msec of signal at a rate of 16 KHz, to have 1600
`coefficients. Such a long adaptive filter is not likely to
`converge in the time that the echo is present. Moreover, an 45
`adaptive filter of 1600 coefficients presents an enormous
`processing burden which is unrealistic to handle. By split(cid:173)
`ting the bands into, for example, 16 channels the present
`invention reduces the sampling rate for each adaptive filter
`to, in this case, 2 KHz per channel. It will be appreciated 50
`that, not only is this system much more manageable, the
`adaptive filters can be optimized for each frequency sepa(cid:173)
`rately by, for example, selecting longer filters for lower
`frequencies where the echo is typically located and shorter
`filters for higher frequencies where the echo is less. In this 55
`case, the filter lengths range, for example, from 16 to 128
`coefficients. With this arrangement, the adaptive filters can
`converge much more easily with these lengths, the treatment
`of each band is independent from the others thereby pre(cid:173)
`venting the problem of a broadband filter concentrating on 60
`a band limited interference while ignoring less pronounced
`ones and the processing burden is reduced.
`Meanwhile, the far end signal (referred to as the reference
`channel) is conditioned, sampled, decimated and split in the
`manner discussed above by respective signal conditioning 65
`block 122, ND converters 124, decimating unit 126 and
`splitter 128. Each band of the selected beam is processed for
`
`6
`echo reduction using echo canceling unit 1161 _m· While
`Normalized LMS filters are preferred, those skilled in the art
`will readily understand that other type of adaptive filters are
`applicable to the present invention. The resulting echo-free
`signals of the different frequency bands are recombined into
`one broadband output by a recombine output unit 118.
`The output of the recombined process is fed into a noise
`gate processor 120. The purpose of the noise gate is to
`prevent steady background noise in the room (such as fan
`noise) from being transmitted to the far end system and
`eliminate residual echoes. The system of the present inven(cid:173)
`tion measures the level of the steady noise and blocks up the
`signals that are below a certain threshold above this noise
`level. When residual echoes are present they may penetrate
`the process and be transmitted to the far end system. In order
`to prevent that, the blocking threshold is actively adjusted to
`the level of the signal present at the reference channel (far
`end). When a high level energy is detected at the far end
`signal, the threshold will be boosted up and gradually
`reduced when this signal disappears. This will prevent
`residual echoes from being transmitted while leaving only
`speech signals from the near end.
`FIG. 2 illustrates the beamforming unit 200 (FIG. 1, 108)
`of the present invention. Signals originated at a certain
`relative direction to the microphone array arrive at different
`phases to each microphone. Summing them up will create a
`reduced signal depending on the phase shift between the
`microphones. The reduction goes down to zero when the
`phases of the microphones are the same, thus creating a
`preferred direction while reducing all other directions. In the
`beamforming process, the microphone signals are phase
`shifted to create a zero phase difference for signals origi(cid:173)
`nated at a predetermined direction. The phase shift is
`achieved by multiplying the microphone signal stored in the
`35 tap delay lines 202 1 _n by a FIR filter coefficient or steering
`vector output from steering vector units 2041 _n·
`In one embodiment, a different weight is applied for each
`microphone to create a shading effect and reduce the side
`lobe level. The weighting factors are implemented as part of
`the FIR filter coefficients. The filters for each direction and
`each microphone are pre-designed and stored as a steering
`vector matrix 2041 _n· The microphone signals are stored in
`a tapped delay line 2021-n with the length of the FIR filter.
`For each direction, each microphone delay line is multiplied
`by multipliers 206 1 _n by its FIR and summed with the other
`microphones after they have been multiplied. The process
`repeats for each direction resulting in a beam output for each
`direction.
`FIG. 3 illustrates the decimation unit 300 (FIG. 1, 110,
`126) of the present invention. Decimation, which is intended
`to reduce the sampling frequency, can be done only once the
`high frequency elements are removed to maintain the
`Nyquist criteria. For example, if the sampling frequency is
`to be reduced to 16 KHz, it is necessary to make sure that
`the signal does not contain elements above 8 KHz because
`sampling will result in aliasing. In order to remove the
`troublesome high frequencies, the signals are first filtered by
`a low pass filter that cuts off the higher frequencies. In more
`detail, the beam samples are stored in a tapped delay line 302
`and multiplied via a multiplier 304 by a low pass filter
`coefficient produced by the low pass filter 306.
`FIG. 4 illustrates the beam splitting unit 400 (FIG. 1, 114,
`128) of the present invention. Although various beam split(cid:173)
`ting techniques may be employed, it is preferred that the
`generalized DFT filter bank using single side band modu(cid:173)
`lation be employed as described, for example, in "Multirate
`
`Petitioner Apple Inc.
`Ex. 1001, p. 11
`
`

`
`6,049,607
`
`10
`
`7
`Digital Signal Processing', Ronald E. Crochiere, Prentice
`Hall Signal Processing Series or "Multirate Digitals Filters,
`Filter Banks, Polyphase Networks, and Applications A
`Tutorial", P. P. Vaidyanathan, Proceedings of the IEEE, Vol.
`78, No. 1, January 1990. The goal of the beam splitter is to
`split the input signal into a plurality of limited frequency
`bands, preferably 16 evenly spaced bands. In essence, the
`beam splitting processes, for example, 8 input points at a
`time resulting in 16 output points each representing 1 time
`domain sample per frequency band. Of course, other quan(cid:173)
`tities of samples may be processed depending upon the
`processing power of the system as will be appreciated by
`those skilled in the art.
`In more detail, the 8 input points 402 are stored in a 128
`tap delay line 404 representing a 128 points input vector
`which is multiplied via a multiplier 406 by the coefficients
`a 128 points complex coefficients pre-designed filter 408.
`The 128 complex points result vector is folded by storing the
`multiplication result in the 128 points buffer 410 and sum(cid:173)
`ming the first 16 points with the second 16 points and so on 20
`using a summer 412. The folded result, which is referred to
`as an aliasing sequence 414, is processed through a 16 points
`FFT 416. The output of the FFT is multiplied via a multiplier
`418 by the modulation coefficients of a 16 points modulation
`coefficients cyclic buffer 420. The cyclic buffer which
`contains, for example, 8 groups of 16 coefficients, selects a
`new group each cycle. The real portion of the multiplication
`result is stored in the real buffer 422 as the requested
`16-point output 424.
`FIG. 5 illustrates the adaptive filter 500 (FIG. 1, 1161_n) of
`the present invention. The reference channel that contains
`the far end signal is stored in a tap delay line 502 and
`multiplied via a multiplier 504 by a filter 506 to obtain the
`estimated echo elements present in the beam signal. The
`estimated interference signal is then subtracted via subtrac(cid:173)
`tor 508 from the beam signal to obtain an echo free signal.
`The filter 506 is adjusted by the NLMS (Normalized Least
`Mean Square) processor 510 to estimate the transfer func(cid:173)
`tion of the loudspeaker to the beamforming process. In other
`words, the filter 506 simulates the transform that the far end
`signal goes through when transmitted by the loudspeaker
`into the air, bouncing back from the walls, received by the
`microphones and applied to the beamforming process of the
`present invention. In order to determine the precise filter
`coefficients, the system tries to obtain minimum energy at
`the output by modifying the filter coefficients (W) according
`to the following formula:
`
`8
`If the content of the near end signal is much stronger than
`the content of the far end signal the filter may diverge or
`converge to wrong values and start distorting the desired
`signal. It is preferred that the adaptation process will occur
`when relevant echo signals are present in the beam signal. To
`determine this, the system calculates the SNR of the far end
`signal and the SNR of the near end signal using the SNR
`estimation units 514,516. If speech is present in the near end
`signal, the SNR of the beam will be stronger than that of the
`reference channel. Thus, when the SNR of the reference
`channel raises up above a predetermined threshold over the
`near end SNR, the inhibit update logic block 518 immedi(cid:173)
`ately allows the LMS coefficient to be updated. Conversely,
`the inhibit update logic block will allow, for example, 100
`msec of adaptation and then inhibit the adaptation when the
`15 ratio drops below the threshold. At this point, the coefficients
`of the adaptive filter of the present invention "freeze" and
`the filtering will use the latest value of the coefficients. Later,
`when adaptation is no longer inhibited, the filters are
`updated from the values at which they were "frozen".
`The exemplary embodiment determines the pr