Abstract:
A communications device is presented for providing bi-directional audio communications between a near-end user and a far-end user via a bidirectional communications channel. The communications device includes an adaptive echo canceller receiving a near-end audio signal and a far-end audio signal and providing an echo-canceled near-end audio signal for transmission to the far-end user via the communications channel. The adaptive echo canceller includes a first bank of analysis filters for filtering the near-end audio signal, a second bank of analysis filters for filtering the far-end audio signal, and a bank of synthesis filters for filtering sub-band echo-canceled signals generated within the adaptive echo canceller. The first and second filter banks have a frequency response optimized to reduce echo residual gain.

Description:
BACKGROUND 
     Acoustic Echo Cancellation (AEC) is a digital signal processing technology which is used to remove the acoustic echo from a speaker phone in two-way or multi-way communication systems, such as traditional telephone or modern internet audio conversation applications. 
       FIG. 1  illustrates an example of one end  105  of a typical two-way communication system, which includes a capture stream path and a render stream path for the audio data in the two directions. The other end is exactly the same. In the capture stream path in the figure, an analog to digital (A/D) converter  122  converts the analog sound captured by microphone  110  to digital audio samples continuously at a sampling rate (fs mic ). The digital audio samples are saved in capture buffer  130  sample by sample. The samples are retrieved from capture buffer in frame increments (herein denoted as “mic[n]”). Frame here means a number (n) of digital audio samples. Finally, samples in mic[n] are processed and sent to the other end. 
     In the render stream path, the system receives audio samples from the other end, and places them into a render buffer  140  in periodic frame increments (labeled “spk[n]” in the figure). Then the digital to analog (D/A) converter  150  reads audio samples from the render buffer sample by sample and converts them to analog signal continuously at a sampling rate, fs spk . Finally, the analog signal is played by speaker  160 . 
     In systems such as that depicted by  FIG. 1 , the near end user&#39;s voice is captured by the microphone  110  and sent to the other end. At the same time, the far end user&#39;s voice is transmitted through the network to the near end, and played through the speaker  160  or headphone. In this way, both users can hear each other and two-way communication is established. But, a problem occurs if a speaker is used instead of a headphone to play the other end&#39;s voice. For example, if the near end user uses a speaker as shown in  FIG. 1 , his microphone captures not only his voice but also an echo of the sound played from the speaker (labeled as “echo(t)”). In this case, the mic[n] signal that is sent to the far end user includes an echo of the far end user&#39;s voice. As the result, the far end user would hear a delayed echo of his or her voice, which is likely to cause annoyance and provide a poor user experience to that user. 
     Practically, the echo echo(t) can be represented by speaker signal spk(t) convolved by a linear response g(t) (assuming the room can be approximately modeled as a finite duration linear plant) as per the following equation:
 
echo( t )=spk( t )* g ( t )=∫ 0   T     e     g (τ)·spk( t −τ) dτ   (1)
 
where * means convolution, T e  is the echo length or filter length of the room response. The room response g(t) is often called the “echo path.”
 
     In order to remove the echo for the remote user, AEC  250  is added to the end  100  of the system shown in  FIG. 2 . When a frame of samples in the mic[n] signal is retrieved from the capture buffer  130 , they are sent to the AEC  250 . At the same time, when a frame of samples in the spk[n] signal is sent to the render buffer  140 , they are also sent to the AEC  250 . The AEC  250  uses the spk[n] signal from the far end to predict the echo in the captured mic[n] signal. Then, the AEC  250  subtracts the predicted echo from the mic[n] signal. This difference or residual is the clear voice signal (voice[n]), which is theoretically echo free and very close to near end user&#39;s voice (voice(t)). 
       FIG. 3  depicts an implementation of the AEC  250  based on an adaptive filter  310 . The AEC  250  takes two inputs, the microphone signal mic[n], which contains the echo and the near-end voice, and the spk[n] signal, which is received from the far end. The spk[n] signal is used to predict the echo signal. The prediction residual signal e[n] is used to adaptively update the cancellation filter h[n] when there is no near-end voice present. The prediction residual signal e[n] is also output by the adaptive filter. When a near-end voice is present, e[n] contains the echo-free, clear near-end voice, which is sent to the far end. Adaptive filter  310  is also referred to as adaptive echo canceller. 
     The actual room response (that is represented as g(t) in the above convolution equation) usually varies with time, such as due to change in position of the microphone  110  or speaker  160 , body movement of the near end user, and even room temperature. The room response therefore cannot be pre-determined, and must be calculated adaptively at running time. The AEC  250  commonly is based on adaptive filters such as Least Mean Square (LMS) adaptive filters  310 , which can adaptively model the varying room response. The LMS algorithm is a least square stochastic gradient step method which, as it is both efficient and robust, is often used in many real-time applications. The LMS algorithm and its well known variations (e.g., the Normalized LMS, or NLMS algorithm) do have certain drawbacks, however. For example, the LMS and other known algorithms can sometimes be slow to converge (i.e., approach the target filtering characteristic, such as the acoustic echo path in a hands-free telephony application), particularly when the algorithm is adapted, or trained, based on a non-white, or colored, input signal such as a human speech signal. Moreover, the order of the adaptive filter (i.e., the number of filter taps) can be quite high in the context of acoustic echo cancellation, and implementation of the adaptive filtering algorithm can therefore be computationally complex. 
     Consequently, recent work has focused on performing the adaptive filtering in sub-bands. In other words, filter banks are used to divide both the microphone signal and the loudspeaker signal into a number of frequency sub-bands. Each sub-band signal is then decimated, or down-sampled, and adaptive filtering is performed in each sub-band to provide a number of echo-canceled sub-band output signals. The resulting sub-band output signals are then interpolated, or up-sampled, and combined to reconstruct the overall echo-canceled microphone signal for transmission to the far-end user. Advantageously, the sub-sampling results in greater computational efficiency as compared to the full-band processing approach and, since variations in the spectral content of the input signals are less severe within each sub-band, overall convergence speed is also improved. 
     However, known sub-band adaptive filtering systems suffer from certain disadvantages as well. For example, signal aliasing between sub-bands can result in slow overall convergence and/or errors in the reconstructed microphone signal. In addition, non-causal coefficient effects arising from the sub-band filters&#39; impulse response can reduce the quality of the cancellation process in the individual sub-bands. Consequently, there is a need for improved methods and apparatus for performing sub-band adaptive filtering in echo suppression systems. 
     SUMMARY 
     The following Detailed Description presents various ways to enhance AEC quality and robustness in two-way communication systems. 
     This Summary is provided to introduce a selection of concepts in a simplified form that is further described below in the Detailed Description. This summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter. Additional features and advantages of the invention will be made apparent from the following detailed description of embodiments that proceeds with reference to the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram illustrating one end of a typical two-way communication system. 
         FIG. 2  is a block diagram of the two-way communication system of  FIG. 1  with audio echo cancellation. 
         FIG. 3  is a block diagram of an implementation of audio echo cancellation based on an adaptive filter. 
         FIG. 4  depicts one example of a sub-band adaptive filtering arrangement. 
         FIG. 5  depicts the relationship among various system delays that may be used to model the non-causal filter coefficients. 
         FIG. 6  is a block diagram of a suitable computing environment for implementing a two-way communication system utilizing the AEC implementation having improved robustness and quality. 
     
    
    
     DETAILED DESCRIPTION 
     The following description relates to implementations of audio echo cancellation having improved robustness and quality, and their application in two-way audio/voice communication systems (e.g., traditional or internet-based telephony, voice chat, and other two-way audio/voice communications). Although the following description illustrates the inventive audio echo cancellation in the context of an internet-based voice telephony, it should be understood that this approach also can be applied to other two-way audio communication systems and like applications. 
     Sub-Band Adaptive Filtering 
       FIG. 4  depicts one example of a sub-band adaptive filtering arrangement  200 . The arrangement  200  can, for example, be used to provide the functionality of the AEC  250  of  FIG. 2 . As shown, the sub-band arrangement  200  includes a first bank of analysis filters  210   0 - 210   K−1 , a first bank of decimators  215   0 - 215   K−1 , a bank of sub-band adaptive echo canceller  120   0 - 120   K−1 , each of which same as the adaptive filter  310  shown in  FIG. 3 , a second bank of analysis filters  220   0 - 220   K−1 , a second bank of decimators  225   0 - 225   K−1 , a bank of interpolators  230   0 - 230   K−1 , a bank of synthesis filters  235   0 - 235   K−1 , and a reconstruction summing device  240 . Those of ordinary skill in the art will appreciate that the components of  FIG. 4  can be implemented using a variety of known hardware configurations, including a general purpose digital computer, standard digital signal processing components, and one or more application integrated circuits. 
     In  FIG. 4 , a reference signal (e.g., the far-end speech signal of  FIG. 1 ) is input to each of the second bank of analysis filters  220   0 - 220   K−1 . The reference signal also passed through an echo path  205  (e.g., the near-end environment of  FIG. 1 ) and forms echoes. Additionally, echoes (output of the echo path  205 ) are input to each of the first bank of analysis filters  210   0 - 210   K−1 . An output of each of the first bank of analysis filters  210   0 - 210   K−1  and an output of each of the second bank of analysis filter  215   0 - 215   K−1  are coupled to sub-band echo cancellers  120   0 - 120   K−1 . An output of each one of the sub-band echo canceller  120   0 - 120   K−1  is coupled to an input of a respective one of the bank of interpolators  230   0 - 230   K−1 . 
     An output of each of the interpolators  230   0 - 230   K−1  is coupled to a respective one of the bank of synthesis filters  235   0 - 235   M−1 , and an output of each of the synthesis filters  235   0 - 235   K−1  is coupled to a respective input of the reconstruction summing device  240 . Output of the reconstruction summing device provides a reconstructed, full-band echo-canceled error signal. 
     In operation, the first bank of analysis filters  210   0 - 210   K−1  splits the echo-containing signal (e.g., the microphone signal) into K (an integer) adjacent frequency bands, and the second bank of analysis filters  220   0 - 220   K−1  splits the echo-causing or reference signal (e.g., the far-end speech signal) into the same K adjacent frequency bands. Since the spectral content of each sub-band signal is limited as compared to the full-band signal, each sub-band signal can be decimated, or down-sampled, by a factor M without loss of information. To reduce aliasing, M is usually chosen to be a fraction of K, typically half of K. Conventionally, the overall bandwidth of interest is divided into K equal sub-bands, each sub-band having a bandwidth of 1/M times the overall bandwidth. Accordingly, the first bank of decimators  215   0 - 215   K−1  down-sample the echo-containing sub-band signals by a factor M, and the second bank of decimators  225   0 - 225   K−1  down-sample the echo-causing sub-band signals by the same factor M in order to reduce computational complexity. 
     Thereafter, adaptive filter processing is carried out within each sub-band in a manner analogous to the above described full-band approach. Specifically, the sub-band echo cancellers  120   0 - 120   K−1  adaptively filter the sub-band echo-causing signals to provide K echo-canceled output signals. (e.g., using an LMS or NLMS algorithm as shown in  FIG. 3 ). 
     The interpolators  230   0 - 230   K−1  then interpolate, or up-sample, the sub-band echo-canceled signals by the factor M to return to the original sample rate, and the synthesis filters  235   0 - 235   K−1  K−1 filter the up-sampled, sub-band echo-canceled signals to cancel aliasing effects introduced by the down-sampling as is well known in the art. The bandwidths of the synthesis filters conventionally match those of the analysis filters (i.e., M equal bandwidth of 1/M times the overall bandwidth of interest). The resulting sub-band signals are then summed via the summing device  240  to produce, or reconstruct, the full-band echo-canceled signal (e.g., for transmission to the far-end user). 
     Those of skill in the art will appreciate that, although each filter block is shown operating in the time domain in  FIG. 4 , some or all of the filtering can be performed in the frequency domain as well (i.e., filtering by vector multiplication in the frequency domain is equivalent to filtering by sample-wise convolution in the time domain). Thus, the arrangement  200  of  FIG. 4  can also include appropriate conversion processors as well (e.g., Fast Fourier Transform, or FFT, processors and Inverse Fast Fourier Transform, or IFFT, processors). Selection between time-domain and frequency domain filtering is a matter of design choice 
     Modeling Non-causal Coefficients with Audio System Delays 
     Suppose a room response is represented by a pure delay system δ(n−d 0 ), i.e. the echo path (room response) g(n) is given by
 
 g ( n )=δ( n−d   0 ).  (2)
 
     Then the microphone signal y(n) can be written as speaker signal x(n) convolving with the room response
 
 y ( n )= x ( n )* g ( n )= x ( n−d   0 ).  (3)
 
     Suppose we have a uniform Discrete Fourier Transform (DFT) filter bank with a prototype analysis filter h(n). The sub-band speaker signal X k (m) is given as 
                         X   k     ⁡     (   m   )       =       ∑     n   =     -   ∞       ∞     ⁢       h   ⁡     (     mM   -   n     )       ⁢     x   ⁡     (   n   )       ⁢     W   K     -   kn             ,     
     ⁢     k   =   0     ,   1   ,   …   ⁢           ,     K   -   1             (   4   )               
where W K =e j(2π/K) , K is number of sub-bands, k is sub-band index; n is the original discrete time index; m is down-sampled time index, and M is down-sampling ratio. Thus the sub-band microphone signal Y k (m) can be written as
 
     
       
         
           
             
               
                 
                   
                     
                       Y 
                       k 
                     
                     ⁡ 
                     
                       ( 
                       m 
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         n 
                         = 
                         
                           - 
                           ∞ 
                         
                       
                       ∞ 
                     
                     ⁢ 
                     
                       
                         h 
                         ⁡ 
                         
                           ( 
                           
                             mM 
                             - 
                             n 
                           
                           ) 
                         
                       
                       ⁢ 
                       
                         x 
                         ⁡ 
                         
                           ( 
                           
                             n 
                             - 
                             
                               d 
                               0 
                             
                           
                           ) 
                         
                       
                       ⁢ 
                       
                         
                           W 
                           K 
                           
                             - 
                             kn 
                           
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
     Replacing the variable n′=n−d 0  yields 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             
                               Y 
                               k 
                             
                             ⁡ 
                             
                               ( 
                               m 
                               ) 
                             
                           
                           = 
                           
                             
                               W 
                               K 
                               
                                 - 
                                 
                                   kd 
                                   0 
                                 
                               
                             
                             ⁢ 
                             
                               
                                 ∑ 
                                 
                                   n 
                                   = 
                                   
                                     - 
                                     ∞ 
                                   
                                 
                                 ∞ 
                               
                               ⁢ 
                               
                                 
                                   h 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         
                                           ( 
                                           
                                             m 
                                             - 
                                             
                                               
                                                 d 
                                                 0 
                                               
                                               M 
                                             
                                           
                                           ) 
                                         
                                         ⁢ 
                                         M 
                                       
                                       - 
                                       
                                         n 
                                         ′ 
                                       
                                     
                                     ) 
                                   
                                 
                                 ⁢ 
                                 
                                   x 
                                   ⁡ 
                                   
                                     ( 
                                     n 
                                     ) 
                                   
                                 
                                 ⁢ 
                                 
                                   W 
                                   K 
                                   
                                     - 
                                     
                                       kn 
                                       ′ 
                                     
                                   
                                 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           = 
                           
                             
                               W 
                               K 
                               
                                 - 
                                 
                                   kd 
                                   0 
                                 
                               
                             
                             ⁢ 
                             
                               
                                 X 
                                 k 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   m 
                                   - 
                                   
                                     
                                       d 
                                       0 
                                     
                                     M 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                     
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     Therefore, when the sub-band approach is used, the sub-band room response of a pure delay system G k (m) can be written as 
     
       
         
           
             
               
                 
                   
                     
                       G 
                       k 
                     
                     ⁡ 
                     
                       ( 
                       m 
                       ) 
                     
                   
                   = 
                   
                     
                       W 
                       K 
                       
                         - 
                         
                           kd 
                           0 
                         
                       
                     
                     ⁢ 
                     
                       
                         δ 
                         ⁡ 
                         
                           ( 
                           
                             m 
                             - 
                             
                               
                                 d 
                                 0 
                               
                               M 
                             
                           
                           ) 
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
     In traditional digital signal processing theory, because X k (m) is a discrete signal and 
             (     m   -       d   0     M       )         
is in general not an integer,
 
                 X   k     ⁡     (     m   -       d   0     M       )       ⁢           ⁢   and   ⁢           ⁢     δ   ⁡     (     m   -       d   0     M       )             
do not exist. They are used here for simple expressions of fractional delay. According to sampling theory, a general expression of delay for any real number d can be written as a sinc function:
 
     
       
         
           
             
               
                 
                   
                     δ 
                     ⁡ 
                     
                       ( 
                       
                         n 
                         - 
                         d 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       sin 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         c 
                         ⁡ 
                         
                           ( 
                           
                             n 
                             - 
                             d 
                           
                           ) 
                         
                       
                     
                     = 
                     
                       
                         
                           sin 
                           ⁡ 
                           
                             [ 
                             
                               π 
                               ⁡ 
                               
                                 ( 
                                 
                                   n 
                                   - 
                                   d 
                                 
                                 ) 
                               
                             
                             ] 
                           
                         
                         
                           π 
                           ⁡ 
                           
                             ( 
                             
                               n 
                               - 
                               d 
                             
                             ) 
                           
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
     So the complete sub-band response is given by 
                         G   k     ⁡     (   m   )       =       W   K     -     kd   0         ⁢       sin   ⁡     (       π   ⁡     (     mM   -     d   0       )       /   M     )           π   ⁡     (     mM   -     d   0       )       /   M           ,     
     ⁢       -   ∞     &lt;   m   &lt;   ∞     ,           (   9   )               
and Y k (m) is the convolution of X k (m) and G k (m)
 
     
       
         
           
             
               
                 
                   
                     
                       Y 
                       k 
                     
                     ⁡ 
                     
                       ( 
                       m 
                       ) 
                     
                   
                   = 
                   
                     
                       W 
                       K 
                       
                         - 
                         
                           kd 
                           0 
                         
                       
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           l 
                           = 
                           
                             - 
                             ∞ 
                           
                         
                         ∞ 
                       
                       ⁢ 
                       
                         
                           
                             sin 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   π 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       mM 
                                       - 
                                       
                                         d 
                                         0 
                                       
                                       - 
                                       lM 
                                     
                                     ) 
                                   
                                 
                                 / 
                                 M 
                               
                               ) 
                             
                           
                           
                             
                               π 
                               ⁡ 
                               
                                 ( 
                                 
                                   mM 
                                   - 
                                   
                                     d 
                                     0 
                                   
                                   - 
                                   lM 
                                 
                                 ) 
                               
                             
                             / 
                             M 
                           
                         
                         ⁢ 
                         
                           
                             
                               X 
                               k 
                             
                             ⁡ 
                             
                               ( 
                               l 
                               ) 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     In (9), the first term W K   −kd     0    is a constant phase term; and the second term is a fractional delay arising from the echo path response impulse, which has an infinite response extending on both negative and positive times. The coefficients corresponding to (mM−d 0 )&lt;0 in (9) are non-causal as they are prior to the onset of the room response impulse. 
     Usually a sub-band echo cancellation system only models positive time coefficients (m&gt;0) in (9), i.e. uses past and current speaker signals to predict current microphone signal and update filter coefficients. Therefore, there are 
             ⌈       d   0     M     ⌉         
non-causal coefficients that can be modeled, where ┌ ┐ denotes the ceiling of a fractional number. Rest of non-causal coefficients is truncated. Because d 0  is a variable depending on near-end environment, in worst case d 0  can be very short so that there is only one non-causal coefficient, which may cause high prediction errors, and consequently result in poor cancellation quality. The error associated with the truncation of non-causal filter coefficients of the room response is referred to as the non-causality coefficient effect.
 
     An easy way to reduce the non-causality coefficient effect, is to deliberately add delay to the microphone signals so that more non-causal coefficients can be modeled in the adaptive filter method. Empirical tests have shown, for instance, that 10 non-causal filter coefficients is sufficient to reduce the non-causality effect well below the error caused by sub-band aliasing; and 5 non-causal coefficients are sufficient to reduce the non-causality effect largely. However, adding a delay to the microphone signal increases the delay of the whole communication system, thus in practice, it is rarely used. 
     The methods and systems described herein detect and utilize inherent audio system delays in two-way communication systems (e.g., computers, speaker telephones, two-way radio, game consoles, conferencing equipment) to model the non-causal filter coefficients. For instance, in modern computers, particular on personal computers, there are several structural layers in the audio system from the application to hardware (e.g., D/A and A/D converters). Every layer may have its own buffer and contributes certain delay. For example, in Windows XP, there is typically a minimum of a 20 to 30 millisecond delay on render side between the time when a sample is sent to the render buffer and when the sample is actually played through the speaker (at the D/A converter). If an application has a longer buffer, the delay will be longer. Similarly on the capture side, there is a delay between the time when a sample is captured by the microphone (at the A/D converter) and when it is seen by an application. Such delays are necessary to achieve glitch-free audio streams on multi-task operation systems. Accordingly, such delays are virtually always present. Therefore, the system delays can be used to model the non-causal filter coefficients.  FIG. 5  depicts the relationship among the various delays. 
     In  FIG. 5 , a frame of the audio signal is sent to the render buffer by an application at t 0 ; the signal is actually played through speaker at t 1 ; the signal is captured by the microphone at t 2 ; and the signal is acquired by the application at t 3 . (t 1 −t 0 ) is the render delay in the capture buffers  130  of  FIG. 1 ; (t 2 −t 1 ) is the echo delay; and (t 3 −t 2 ) is the capture delay in the render buffers  140  in  FIG. 2 . Thus, the render delay and the capture delay can be used to model the non-causal filter coefficients. In other words, the actual delay caused by the room response is (t 2 −t 1 ), but the total delay (t 3 −t 0 ) can be used to model the sub-band room response, of which (t 1 −t 0 )+(t 3 −t 2 ) is used for modeling the non-causal coefficients. The maximum number of allowed non-causal filter coefficients without inducing extra system delay is given by 
                     ⌊         (       t   3     -     t   2       )     +     (       t   1     -     t   0       )       FrameSize     ⌋     ,           (   11   )               
where └ ┘ denotes the floor of a fractional number, and “FrameSize” is the process frame size.
 
Optimizing the DFT Filter Bank by Minimizing Echo Residual Gain
 
     One problem with the filter bank approach to sub-band processing is that the transition between bands makes it impossible to perfectly isolate each band from each adjacent band without the use of “ideal” band pass filters (i.e., filters with infinitely sharp cutoffs). There is a known trade-off between the amount of echo cancellation possible, the filter roll-off, filter group delay distortion, and reconstructability of the sub-bands to regenerate the original input signal without distortion. However, the use of the band-pass filters for echo cancellation suffers from problems relating to distortion caused by aliasing during the down sampling process. This problem arises because the spectrum in the stop-band of filters in filter bank is reflected onto the pass-band and becomes aliases. Since aliasing is nonlinear it cannot be canceled by an adaptive filter, thus limiting the amount of overall allowable echo cancellation using a sub-band adaptive filtering technique. Accordingly, the quality of the sub-band filtering technique is mainly limited by the total aliasing energy. Therefore, the aliasing energy is often minimized when designing the analysis filter banks  210  and  220 . However, this only controls the sub-band cancellation quality. When the signal is reconstructed, the sub-band error signals are passed into the synthesis filters  235  and then interpolated to the original sampling rate. As a result the effects of all the filter banks and not just the analysis filters  210  and  220  should be taken into account. 
     Assume that in the filter banks  210  and  220 , the analysis filter is h k (n) with a frequency response H k (e jω ), and the synthesis filter in synthesis filters  230  is f k (n) with a frequency response F k (e jω ). If the sub-band signals are not modified (i.e., if there is no processing in the sub-band domain), the spectrum of the reconstructed signal {circumflex over (X)}(e jω ) (i.e., the spectrum provided at the output of the summing device  240  in  FIG. 4 ) can be written as 
     
       
         
           
             
               
                 
                   
                     
                       X 
                       ^ 
                     
                     ⁡ 
                     
                       ( 
                       
                         ⅇ 
                         
                           j 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           ω 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       M 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           0 
                         
                         
                           K 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         
                           
                             F 
                             k 
                           
                           ⁡ 
                           
                             ( 
                             
                               ⅇ 
                               jω 
                             
                             ) 
                           
                         
                         ⁢ 
                         
                           
                             ∑ 
                             
                               l 
                               = 
                               0 
                             
                             
                               M 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                             
                               
                                 H 
                                 k 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   ⅇ 
                                   
                                     j 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         ω 
                                         - 
                                         
                                           2 
                                           ⁢ 
                                           π 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           
                                             l 
                                             / 
                                             M 
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                             ⁢ 
                             
                               X 
                               ⁡ 
                               
                                 ( 
                                 
                                   ⅇ 
                                   
                                     j 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         ω 
                                         - 
                                         
                                           2 
                                           ⁢ 
                                           π 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           
                                             l 
                                             / 
                                             M 
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
     A further assumption is that echoes in the pass-band of the analysis filters can be completely cancelled by an adaptive filter. In other words, in the k-th sub-band, the signal in the frequency range of 
             [           2   ⁢   π   ⁢           ⁢   k     K     -     π   M       ,         2   ⁢   π   ⁢           ⁢   k     K     +     π   M         ]         
can be completely cancelled, because frequency components in this range remain linear after the decimation while components out of this range do not. This assumption is an ideal case. Due to limited filter length, this assumption cannot be realized in practice. However, it is approximately accurate up to the limitation of truncated filter length.
 
     For simplicity, an ideal echo cancellation system can be incorporated into the filter bank analysis filter by modifying the frequency response of the analysis filter H k (e jω ) to 
     
       
         
           
             
               
                 
                   
                     
                       H 
                       k 
                       ′ 
                     
                     ⁡ 
                     
                       ( 
                       
                         ⅇ 
                         
                           j 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           ω 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             0 
                             , 
                           
                         
                         
                           
                             ω 
                             ∈ 
                             
                               [ 
                               
                                 
                                   
                                     
                                       2 
                                       ⁢ 
                                       π 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       k 
                                     
                                     K 
                                   
                                   - 
                                   
                                     π 
                                     M 
                                   
                                 
                                 , 
                                 
                                   
                                     
                                       2 
                                       ⁢ 
                                       π 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       k 
                                     
                                     K 
                                   
                                   + 
                                   
                                     π 
                                     M 
                                   
                                 
                               
                               ] 
                             
                           
                         
                       
                       
                         
                           
                             
                               
                                 H 
                                 k 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   ⅇ 
                                   jω 
                                 
                                 ) 
                               
                             
                             , 
                           
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
     Replacing H k (e jω ) with H k ′(e jω ) in (12) yields total echo residual of a sub-band echo cancellation system ( FIG. 4 ). 
     
       
         
           
             
               
                 
                   
                     
                       
                         X 
                         ^ 
                       
                       ′ 
                     
                     ⁡ 
                     
                       ( 
                       
                         ⅇ 
                         jω 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       M 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           0 
                         
                         
                           K 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         
                           
                             F 
                             k 
                           
                           ⁡ 
                           
                             ( 
                             
                               ⅇ 
                               jω 
                             
                             ) 
                           
                         
                         ⁢ 
                         
                           
                             ∑ 
                             
                               l 
                               = 
                               0 
                             
                             
                               M 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                             
                               
                                 H 
                                 k 
                                 ′ 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   ⅇ 
                                   
                                     j 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         ω 
                                         - 
                                         
                                           2 
                                           ⁢ 
                                           π 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           
                                             l 
                                             / 
                                             M 
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                             ⁢ 
                             
                               X 
                               ⁡ 
                               
                                 ( 
                                 
                                   ⅇ 
                                   
                                     j 
                                     ⁡ 
                                     
                                       ( 
                                       
                                         ω 
                                         - 
                                         
                                           2 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           π 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           
                                             l 
                                             / 
                                             M 
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
     An “echo residual gain” can thus be defined as 
     
       
         
           
             
               
                 
                   
                     
                       G 
                       e 
                     
                     ⁡ 
                     
                       ( 
                       
                         ⅇ 
                         jω 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       M 
                     
                     ⁢ 
                     
                       
                         ( 
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               0 
                             
                             
                               K 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                             
                               
                                  
                                 
                                   
                                     F 
                                     k 
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       ⅇ 
                                       jω 
                                     
                                     ) 
                                   
                                 
                                  
                               
                               2 
                             
                             ⁢ 
                             
                               
                                 ∑ 
                                 
                                   l 
                                   = 
                                   0 
                                 
                                 
                                   M 
                                   - 
                                   1 
                                 
                               
                               ⁢ 
                               
                                 
                                    
                                   
                                     
                                       H 
                                       k 
                                       ′ 
                                     
                                     ⁡ 
                                     
                                       ( 
                                       
                                         ⅇ 
                                         
                                           j 
                                           ⁡ 
                                           
                                             ( 
                                             
                                               ω 
                                               - 
                                               
                                                 2 
                                                 ⁢ 
                                                 
                                                     
                                                 
                                                 ⁢ 
                                                 π 
                                                 ⁢ 
                                                 
                                                     
                                                 
                                                 ⁢ 
                                                 
                                                   l 
                                                   / 
                                                   M 
                                                 
                                               
                                             
                                             ) 
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                    
                                 
                                 2 
                               
                             
                           
                         
                         ) 
                       
                       
                         1 
                         / 
                         2 
                       
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
     Accordingly, when designing the DFT filter banks for a sub-band echo cancellation system, i.e. finding a set of optimal analysis and synthesis filters to achieve best echo cancellation quality, besides the well known criterion of minimizing sub-band aliasing, the echo residual gain in (15) should also be minimized. 
     Computing Environment 
     The above-described AEC digital signal processing techniques can be realized on any of a variety of two-way communication systems, including among other examples, computers; speaker telephones; two-way radio; game consoles; conferencing equipment; and etc. The AEC digital signal processing techniques can be implemented in hardware circuitry, in firmware controlling audio digital signal processing hardware, as well as in communication software executing within a computer or other computing environment, such as shown in  FIG. 6 . 
       FIG. 6  illustrates a generalized example of a suitable computing environment ( 800 ) in which described embodiments may be implemented. The computing environment ( 800 ) is not intended to suggest any limitation as to scope of use or functionality of the invention, as the present invention may be implemented in diverse general-purpose or special-purpose computing environments. 
     With reference to  FIG. 6  the computing environment ( 800 ) includes at least one processing unit ( 810 ) and memory ( 820 ). In  FIG. 6 , this most basic configuration ( 830 ) is included within a dashed line. The processing unit ( 810 ) executes computer-executable instructions and may be a real or a virtual processor. In a multi-processing system, multiple processing units execute computer-executable instructions to increase processing power. The memory ( 820 ) may be volatile memory (e.g., registers, cache, RAM), non-volatile memory (e.g., ROM, EEPROM, flash memory, etc.), or some combination of the two. The memory ( 820 ) stores software ( 880 ) implementing the described audio digital signal processing for robust and high quality AEC. 
     A computing environment may have additional features. For example, the computing environment ( 800 ) includes storage ( 840 ), one or more input devices ( 850 ), one or more output devices ( 860 ), and one or more communication connections ( 870 ). An interconnection mechanism (not shown) such as a bus, controller, or network interconnects the components of the computing environment ( 800 ). Typically, operating system software (not shown) provides an operating environment for other software executing in the computing environment ( 800 ), and coordinates activities of the components of the computing environment ( 800 ). 
     The storage ( 840 ) may be removable or non-removable, and includes magnetic disks, magnetic tapes or cassettes, CD-ROMs, CD-RWs, DVDs, or any other medium which can be used to store information and which can be accessed within the computing environment ( 800 ). The storage ( 840 ) stores instructions for the software ( 880 ) implementing the described audio digital signal processing for robust and high quality AEC. 
     The input device(s) ( 850 ) may be a touch input device such as a keyboard, mouse, pen, or trackball, a voice input device, a scanning device, or another device that provides input to the computing environment ( 800 ). For audio, the input device(s) ( 850 ) may be a sound card or similar device that accepts audio input in analog or digital form, or a CD-ROM reader that provides audio samples to the computing environment. The output device(s) ( 860 ) may be a display, printer, speaker, CD-writer, or another device that provides output from the computing environment ( 800 ). 
     The communication connection(s) ( 870 ) enable communication over a communication medium to another computing entity. The communication medium conveys information such as computer-executable instructions, compressed audio or video information, or other data in a modulated data signal. A modulated data signal is a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media include wired or wireless techniques implemented with an electrical, optical, RF, infrared, acoustic, or other carrier. 
     The described audio digital signal processing for AEC techniques herein can be described in the general context of computer-readable media. Computer-readable media are any available media that can be accessed within a computing environment. By way of example, and not limitation, with the computing environment ( 800 ), computer-readable media include memory ( 820 ), storage ( 840 ), communication media, and combinations of any of the above. 
     The described audio digital signal processing for robust and high quality AEC techniques herein can be described in the general context of computer-executable instructions, such as those included in program modules, being executed in a computing environment on a target real or virtual processor. Generally, program modules include routines, programs, libraries, objects, classes, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The functionality of the program modules may be combined or split between program modules as desired in various embodiments. Computer-executable instructions for program modules may be executed within a local or distributed computing environment. 
     For the sake of presentation, the detailed description uses terms like “determine,” “generate,” “adjust,” and “apply” to describe computer operations in a computing environment. These terms are high-level abstractions for operations performed by a computer, and should not be confused with acts performed by a human being. The actual computer operations corresponding to these terms vary depending on implementation.