Multistage Echo Canceler Including Time Variation Compensation

U.S. patent applications Ser. No. 08/368,687 and Ser. No. 08/368,684 were filed on Jan. 4, 1995, and U.S. patent application Ser. No. 08/455,377 was filed concurrently herewith.

This invention relates to cancelation of echos in a communication circuit and an acoustic environment and, more particularly, to compensating for time variation in the echo path.

Echo cancelers are commonly used to compensate for both electrical and acoustic echos in communications systems. Typical echo cancelers use well known adaptive filtering algorithms to construct a model of the echo chapel which is excited by the same signal that is delivered to the actual echo channel. In some instances, the echo path can be time varying, for example, when a person or some other object moves about in an acoustic environment where an acoustic echo is being canceled. In such situations a large adaptation step size is often used to improve the convergence speed of the adaptive filtering algorithm used in the echo canceler. Use of a large step size, however, has detrimental effects on the overall performance of the echo canceler and any resulting residual echo, and tends to result in a less stable echo canceler. In order to effectively cancel acoustic echos, it is also desirable to employ an echo canceler having a "long" impulse response in order to model the echo duration found in typical rooms or the like. Use of such "long" echo cancelers having a long impulse response synthesis capability usually means slow convergence times of the adaptive filtering algorithms used in the echo canceler. Thus, when movement occurs in the room, or the impulse response of the echo path changes, the adaptive filtering algorithms used in the echo canceler have difficulty "reconverging" to the new echo path impulse response.

One technique for recovering from echo path changes includes the use of recursive update algorithms, which are known to converge faster than the conventional LMS technique. An arrangement disclosed in an article by V. A. Margo et al. entitled "Multiple Short-Length Adaptive Filters For Time-Varying Echo Cancellation", 1993 IEEE International Conference on Acoustics, Speech, and Signal Processing, Apr. 27-30, 1993, pages I-161-I-164, deals with sparse echo path responses by employing multiple separated echo cancelers that are spaced in time along the echo path. Unfortunately, acoustic echos can not in general be viewed as having a sparse impulse response. It has also been proposed to use a larger step size on the coefficients of the adaptive filtering algorithm being used that are large and a smaller step size on smaller coefficients, along with several other variants.

I have observed that for an acoustic system, most of the change in the echo path impulse response occurs as a result of movement close to either the microphone or the loudspeaker used in the system. Thus, the largest change in the echo path impulse response occurs in a relatively short time interval compared to the length of the whole echo path impulse response. Most of the remaining portion of the echo path impulse response remains substantially stationary. Therefore, if the echo path impulse response is treated as two separate impulse responses, one substantially stationary and one dynamic, i.e., time varying, two separate echo cancelers can be used to deal individually with each portion of the impulse response.

Therefore, the problems and limitations of prior acoustic echo canceler arrangements are overcome by employing a first echo canceler having a comparatively long first impulse response synthesis capability which is connected between a transmit path and receive path for generating a first error signal and for canceling echo signals in the transmit path, and at least a second echo canceler having a comparatively short second impulse response synthesis capability connected in series with a delay unit, with the series connection connected in parallel with the first echo canceler between the transmit and the receive path. The second echo canceler is supplied with the first error signal from the first echo canceler and is adaptively operating simultaneously with but independent of the first echo canceler to further cancel echos in the transmit path.

Specifically, the first echo canceler is intended to capture the substantially stationary and any slowly varying components of the echo path impulse response, and the second echo canceler is intended to capture the more time varying, i.e., dynamically varying, component of the echo path impulse response. Because the second echo canceler has a shorter impulse response synthesis capability than the first echo canceler, it will adapt significantly faster than the first echo cancel and, therefore, it can capture the more time varying component of the echo path impulse response.

I have further recognized that in certain applications, the more time varying component of the echo path impulse response may exist in a relatively short time interval. For instance, in the canceling of acoustic echos, the most time variation in the echo path impulse response results from the movement of objects and/or persons near either the microphone or the loudspeaker. This movement results in significant changes in the early portion of the echo path impulse response. Aligning the tap coefficients of the second echo canceler with this early portion of the echo path impulse response provides significantly enhanced echo cancelation performance over that achievable with only the first echo canceler. This is realized by placing a "short" fixed delay in series with the receive path signal to the second echo canceler.

In other applications, the time varying component of the echo path impulse response still exists in a relatively short time interval, but the time varying component relative to the overall echo path impulse response may change with time or may not be known a priori. Under these circumstances, it is desirable to dynamically align the coefficients of the second echo canceler over the echo path impulse response. This is realized by employing a dynamically adjustable delay in series with the receive path to the second echo canceler. In one embodiment, the delay value is dynamically generated in response to the tap coefficient values of the first echo canceler.

In another embodiment, the delay is dynamically set to a value such that a predetermined tap coefficient, for example the center one, of the second echo canceler is substantially aligned with the first echo canceler tap coefficient having the largest value.

In still another embodiment, a determination is made as to which of the first echo canceler tap coefficients values are changing the most. Then, the delay in series with the second echo canceler is dynamically adjusted to a value such that a predetermined tap coefficient, for example the center one, of the second echo canceler is substantially aligned with the first echo canceler tap coefficient having the largest value.

In yet another embodiment, the tap coefficients of the first echo canceler are divided into groups, each having a predetermined number of tap coefficients. Then, the changing nature of the tap coefficient values in each group is used in determining the dynamic delay value adjustment in order to position the tap coefficients of the second echo canceler relative to the tap coefficients of the first echo canceler.

FIG. 1 shows, in simplified block diagram form, details of an audio system including first and second echo cancelers in one embodiment of the invention employing a fixed delay in series with the second echo canceler;

FIG. 2 shows, in simplified block diagram form, details of an audio system including first and second echo cancelers in an embodiment of the invention employing a dynamically adjustable delay in series with the second echo canceler;

FIG. 3 shows, in simplified block diagram form, details of one adjustment generator which may be employed in the embodiment of FIG. 2;

FIG. 4 shows, in simplified block diagram form, details of another adjustment generator which may be employed in the embodiment of FIG. 2; and

FIG. 5 shows, in simplified block diagram form, details of still another adjustment generator which may be employed in the embodiment of FIG. 2.

FIG. 1 shows, in simplified block diagram form, one embodiment of the invention including an echo canceler arrangement that can be employed in either a full-band application or as one of a multiple of sub-bands. Specifically, a received signal x(k) is supplied to receive input 101 and, in turn, via receive path 102 to fixed delay 103, echo canceler 104 and loudspeaker 105. Echo canceler 106 is connected in series with fixed delay 103. Echo cancelers 104 and 106 may be any one of a number known in the art. It is noted that the signals being processed in echo cancelers 104 and 106, and fixed delay 103 are digital. The required digital to analog (D/A) and analog to digital (A/D) converters in receive path 102 and transmit path 112, respectively, are not shown. In this example, echo cancelers 104 and 106 include adaptive transversal filters 107 and 108, respectively, which are of a type broadly disclosed in U.S. Pat. No. 3,500,000 and also described in an article by D. L. Duttweiler entitled, "A Twelve-Channel Digital Echo Canceler", IEEE Transactions on Communications, VOL. COM-26, No. 5, May 1978, Pages 647-653. Briefly, echo canceler 104 includes adaptive transversal filter 107 and algebraic combining unit 109. Similarly, echo canceler 106 includes adaptive transversal filter 108 and algebraic combining unit 110. As indicated above, the inventive echo canceler arrangement shown in FIG. 1 can be employed in a sub-band echo canceler having multiple such sub-bands, the embodiment of FIG. 1 showing one such sub-band with the X and Y analysis filters not being shown and the E synthesis filter also not being shown. Such filter arrangements are shown in the Duttweiler U.S. patent application Ser. No. 08/368,687 and the Shaw U.S. patent application Ser. No. 08/368,684, noted above.

In practice microphone 111 picks up the desired speech signal from anybody talking in a room, enclosed area or the like, but also unavoidably picks up the audio output from loudspeaker 105. Conceptually, the audio signal picked up by microphone 111 has two acoustic echo path components, one echo path component is that which first echo canceler 104 is intended to capture, i.e., the substantially stationary and any slowly varying components of the echo path impulse response, and the other is that which the second echo canceler 106, in conjunction with delay 103, is intended to capture, namely, the more time varying, i.e., dynamically varying, component of the echo path impulse response. Because transversal filter 108 of second echo canceler 106 has a "shorter" impulse response synthesis capability than transversal filter 107 of first echo canceler 104, it will adapt significantly faster than the transversal filter 107 of first echo canceler 104 and, therefore, it can capture the more time varying component of the echo path impulse response. The slowly changing component is changing over seconds to minutes, while the more time varying component changes over 10's to 100's of milliseconds. In one example, not to be construed as limiting the scope of the invention, adaptive filter 107 of "long" echo canceler 104 includes 39 tap coefficients at 5 milliseconds thereby having a synthesis capability of 195 milliseconds, and adaptive filter 108 of "short" echo canceler 106 includes 8 tap coefficients at 5 milliseconds each, thereby having a synthesis capability of 40 milliseconds each (in a full-band acoustic echo canceler or in one sub-band of a sub-band acoustic echo canceler). It is noted that the time variation of the echo path impulse response is caused by the reflected echo components in the room, as well as movement of objects and/or people in the room.

In this example, first echo canceler 104 is primarily expected to synthesize the substantially stationary and any slower varying echo components of the echo path impulse response. To this end, adaptive transversal filter 107 of echo canceler 104 is relatively "long", i.e., has significantly more tap coefficients than adaptive filter 108 of echo canceler 106, and is configured to adapt relatively slowly, which will allow it to perform satisfactorily in synthesizing the substantially stationary component and any slowly varying component of the echo path impulse response. This slow adaptation is necessary in order to properly converge to the first echo estimate in the presence of the substantially stationary and any slowly varying components of the echo path impulse response. If the adaptation rate were too fast an erroneous first echo estimate could result. The signal y(k) from microphone 111 is supplied via transmission path 112 to algebraic combining unit 109, where a first echo estimate of the substantially stationary and any slowly varying components of the echo path impulse response, synthesized by adaptive transversal filter 107 of echo canceler 104, is subtracted from it to generate first error signal u(k). For purposes of this description transmission path 112 is considered to be the path from microphone to output terminal First error signal u(k) is supplied to adaptive transversal filter 107 where it is utilized in conjunction with the received signal x(k) to synthesize the first echo estimate, in well known fashion. First error signal u(k) is supplied to one input of algebraic combining unit 110 of echo canceler 106. Adaptive transversal filter 108 of echo canceler 106 synthesizes a second echo estimate of the time varying component of the echo path impulse response. To this end, adaptive transversal filter 108 is configured for fast adaptation. Additionally, note that in this example, because adaptive filter 108 has significantly fewer tap coefficients than adaptive filter 107, delay 103 is selected so that the tap coefficients of adaptive filter 108 are positioned in time relative to the echo path impulse response where the most time varying echo path impulse response component(s) are positioned relative to the tap coefficients of adaptive filter 107 impulse response. Typically, the center tap coefficient of adaptive filter 108 will be centered on the tap coefficient of adaptive filter 107 where the most time variation is known to occur. It should be noted, however, that it would not make sense to center the tap coefficients of adaptive filter 108 such that any of them would be below zero (0) time of the echo path coefficient of adaptive filter 107 at zero (0) time on the echo path impulse response, i.e., the first tap coefficient of adaptive filter 108 would, then, be aligned with the first tap coefficient of adaptive filter 107. Further, in certain applications the delay interval of fixed delay 103 may be selected to be zero (0). Additionally, in certain applications it may be desirable to skew the tap coefficients of adaptive transversal filter 108 one way or the other relative to the center tap coefficient.

The second echo estimate synthesized by adaptive transversal filter 108 is algebraically subtracted from first error signal u(k) by algebraic combining unit 110 to yield second error signal e(k). The second error signal e(k) is supplied to output terminal 113, as the desired output to be transmitted to a remote receiver, and is also supplied to adaptive transversal filter 108 where it is employed with the delayed input signal x(k) to adapt the second echo estimate, in well known fashion.

FIG. 2 shows, in simplified block diagram form, details of an audio system including first and second echo cancelers in an embodiment of the invention employing a dynamically adjustable delay in series with the second echo canceler. The elements of the embodiment shown in FIG. 2 which are identical in structure and function to those shown in FIG. 1 have been similarly numbered and will not be described again in detail.

Specifically, shown is adjustable delay 201 being connected in series between receiver path 102 and echo canceler 106, and therein, adaptive transversal filter 108. Also shown, is delay adjustment generator 202 which is supplied with tap coefficient values from adaptive transversal filter 107 of echo canceler 104, namely, tap coefficients C.sub.0, C.sub.1 through C.sub.N. Delay adjustment generator 202 employs tap coefficients C.sub.0, C.sub.1 through C.sub.N for generating a delay adjustment value .DELTA.D, which is supplied to adjustable delay 201 for dynamically adjusting the positions of the tap coefficients of adaptive filter 108 relative to the tap coefficients of adaptive filter 107 in order to cancel the more time varying component of the echo path impulse response. In certain applications, it may be desirable to shift the tap coefficients of the second adaptive filter 108 when the delay adjustment value .DELTA.D, which usually is an integer sample count. Thus, as the delay adjustment value .DELTA.D changes from one value to another, it is advantageous to shift the tap coefficients of second adaptive filter 108 in order to maintain relative alignment with the tap coefficients of the first adaptive filter 107 and to compensate for the change in the delay adjustment value .DELTA.D. A number of embodiments of delay adjustment generator 202 are shown in FIGS. 3-5, and described below.

FIG. 3 shows, in simplified block diagram form, details of one embodiment of adjustment generator 202 which may be employed in the embodiment of FIG. 2. Specifically, shown are magnitude units 301-0 through 301-N, to which tap coefficients C.sub.0, C.sub.1 through C.sub.N from adaptive transversal filter 107 (FIG. 2) are supplied for obtaining their respective magnitudes. Maximum value selector 302 selects the tap coefficient having the largest magnitude. Thereafter, algebraic combining unit 303 subtracts a prescribed value from the selected tap coefficient having the largest magnitude value, namely, M/2 in this example, in order to generate delay adjustment value .DELTA.D such that the tap coefficients of adaptive filter 108 are centered about the tap coefficient of adaptive transversal filter 107 having the largest magnitude. The delay adjustment value .DELTA.D is supplied to adjustable delay 201, where it is used to adjust the delay in series with echo canceler 106 to achieve the desired centering of the tap coefficients of adaptive transversal filter 108 about the tap coefficient of adaptive transversal filter 107 having the largest magnitude. Typically, the center tap coefficient of adaptive filter 108 will be centered on the tap coefficient of adaptive filter 107 where the most time variation is occurring. It should be noted, however, that it would not make sense to center the tap coefficients of adaptive filter 108 such that any of them would be below zero (0) time of the echo path coefficient of adaptive filter 107 at zero (0) time on the echo path impulse response, i.e., the first tap coefficient of adaptive filter 108 would, then, be aligned with the first tap coefficient of adaptive filter 107. Additionally, in certain applications it may be desirable to skew the tap coefficients of adaptive transversal filter 108 one way or the other relative to the center tap coefficient.

FIG. 4 shows, in simplified block diagram form, details of another embodiment of adjustment generator 202 which may be employed in the embodiment of FIG. 2. Specifically, shown, are magnitude units 401-0 through 401-N, to which tap coefficients C.sub.0, C.sub.1 through C.sub.N from adaptive transversal filter 107 (FIG. 2) are supplied for obtaining their respective magnitudes. Long term averages of the magnitudes of tap coefficients C.sub.0, C.sub.1 through C.sub.N are obtained via low pass filters (LPFs) 402-0, 402-1 through 402-N and associated algebraic combining units 403-0, 403-1 through 403-N, respectively. As shown the output from each of LPFs 402 is algebraically subtracted via algebraic combining units 403 from the current value of the corresponding magnitude values from units 401 for the associated tap coefficients to yield difference values .DELTA.C.sub.0, .DELTA.C.sub.1 through .DELTA.C.sub.N. Then, the magnitudes of difference values .DELTA.C.sub.0, .DELTA.C.sub.1 through .DELTA.C.sub.N are obtained via magnitude units 404-0, 404-1 through 404-N. Maximum value selector 405 selects the long term average tap coefficient having the largest differential magnitude value of .DELTA.C.sub.0, .DELTA.C.sub.1 through .DELTA.C.sub.N. Thereafter, algebraic combining unit 306 subtracts a prescribed value from the selected tap coefficient, namely, M/2 in this example, in order to generate delay adjustment value .DELTA.D such that the tap coefficients of adaptive filter 108 (FIG. 2) are centered about the tap coefficient of adaptive transversal filter 107 having the largest difference magnitude. The delay adjustment value .DELTA.D is supplied to adjustable delay 201 (FIG. 2), where it is used to adjust the delay in series with echo canceler 106 to achieve the desired centering of the tap coefficients of adaptive transversal filter 108 about the tap coefficient of adaptive transversal filter 107 having the largest difference magnitude. Typically, the center tap coefficient of adaptive filter 108 will be centered on the tap coefficient of adaptive filter 107 where the most time variation is occurring. It should be noted, however, that it would not make sense to center the tap coefficients of adaptive filter 108 such that any of them would be below zero (0) time of the echo path coefficient of adaptive filter 107 at zero (0) time on the echo path impulse response, i.e., the first tap coefficient of adaptive filter 108 would, then, be aligned with the first tap coefficient of adaptive filter 107. Additionally, in certain applications it may be desirable to skew the tap coefficients of adaptive transversal filter 108 one way or the other relative to the center tap coefficient.

FIG. 5 shows, in simplified block diagram form, details of still another embodiment of delay adjustment generator 202, which may be employed in the embodiment of FIG. 2. Specifically, in this embodiment of delay adjustment generator 202 the tap coefficients from adaptive filter 107 (FIG. 2) are arranged into predetermined groups. In this example, each group has an equal number of tap coefficients, although in certain applications this may not be the case. Accordingly, shown are a first group including tap coefficients C.sub.0, C.sub.1 through C.sub.L-1, a second group including tap coefficients C.sub.L, C.sub.L+1 through C.sub.2L-1, through a last group including tap coefficients, C.sub.XL, C.sub.XL+1 through C.sub.XL+L-1. Also shown, are magnitude units 501-0, 501-1 through 501-L-1, to which tap coefficients C.sub.0, C.sub.1 through C.sub.L-1, respectively, from adaptive transversal filter 107 (FIG. 2) are supplied for obtaining their respective magnitudes, magnitude units 501-L, 501-L+1 through 501-2L-1, to which tap coefficients C.sub.L, C.sub.L+1 through C.sub.2L-1, respectively, are supplied for obtaining their respective magnitudes, and magnitude units 501-L, 501-XL+1 through 501+-L-1, to which tap coefficients C.sub.L, C.sub.L+1 through C.sub.2L-1, respectively, are supplied for obtaining their respective magnitudes. The coefficient magnitude value outputs from magnitude units 501 for each group are supplied to a corresponding algebraic combining unit, namely, outputs from magnitude units 501-1 through 501-L-1 are supplied to summing unit 502-B1, outputs from magnitude units 501-L through 501-2L-1 are supplied to summing unit 502-B2, and outputs from magnitude units 501-XL through 501-XL+L-1 are supplied to summing unit 502-BX. Note that the coefficient magnitude outputs from any intervening groups between the second group and the last group are supplied to a corresponding summing unit 502. Long term averages of the summed magnitudes of the tap coefficients from each of the summing units 502 are obtained by supplying the summed values from summing units 502-B1, 502-B2 through 502-BX to LPFs 503-B1, 503-B2 through 503-BX, respectively, and to algebraic combing units 504-B1, 504-B2 through 504-BX, respectively, where they are subtracted from the outputs from LPFs 503-B1, 503-B2 through 503-BX, respectively, to yield difference values .DELTA.C.sub.B1, .DELTA.C.sub.B2 through .DELTA.C.sub.BX. Then, the magnitudes of difference values .DELTA.C.sub.B1, .DELTA.C.sub.B2 through .DELTA.C.sub.BX are obtained via magnitude units 505-B1, 505-B2 through 505-BX. Maximum value selector 506 selects the largest of the long term average tap coefficient difference magnitude value of .DELTA.C.sub.B1, .DELTA.C.sub.B2 through .DELTA.C.sub.BX. Then, multiplier unit 507 multiples the selected difference magnitude value by the number of tap coefficients in each of the groups the groups, namely, L. Thereafter, algebraic combining unit 508 subtracts a prescribed value from the output from multiplier unit 507, namely, M/2 in this example, in order to generate delay adjustment value .DELTA.D such that the tap coefficients of adaptive filter 108 (FIG. 2) are centered about the tap coefficient of adaptive transversal filter 107 having the largest difference magnitude value. The delay adjustment value .DELTA.D is supplied to adjustable delay 201 (FIG. 2), where it is used to adjust the delay in series with echo canceler 106 to achieve the desired centering of the tap coefficients of adaptive transversal filter 108 about the tap coefficient of adaptive transversal filter 107 having the largest difference magnitude value. Typically, the center tap coefficient of adaptive filter 108 will be centered on the tap coefficient of adaptive filter 107 where the most time variation is known to occur. It should be noted, however, that it would not make sense to center the tap coefficients of adaptive filter 108 such that any of them would be below zero (0) time of the echo path coefficient of adaptive filter 107 at zero (0) time on the echo path impulse response, i.e., the first tap coefficient of adaptive filter 108 would, then, be aligned with the first tap coefficient of adaptive filter 107. Additionally, in certain applications it may be desirable to skew the tap coefficients of adaptive transversal filter 108 one way or the other relative to the center tap coefficient.

Although several arrangements have been disclosed regarding alignment of the tap coefficients of the second adaptive filter relative to the tap coefficients of the first adaptive filter, and for generating the delay adjustment signal .DELTA.D, it will be apparent to those skilled in the art that other such arrangements may be employed without departing from the spirit or scope of the invention. For example, a so-called center-of-gravity technique may be employed to align the tap coefficients of the second adaptive filter relative to the tap coefficients of the first adaptive filter, and the groups of tap coefficients of the first adaptive filter employed in generating the delay adjustment signal .DELTA.D may have a different number of tap coefficients per group.