Call Today 716.688.4675

Critically Sampled Uniform Sub-Band Echo Cancellation using LMS-type Algorithms

When the sub-band structure was first introduced, it was assumed that sub-band distribution should be uniform. However as the method was employed, it was found that despite its obvious computational advantage over full-band methods, the standard least-mean-squares algorithms sometimes had trouble converging and echos sometimes propagated through the systems largely unattenuated. With critical sampling, the reason for both of these errors is illustrated in Figure 1.

Figure 1: Magnitude Responses of Adjacent Uniform Filterbanks With Critical Sampling [1]

As the figure shows, because we cannot realize a filter with perfect stop-band attentuation, critical sampling will inevitably lead to overlap between adjacent filterbanks. In contrast to the noise reduction scenario, this may cause problems due to the adaptive nature of acoustic echo cancellers AEC).

Wiener Solution and Convergence

For simplicity in illustrating how this structure may become problematic, we will use the Wiener solution, as the least-mean-squares algorithms attempt to approximate its optimal solution in an adaptive scheme. Recall the Wiener solution as shown in (1):

Where wio is the optimal weight vector for the ith  subband, and Ruiui is the auto-correlation matrix for the ith subband frame. Considering  and denoting   as the map associated with the auto-correlation matrix, we restrict our attention to F|UA where UA is the space containing only the overlapping region.

As Figure 1 shows, the imperfect gain window produces a downward sloping envelope that causes magnitude attenuation in the overlapping regions, leading to an entropy increase in F|UA. This information loss will cause this map to be ill-conditioned [2]. In terms of its associated matrix, this presents us with small eigenvalues. This presents a problem for three reasons. First, the ill-condition of the map will produce large deviations in the sub-band weights in response to relatively small changes in the speech signals. Secondly, small eigenvalues lead to large misadjustments. Third, the downsampling procedure causes frequency domain alaising that spreads the information entropy across adjacent bands resulting in the already ill-conditioned matrix to become even more sensitive.

In the cases when most of the sub-band energy is distributed in these overlapped regions, this may lead to virtually no convergence. In other cases, this will cause LMS type algorithms to have trouble converging. The problem is illustrated in Figure 2 below.

Figure 2: The Ill-Conditioned Convergence Problem

To solve this problem, one needs to simply add energy to these regions thereby decreasing their information entropy. One way to do this is to create both far-end and near-end analysis banks of different widths. A second method is to analyze your microphone output in parallel using wideband filters in one path, while using narrowband filters in the other. At the end, either choose which method is working best or aggregate the best aspects of both outputs with a linear combination. Using non-uniform sub-bands in a serial structure may work too, as long as your algorithm can accurately identify the problem narrow-band regions of the filter, either by a-priori assumptions or by using adaptive sub-band bandwidth selection. Another method is to ensure proper processing of these overlapping regions by starting with a model of an arbitrary FIR structure as in [3]. In implementing all of these methods, you are assured that through at least one path, the information in the echo signals in those overlapping regions will be captured.

In quite a different vein, you can attempt to avoid this problem all together. Considering this problem as systemic, one way to do this is to use cross-adaptive filters to introduce terms that will cancel the interband aliasing as in [4]. Alternatively, you might use the methods of [1] to subtract these overlap regions all together. Of course, it will be your systems design goals that will dictate the methods you employ. In general, each method will present with problems, as reduced computational complexity often comes with increased misalignment and convergence time.


[1] S. Kim et al, “Alias-Free Subband Adaptive Filtering With Critical Sampling,” IEEE Transactions of Signal Processing, vol. 56, no. 5, May 2008, pp. 1894-1904
[2] H. Allison, “Inverse unstable problems and some of their applications,” Math Scientist, vol. 4, pp. 9-30
[3] M. R. Petraglia et al, New structures for adaptive ltering in subbands with critical sampling, IEEE Trans. Signal Process., vol. 48, no. 12, December 2000, pp. 33163327
[4] A. Gilloire and M. Vetterli, “Adaptive Filtering in subbands,” Proc.IEEE Int. Conf. Acoust., Speech, Signal Process., April 1988, pp.15721575.

More Information

VOCAL Technologies, Ltd.
520 Lee Entrance, Suite 202
Amherst New York 14228
Phone: +1-716-688-4675
Fax: +1-716-639-0713