Dynamically-reduced complexity implementation of echo cancelers

In some adaptive filter applications, particularly echo cancellation, most of the tap coefficients in the convolution sum are essentially zero. We introduce and examine some No-Overkill Schemes (NOS) that eliminate the multiplications required for these zero coefficients by estimating which coefficients are nearly zero and setting them to exactly zero. In addition to reducing computation, this approach has the advantage of reducing the excess mean-square error, since the taps set to zero have no asymptotic fluctuation, Specifically, the NOS schemes work by dynamically partitioning the filter taps into active-taps and zero-taps. We estimate the time to convergence and the reduction in the excess mean-square-error due to the statistical fluctuation of the falter coefficients. Our results indicate that these No-Overkill Schemes significantly reduce the computational requirements with little or no increase in the time to convergence. Robustness of these schemes to a time varying channel is also considered. The NOS schemes increase the control overhead in the implementation of the adaptive filter, so additional examination of implementation tradeoffs for minimum cost is required.