Proc. 1999 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, New Paltz, New York, Oct. 17~20, 1999
`
`ON THE OPTIMALITY OF SUBBAND ADAPTIVE FILTERS
`
`Stephan Weiss and Robert W. Stewart
`
`Department of Electronic and Electrical Engineering
`University of Strathclyde, Glasgow G 1 lXW, Scotland, UK
`{weiss,bob}®spd.eee.strath.ac.uk
`
`ABSTRACT
`In this paper, we derive a polyphase analysis to determine the op~
`timum filters in a subband adaptive filter (SAF) system. The struc~
`ture of this optimum solution deviates from the standard SAF ap~
`proach and presents its best possible solution only as an approxi(cid:173)
`mation. Besides this new insight into SAF error sources, the dis~
`cussed analysis allows to calculate the optimum subband responses
`and the standard SAF approximation. Examples demonstrating the
`validity of our analysis and its use for determining SAF errors are
`presented.
`
`1. INTRODUCTION
`
`Adaptive filtering in subbands is a useful approach loa number of
`problems such as acoustic echo cancellation [1, 2]. identification of
`room acoustics [3], equalization of acoustics [4], or beamforming
`[5], where high computational cost can be reduced by processing
`in decimated subband signals. In Fig. 1, a subband adaptive fil(cid:173)
`ter (SAF) is shown in a system identification setup of an unknown
`system s[n], whereby the input x[n] and the desired signal d[n]
`are split into K frequency bands by analysis filter banks built of
`bandpass filters hk[n]. Assuming a cross-band free SAF design
`
`x[n]
`
`Figure 1: Subband adaptive filter (SAF) in system identification
`setup.
`
`[2], an adaptive filter wk(n] is applied to each subband decimated
`by N S I<. Finally, the fullband error signal e[n] can be re(cid:173)
`constructed via a synthesis bank. The structures of both analysis
`and synthesis is shown in Fig. 2. Ideally, the overall system con(cid:173)
`sisting of analysis and synthesis should only implement a delay,
`i.e. x[n] = x[n-t.].
`However, subband adaptive filters (SAP) are subject to anum~
`ber of limitations, which have been investigated, for example, with
`
`59
`
`analysis tllter bank
`
`synthesis filter bank
`
`Figure 2: Analysis and synthesis filter bank performing a signal
`decomposition into K frequency bands decimated by N ::; K.
`
`respect to the required filter length (2, 61 or to lower bounds for the
`MMSE and the modelling accuracy [8]. These analyses have been
`performed using modulation description (2], time domain [6J, or
`frequency domain approaches [1, 7, 8].
`Here, we discuss an SAF system as shown in Fig. I using a
`polyphase description [9] of its signals and filters. Sec. 2 reviews
`the idea of the polyphase expansion and presents the analysis of ail
`involved signals. In Sec. 3, we introduce the formulation for the
`optimum subband adaptive filters, which wilt require a modifica(cid:173)
`tion to the structure given in Fig. 1. We discuss in detail, how this
`optimum solution relates to the level of optimality, that is achiev(cid:173)
`able with the standard adaptive structure in Fig. 1, which will al(cid:173)
`low an assessment of the errors occurring in such standard SAF
`systems, Sec. 4 will discuss an example to highlight the use and
`insight reached by the analysis presented here.
`
`2, POLYPHASE ANALYSIS
`
`First, we derive expressions for the z-transforms for the decimated
`desired signal in the kth subband, rtfo(z) e-o d,[n], and for the
`decimated input signal in the kth subband, A1(z) e-o xk[n], as
`labelled in Fig. 1. This will allow us to assemble the z~transform
`of the kth decimated subband error signal, Ef(z) e-o e,(z). In
`our notation, superscript { · }d for z-transforms of signals refers to
`decimated quantities, while normal variables such as Xk(z) indi(cid:173)
`cate undecimated signals, i.e. in this case the input signal in the
`kth subband before going into the decimator as shown in Fig. 2.
`
`2.1. Polyphase Expansion
`
`The decimator and upsamplers in Fig. 2 are linear periodically
`time-varying (LPTV) operations, which makes it difficult to ap(cid:173)
`ply standard analysis tools for linear time-invariant (LTI) systems.
`However, polyphase analysis [10, 9] allows to express LPTV sys(cid:173)
`tems mostly as multiple-input multiple-output (MIMO) LTI sys-
`
`Petitioner Apple Inc.
`Ex. 1018, p. 59
`
`

`

`Proc. 1999/EEE Workshop on Applications of Signal Processing to Audio and Acoustics, New Paltz, New York, Oct. 17-20, 1999
`
`2.2. Description of Subband Desired Signal
`
`Further to the analysis in Sec. 2.1, we want to trace the decimated
`desired subband signal IYf ( z) back lo the input signal, X (z) e--o
`x[n]. Through the unknown system in Fig. 1, the relation between
`input and desired signal is given by D(z) = S(z) · X(z), where
`S(z) e---o s[n] is the z-transform of the unknown system. With
`some effort, this expression for the desired signal can he appro(cid:173)
`priately expanded such that the nth polyphase component in (3) is
`given by
`
`D,.(z) = ~T(z) · A,.(z) · X(z)
`
`.
`
`(6)
`
`The polyphase vectors~(z) andX{z) refer to the unknown sys(cid:173)
`tem S(z) and the input signal X(z) in analogy to the definitions
`(3) and (2). The matrix A,.(z) is a delay matrix defined as
`
`Thus, the overall description for the decimated kth desired sub(cid:173)
`band signal yields
`
`(7)
`
`(8)
`
`where the symmetric matrix S(z) = sT(z) has been substituted
`for brevity. Now the unknown system has been swapped with the
`multiplexing operation in Fig. 3(c).
`
`2.3. Description of Subband Input and Error Signals
`
`Similarly to the previous analysis, the kth decimated input signal
`can be derived as
`
`Xf(z) = H'[(z) · X(z)
`
`.
`
`(9)
`
`Finally, we use (8) and (9) to formulate the kth subband error
`signal, Et(z) .__, ek[n], including the kth adaptive filter with z(cid:173)
`transform Wk(z) o---o w,[n]:
`
`Et(z) = D~(z)- Wk(z) · Xt(z)
`= { lik'(z) · S(z) -lli(z) · Wk(z) }x(z). (II)
`
`(10)
`
`Hence, polyphase. descriptions for all involved decimated sub(cid:173)
`band signals have been derived. In particular. note that the desired
`suhhand signal now is entirely expressed in terms of the polyphase
`components of both the analysis filters, the unknown system, and
`the input signaL
`
`(c)
`
`Figure 3: Analysis and synthesis filler bank performing a signal
`decomposition into K frequency hands decimated by N :$_ K.
`
`terns, with decimators and upsamplers being described by multi(cid:173)
`plexing and demultiplexing operations.
`Considering the z-transform of the kth analysis filter, Hk (z ),
`Hk (z) e--o hk[n], it can be written in expansion form
`
`N-1
`
`Hk(z) = L z-" · Hk,n(zN)
`
`n=O
`
`(I)
`
`where Hk,n(z), n = O(l)N -1, are theN polyphase components
`of Hk(z). Fig. 3 shows the effect of this expansion as applied
`in the desired path of the SAF structure (compare to Figs. 1 and
`2). While Fig. 3(a) contains the kth branch of the analysis oper(cid:173)
`ation applied to the desired signal, Fig. 3(b) represents the flow
`graph using the expansion (1). It is now possible to exploit the
`first Nobel identity [11] to swap the decimators with the polyphase
`fillers Hk,n(zN) in Fig. 3(b), resulting in the structure shown in
`Fig. 3(c). Effectively, filtering now is performed at the lowest pos(cid:173)
`sible rate.
`The multiplexed signals fed into the polyphase filters H,,n(z)
`arc obtained by an analogous polyphase expansion of the desired
`signal D(z),
`
`N-1
`
`D(z) = L z-" · D,.(zN).
`
`n=O
`
`(2)
`
`Defining vector notation for the pol yphasc components of Hk ( z)
`and D(z),
`
`Q(z)
`H,(z) =
`
`[Do(z) D1(z)
`
`[Hkto(z) Hkl1
`
`DN-1(z)f
`
`,.
`HkiN-1(z)]
`
`(3)
`
`(4)
`
`it is possible to express the kth desired signal decimated by a factor
`Nas
`
`Note, that the mathematical expression (5) directly refers to the
`structure in Fig. 3(c).
`
`In the following, we use the expressions found in Sec. 2 lo obtain
`an optimum solution for the adaptive subband filters, Wk(z).
`
`(5)
`
`J, OPTIMUM SUBBAND FILTERS
`
`60
`
`Petitioner Apple Inc.
`Ex. 1018, p. 60
`
`

`

`X(z)
`
`[R·'"(z) ~~~
`~~: ···s·.(z).
`•
`: /
`- E1 (z)
`r±J ~ ;
`. .
`:
`~· W.1NI{Zy
`
`Figure 4: SAF optimal polyphase solution in the kth subband.
`
`3.1. Error Minimization
`
`Assuming that no disturbances are present and the SAF system in
`Fig. 1 can perfectly model the unknown system, Ef(z) should be
`zero in the steady state. As it is desirable to achieve optimality
`of the subband filters regardless of the input, the requirement for
`optimality (in every sense) is
`
`'
`H., (z) · S(z) ""H., · Wk,opt(z)
`T
`T
`
`(12)
`
`following from (11 ). Hence, we obtain N cancellation conditions
`indicated by superscripts o<nl. which have to be fulfilled:
`w<nl (z) = H[(z) · A;;(z) · S(z)
`k,opt
`Hkjn(z)
`
`'VnE{O;N-1}.
`
`(13)
`
`TI!erefore, ideally Wk(z) in (11) and (12) should be replaced by an
`NxN diagonal matrix with entries W~n) (z). For the kth subband,
`this solution with N polyphase filters is given by the structure in
`Fig.4.
`
`3.2. Discussion
`
`An alternative notation to (13) is to write the nth optimum solution
`as
`
`N-1
`
`w~~pt(z) = L A~l~(z). S"(z)
`
`11""'0
`
`(14)
`
`and interpret it as a superposition of polyphase components of
`S(z), "weighted" by transfer functions
`
`A(")( ) _
`-l(n+")/NJ Hkl(n+") modN(z)
`k)n z - z
`'
`( )
`H
`kin Z
`
`.
`
`(1 5)
`
`This forms the basis for some interesting observations.
`Firstly, the length of the optimum subband responses is obvi(cid:173)
`ously given by 1/N of the order of S(z), but extended by the trans(cid:173)
`fer functions (15). These extending transients are causal for poles
`of Ail~. (z) within the unit circle, and non-causal for stabilized
`poles outside the unit-circle [12]. Hence, besides the motivation
`for a non-causal optimum response, it is particularly interesting
`that the required SAF length obviously depends on the transients
`caused by the analysis filters Hk(z).
`
`61
`
`Proc. 1999 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, New Paltz, New York, Oct. 17-20, 1999
`
`N l :~· ·-,: [Hklo(z)}
`
`X(z)
`
`Figure 5: SAF standard solution in the kth subband.
`
`Secondly in general, particularly when the stopband attenua(cid:173)
`tion of the analysis filters is insufficient, the components Hkln (z)
`in (15) differ, hence leading to different polyphase solutions H{~Jpt(z)
`in every of theN branches in Fig. 4. Only if all elements in (15)
`are identical, the optimal subband responses can be swapped with
`the adder and give the well-known standard SAF solution shown
`in Fig. 5.
`Thus, if non-ideal filter banks are used and in particular alias(cid:173)
`ing is present in the subband signals, this optimum standard SAF
`solution gives the closest 12 match to all N optimal polyphase so(cid:173)
`lutions:
`
`Wk,opt(z) = ~ L w~~pt(z) .
`
`N-1
`
`n:::=O
`
`(16)
`
`The error made in this approximation can explain MMSE and mod(cid:173)
`elling limitations of the SAF approach and repreSents an alterna(cid:173)
`tive coefficient I time-domain description as opposed to spectrally
`motivated SAF error explanations in the literature [2, 8].
`
`4, EXAMPLES
`
`To verify the validity of our analysis, we first discuss an unrealistic,
`but very simple example of a critically decimated 2-channel SAF
`system using Haar filters [9]. We want to identify the unknown
`system S(z) = l+z- 1 using a unit variance Gaussian white noise
`excitation, and here only consider the lowpass band produced by
`the analysis Haar filter Ho(z) = 1 + z- 1
`. Evaluating (14) and
`(15) yields as optimum polyphase solution
`
`o,opt z = 1 + z
`wo,opt z = 2 ' W (1)
`(0)
`(
`)
`
`(
`
`)
`
`-1
`
`.
`
`(17)
`
`Tn a simulation using a recursive least squares (RLS) algorithm
`[13], the converged adaptive filter Wo(z) = 1.4873 + 0.5067z- 1
`very closely agrees with the analytical solution (16) calculated
`from (17),
`
`Wo,opt(z) = 1.5 + 0.5z- 1
`
`Additionally, the PSD of the Oth adapted sub baud error signal,
`Se0 ( ei 0
`), can be analytically predicted by inserting the optimum
`standard solution (16) into (11),
`
`s.,(e;") = \E~(e;")\ 2 = 1- cosO
`
`,
`
`(18)
`
`Petitioner Apple Inc.
`Ex. 1018, p. 61
`
`

`

`Proc. 1999/EEE Workshop on Applications of Signal Processing to Audio and Acoustics, New Paltz, New York, Oct. 17-20, 1999
`
`9 -----,---
`
`~~~
`desired signal PSD
`
`simulated
`
`analytical pred.
`
`,_- ~'
`
`'~
`
`tmor S\grtal PSO
`
`s1mulated
`analytical prediCtion
`
`, I
`
`~~~--...v
`
`~~__.--._,.---
`~-~
`
`-=- --~ -l-------'------.J _ _ , _ ~~
`
`o 1
`
`0.2
`
`0_3
`
`o 4
`0.6
`0.5
`normalized frequency OJn
`Figure 6: Com-pari~on between simulated and analytically pre(cid:173)
`dicted PSDs in the Oth subband.
`
`o.7
`
`o_B
`
`0.9
`
`10
`
`15
`
`25
`
`20
`timen
`Figure 7: Optimal polyphase solutions, standard SAF approxima(cid:173)
`tion, and simulation result of a system using a 32 tap analysis filter.
`
`30
`
`35
`
`40
`
`which can he used to determine the minimum mean squared er(cid:173)
`ror of the SAF system alternative to spectral methods [8]. Fig. 6
`demonstrates the excellent fit between the analytically calculated
`PSD in (18), and the measured results from the RLS simulation.
`Also shown is the analytically predicted and measured PSD of the
`Oth desired subband signal sd,(ej0 ) = 6 + 2cos0 (hence the
`uncancelled error signal) calculated via (5).
`As a second example, Fig. 7 shows analytical and simulated
`results for the Oth subband in critically sampled 2-channel SAF
`system employing the 32 tap QMF filter 32C [14]. The responses
`w~~~p1 [n] and w6~~pt(n] are the optimum polyphase solutions as
`indicated in Fig. 4.
`[n the two bottom diagrams, the analytical
`solution (16) for the best approximation wk,opt[n] of the standard
`SAF setup in Fig. 5 closely agrees to the result of an RLS solution,
`Wo,adapt(n].
`
`5. CONCLUSION
`
`We have introduced a polyphase analysis of an SAF system, which
`leads to an optimum polyphase solution for the subband filters,
`which can be computed using the formulations presented here. In(cid:173)
`terestingly, the standard SAF solution can only allow an approx-
`
`62
`
`imation of these optimal polyphase solutions, which gives alter·
`native insight into the inaccuracies and limitations of the SAP ap(cid:173)
`proach. Thus, the 'classical' error explanation by aliasing [1, 7, 8]
`is replaced by the approximation of potentially differing polyphase
`solutions. Therefore potential of the presented analysis lies in
`the access to the optimum and approximate solutions, which may
`complement analysis with regard to other error sources 18].
`
`6. ACKNOWLEDGMENT
`
`The authors would like to gratefully acknowledge Dr. Ian Proudler
`of DERA, Malvern, England, who partially supported this work.
`
`7. REFERENCES
`
`[ l] W. Kellermann, "Analysis and Design of Multi rate Sys(cid:173)
`tems for Cancellation of Acoustical Echoes", in Proc. IEEE
`ICASSP, New York, 1988, val. 5, pp. 2570-2573.
`[2] A. Gilloire and M. Vetterli, "Adaptive Filtering in Subbands
`with Critical Sampling: Analysis, Experiments and Appli(cid:173)
`cations to Acoustic Echo Cancelation",
`IEEE Trans SP,
`vol. SP-40, no. 8, pp. 1862-1875, Aug. 1992.
`f3] M. Sch6nle, N.J. Fliege, and U. ZOlzer, "Parametric Approx(cid:173)
`imation of Room Impulse Responses by Multirate Systems",
`in Proc. IEEE JCASSP, Minneapolis, 1993, vol. I, pp. 153-
`156.
`[4] S. Weiss, S.R. Dooley, R.W.. Stewart, and A.K. Nandi,
`"Adaptive Equalization in Oversamplcd Subbands",
`lEE
`Electr. Let., vol. 34, no. 15, pp. 1452-1453, July 1998.
`[5] W. Kellermann, "Strategies for Combining Acoustic Echo
`Cancellation and Adaptive Beamforming Microphone Ar(cid:173)
`rays", in Proc.IEEEICASSP, Munich, 1997, val. I, pp. 219-
`222.
`[6] R.J. Wilson, P.A. Naylor, and D.M. Brookes, "Performance
`Limitations of Subband Acoustic Echo Controllers",
`in
`Proc. fWAENC, Imperial College, London, 1997, pp. 176-
`179.
`[71 M.R. Petraglia and S.K. Mitra, "Performance Analysis of
`Adaptive Filter Structures Based on Subband Decomposi(cid:173)
`tions", in Proc. JSCAS, Chicago, 1993, vol. I, pp. 60-63.
`L81 S. Weiss, R.W. Stewart, A. Stenger, and R. Rabenstein,
`"Performance Limitations of Subband Adaptive Filters", in
`Proc. EUS/PCO, Rodos, Greece, 1998, vol. III, pp. 1245-
`1248.
`[9] N.J. Fliege, Multirate Digital Signal Processing: Multirate
`Systems, Filter Banks, Wavelets, John Wiley & Sons, Chich(cid:173)
`ester, 1994.
`[ l 0] P. Vary, "On the Design of Digital Filter Banks Based on
`a Modified Principle of Polyphase", Archiv Elektr. Ohern:,
`vol. 33, pp. 293-300, 1979.
`[11] P.P. Vaidyanathan, Multirate Systems and Filter Banks, Pren·
`lice Hall, Englewood Cliffs. 1993.
`[12] B. Widrow and E. Walach, Adaptive Inverse Control, Pren~
`ticc Hall, Englewood Cliffs, 1995.
`[13J S. Haykin, Adaptive Filter Theory, Prentice Hall, Englewood
`Cliffs, 2nd ed. , 1991.
`[141 R.E. Crochiere and LR. Rabiner, Multirate Digital Signal
`Processing, Prentice Hall, Englewood Cliffs, 1983.
`
`Petitioner Apple Inc.
`Ex. 1018, p. 62
`
`