PATENT NUMBER
`
`I
`
`6049607
`llllllllllllllllllllllllllllllllllllllllllll.
`6049607
`
`APR 1 l 2000
`
`rH'(
`Q.A. I). •t 0./
`
`!. i' i{':f
`
`U.S. UTILITY PATENT APPLICATION
`PATENT DATE
`O.I.P.E •.
`
`•
`
`I
`
`SECTOR CLASS 38·-·······
`
`SUBCLASS
`a~~--~----·...:.. ..
`I . -r·
`
`..... -
`
`!
`
`ARTUNIT
`,
`~ U.../. .. ?
`~-7!_;>'.
`~L-7 v.?7FILEo WITH: D o1sK (CRF) D FICHE
`
`{
`
`(Attached in pocket on right Inside flap)
`
`PREPARED AND APPROVED FOR ISSUE
`
`ISSUING CLASSIFICATION
`
`ORIGINAL
`
`CROSS REFERENCE(S)
`
`CLASS
`
`SUBCLASS
`
`CLASS
`
`SUBCLASS (ONE SUBCLASS PER BLOCK)
`
`INTERNATIONAL CLASSIFICATION
`
`D Continued on Issue Slip Inside File Jacket
`
`DRAWINGS
`
`Total Clai/"
`37
`
`I
`
`(date)
`
`subsequent to
`has been disclaimed.
`D b) The term of this patent shall
`not extend beyond the expiration date
`of U.S Patent. No. ____ _
`
`W. ISEN
`SUPERVISORY PATENT EXAMINER
`T~QtR'IQLQa¥l CENTER 270~oate)
`
`D c) The terminal _months of
`this patent have been disclaimed.
`
`IJ[J/dj
`
`(Date)
`
`WARNING:
`The Information disclosed herein may be restricted. Unauthorized disclosure may be prohibited by the United States Code Title 35, Sections 122, 1.8·1 and
`Possession outside the U.S. Patent & Trademark Office Is restricted to authorized employees and contractors only.
`
`Form PT0·436A
`(Rev. 10/97)
`
`·.
`
`(LABEL AREA)
`Issue Fee· .n
`
`1
`
`(FACE)
`
`Petitioner Apple Inc.
`Ex. 1002, p. 1
`
`

`

`·ADPI .,.. - ~'"'"f\N
`~·" Tfi""J.£1T
`11 L,-1~~ ; 1v ~
`r P. • l:n
`. .llfll!llllli IIIII llli]Ulfflllll 11111111
`09157035
`
`CONTENTS
`Date received
`(Incl. c. of M.)
`or
`Date Mailed
`
`~~. I'IALS _ .. - . - -
`SEp- 2 5 S:8 2 ~
`
`Date received
`(Incl. C. of M.)
`or
`Date Mailed
`
`42. _ _ _ _ _ _ _ _ _ _ _
`
`43. _ _ _ _ _ _ _ _ _ _ _ - - - - - -
`
`44. ________________ - - - - - - -
`
`4 5 . - - - , . - - - - - - - - - - - - - - - - - - -
`46. _______________ - - - - - - -
`
`47.
`
`4 8 . - - - - - - - - - -
`
`49.-----------------
`50. _ _ _ _ _ _ _ _ _ _
`
`5 1 . - - - - - - - - - - - - - - - - - - -
`52. ____ ~---------- - - - - - - -
`~-------------- --------
`54. _ _ _ _ _ _ _ _ _ _ _ _ - - - - - -
`
`7. _ _ _ _ _ _ _ _ _ _
`
`8 . - - - - - - - - - - ------.:
`9. _ _ _ _ _ _ _ _ _ _ - - - - -
`10. _ _ _ _ _ _ _ _ _ _
`
`11. _ _ _ _ _ _ _ _ _ _
`
`12. _ _ _ _ _ _ _ _ _ _
`
`13. _ _ _ _ _ _ _ _ _ _
`
`14 . - - - - - - - - - - - - - - -
`
`5 5 . - - - - - - - - - - - - - -
`
`1 5 . - - - - - - - - - -
`16. _ _ _ _ _ _ _ _ _ _ - - - - -
`
`17. _ _ _ _ _ _ _ _ _ _ - - - - -
`18. _ _ _ _ _ _ _ _ _ _
`
`5 6 . - - - - - - - - - - - - -
`57. ____________ ~ - - - -
`58. ___________ _
`
`59. _ _ _ _ _ _ _ _ _ _;___ - - - - -
`
`1 9 . - - - - - - - - - -
`
`2 .0 . - - - - - - - - - -
`
`60. ---------~--
`
`61. - - - - - - - - - - - - - -
`
`21 . - - - - - - - - - - - - - - -
`
`2 2 . - - - - - - - - - -
`23. _ _ _ _ _ _ _ _ _ _ _ - - - - -
`
`'24. _ _ _ _ _ _ _ _ _ _ - - - - -
`
`6 2 . - - - - - - - - - -
`63. _____________ - - - - - -
`
`64. ______________ - - - - - -
`65. _ _ _ _ _ _ _ _ _ _ _
`
`2 5 . - - - - - - - - - -
`
`2 6 . - - - - - - - - - -
`
`2 7 . - - - - - - - - - -
`28. _ _ _ _ _ _ _ _ _ _
`
`66. _ _ _ _ _ _ _ _ _ __
`
`6 7 . - - - - - - - - - - - -
`
`6 8 . - - - - - - - - - - -
`
`6 9 . - - - - - - - - - - -
`
`29. - - - - - ' - - - - - -
`
`70. - - - - - - - - - - - - - - ---""-"'--:o---
`
`30. - - - - - - - - - -
`31. _ _ _ _ _ _ _ _ _ _ - - - - -
`
`71. - - - - - - - - - - - - -
`72., _ _ _ _ _ _ _ _ _ _ _
`
`·32. -------'---~- - - - - -
`3 3 . - - - - - - - - - - - - - - -
`
`3 4 . - - - - - - - - - -
`
`3 5 . - - - - - - - - - -
`36. _ _ _ _ _ _ _ _ _ _
`
`37., _ _ _ _ _ _ _ _ _ _
`
`3 8 . - - - - - - - - - : - - -
`3 9 . - - - - - - - - - -
`
`4 0 . - - - - - - - - - - - - - - -
`
`41 . - - - - - - - - - - - - - - -
`
`73. _ _ _ _ --,.-_ _ _ _ _ _ - - - - -
`
`7 4 . - - - - - - - - - - - - -
`75. _ _ _ _ __.:... _ _ _ _ _ -:--
`76. --------=------'--- ------'J-1'/.{~~-
`77. _ _ _ _ _ _ _ _ _ _ _
`
`78. _ _ _ _ _ _ _ _ _ _ - - - - - -
`
`79. _ _ _ _ _ _ _ _ _ _ _ - - - -
`
`8 0 . - - - - - - - - - - - -
`
`8 1 . - - - - - - - - - - - -
`82. _ _ !,___ ______ _
`
`(FRONT)
`
`Petitioner Apple Inc.
`Ex. 1002, p. 2
`
`

`

`SERIAL NUMBER
`
`09/157,035
`
`FILING DATE
`
`09/18/98
`
`~ JOSEPH MARASH, HAIFA, ISRAEL; BARUCH BERDUGO, KIRIAT-ATA, ISRAEL.
`()
`::::;
`0..
`0..
`~
`
`**CON'I'INUING DOMESTIC DATA*********************
`VERIFIED
`
`!/f!ll.c;LtJ /-····
`
`_.,.r'
`
`**371 (NAT'L STAGE) DATA*********************
`VERIFIED
`,.
`/ /
`~~/'
`'
`
`**FOREIGN APPLICA~IONS************
`VERIFIED
`.. /_..,
`
`I .. REQUIRED, FOREIGN FILIN5 LI<::!ENSE GRANTED 04/27/99 ** SMALL ENTITY **
`
`STATE OR
`·
`Dyes ~o
`Foreign Priorit'f claimed
`35 USC 119 (a·d) conditions met..,.,gyes ono OMet after Allowance COUNTRY
`\]_J.:!j'
`ILX
`
`lnl' IBIS
`
`lnl' IBIS
`
`Verified and Acknowledged
`
`SHEETS
`DRAWING
`7
`
`TOTAL
`CLAIMS
`37
`
`INDEPENDENT
`CLAIMS
`3
`
`(/)
`
`'l'HOMAS J KOWALSKI
`i:3
`F'ROMMER LAWRE!I~,CE u HAUG
`~ 745 FIFTH AVENUE
`~ NEW YORK NY 10151
`
`INTERFERENCE CANCELING METHOD AND APPARATUS
`
`w
`~ ;::
`
`FEES: Authority has been given in Paper
`No.
`to cnarg~/credit DEPOSIT ACCOUNT
`NO.
`for the following:
`
`$647
`
`!,·o
`r-------------.---------------------------~-------------.------------------·---·------------~
`FILING FEE
`All F~s~
`RECEIVED
`0 1.16 Fees {Filing)
`8 1. 17 Fees (Processing Ext. of time)
`1.18 Fees (Issue)
`0 Other
`0 Credit
`L...-----L---------1....:=----------'---
`
`'
`
`J
`
`'
`
`Petitioner Apple Inc.
`Ex. 1002, p. 3
`
`

`

`FROMMER LAWRENCE & HAUG LLP
`745 Fifth Avenue
`New York, New York 1015~
`Tel (212) 588-0800
`Fax (212) 588-0500
`PATENT APPLICATION TRANSMITTAL
`Date: September 18,
`Re :
`6 7 0 0 2 5 - 7 0 0 T
`THE COMMISSIONER OF PATENTS AND TRADEMARKS
`Box PATENT APPLICATION
`Washington, D.C. 20231
`
`1998
`
`TO:
`
`Sir:
`
`With reference to~~iling in the United States Patent and
`Trademark Office
`,_
`application-~- patent in the name of:
`PH MARASH an~RUCH BERDUG~
`0
`
`entitled: INTERFERENCE CANCELING ME!'3:'II6::0 1dfB :P:PPARATUS
`
`following are enclosed:
`Specification (20 pages) and One Page of Abstract (p.
`37 Claims (including ~ independent claims; pp. 21-28)
`2 Sheets of Drawings (Figs. 1-7)
`--tlnSigned Declaration and Power of Attorney (2 pages)
`The filing fee will be paid later, in response to a
`Notice to File Missing Parts. Kindly accord the
`application a September 18, 1998 filing date and
`address all communications to the undersigned at the
`address above.
`
`2 9)
`
`"'~in; 1paperl { J ,/f_Lj_
`(T~ed or printed name of per~~
`-:t!J?:-&e,.
`""'· !d!LlL-U'Zt!P
`
`(Signature of person mailing paper or fee)
`
`Petitioner Apple Inc.
`Ex. 1002, p. 4
`
`

`

`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`APPLICATION FOR LETTERS PATENT
`
`PATENT
`670025-7007
`
`Applicant:
`
`Joseph MARASH and Baruch BERDUGO
`
`Title:
`
`INTERFERENCE CANCELING METHOD AND APPARATUS
`
`No. of Pages (Spec)
`
`20
`
`No. of Claims:
`
`37 (pp 21-28)
`
`No. of pages (Abstract)
`
`1
`
`(p 29)
`
`7 (Figs. 1-7)
`
`Sheets of Drawings:
`.
`EXPRESS M,AJ.~ 3S
`Mailing Label NumberiO~SIJ 1fo 0 as
`Date of Deposit
`September 18, 1998
`I hereby certify that this paper or fee is being
`deposited with the United States Postal Service
`"Express Mail Post Office to Addressee" Service
`under 37 CFR 1.10 on the date indicated above and
`is addressed to the Assistant Commissioner for Patents,
`Washington~. 20231, BOX NEW PATENT APPLICATION
`
`~uJd7fJ WJ7£/?
`
`Thomas J. Kowalski
`Reg .. No. 32,147
`I. Marc Asperas
`Reg. No. 37,274
`FROMMER LAWRENCE & HAUG, LLP
`745 Fifth Avenue
`New York, New York 10151
`(212) 588-0800
`FAX
`(212) 588-0500
`
`I I
`I f.
`
`~
`
`ANDREA.37\LAMAR\7007.COV
`
`Petitioner Apple Inc.
`Ex. 1002, p. 5
`
`

`

`PATENT
`670025-7007
`
`TITLE OF THE INVENTION
`
`INTERFERENCE CANCELING METHOD AND APPARATUS
`
`RELATED APPLICATIONS
`
`Reference is made to co-pending U.S. applications Serial Nos. 08/672,899
`
`(allowed), 09/130,923, 08/840,159, 09/059,503 and 09/055,709, each ofwhich 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
`
`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
`
`Tele-conferencing plays an extremely important role in communications today.
`
`The teleconference, particularly the telephone conference Cflll, 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 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,
`
`ANDREA.37\LAMAR\209l.AP3
`
`Petitioner Apple Inc.
`Ex. 1002, p. 6
`
`

`

`PATENT
`670025-7007
`
`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 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 systein 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 tge 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
`
`transmission of the reverberations, the half-duplex communication becomes a significant
`
`draViback 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.
`
`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)
`
`ANDREA.37\LAMAR\209J.AP3
`
`2
`
`Petitioner Apple Inc.
`Ex. 1002, p. 7
`
`

`

`PATENT
`670025-7007
`
`and subtracts those signals representing the echo from the near-end microphone 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 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 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
`
`froll!. 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 a minimum, leaving an
`
`echo-free signal.
`
`Important to the adaptation process ~s 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 ofthe reference channel and the output level. In
`
`ANDREA.3 7\LAMAR\209J.AP3
`
`3
`
`Petitioner Apple Inc.
`Ex. 1002, p. 8
`
`

`

`PATENT
`670025-7007
`
`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 ofNormalized 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 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 loudspeaker signal and the egho 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.
`
`ANDREA.37\LAMAR\209l.AP3
`
`4
`
`Petitioner Apple Inc.
`Ex. 1002, p. 9
`
`

`

`PATENT
`670025-7007
`
`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 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 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 ofmicrophones coulc;tbe 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.
`
`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 ofthe 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 systems is that the
`
`background noise from several systems is transmitted to all the participating systems and it is
`
`ANDREA.3 7\LAMAR\209l.AP3
`
`5
`
`Petitioner Apple Inc.
`Ex. 1002, p. 10
`
`

`

`PATENT
`670025-7007
`
`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
`
`It is therefore an object ofthe invention to provide an interference canceling
`
`system.
`
`It is another object of the invention to provide an interference 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.
`
`It is further an object ofthe 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
`
`con:(erencing 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 source. A reference input inputs the interference
`'
`signal generated by the interference source. A bea.rp. splitter beam-splits the target signal into a
`
`ANDREA.37\LAMAR\209l.AP3
`
`6
`
`Petitioner Apple Inc.
`Ex. 1002, p. 11
`
`

`

`PATENT
`670025-7007
`
`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 signals, whereby for each 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 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 ofthe present invention may further comprise an inhibitor.
`
`The inhibitor permits the adaptive filter to adapt (change coefficients) when a signal-to-noise
`
`ratio·ofthe 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 invention is a OFT
`
`filter bank using single side band modulation. Additionally, the present invention may comprise
`
`a beam selector for selecting at least one of a plurality ofbea11JS for adaptive filtering by the
`
`adaptive filter representing a direction from which the main signal is received. In this case, the
`
`ANDREA.37\LAMAR\209l.AP3
`
`7
`
`Petitioner Apple Inc.
`Ex. 1002, p. 12
`
`

`

`PATENT
`670025-7007
`
`adaptive filter updates coefficients representing 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 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 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 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 ofthe reference signal of the
`
`far end goes down.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`A more complete appreciation ofthe present invention 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.
`
`ANDREA.37\LAMAR\209I.AP3
`
`8
`
`Petitioner Apple Inc.
`Ex. 1002, p. 13
`
`

`

`PATENT
`670025-7007
`
`Fig. 3 illustrates the decimation unit of the present invention.
`
`Fig. 4 illustrates the beam splitting unit ofthe 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
`
`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 1 04 and converted into digital
`
`form by the AID converter 1 06. While Figure 1 appears to depict the microphone elements 1 02
`
`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 AID 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 sampling frequencies which are
`
`suitable as those skilled in the art will readily understand.
`
`The sampled signals of each microphone are stored in a tap delay line (not shown)
`
`and multiplied by a steering matrix in the beam forming unit 1 08 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 is not limited to any specific
`
`ANDREA.37\LAMAR 1209l.AP3
`
`9
`
`Petitioner Apple Inc.
`Ex. 1002, p. 14
`
`

`

`PATENT
`670025-7007
`
`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 11 0 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 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 closest direction to that actual and
`
`performs 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 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 1 00 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
`
`burden which is unrealistic to handle. By splitting 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 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
`
`ANDREA.37\LAMAR\2091.AP3
`
`10
`
`Petitioner Apple Inc.
`Ex. 1002, p. 15
`
`

`

`PATENT
`670025-7007
`
`lower frequencies where the echo is 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 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 of the selected
`
`beam is processed for echo reduction 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.
`
`The output of the recombined process is fed into a noise gate processor 120. The
`
`purp.ose 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. 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).
`
`ANDREA.37\LAMAR\209l.AP3
`
`11
`
`Petitioner Apple Inc.
`Ex. 1002, p. 16
`
`

`

`PATENT
`670025-7007
`
`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.
`
`Figure 2 illustrates the beamforming unit 200 (Figure 1, 108) ofthe 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 originated at a predetermined direction. The phase shift is achieved
`
`by multiplying the microphone signal stored in the tap delay lines 202 1_0 by a FIR filter
`
`coefficient or steering vector output from steering vector units 204 1_0
`
`•
`
`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_0 • 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_0 by its FIR and summ~,d with the other microphones after they
`
`have been multiplied. The process repeats for each direction tesulting in a beam output for each
`
`direction.
`
`ANDREA.37\LAMAR\209!.AP3
`
`12
`
`Petitioner Apple Inc.
`Ex. 1002, p. 17
`
`

`

`PATENT
`670025-7007
`
`Figure 3 illustrates the decimation unit 300 (Figure 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 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 low
`
`pass filter 306.
`
`Figure 4 illustrates the beam splitting unit 400 (Figure 1, 114, 128) ofthe 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", Ronald E. Crochiere, Prentice Hall Signal
`
`Processing Series or "Multirate Digitals Filters. Filter Banks. Polyphase Networks. and
`
`Applications A Tutorial", P. P. Vaidyanathan, Proceedings ofthe IEEE, Vol. 78, No. 1, January
`
`1990. The goal of the beam splitter is to split the input signal into a plurality oflimited 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 quantities of samples may be processed depending upon the
`
`processing power of the s.ystem as will be appreciated by thos'e skilled in the art.
`
`ANDREA.37\LAMAR\209l.AP3
`
`13
`
`Petitioner Apple Inc.
`Ex. 1002, p. 18
`
`

`

`PATENT
`670025-7007
`
`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 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 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.
`
`Figure 5 illustrates the adaptive filter 500 (Figure 1, 1161_0
`
`) 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 subtractor 508 from
`
`the oeam signal to 0 btain an echo free signal.
`
`The filter 506 is adjusted by the NLMS (Normalized Least Mean Square)
`
`processor 51 0 to estimate the transfer function of the loudspeaker to the beamforming process.
`