Note: Descriptions are shown in the official language in which they were submitted.
CA 02410749 2002-11-O1
Convergence Improvement for Oversampled Subband Adaptive Filters
Field of the Invention:
The present invention relates to adaptive filter, more specifically to a
system and method for improving convergence in subband adaptive filers.
Backaround of the Invention:
It is well known that a noise cancellation system can be implemented with
a fullband adaptive filter working on the entire frequency band of interest
[4]. The
Least Mean-Square (LMS) algorithm and its variants are often used to adapt the
fullband filter with relatively low computation complexity and good
performance.
However, the fullband LMS solution suffers from significantly degraded
performance with colored interfering signals due to large eigenvalue spread
and
slow convergence [4,5,6]. Moreover, as the length of the LMS filter is
increased,
the convergence rate of the LMS algorithm decreases and computational
requirements increase. This can be a problem in applications, such as acoustic
echo cancellation, that demand long adaptive filters to model the return path
response and delay. These issues are especially important in portable
applications, where processing power must be conserved.
As a result, subband adaptive filters (SAF) become a viable option for
many adaptive systems. The SAF approach uses a filterbank to split the
fullband
signal input into a number of frequency bands, each serving as input to an
adaptive filter. The subband decomposition greatly reduces the update rate and
the length of the adaptive filters resulting in a much lower computational
complexity. Further, subband signals are often decimated in SAF systems. This
leads to a whitening of the input signals and an improved convergence behavior
[7). If critical sampling is employed, the presence of aliasing distortions
requires
the use of adaptive cross-filters between adjacent subbands or gap filterbanks
[7,8]. However, systems with cross-filters generally converge slower and have
higher computational cost, while gap filterbanks produce significant signal
distortion.
CA 02410749 2002-11-O1
2
It is desirable to provide a subband adaptive filter system which can meet
a high speed processing, low power consumption and high quality and is
applicable to a noise (echo) cancellation.
Summary of the Invention:
It is an object of the present invention to provide a system and method to
overcome one or more of the problems cited above.
It is an object of the present invention to provide a system and method for
improving convergence of a subband adaptive filter.
The inventors have investigated the convergence properties of an SAF
system based on generalized DFT (GDFT) filterbanks. The filterbank is a highly
oversampled one (oversampling by a factor of 2 or 4 or more). Due to the ease
of implementation, low-group delay and other application constraints a higher
oversampling ratio than those typically proposed in the literature may be
used.
The oversampled input signals received by the subband processing
blocks are no longer white in spectrum. In fact, for oversampling factors of 2
and
4, their bandwidth will be limited to pl2 and p/4 respectively. As a result,
one
would expect a slow convergence rate due to eigenvalue spread problem [4,5,6].
On the other hand, while the oversampled subband signals are not white, their
spectra are colored in a predicable way and can therefore be modified by
further
processing to whiten them in order to increase the convergence rate. Thus, the
inherent benefit of decreased spectral dynamics resulting from subband
decomposition is not lost due to oversampling. Various spectral whitening
techniques will be described hereafter. Another method of improving the
convergence rate is to employ adaptation strategies that are less sensitive to
eigenvalue spread problem. One of these strategies is the Affine Projection
(AP)
algorithm. Exact and approximate versions of the AP algorithm are proposed to
speed up the convergence rate of the SAF system on an oversampled filterbank.
Oversampled SAF systems offer a simplified structure that without
employing cross-filters or gap filterbanks, reduce the alias level in
subbands. To
reduce the computation cost, often a close to one non-integer decimation ratio
is
used [9].
CA 02410749 2002-11-O1
In accordance with a further aspect of the present invention, there is
provided an echo cancellation system which includes a SAF system having
functionality of convergence improvement, such as whitening by spectral
emphasis, whitening by adding noise, whitening by decimation, Affine
projection
algorithm. The system may include Double-Talk Detector to control the
adaptation process. The system may have functionality of adaptation step size
control.
In accordance with a further aspect of the present invention, there is
provided an echo cancellation system which includes an adaptive processing
and non-adaptive processing.
In accordance with a further aspect of the present invention, there is
provided a cross-talk resistant subband adaptive filter.
A further understanding of other features, aspects and advantages of the
present invention will be realized by reference to the following description,
appended claims, and accompanying drawings,
Brief Description of the Drawings:
The invention will be further understood from the foNowing description with
reference to the drawings in which:
Figure 1 is a block diagram showing a subband adaptive filters (SAF)
system for whitening by spectral emphasis method in accordance with a first
embodiment of the invention;
Figure 2 is a block diagram showing a SAF system for whitening by
additive noise method in accordance with a secod embodiment of the invention;
Figure 3 is a block diagram showing a SAF system for whitening by
decimation method in accordance with a third embodiment of the invention;
Figure 4 is a graph showing signal spectra at various points of Figure 3;
Figure 5 is a graph showing Average Normalized Filter MSE for speech in
0 dB SNR White noise, (a) without whitening, (b) whitening by spectral
emphasis, (c) whitening by decimation;
CA 02410749 2002-11-O1
4
Figure 6 is a graph showing eigenvalues of the autocorrelation matrix of
the reference signal for: No whitening, Whitening by spectral emphasis,
whitening by decimation, and whitening by decimation and spectral emphasis;
Figure 7 is a graph showing measured mean-squared error for: No
whitening, whitening by spectral emphasis, whitening by decimation, and
whitening by decimation and spectral emphasis;
Figure 8 is a graph showing measured mean-squared error for Affine
Projection Algorithm (APA) with different orders;
Figure 9 is a block diagram showing an adaptive echo cancellation
system in accordance with an embodiment of the invention;
Figure 10 is a block diagram showing a task of echo cancellation of Figure
9;
Figure 11 is a block diagram showing a first embodiment of an adaptive
processing block (APB) of Figure 10;
Figure 12 is a block diagram showing a second embodiment of an APB of
Figure 10;
Figure 13 is a block diagram showing a third embodiment of an APB of
Figure 10;
Figure 14 is a block diagram showing a fourth embodiment of an APB of
Figure 10;
Figure 15 is a graph showing a coherence function of a diffuse noise;
Figure 16 is a block diagram showing an oversampled SAF system for
noise reduction in accordance with a forth embodiment of the invention;
Figure 17 is a block diagram showing one embodiment of an adaptive
processing block (APB) and a non-adaptive processing block (NAPB) of Figure
16;
Figure 18 is a block diagram showing a cross-talk resistant APB of Figure
10 and Figure 16.
CA 02410749 2002-11-O1
Detailed Description of the Preferred Embodiment(s):
Whitening by spectral emphasis
Figure 1 shows a block diagram of an SAF system that includes the
5 proposed whitening by spectral emphasis method. As shown an unknown plant
P(z) is modeled by the adaptive filter, W(z). After WOLA analysis, subband
signals are decimated by a factor of M/OS, where M is the number of filters,
and
OS is the oversampling factor. At this stage, the subband signals are no
longer
full-band. Rather, as shown in Figure 1 (points 1 and 2), their bandwidth is
now
p/OS. The emphasis filter (gP~e(z)) then amplifies the high frequency contents
of
signals at points 1 and 2 to obtain almost white spectra. The filter gain (G)
is a
design parameter that depends on the analysis filter shape.
Whitening by additive noise
Alternatively, high-pass noise can be added to bandpass signals to make
them whiter in spectrum. As shown in Figure 2, first the average power (G) of
the
signal at point 1 is estimated and used to modulate a high-pass noise a(n).
The
input to adaptive filter (point 3) is then whitened by adding G.a(n) to the
signal at
point 1.
Whitening by decimation
Figure 3 shows a block diagram of the SAF system with a proposed
whitening by decimation method. As shown, the subband signals (for both the
reference input x(n) and the primary input d(n)) are further decimated by a
factor
of DEC<OS. Assume, without loss of generality, that DEC is at its maximum,
DEC= OS-1. As demonstrated in Figure 4 (point 3), this increases the bandwidth
to p (OS-1)/OS (3p/4 for OS=4) without generating in-band aliasing. Due to the
increased bandwidth, the LMS algorithm now converges much faster. To be able
to use the adaptive filter (Vlld(z)), it is expanded by OS-1. This may create
in-
band images (point 4 in Figure 4). However, since the signal at point 1 does
not
contain considerable energy for w> p/OS, the spectral images will not
contribute
to any errors.
CA 02410749 2002-11-O1
6
Affine Projection
In order to further increase the convergence rate, a class of adaptive
algorithms called Affine Projection have been proposed [12]. Affine Projection
Algorithm (APA) forms a link between Normalized LMS (NLMS) and Recursive
Least Square (RLS) adaptation algorithms: faster convergence of RLS and low
computational requirements of NLMS are compromised in APA.
In NLMS, the new adaptive filter weights have to best fit the last input
vector to the corresponding desired signal. In APA, this fitting expands to
the P-1
past input vectors (P being the APA order). Adaptation algorithm for the Pt"
order
APA can be summarized as follows:
1) update X~ and do
2) en =d~ _ X~W
3) Wn+, = W~ + mX" (X~ X" + a I)-' en
where:
X~: an L' P matrix containing P past input vectors _
d~ : a vector of the past P past desired signal samples
W~ : adaptive filter weights vector at time n
a : regularization factor
The convergence of APA is surveyed in [12, 13]. It is shown that as
projection order P increases, the convergence rate becomes less dependant on
the eigenvalue spread. Increasing the APA order results in faster convergence
at
the cost of more computational complexity of the adaptation algorithm.
We propose the use of the APA for a SAF system implemented on a
highly oversampled WOLA filterbank [1,2,3]. An APA order of P = 2 can be a
CA 02410749 2002-11-O1
good choice, compromising fast convergence and low complexity. In this case,
the matrixXn X~ can be approximated by R (autocorrelation matrix of the
reference signal) [14]. So, for P = 2, it is sufficient to estimate the first
two
autocorrelation coefficients (r(0) and r(1 )) and then inverse the matrix R ,
analytically. A first order recursive smoothing filter can be used to estimate
r(0)
and r(1 ).
Combination of the above techniques
It is possible to combine any two or more of the described techniques to
achieve a higher performance. For example, whitening by decimation improves
the convergence rate by increasing the effective bandwidth of the reference
signal. However, it cannot deal with the smallest eigenvalues that are
associated with the stop band region of the analysis filter. On the other
hand,
whitening by spectral emphasis improves the convergence by limiting the stop
band loss thereby increasing the smallest eigenvalues. A combination of the
two
techniques will enable us to take advantage of the merits of both systems.
Performance evaluation
Preliminary assessments show that the performance of the whitening by
additive noise is very similar to whitening by spectral emphasis. However, the
computation cost of whitening by additive noise is less since it does not need
emphasis filters. Instead, it needs a very simple filter (per subband) to
estimate
the signal power.
Figure 5 shows typical convergence behavior of the proposed whitening
by decimation compared to no whitening and whitening by emphasis. The
application of the SAF system has been 2-microphone adaptive noise
cancellation. As shown, whitening by decimation converges mush faster than the
other two methods.
Whitening by decimation greatly improves the convergence properties of
the SAF system. At the same time, since the adaptive filter operates at a low
frequency, the method offers less computation than whitening by emphasis or by
adding noise. However, the proposed whitening by decimation is applicable only
CA 02410749 2002-11-O1
g
to oversampling factors (OS) of more than 2. For detailed mathematical models
of SAF systems see [9,15].
Figure 6 shows the theoretical Eigenvalues of the autocorrelation matrix
of the reference signal for: No whitening, Whitening by spectral emphasis,
Whitening by decimation, and Whitening by decimation and spectral emphasis.
The method employed is described in [6]. As shown, while whitening by spectral
emphasis and by decimation both offer improvements (demonstrated by a rise in
the eigenvalues), a combination of both method is more promising. This
conclusion is confirmed by the mean-squared error (MSE) results shown in
Figure 7. Finally, Figure 8 shows the MSE results APA orders of P = 1, 2, 4
and
5 (The APA for P = 1 yields an NLMS system). As shown, increasing the AP
order, improves both the convergence rate and the MSE.
The present invention will be further understood by the additional
description A, B and C attached hereto.
IS
Alternate embodiment
Echo Cancellation by SAFs using Improved Convergence Techniques
As mentioned above, in echo cancellation long filter lengths may be used
due to long duration of echo path. As a result, fast adaptation techniques for
echo cancellation are now described in detail. Figure 9 shows an application
of
adaptive systems for echo cancellation. As shown, the Far-End (FE) acoustic
input signal is converted to an electric signal x(t) that is sent to the Near-
End
(NE) speaker. The NE microphone then receives an acoustic echo signal (called
FE echo) from the NE speaker. The NE microphone also receives NE input
(speech and noise) signal, and converts the total signal (FE echo + NE input)
to
an electric signal d(t). An adaptive filer minimizes the error signal e(t) to
eliminate
FE echo. Once converged, the adaptive filter essentially models the transfer
functions of the NE speaker and NE microphone, as well as the acoustic
transfer
function between the NE speaker and the microphone. Echo can also be
generated by electrical signals leaking back to the FE side through various
(undesired) electrical paths between the FE and the NE sides. The proposed
techniques cover both acoustical and electrical echoes, however, in the
discussions only acoustical echo is discussed.
CA 02410749 2002-11-O1
9
Figure 10 demonstrates the task of echo cancellation (Figure 9)
implemented in a subband domain. As shown signals x(t) and d(t) are first
sampled and then analyzed by two analysis filterbanks to obtain complex
frequency-domain subband signals x;(n) and d;(n), i=0,1, ,K-1, K being the
number of subbands. Pairs of [x;(n) ,d;(n)] are next used as inputs to
Adaptive
Processing Blocks (APB in Fig. 10). The outputs of APBs (complex subband
signals e;(n)) are then combined in the synthesis filterbank to obtain the
time-
domain echo-cancelled signal e(n). We now describe a few possible APBs that
could efficiently cancel echo. The APB blocks in Figure 10 and its possible
examples (described in Figures 11, 12, 13, 14, 16, 17, and 18) can employ any
of the convergence improvement techniques introduced above (whitening by
spectral emphasis, whitening by adding noise, whitening by decimation, Affine
projection algorithm, and a combination of two or more of those techniques) to
achieve fast convergence.
Figure 11 shows a possible APB to be employed in Figure 10. As shown a
Double-Talk Detector (DTD) is employed to control the adaptation process. The
DTD includes two voice-activity detectors (VADs), one (FE VAD) operating on
the FE signal and another one (NE VAD) employing the signal d;(n). It also
contains a logic that based on the two VAD decisions, specifies when double-
talk
(both NE and FE sides talking), single-talk (only one of the FE or NE sides
talking) or common-pause (none of the two sides talking) situations occur. The
DTD allows quick adaptation of the adaptive filter only during FE signal-talk.
In
other situations, it stops or slows down the adaptation.
Demonstrated in Figure 12 is another possible APB for Figure 10. As
shown, the NE VAD now uses the error signal e;(n). The rational behind using
the error signal is as follows. At the start of the adaptation process, the
error
signal is almost the same as d;(n) since the adaptive filter is identically
zeros. As
the DTD allows the adaptive filter to adapt, more and more of the echo is
cancelled from d;(n). As a result, the DTD detects more instances of FE single-
talk and the filter gets more chance to further adapt. This in turn will
cancel echo
more efficiently. This looping improves the performance of the DTD and as a
result the echo cancellation system. This strategy is particularly helpful
when
there are high levels of echo.
CA 02410749 2002-11-O1
Adaptation Step-size control
The NE signal might contain both speech and noise. As a result, the NE
noise might be present even when the DTD detects a FE single-talk situation.
5 This would create problems for the adaptive processor if a large adaptation
step-
size (rr) were chosen. One solution to this problem is to condition the
adaptation
step-size on the level of the FE echo (FEE) signal relative to the level of
the NE
noise (NEN) signal, i.e. on the ratio of ~FEE~2! ~NEN~2. An estimate of the
NEN
energy can be obtained by measuring the energy of d;(n) in common-pause. To
10 estimate energy of the FEE, one can subtract the NEN energy estimate from
energy of d;(n) during FE single-talk, i.e.:
~d;(n)~2 in common-pause ~NEN~2 estimate
~d;(n)~2 in FE single talk ~NEN~2 estimate ~FEE~2 estimate
Figure 13 shows an APB (to be used in Figure 10) that contains a rr~
Adaptation block. Based on the DTD result and the estimate of ~FEE~21 ~NEN~2 ,
the block varies the value of the step-size. Various strategies are possible
to
adapt the step-size. Generally as the ratio of ~FEE~21 ~NEN~2 increases,
larger
step-sizes are employed.
Alternative method of DTD
The adaptive filters employed for echo cancellation might have high filter
orders due to long echo paths. As a result, the adaptive filter may converge
slowly. Since the DTD of Figure 12 is relying on the adaptive filter
performance,
this slow convergence might create a problem for the whole system. Here a
possible solution is proposed. Figure 14 shows an APB (to be used in Figure
10)
that employs two adaptive filters. Adaptive filter 2 contains is a low-order
filter
that is basically used for DTD. Adaptive filter 1 works with the rr+Adaptation
block
and performs similar to the system in Figure 13. The low-order adaptive filter
2
can adapt faster than the adaptive filter 1. Most of the echo would be
eliminated
quickly at its output (f;(n)), and the NE VAD in the DTD would perform well
even
before full convergence of the adaptive filter 1.
CA 02410749 2002-11-O1
ll
Atte~nate embodiment
Combination of adaptive and non-adaptive processing for noise and
echo cancellation
The general SAF system of Figure 10 performs well for noise cancellation
as long as the noises in the two inputs x(n) and d(n) are correlated. It is
well-
known that the (optimum) adaptive filter is estimated as [5]:
u'~(f) =px~r(f)
P~(f)
where
pxa(f)=a, ra(k)e-~~a'
k
and rx~(k) is the cross-correlation of input signals x(n) and d(n) at delay k.
So,
the cross correlation plays a major role in estimating the transfer function
between two inputs. In the case of weak correlation, adaptive filter only
removes
the correlated portion of the noise and leaves the uncorrelated part intact.
The most valid feature to characterize the correlation of two noise signals
x(n) and d(n) (here it assumed that the input signal d(n) contains only noise
and
there is no speech signal present), is the coherence function[18]:
Gx~ (f) = I P~ U) I2
P~U)~'a~(f)
In each frequency f, equation (1 ) characterizes the correlation of two input
signals by a value between 0 and 1 and consequently, determines the amount of
noise that can be cancelled in that frequency through adaptive filtering. More
precisely, the noise reduction factor of adaptive filtering is equal to [18]:
NR( f ) = Input noise power at frequency f __ 1
output noise power at frequency f 1- Gx~ ( f )
CA 02410749 2002-11-O1
12
Diffuse Noise Field
In a diffuse noise field, two microphones receive noise signals from all
directions
equal in amplitude and random in phase. This results in a squared Sinc
(magnitude squared) coherence function for diffuse noise field [19]:
Gxd(l)=sin2(2pldlc)=Sinc2(2~d)
(2pfd I c)2 c
where d is the microphone spacing and c is the sound velocity (c = 340 m/s).
Figure 15 shows the coherence function of a diffuse noise for d=38 mm.
According to this coherence function, increasing microphone spacing d, will
decrease the noise reduction capability of adaptive filter in more subbands.
Although a decrease in distance of two microphones can be proposed as a
remedy, but clearly this intensifies the cross-talk problem (described in next
Section) and thus, is not an acceptable solution.
Many practical noise fields are diffuse (16,17]. As a result, the noises
recorded by the two microphones are only coherent at low frequencies. This
implies that the SAF system can partially remove the noise from d(n). There
are
some other possible scenarios where the two noises present at the two
microphones do not have a flat coherence function (of value 1 ) across various
frequencies. In such cases, the SAF system can only partially enhance the
signal.
The system in Figure 16 can cope with these situations. The system in
Figure 16 includes an extra (compared to Figure 10) non-adaptive processing
block (NAPB) in each subband. The NAPB can pertorm single-mic or two-mic
non-adaptive noise reduction. For example, as shown in Figure 17, the NAPB
can be a single-mic Wiener filter to eliminate the residual uncorrelated noise
at
the output of the subband adaptive filter. Other single-mic or two-mic noise
reduction strategies are also possible. Since the correlated noise is already
eliminated by the APB stage, the artifacts and distortions due to the NAPE
would
have less degrading effects at the output. For diffuse noises, the important
low-
frequency region of speech signal will not be distorted since the low-
frequency
noises at the two mics are correlated and will be eliminated mostly by the APB
without generating artifacts.
CA 02410749 2002-11-O1
13
Alternate embodiment
Cross-Talk Resistant subband adaptive filters for noise cancellation
The performance of adaptive noise cancellation systems can be severely limited
in cross-talk, i.e. when the speech (or desired) signal leaks into the
reference
(noise) microphone. To remedy this problem, cross-talk resistant adaptive
noise
canceller (CTRANC) has been proposed in the literature [20]. However, the
proposed systems are implemented in time-domain and not in subband domain.
The use of CTRANC techniques for SAF systems implemented on oversampled
filterbanks is now described. Figure 18 shows the block diagram of a cross-
talk
resistant APB, to be used in systems of Figure 10 or Figure 16. As shown,
there
are two adaptive filters V;(z) and W;(z) in each subband. After convergence,
the
signal e;(n) provides the enhanced (subband) speech signal while the signal
f;(n)
provides the noise signal without speech interference.
The SAF system and the noise cancellation system of the present
I S invention may be implemented by any hardware, software or a combination of
hardware and software having above described functions.
While particular embodiments of the present invention have been shown
and described, changes and modifications may be made to such embodiments
without departing from the true scope of the invention.
References
(1] R. Br~ennan and T. Schneider, Filterbank Structure and Method for
Filtering and Separating an Information Signal into Different Bands,
Particularly
for Audio Signal in Hearing Aids . United States Patent 6, 236, 731. lN0
98/47313. April 16, 1997.
[2] R. Brennan and T. Schneider, A Flexible Filterbank Structure for
Extensive Signal Manipulations in Digital Hearing Aids , Proc. IEEE Inf. Symp.
Circuits and Systems, pp.569-572, 1998.
[3] R. Brennan and T. Schneider, Apparatus for and method of filtering in
an digital hearing aid, including an application specific integrated circuit
and a
programmable digital signal processor , United States Patent 6,240, 992, May
200 9.
CA 02410749 2002-11-O1
14
[4] B. Widrow et al., Adaptive noise cancellation: Principles and
applications . Proc. IEEE, vol. 63, no. 12, Dec. 1975.
[5] Haykin, S., Adaptive Filter Theory. Prentice Hall, Upper Saddle River,
3'd Edition, 1996.
[6] Dennis R. Morgan, Slow Asymptotic Convergence of LMS Acoustic
Echo Cancelers , IEEE Trans. Speech and Audio Proc., Vol. 3, No. 2, pp. 126-
136, March 1995.
[7] A. Gilloire and M. Vetterli, Adaptive Filtering in Subbands with Critical
Sampling: Analysis, Experiments and Applications to Acoustic Echo
Cancellation . IEEE Trans. Signal Processing, vol. SP-40, no. 8, pp. 1862-
1875,
Aug. 1992.
[8] J. J. Shynk, Frequency-Domain and Multirate Adaptive Filtering .
IEEE Signal Professing Magazine, pp. 14-37, Jan. 1992.
[9] S. Weiss, On Adaptive Filtering in Oversampled Sub-bands , PhD.
Thesis, Signal Processing Division, University of Strathclyde, Glasgow, May
1998.
(10] King Tam et. al., Sub-band Adaptive Signal Processing in an
Oversampled Filterbank , IDF filed on August 7, 2002, Application No.
2,354,808.
[11] King Tam, Hamid Sheikhzadeh, and Todd Schneider, highly
oversampled subband adaptive filters for noise cancellation on a low-resource
dsp system , Proc. Of ICSLP 2002.
[12] K. Ozeki and T. Umeda, An adaptive algorithm filtering using an
orthogonal projection to the affine subspace and its properties, Electronics
and
Communications in Japan, vol. 67-A, no. 5, pp.19-27, Feb. 1984.
[13] M. Montazeri and P. Duhamel, A set ofalgorithms linking NLMS and
block RLS algorithms IEEE Tran. on Signal Processing, vol. 43, no. 2, pp. 444-
453, Feb. 1995.
[14] V. Myllyla, Robust fast affine projection algorithm for acoustic echo
cancellation, in proc. of infer. Workshop on Acoustic Echo and Norse Control,
Sep. 2001.
[15] S. Weiss et al., Polyphase Analysis of Subband Adaptive Filters ,
33'd Asilomar Conference on Signals, Systems, and Computers, Monterey, CA,
1999.
CA 02410749 2002-11-O1
[16] Ann Spriet, Marc Moonen, and Jan Wouters, Robustness analysis of
GSVD based optimal filtering and generalized sidelobe canceller for hearing
aid
applications , IEEE workshop on Applications of Signal Processing to Audio and
Acoustics, Oct. 2001, New York.
5 [17] lain A. McCowan and Herve Bourlard, Microphone array post-filter
for diffuse noise field , ICASSP 2002.
[18] M. M. Goulding, Speech enhancement for mobile telephony, IEEE
Trans. Vehicular Tech., vol. 39, no. 4, pp. 316-326, Nov.1990.
[19] A. G. Piersol, Use of coherence and phase data between two
10 receivers in evaluation of noise environments, Journal of Sound and
Vibration,
vol. 56, no. 2, pp. 215-228, 1978.
[20] G. Mirchandani et. al., A new adaptive noise cancellation scheme in
the presence of crosstalk , IEEE traps. On Circuits and Systems, Il: Analog
and
digital signal processing, Vol. 39, No. 10, Oct. 1992, pp. 681-694.
CA 02410749 2002-11-O1
16
Additional Description A
Technical Report
Polyphase Analysis of Subband Adaptive Filters
CA 02410749 2002-11-O1
Polyphase Analysis of Subband Adaptive Filters
Stephan Weissl, Robert W. Stewart2, Moritz Harteneck3, and Alexander Stenger4
1 Dept. Electronics & Computer Science, University of Southampton, UK
2 Dept. Electronic & Electrical Eng., University of Strathclyde, Glasgow, UK
3 Infineon Technologies AG, Munich, Germany
4Telecommunications Institute I, University of Erlangen, Germany
s.xeiss~ecs.soton.ac.uk, r.stexart~eee.strath.ac.uk
Abstract jest to a number of limitations, which have been inves-
tigated, for example, with respect to the required filter
Based on a polyphase analysis of a subband adaptive length (3, 14] or to lower
bounds for the MMSE and
alter (SAF) system, it is possible to calculate the opti- the modelling
accuracy (12]. These analyses have been
mum aubband impulse responses to which the SAF sys- performed using modulation
description (3, ?], time do-
tem will converge. In this paper, we gave some insight main (14), or frequency
domain approaches (5, 12J.
into how these optimum impulse responses are calcu- Here, we discuss the 5AF
in Fig. l using a polyphase
lated, and discuss two applications of our technique. description of the
signals and filters therein (2J. This
Firstly, the performance limitations of an SAF sys- will provide some new and
alternative insight into the
tem can be explored with respect to the minimum mean optimality of SAFs. Sec.
2 analyses the subband er-
square error performance. Secondly, fullband impulse rora, which leads to the
derivation and discussion of an
responses can be correctly projected into the subband optimal subband filter
structure in Sec. 3. Application
domain, which is required for example for translating examples for the
proposed techniques are underlined
constraints for subband adaptive 6eamforming. Exam- by simulations in Sec. 4.
pies for both applications are presented.
2. Polyphase Analysis of Subband Errors
1. Introduction
The aim of this section is to express the subband er-
Adaptive filtering in aubbanda is a popular ap- ror signals, Ek{x) ~-o ek(x),
in terms of the polyphase
proach to a number of problems, where high compu- components of all involved
signals and systems. Im-
tational cost and slow convergence due to long filters plicitly, this means
that we are trying to find a lin-
permits the direct implementation of a fullband algo- ear, time-invariant
{LTI) description of the error sig-
rithm. These problems include acoustic echo cancella- nil. To achieve this
task, we first require suitable rep-
tion (5, 3), identification of room acoustics (8), equal- resentations for the
decimated desired signal in the kth
ization of acoustics (10], or beamforming (6, 11]. In subband, Dk (z) ~-o dk
(nJ, and for the decimated in-
Fig. 1, a subband adaptive filter (SAF) is shown in a put signal in the kth
subband, Xk(x) ~--o xk(n], as
system identification setup of an unknown system s(n), labelled in Fig. 1. In
our notation, superscript {~}d for
whereby the input x(n) and the desired signal d(nJ are z-transforms of signals
refers to decimated quantities,
split into K frequency bands by analysis filter banks while normal variables
such as Xk(x) indicate undeci-
built of bandpass filters h~(n). Assuming a cross-band mated signals, i.e. in
this case the input signal in the
free SAF design (3], an adaptive filter wk(nJ is applied kth subband before
going into the decimator as shown
to each subband decimated by N <_ K. Finally, the in Fig. 1.
fullband error signal e(n] can be reconstructed via a The formulation of the
kth decimated desired sig
synthesis bank. nil Dk(z) ~--o dk(n] will be the first aim. We define
However, subband adaptive filters (SAF) are sub- the expansion of the desired
signal D(x) ~-o d(n] into
CA 02410749 2002-11-O1
-
analysis
unknown f lter bank
system ; ~]ds[n]
~= dfn]' 'L~,~N, dUn]
s.
N ~ ~dKtLn]
'~~___:~ ' j _ ~ _ _______
(n] of ] e~[n]
;,rv : . ,~~ _O---~-~N--
;xx~Ln] extLn]'
analysis adaptive synthesis
filter bank . filters filter bank
Fig. 1. Subband adaptive filter (SAF) in a system identification setup.
type-2-polyphase components (9J Dn(x), X(z) is defined similarly to (3) based
on the
type-2-polyphase components of the input signal
w-i X (z) ~-o x(n~. The matrix An(z) in (6) is a delay
D(x) _ ~ x-N+n+1 , Dn{zrr) , (1) matrix defined as
n=0
_ 0 IN_"
and a type-1-polyphase expansion (9J of the analysis An{x) - [ x-lIn 0 ] ' (7)
filters H~(x),
With (5) and {6), the decimated kth desired subband
N-1 signal Dk{z)
Hk{z) _ ~ x n-Hk,n{zN) . {2) r~T(z)Ao(z)
n=0
TzAlx
Similarly, for all following polyphase expansions, it Dk(z) = H~(z) ~ ( ) ( )
X(z) = H~(x)S(z)X(x)
is assumed for compatibility that systems are rep-
resented by a type-1-polyphase expansion, and sig- ST(z)Aw-i{x)
nals by type-2-polyphase expansions. Bringing these (8)
polyphase components of (1) and (2) into vector form, can be assembled. For
brevity, the substituted matrix
D(x) - (Da(x) Dl (z) . . . DN i(z)]T (3) S(x) holds differently delayed
polyphase components of
the unknown system.
Hk(x) - (H,~~o(z) Hk~l . . . Hk~N 1 {x)~ {4) With the type-2-polyphase
components of X (x) arid
the polyphase representation of the analysis filter bank
Dk(x) can now be expressed as in (2) it is comparably simple to derive the kth
deci
d s mated input signal Xk (x) as
Dk(z) _ ~ (x) ' D(x) - (5)
Xk (x) - Hk (x) . X (x) . (9)
To trace the desired signal back to the input signal -
X (x) ~-o x(n~, the expression D(x) = S(z) . X (x) can Finally, with (8), (9),
and the transfer function
be appropriately expanded such that the nth polyphase of the kth adaptive
filter W~ (x) ~-o wk (n) it is pos
component in (3) may be written as sible to formulate the kth subband error
signal,
Dn(z) _ ~T(z) . An(x) . X{z) . (6) Ek{z) ~-o ex(n):
Ek {x) = D~(z) - Wk (z) . X~ (x) {10)
The vector S(x) contains the type-1-polyphase com- ( l
ponents of the unknown system S(z) - -~-o s(n), while - S Hk (z)~S(x) - H~
(x).Wk(x) 5X(z)(11)
CA 02410749 2002-11-O1
Fig. 3. SAF standard solution in the kth subband.
Flg. 2. SAF optimal polyphase solutions in the
kth subband.
3.2. Interpretation
Note, that for the description of E~ (z), the time-
varying decimators have been swapped with all system Alternatively, the nth
optimum solution can be writ-
elements in the SAF structure of Fig. 1, and (11) only ten as
contains LTI terms.
N-1
Wk Pt (x) _ ~ A~~n(z) ' ,S"(z) . (14)
3. Subband Error Minimization "-o
and interpreted as a superposition of polyphase com
This section discusses the optimum subband filters ponents S"(x) of the
unknown system S(z), "weighted"
to solve the identification problem outlined in Sec. 1, by transfer functions
based on the polyphase analysis of the subba,nd errors
in the previous Sec. 2. " H z
A~I~(,z) = z-~(n+v)/1Vl . k~~n+v) modm( ) ' (15)
Hk~n(x)
3.1. Optimum Subband Filters
From this, we can observe, that the length of the opti
As no external disturbance of the SAF system in mum subband responses is
obviously given by 1/N of
Fig. 1 by observation noise is present, ideally the at- the order of S(z), but
extended by the transfer func
tainable minimum mean square error (MMSE) should dons (15). These extending
transients are causal for
be zero. This is identical to setting Ek(x) in (11) equal poles of Ak~n(z)
within the unit circle, and aca,usal for
to zero. As independence of the optimum solution from stabilized poles outside
the unit-circle (13], motivating
the input signal's polyphase components in X (x) is de- a non-causal optimum
response.
sirable, the requirement for optimality (in every sense) Further, for an
ideal, alias-free filter bank, the
is given by polyphase components Hyn(z) in (15) should not differ
in magnitude but only in phase, which is compensated
Hk (x) ~ S(x) ' XT ~ Wk,opt (z) . (12) for by the delay element in (15). Hence
all N solutions
become identical, an the N optimum polyphase filters
Hence, we obtain N)cancellation conditions indicated can be replaced by a
single filter Wk,opt(z) as shown
by superscripts { } , which have to be fulfilled: in Fig. 3, which is
equivalent to the original standard
(n) Hk (x) ~ AT (x) ~ S_(z) setup in Fig. 1. In general, and particularly if
a,liasing
Wit,oPt(x) = H~~"(x) do E {0;N-1} . is present, the optimum polyphase
solutions Wk opt(z)
(13) wdl differ. In this case the optimum standard SAr' so
lution according to Fig. 3 gives the closest l2 match to
Therefore, ideally W,t(x) in (11) and (12) should be ~1 N polyphase solutions:
replaced by an N x N diagonal matrix with entries N_1
Wk")(z), n = 0(1)N-1. For the kth subband, this Wk,oPt(x) = N ~ Wk pt (x) .
(lfi)
solution with N polyphase filters is depicted in Fig. 2. "=o
CA 02410749 2002-11-O1
._
the structure of the standard SAF system in Fig. 3, the
desired signal PSD analytlCal solution (16) calculated from (18) is given by
. ,,r'" _ ',,
,, - - - simulated the mean of the two optimum polyphase solutions,
enalylical prod.
s .~,.". ,
Wo,opt (x) = 1.5 + 0.5x-1
error signal PSD: ~ , , n "~' ,
This result obviously very closely agrees with the sim-
s
anaycal prea~,;on ulation result in {17).
Based on the above analytical solutions, it is now
' possible to predict the subband error signal as due to
°o o., o.Z o.3 0., o.s o.8 o.~ o.0 °.9 , the mismatch of {18)
and (4.1). The PSD of the 0th
adapted subband error signal, Seo(e~n), can be anal
Flg. 4. Comparison between simulated and ana- lytically predicted by inserting
the optimum standard
lytically predicted PSDs in the 0th subband. solution {16) into (11),
seo(e~~) = I~%'b(e~o)Ia = 1- cosSt , (19)
The error made in this approximation explains error which can be used to
determine the minimum mean
and modelling limitations of the SAF approach and squared error of the SAF
system alternative to spec-
represents an alternative coefficient / time-domain de- tral methods (12J.
Fig. 4 demonstrates the excellent fit
scription as opposed to spectrally motivated SAF error between the
analytically calculated PSD in (19), and
explanations in the literature (3, 12J. Interestingly, in the measured results
from the RLS simulation. Also
(7J the same polyphase structure as in Fig. 2 is obtained shown is the
analytically predicted and measured PSD
using modulation description (2J 5 , although only for of the 0th desired
subband signal Sdo (esn ) = 6+2 cos St
the critically sampled case. (hence the uncancelled error signal) calculated
via (5).
4. Applications and Simulations 4.2. Subband Projection
We now want to explore two applications for the
polyphase analysis presented in Secs. 2 and 3. A second application example is
concerned with sub
stituting subband adaptive system identification with
4.1. Error Limits the proposed analysis. If a digital impulse response
is given in the fullband, but should be projected into
A very basic example given in the following will the subband domain, an SAF
identification is mostly
demonstrate the ability of the proposed analysis to pre- required. This could
be to produce computationally ef
dict optimal subband responses and error terms in the fi~ent sound processing
from a given (fullband) room
context of SAF systems. For this example, a 2-channel transfer function (8J,
or the projection of constraints
critically decimated standard SAF system as in Fig. 1 into the subband domain
when performing subband
based on a Haar filter bank (2J should adaptive iden- captive beamforming
(11J.
tify an unknown system S(x) = 1 + z1, using unit vari- We assume an SAF system
with K = 8 channels
ance Gaussian white noise excitation. Looking at the decimated by N = 6, and
wide analysis filters to im-
channel k = 0 produced by the Haar lowpass filter prove spectral whitening in
the subbands (11. Analysis
Ho(x) = 1 + x-1, an RLS adaptive algorithm (4J con- and synthesis banks are
derived from the two different
verges to the solution prototype filters shown in Fig. 5. With a lowpass full-
band response s(nJ given, an RLS adaptive identifica
WO,adapt {x) = 1.4873 + 0.5067x-1 . (17) tion yields in the subband k = 0 the
coefficients shown
Analytical evaluation via (14) and (15) yields the m Fig. 6, along with the
analytic solution according to
N = 2 optimum polyphase solutions for the band k = 0 (14) and (16). For the
analytic solution, the roots of
the denominator polynomial in (15) have been substi
Wo o~pt(z~ = 2 , Wolopt(x) = 1 + z-1 , (18) tuted by appropriate causal and a
causal FIR filters.
Obviously, the match between adaptive and analyti-
which refers to the optimal subband adaptive filter cal solution is very
close; and themore direct analytical
structure shown in Fig. 2. If this setup is simplified to approach can replace
an adaptive projection.
CA 02410749 2002-11-O1
.,
°s 6. Acknowledgements
o.,s _ _ a°e~~ w°,°,rae
$yre is o,o,o,ype
;c °' The authors gratefully acknowledge Dr. Ian
r °°~ ' K. Proudler, of DERA, Malvern, UK, who partially
o ~~ _ supported this work. S. Weiss would like to thank the
' ' Royal Academy of Engineering for providing a travel
o ,o zo °o ,o s° so ~o e° eo
grant.
,
° ! ~ . - _ ~n~ss ~ N~ References
--ZO , .
-'° ~ r~ ; (1) P.L. de LeGn II and D.M. Etter. "Experimental
-oo -~ ~j!I ' ~, "y''Y r ~7 ,11I I~~~Ip ~" ~ , ,.. ........ Results with
Increased Bandwidth Analysis Filters
' ~y Srs ~I~r4suar4,'y"n;i,,u~,4~i'.,y~ ~ r,
' , Wr s: ! a y y ' 4 , f ,~ .~ ,~ "'~, in Oversampled Subband Acoustic Echo
Cancelers .
0 0., o.x o.a o.~ o.s o.s o.~ o.e o.o , IEEE Stg Proc Letters,
Vol.2(No.l):pp.l-3, Jan. 1995.
~~~~~~~~~~'~ (2J N.J. Fliege. Multirute Digital Signal Processing: Mul
Flg. 5. Prototype filters. tirate Systems, Falter Banks, Waveleta. Wiley,
1994.
[3J A. Gilloire and M. Vetterli. "Adaptive Filtering
z5 ~ ~a~~~ in Subbands with Critical Sampling: Analysis, Ex-
periments and Applications to Acoustic Echo Can-
celation". IEEE ?fans Signal Processing, Vo1.40
(No.B):pp.1862-1875, Aug. 1992.
o.s (4J S. Haykin. Adaptive Filter Theory. Prentice Hall, 2nd
0
-o.so ,o zo ao ~o so ao ~o eo 00 ,oo ed> 1991.
[5j W. Kellermann. "Analysis and Design of Multirate
Systems for Cancellation of Acoustical Echoes" . In
aae n8 Proc. ICASSP, vol 5, pp.2570-2573, New York, 1988.
--~-- ena~ytic [6] W. Kellermann. "Strategies for Combining Acoustic
' Echo Cancellation and Adaptive Beamforming Micro-
° phone Arrays" . In Proc. IEEE ICASSP, vol I, pp.219-
-' 222, Munich, April 1997.
-2 [7j S. S. Pradhan and V. U. Reddy. "A New Approach
-'o ,o ~o ~o b so so ~o ~0 00 ,oo to Subband Adaptive Filtering" . IEEE bane
Signal
""'°"" Processing, Vo1.47(No.3):pp.655-664, March 1999.
Fig. 6. Adaptive and analytic subband response [8] M. Schonle, N.J. Fliege,
and U. Zolzer. "Parametric
for k = 0. Approximation of Room Impulse Responses by Multi
rate Systems". In Proc. IEEE ICASSP, vol I, pp.153
5. ~iOriClilSiOriS 156, Minneapolis, May 1993.
(9] P.P. Vaidyanathan. Multirnte Systems and Filter
Banks. Prentice Hall, 1993.
We have introduced an analysis of an SAF system, [10] S. WeiB, S.R. Dooley,
R.W. Stewart, and A.K. Nandi.
which formulates the subba,nd errors in dependency "Adaptive Equalization in
Oversampled Subbands".
of LTI polyphase components only. The main result IEE Elec. Let.,
Vo1.34(No.lS):pp.1452-1453, Jvly
was a structural difference between what the optimum 1998'
[11J S. Weiss, R.W. Stewart, M. Schabert, LK. Proudler,
SAF requires and what the standard SAF structure and M.W. Hoffman. "An
Efficient Scheme for Broad-
provides. As a qualitative measure, this difference in band Adaptive
Beamforming". In Aeilomnr Conf
structure gives alternative insight into the inaccuracies Sig. Sys. Comp.,
Monterey, CA, Nov. 1999.
and limitations of the standard SAF approach. But [12j S. WeiB, R.W. Stewart,
A. Stenger, and R. Raben-
as demonstrated, the approach can also be utilized stein. "Performance
Limitations of Subband Adaptive
to quantify errors. Different from alias measurement Filters". In Proc.
EUSIPCO, vol. III, pp. 1245-1248,
methods for error prediction ~12), the analysis also of Rodos, Sept. 1998.
fers access to the coefficient domain and thus allows us (13) B. Widrow and E.
Walach. Adaptive Inverse Control.
to state optimum SAF subband responses. As an appli- Prentice Hall, 1995.
(14) R.J. Wilson, P.A. Naylor, and D. Brookes. "Perfor-
cation for the latter, an example was given that allows mice Limitations of
Subband Acoustic Echo Con-
us to substitute the subband projection by SAF system trollers". In Proc.
IWAENC, pp.176-179, London,
identification with the proposed analytical polyphase Sept. 1997.
approach.
CA 02410749 2002-11-O1
17
Additional Description B
Technical Report
Highly Oversampled Subband Adaptive Filters for Noise
Cancellation on a Low-Resource DSP System
