Abstract:
A method is presented for dynamic resource allocation in a speech signal echo canceler enabling more efficient echo cancellation and as a result the ability for an Integrated Circuit to handle additional channels than heretofore possible. This is accomplished by applying one or more of three efficiency enhancing strategies. First, no update of coefficients is computed or convolution performed if the power level of the far end speech signal is below a given threshold. Second, convolution is limited to the set of active taps (i.e., taps that account for most of the power in the echo). Third, new coefficients are computed only when the power of the error signal is greater than a given threshold. Lastly, the set of active coefficients is periodically updated. These strategies release computational resources from unnecessary computations and divert them to other channels that may be active.

Description:
FIELD OF INVENTION 
     The invention relates generally to improved methods of echo cancellation. Specifically, the invention improves upon the efficiency of echo cancellation by providing a dynamic allocation of echo cancellation resources, thus allowing for increased capacity of multi-channel echo canceler integrated circuits (ICs). 
     BACKGROUND OF THE INVENTION 
     Referring to FIG. 1, a prior art network, such as a telephone network is shown wherein an echo y(n) is generated when a far end signal x(n) crosses a hybrid local loop telephone termination  100 . The path through termination  100  will hereinafter be referred to as the echo path, and its impulse response will be referred to as the echo path impulse response. ‘n’ is used herein to refer to the index of the samples of the signal. 
     Methods of echo cancellation in networks are well known. Generally, an echo canceler device  300  receives signal x(n) as an input and computes an estimate ŷ(n) of the echo, y(n). In general, the estimate ŷ(n) at time instant n is determined by multiplying the current and past L-1 samples by L filter coefficients, respectively. The output from the echo canceler  300  is input to an adder  200  which outputs the difference between the estimated echo ŷ(n) and the signal s(n) which consists of the echo y(n) together with the near end signal, v(n), and the near end background noise, w(n). 
     When the coefficients correspond to those of the impulse response of the true echo path, the echo is canceled. However, the echo path is initially unknown and in addition may change over time. Therefore the filter coefficients are iteratively adjusted to adapt to the echo path&#39;s current response. To this end, the output of the adder  200  is fed back to the processor running the adaptive algorithms  375 . In each sample period, new coefficients are computed, resulting in a new estimate of the echo path impulse response. 
     The DTD (an abbreviation for Double Talk Detector) shown in block  400 , detects when both the far and near end speech are present simultaneously. In this event, the signal y(n) is not strictly the echo of x(n) but rather the combination of the echo, a near end speech signal and some noise. In this event, new coefficients should not be computed for filter  350  since they would be wrong. DTD  400  detects the double talk condition and instructs the echo canceler to continue to compute an estimate of the echo but not to adapt the coefficients. 
     The estimate of the echo, ŷ(n), is generally derived as follows: Assume a sampling rate of 8 kHz and an echo path impulse response of duration 64 ms. Then the number of coefficients, L, that must be adapted, is 512. Echo canceler device  300  comprises a processor executing a filter  350  and an adaptive algorithm  375 . The aim of the adaptation algorithms is to make the coefficients of the filter  350  equal to the corresponding coefficients of the actual impulse response of the echo path. Filter  350  performs a convolution of x(n) with the estimated impulse response by multiplying each filter coefficient with its corresponding sample of the far end signal, x(n) (the current sample x(n) and the previous L-1 samples), and adding all the L products. The result is the echo estimate ŷ(n). 
     As currently designed, adaptive echo cancelers compute new coefficients and an echo estimate ŷ(n) at each sampling instant. Currently, network echo canceler integrated circuits (ICs) are designed to process, for example, 32 channels. Thus, in the above example, the echo canceler IC must update 512 coefficients and perform a 512 tap convolution for each of the 32 channels every 1/8000 of a second, or 125 μs. It is desirable to increase the efficiency of echo cancelers such that an IC can handle a larger number of channels. 
     SUMMARY OF THE INVENTION 
     The subject invention provides a new echo cancellation method for voice signals which increases the computational efficiency of present-day echo cancelers such that a single echo canceler IC can handle a larger number of voice channels. This is accomplished by determining the active taps of the impulse response (i.e., those taps that have coefficients with significant magnitudes) and updating the filter coefficients only for the active taps and only when the short term power of the error signal e(n), which is the difference between the estimated echo and the actual echo, is greater than a predetermined threshold. If the error is below the predetermined threshold the filter continues to perform a convolution with the active taps using previously determined coefficients. Furthermore, additional efficiency for line echo cancelers is realized by advantageously performing the coefficient updates and convolution in only those intervals where the short time power of x(n) is above a specified threshold. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates a generic voice network with a line echo canceler. 
     FIG. 2 is a flow chart of the algorithm for one embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention seeks to enhance the ability of an echo canceler to handle increasing number of channels by efficiently allocating computational resources. Primary applicability of the method of the present invention will be to echo canceler ICs handling a large number of channels (for example several hundred), but not for single-channel cancelers. In accordance with the present invention, the per channel computational load of an echo canceler is reduced by applying one or more of the following strategies. 
     First, in contrast to many existing echo cancelers, much of the computation is eliminated during time intervals when there is no far end speech. This strategy is particularly relevant to line echo cancelers, such as those employed in the telephone network. In such applications, any particular channel is active, on average, only about fifty percent (50%) of the time. Thus approximately fifty percent (50%) of the computational load of a canceler IC is reduced by limiting the computations to only those channels that are active at any time. Furthermore, even during periods of otherwise active speech, there are pauses between words and sentences. One can determine if a channel is idle or active by monitoring the short term estimate of the power of x(n). When this estimate is below a specified threshold, not only is it unnecessary to update the coefficients, it is not even necessary to compute an estimate of the echo signal since there is no significant echo that needs to be cancelled. The threshold is particular to a given network, and those skilled in the art will know how to determine the threshold indicative of whether a channel is active or idle. 
     A second strategy employed by the present invention is to limit the adaptation process to only the active taps of the echo impulse response. The active taps are the most significant taps of the echo impulse response, the determination of which is described below. While the impulse response of a typical echo path has a duration of about 64 ms, which corresponds to 512 taps, the number of active taps is generally between 50 and 100. The method of the present invention periodically identifies the set of active taps and adapts only those. Also, it performs the convolution with just the active taps. 
     The third strategy employed by the present invention is not to adapt the filter coefficients when the short time power in the error signal is below a specified threshold. 
     Referring to FIG. 2, a flow chart is shown illustrating one embodiment of the present invention employing all three of the foregoing strategies. Starting at a particular time instant, a sample of the far end speech x(n) is taken, as shown in block  5 . An initial determination is made, as shown in block  10  as to whether the short time estimate of the power of the far end signal x(n) is greater than a given threshold  8 . As explained above, there is no need to update the coefficients or to compute the estimate of the echo if the far end signal x(n) is very small. Accordingly, and as shown in block  15 , if the estimated short term power of x(n) is below  8 , no computations are made, and the process starts over in the next sample period. 
     If the far end signal is significantly large so as to indicate the transmission of speech, then a determination is made in decision block  40  as to whether or not the current sample n is divisible by M as a whole integer. The determination step of block  40  is performed so as to adapt all of the coefficients, not merely those corresponding to the active taps, once every M sample periods. For all other time instants, only the active taps are adapted. The active taps are initially identified as all of the L taps. However, as described below, over time the set of active taps is narrowed to a much smaller sub-set of the L taps. 
     It should be noted that as M increases in value, the complexity of the method of the present invention as shown in FIG. 2, decreases. On the other hand, with larger M, the ability to quickly respond to echo path changes is degraded. Typically, a value M=10 has been found to be a good compromise between these two opposing tendencies. 
     If it is determined that n is divisible by M, then an error signal e(n), which is the difference between the echo y(n) and the estimated echo ŷ(n), is computed using all L taps of the impulse response, as shown in block  50 . Thereafter, as shown in block  55 , the coefficients corresponding to all of the L taps are adapted and updated. Any of several known algorithms may be used for this adaptation. Due to the efficiency enhancing steps used in accordance with the present invention, the simple, well known NLMS algorithm may be used advantageously to adapt new coefficients. More complex algorithms, which are otherwise desirable, are not necessary. 
     After updating the L coefficients, a new set of active taps is identified. While different approaches to determine the active taps may be identified, in one advantageous method, the active taps are identified, as shown in block  60 , by sorting all L coefficients in descending order of absolute value. The active set is then defined as the first L a  coefficients whose cumulative magnitude just exceeds the cumulative magnitude of all L coefficients multiplied by a threshold T. The threshold T is set to a value in the range between 0.9 and 1. From here the process starts over in the next sample period with all computations based on what has now been determined as the active set of coefficients. The active set is unchanged for M- 1  sample periods, although the values of the coefficients in this set may be updated as specified below. 
     Returning to the decision block  40 , if n is not divisible by M, then an error signal e(n), which is the difference between the echo y(n) and the estimated echo ŷ(n), is computed using the active taps of the impulse response, as shown in block  20 . In block  30  a third determination is made as to whether a certain decision function ε(n), which is a function of the error e(n), is greater than a given threshold. A good choice for this decision function is the normalized mean squared error defined as ε(n)=10 log [(&lt;e 2 (n)&gt;)/(&lt;y 2  (n)&gt;+α)], where α is a regularization parameter that prevents division by zero during silences between words. In this equation &lt;e 2 (n)&gt; is the average of e 2 (k) over all sample indices from n-N+1 to n, and &lt;y 2  (n)&gt;is the average of y 2 (k) over the same sample indices. The averaging window N should be chosen small enough so as to be able to track changes in the echo path adequately, yet long enough to get a stable estimate of power. Generally, this is approximately 100 ms. At each n, ε(n) is compared to a specified threshold, Th. The error is determined to be too small if ε(n) is less than Th. In such case, no adaptation is done. The threshold Th is typically set between −30 and −40 dB, a value that is several dB above the typical average power of the circuit noise. 
     If, on the other hand, the error is determined to be large enough (i.e., ε(n) is greater than Th), the active taps are updated, as shown in block  45 . As in the case of block  55 , the well known NLMS adaptive algorithm may be advantageously employed in this step. 
     It should be noted that the foregoing was described in connection with only one of the channels handled by the echo canceler IC. In practice the entire process must be repeated for each of the channels. 
     It is possible for an echo canceler to temporarily run out of resources. This can be attended to by foregoing coefficient updates on some of the active channels, or by increasing Th. 
     The foregoing merely illustrates the principles of the present invention. Those skilled in the art will be able to devise various modifications, which although not explicitly described or shown herein, embody the principles of the invention and are thus within its spirit and scope.