peT
`
`WORLD INTELLECTUAL PROPERTY ORGANIZATION
`International Bureau
`
`INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`WO 00/18099
`
`(11) International Publication Number:
`
`(51) International Patent Classification 6 :
`H04M 9/08, H04R 3/00
`
`Al
`
`(43) International Publication Date:
`
`30 March 2000 (30.03.00)
`
`(21) International Application Number:
`
`PCT/US99121186
`
`(22) International Filing Date:
`
`14 September 1999 (14.09.99)
`
`(81) Designated States: AU, CA, CN, IL, JP, US, European patent
`(AT, BE, CH, CY, DE, DK, ES, FI, FR, GB, GR, IE, IT,
`LU, MC, NL, PT, SE).
`
`Published
`With international search report.
`Before the expiration of the time limit for amending the
`claims and to be republished in the event of the receipt of
`amendments.
`
`(30) Priority Data:
`09/157,035
`
`18 September 1998 (18.09.98) US
`
`(71) Applicants (for all designated States except US): LAMAR
`SIGNAL PROCESSING, LTD. [-IlL]; 5th floor, Kohav
`Yokneam Building, P.O. Box 273, Yokneam 20692 (IL).
`ANDREA ELECTRONICS CORPORATION [US/uS]; 45
`Melville Park Road, Melville, NY 11747 (US).
`
`(72) Inventors; and
`(75) Inventors/Applicants (for US only): MARASH, Joseph
`[ILlIL]; Shim kin Street lA, 34750 Haifa (IL). BERDUGO,
`Baruch [lUlL]; Hanarkisim Street 6, 28000 Kiriat-Ata (IL).
`
`(74) Agents: KOWALSKI, Thomas, J. et al.; Frommer Lawrence &
`Haug LLP, 745 Fifth Avenue, New York, NY 10151 (US).
`
`(54) Title: INTERFERENCE CANCELING METHOD AND APP ARA TUS
`
`BEAN
`FORMER
`
`DEClNATION
`
`BEAM SELECT
`
`Sf'LfT
`
`BEAN
`:":RE""auf::ORED-:--1 SELECT LOGIC
`DIRECTION
`
`DECINATION
`
`BANOO
`
`128
`I--r----i SPLIT 1----1--"
`
`WDfS
`
`(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 (114) 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 frequency bands. The adaptive filter (500)
`adaptively filters each band-limited interference signal from each corresponding band-limited target signal. The beam selector (112) 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 (120) gates the main signal adaptatively filtered by the adaptive filter by opening the noise gate (120) 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 (500)
`cancels an echo present in the reference signal broadcast to a far end of the teleconference.
`
`RTL607_1021-0001
`
`Realtek 607 Ex. 1021
`
`

`
`FOR THE PURPOSES OF INFORMATION ONLY
`
`Codes used to identify States party to the PCT on the front pages of pamphlets publishing international applications under the PCT.
`
`AL
`AM
`AT
`AU
`AZ
`BA
`BB
`BE
`BF
`BG
`BJ
`BR
`BY
`CA
`CF
`CG
`CH
`CI
`CM
`CN
`CU
`CZ
`DE
`DK
`EE
`
`Albania
`Annellia
`Austria
`Australia
`Azerbaijan
`Bosnia and Herzegovina
`Barbados
`Belgium
`Burkina Faso
`Bulgaria
`Benin
`Brazil
`Belarus
`Canada
`Central African Republic
`Congo
`Switzerland
`Cl\te d'Jvoire
`Cameroon
`China
`Cuba
`Czech Republic
`Gennany
`Denmark
`Estonia
`
`ES
`FI
`FR
`GA
`GB
`GE
`GH
`GN
`GR
`HU
`IE
`IL
`IS
`IT
`JP
`KE
`KG
`KP
`
`KR
`KZ
`LC
`LI
`LK
`LR
`
`Spain
`Finland
`France
`Gabon
`United Kingdom
`Georgia
`Ghana
`Guinea
`Greece
`Hungary
`Ireland
`Israel
`Iceland
`Italy
`Japan
`Kenya
`Kyrgyzstan
`Democratic People's
`Repnblic of Korea
`Republic of Korea
`Kazakstan
`Saint Lucia
`Liechtenstein
`Sri Lanka
`Liberia
`
`LS
`LT
`LU
`LV
`MC
`MD
`MG
`MK
`
`ML
`MN
`MR
`MW
`MX
`NE
`NL
`NO
`NZ
`PL
`PT
`RO
`RU
`SD
`SE
`SG
`
`Lesotho
`Lithuania
`Luxembourg
`Latvia
`Monaco
`Republic of Moldova
`Madagascar
`The fonner Yugoslav
`Republic of Macedonia
`Mali
`Mongolia
`Mauritania
`Malawi
`Mexico
`Niger
`Netherlands
`Norway
`New Zealand
`Poland
`Portugal
`Romania
`Russian Federation
`Sudan
`Sweden
`Singapore
`
`SI
`SK
`SN
`SZ
`TD
`TG
`TJ
`TM
`TR
`TT
`UA
`UG
`US
`UZ
`VN
`YU
`ZW
`
`Slovenia
`Slovakia
`Senegal
`Swaziland
`Chad
`Togo
`Tajikistan
`Turkmenistan
`Turkey
`Trinidad and Tobago
`Ukraine
`Uganda
`United States of America
`Uzbekistan
`Viet Nam
`Yugoslavia
`Zimbabwe
`
`RTL607_1021-0002
`
`

`
`WO 00/18099
`
`PCTlUS99/21 186
`
`TITLE OF THE INVENTION
`
`1
`
`INTERFERENCE CANCELING METHOD AND APPARATUS
`
`5
`
`RELATED APPLICATIONS
`
`Reference is made to co-pending U.S. applications Serial Nos.
`
`09/157,035,08/672,899 (allowed), 09/130,923, 08/840,159, 09/059,503 and
`
`10
`
`09/055,709, each of which is hereby incorporated 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
`
`15
`
`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
`
`communications.
`
`BACKGROUND OF THE INVENTION
`
`20
`
`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 communicate.
`
`Internet conferencing, which provides a personal forum by which the speakers can see
`
`25
`
`one another, is enormously 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, transmitted to a "far end system" and broadcast by a far-end
`
`RTL607_1021-0003
`
`

`
`wo 00118099
`
`PCTJUS99/21186
`
`2
`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 their
`
`reverberations and transmits them back to the far-end, together with the desired
`
`5
`
`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 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
`
`10
`
`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
`
`15 microphone is blocked for a prolonged period to avoid transmission of the
`
`reverberations, the half-duplex communication 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 becomes quite annoying.
`
`20
`
`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 at the near-
`
`end loudspeaker, estimates the resulting signal present at the near-end microphone
`
`(including the reverberations) and subtracts those signals representing the echo from
`
`the near-end microphone signals. The echo-free signals are then transmitted back to
`
`25
`
`the far-end system.
`
`RTL607_1021-0004
`
`

`
`WO 00/18099
`
`PCTlUS99/21186
`
`3
`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-
`
`5
`
`end loudspeaker to the near-end microphone, the room structure, position of the
`
`system and even the presence of people in the room. Since it is impossible 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 system is updated
`
`10
`
`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, Dec. 1967) with the far-
`
`end signal used as the reference signal. The LMS filter estimates the interference
`
`elements (echoes) present in the interfered channel by mUltiplying the reference
`
`channel by a filter and subtracting the estimated elements from the interfered signal.
`
`15
`
`The resulting output is used for updating the filter coefficients. The adaptation
`
`process will converge when the resulting output energy is at 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
`
`20
`
`is controlled by a predetermined adaptation coefficient, the level of the reference
`
`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
`
`25
`
`adaptation coefficient by the reference channel energy, this method is called the
`
`RTL607_1021-0005
`
`

`
`WO 00/18099
`
`PCT/US99/21186
`
`4
`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, ifnot designed properly, may fail to track when large and fast changes in
`
`5
`
`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 than the non-interfering signal, there is not much to reduce and the
`
`10
`
`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 loudspeaker 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
`
`15
`
`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 number 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
`
`20
`
`using a linear combination of microphones. By multiplexing the microphones or
`
`steering the directional audio 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
`
`25
`
`directional beam and prevent the transient echo, one can either perform continuous
`
`RTL607_1021-0006
`
`

`
`WO 00/18099
`
`PCTIUS99/21186
`
`5
`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 computation load required to perform numerous echo-canceling
`
`systems concurrently on each of the microphones or allowable beams is not realistic.
`
`5
`
`An efficient echo-canceling system is needed which will reduce the
`
`echo drastically. However, because of the large 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
`
`10
`
`place.
`
`Another problem typical to multi-user conferencing systems 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
`
`15
`
`systems.
`
`OBJECTS AND SUMMARY OF THE INVENTION
`
`It is therefore an object ofthe invention to provide an interference
`
`canceling system.
`
`It is another object of the invention to provide an interference
`
`20
`
`canceling system to cancel interference while providing 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.
`
`RTL607_1021-0007
`
`

`
`WO 00118099
`
`PCTfUS99/21186
`
`6
`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
`
`5
`
`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 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
`
`10
`
`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 bearn-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 signals, whereby for each
`
`15
`
`band-limited target signal there is a corresponding band-limited interference signal.
`
`An adaptive filter adaptively filters, each band-limited interference signal from each
`
`corresponding band-limited target signal.
`
`When the target signal represents speech generated at a near end of a
`
`teleconference, the adaptive filter of the present invention cancels an echo present in
`
`20
`
`the reference signal 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 broadcast 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
`
`RTL607_1021-0008
`
`

`
`wo 00/18099
`
`PCT/US99/21186
`
`7
`a signal-to-noise ratio of the reference signal exceeds a predetermined threshold 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
`
`5
`
`invention is a DFT filter bank using single side band modulation. Additionally, the
`
`present invention may comprise a beam selector for selecting 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. In this case, the adaptive filter updates
`
`coefficients representing the transfoml function and comprehensively stores the
`
`10
`
`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 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 for gating the
`
`15 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, the noise gate determines the predetermined
`
`threshold by selecting a low threshold when a signal-to-noise ratio of the reference
`
`20
`
`signal of the far end is low, updating the predetermined threshold upwards when the
`
`signal-to-noise ratio of the reference signal of the far end goes up and gradually
`
`reducing the predetermined threshold when the signal-to-noise ratio of the reference
`
`signal of the far end goes down.
`
`RTL607_1021-0009
`
`

`
`WO 00118099
`
`PCTfUS99/21186
`
`8
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`A more complete appreciation of the present invention and many of its
`
`attendant advantages will be readily obtained by reference to the following detailed
`
`.5
`
`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 invention.
`
`10
`
`Fig. 4 illustrates the beam splitting unit of the present invention.
`
`Fig. 5 illustrates the adaptive filter of the present invention.
`
`Fig. 6 illustrates the recombining unit of the present invention.
`
`Fig. 7 illustrates the noise gate of the present invention.
`
`DETAILED DESCRIPTION
`
`15
`
`Figure 1 illustrates the exemplary echo canceling system of the present
`
`invention. An array of microphone elements 102 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 AID converter 106. While Figure 1
`
`appears to depict the microphone elements 102 as an array, it will be appreciated by
`
`20
`
`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 64KHz per
`
`channel but, of course, may be substituted with other types of converters and
`
`25
`
`sampling frequencies which are suitable as those skilled in the art will readily
`
`understand.
`
`RTL607_1021-0010
`
`

`
`wo 00118099
`
`9
`The sampled signals of each microphone are stored in a tap delay line
`
`PCT/US99/21186
`
`(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
`
`5
`
`present invention 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, 8KHz and decimated by decimating unit 110 to reduce the sampling rate and
`
`hence the computational load on the system. In this manner, the sampling rate is
`
`reduced to 16 KHz for each channel. It shall be appreciated that the decimation
`
`10
`
`process may be performed prior to the beamforming process to further reduce the
`
`processing burden.
`
`The system receives an indication as to the direction of the 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
`
`15
`
`closest direction to that actual and perfonns echo cancellation 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
`
`20
`
`frequency band separately. Without this arrangement, an 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 16KHz, to have 1600 coefficients. Such a
`
`long adaptive filter is not likely to converge in the time that the echo is present.
`
`Moreover, an adaptive filter of 1600 coefficients presents an enormous processing
`
`25
`
`burden which is unrealistic to handle. By splitting the bands into, for example, 16
`
`RTL607_1021-0011
`
`

`
`wo 00/18099
`
`PCTJUS99/21186
`
`10
`channels the present invention reduces the sampling rate for each adaptive filter to, in
`
`this case, 2 KHz per channel. It will be appreciated that, not only is this system much
`
`more manageable, the adaptive filters can be optimized for each frequency separately
`
`by, for example, selecting longer filters for lower frequencies where the echo is
`
`5
`
`typically located and shorter filters for higher frequencies where the echo is less. In
`
`this 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 preventing the
`
`problem of a broadband filter concentrating on a band limited interference while
`
`10
`
`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 block 122, AID converters 124, decimating unit 126
`
`and splitter 128. Each band ofthe selected beam is processed for echo reduction
`
`15
`
`using echo canceling units 116 1-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.
`
`20
`
`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 invention measures the level of the steady noise
`
`and blocks up the signals that are below a certain threshold above this noise level.
`
`25 When residual echoes are present they may penetrate the process and be transmitted
`
`RTL607_1021-0012
`
`

`
`wo 00/18099
`
`PCT/US99/21186
`
`11
`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
`
`5
`
`being transmitted while leaving only speech signals from the near end.
`
`Figure 2 illustrates the beamforming unit 200 (Figure 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
`
`10
`
`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
`
`originated at a predetermined direction. The phase shift is achieved by multiplying
`
`the microphone signal stored in the tap delay lines 202 1-n by a FIR filter coefficient or
`
`15
`
`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 204 1_n . The
`
`20 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.
`
`RTL607_1021-0013
`
`

`
`wo 00/18099
`
`12
`Figure 3 illustrates the decimation unit 300 (Figure 1,110, 126) of the
`
`PCTlUS99/21186
`
`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,
`
`5
`
`it is necessary to make sure that the signal does not contain elements above 8KHz
`
`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
`
`10
`
`low pass filter 306.
`
`Figure 4 illustrates the beam splitting unit 400 (Figure 1, 114, 128) of
`
`the present invention. Although various beam splitting techniques may be employed,
`
`it is preferred that the generalized DFT filter bank using single side band modulation
`
`be employed as described, for example, in "Multirate Digital Signal Processing",
`
`15
`
`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
`
`20
`
`example, 8 input points at a time resulting in 16 output points each representing 1
`
`time domain sample per frequency band. Of course, other quantities 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
`
`25
`
`404 representing a 128 points input vector which is mUltiplied via a multiplier 406 by
`
`RTL607_1021-0014
`
`

`
`WO 00/18099
`
`PCT/US99/21186
`
`13
`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 summing the first 16 points with the second 16 points and so on
`
`using a summer 412. The folded result, which is referred to as an aliasing sequence
`
`5
`
`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
`
`10
`
`424.
`
`Figure 5 illustrates the adaptive filter 500 (Figure 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
`
`15
`
`is then subtracted via subtractor 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 function of the loudspeaker to the
`
`beamforming process. In other words, the filter 506 simulates the transform that the
`
`20
`
`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:
`
`25
`
`(1) Wen, t+ 1)= Wen, t)+ X(n)*E* A
`
`RTL607_1021-0015
`
`

`
`WO 00/18099
`
`PCTJUS99/21186
`
`14
`Wherein, n is the nth coefficient ofW, t is time, E is the error signal output and A is a
`
`normalized factor that determines the size of the adaptation process. The
`
`normalization is obtained by dividing a fixed value (adaptation factor) by P, the
`
`reference channel energy. The normalization is intended to prevent fast steps when
`
`5
`
`the signal is strong (i.e., X and E are large) and small steps when weak (i.e., X and E
`
`are small) which provides smooth performance over all ranges of signal levels.
`
`When a fast attack in the reference signal appears, such as when an
`
`abrupt sound, e.g., speech, noise, is generated at the far end, the energy estimation
`
`process may be too slow in reaction resulting in large steps of adaptation and
`
`10
`
`divergence of the filter. To prevent this, the new X*X is compared to the energy
`
`estimation calculated by power estimator 512 and if the ratio exceeds a certain
`
`threshold (meaning a fast increase in the signal level) the value of X*X replaces the
`
`energy estimation.
`
`If the content of the near end signal is much stronger than the content
`
`15
`
`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,
`
`20
`
`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 immediately 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 ratio drops
`
`25
`
`below the threshold. At this point, the coefficients of the adaptive filter of the present
`
`RTL607_1021-0016
`
`

`
`wo 00/18099
`
`PCTlUS99/21186
`
`15
`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 predetermined threshold
`
`5
`
`for the inhibit update logic block 518 in discrete periods. The timing of these discrete
`
`periods is determined in part by the hysteresis that differentiates between the reaction
`
`time of the attack to that of the decay of the SNR ratios which are obtained through
`
`the reaction time of the energy calculation. More specifically, the SNR is computed
`
`by di