Chapter 3
MULTIRATE FILTER BANKS
This chapter introduces and summarizes the general theory and application of multirate filter banks relevant to this research. Included is a general introduction to multirate theory and an overview of perfect reconstruction filter banks, Johnston filters, and IIR approximations to FIR multirate filters.
Introduction
A basic multirate filter bank is shown in Figure 9a. Multirate filter banks are so named because they effectively alter the sampling rate of a digital system, as indicated by the decimators (downsamplers) following the analysis filters, A0 and A1, and the expanders (upsamplers) preceding the synthesis filters, S0 and S1. Properly designed analysis and synthesis filters combined with the properties of decimation and expansion allow filter banks to partition a wideband input signal into multiple frequency bands (often called subbands or channels) and to recombine these subband signals back into the original signal. In the case of Figure 9, the analysis filters, A0 and A1, are typically complementary lowpass and highpass filters that mirror each other about the digital frequency, p/2, as shown in Figure 9b. Such filters are often called quadrature mirror filters (QMF), since p/2 corresponds to one fourth the sampling frequency.
Figure 9. (a) Block diagram of a simple two-channel multirate system, and (b) approximate magnitude responses of analysis filters, A0 and A1
Decimation and Expansion
Clearly, the concept of multirate filtering relies on the two processes that effectively alter the sampling rate, decimation and expansion. Decimation or downsampling by a factor of M essentially means retaining every Mth sample of a given sequence. Decimation by a factor of M can be mathematically defined as
(16)
or equivalently,
(17)
Expansion or upsampling by a factor of M essentially means inserting M-1 zeros between each sample of a given sequence. Expansion by a factor of M can be mathematically defined as
(18)
or equivalently,
(19)
Errors in the QMF Bank
The QMF bank is prone to three types of distortion: aliasing distortion, amplitude distortion, and phase distortion. Practical filters have a non-zero transition band. In order for the QMF bank to remain lossless, then, the analysis filters must overlap as shown in Figure 9b. Hence, the analysis filters are not strictly band-limiting and the subsequent decimation causes aliasing.
Fortunately, aliasing can be completely cancelled by properly designing the synthesis filters, S0 and S1. With Equations 17 and 19, the output of the QMF bank can be expressed as
(20)
The aliasing component in y(n) becomes zero when
(21)
or, more specifically, when
(22)
Thus, aliasing in one branch is completely cancelled by the synthesis filter in the opposite branch. The entire alias-free filter bank can now be expressed as the single transfer function,
(23)
Then, letting z = ejw
(24)
If |H(ejw)| isn’t constant and non-zero for all w (allpass), the filter bank suffers from amplitude distortion. Likewise, if H(ejw) does not have linear phase (if f (w) is not of the form a× w + b) the filter suffers from phase distortion. It is important, at this point, to emphasize that these two conditions apply to the filter bank as a whole (Equation 24), not the individual analysis and synthesis filters. When the filter bank is free from aliasing, amplitude distortion, and phase distortion, it is called a perfect reconstruction (PR) filter bank.
The Noble Identities
The ability to manipulate specific blocks of the multirate filter bank is of use when searching for computationally optimized implementations. Indeed, the noble identities and the polyphase representation provide a means of immediately improving the computational efficiency of the structure shown in Figure 9a.
The noble identities are concisely stated by Figure 10. They allow for the transposition of analysis and synthesis filters with their associated decimators and expanders. The identities may not hold true if H(z) is not rational.
Figure 10. The noble identities for multirate systems (adapted from Vaidyanathan 1993).
Polyphase Representation
Polyphase representation is, in simple terms, a method of re-organizing the coefficients of a given transfer function, h(n). The transfer function can be represented in terms of its even and odd coefficients.
(25)
Therefore,
(26)
where
(27)
This idea can be extended to further decomposition by a factor of M (Vaidyanathan, 1993a, p. 121). Then H(z) takes on the "Type 1 polyphase" form
(28)
where
(29)
with
(30)
Graphically, Figure 11 illustrates the relationship between h(n) and its pth polyphase component.
Figure 11. Relationship between h(n) and its pth polyphase component.
The "Type 2 polyphase" form is a permutated version of the Type 1 form and is given by
(31)
where
(32)
By combining the polyphase representation and the noble identities, it is possible to implement more efficient analysis filter/decimator and expander/synthesis filter blocks of the form shown in Figure 12. Figure 12a illustrates the analysis filter/decimator polyphase implementation directly from Equation 25. Figure 12b shows the same implementation after invoking the noble identities. Figure 12c shows the expander/synthesis filter polyphase implementation, which takes advantage of the Type 2 representation. Figure 12d again shows the effect of the noble identities.
Figure 12. Polyphase analysis and synthesis: (a) the direct polyphase implementation of an analysis filter and decimator, (b) the same implementation after invoking the noble identities, (c) the polyphase implementation of an expander and synthesis filter, and (d) the same implementation after invoking the noble identities (adapted from Vaidyanathan, 1993a).
Although the implementation shown in Figure 12b appears to be more complicated, consider that the two polyphase components must only operate at half the sampling rate of the original filter. That is, each sample of output requires the same amount of computation (the combined order of E0 and E1 is identical to the original filter), but has twice as much time to do it. Also, all the outputs of the polyphase implementation are used, whereas, in the original structure, every other output sample is discarded by the decimator. Similarly, the expander/synthesis filter implementation shown in Figure 12d improves efficiency because the two polyphase components need not spend half their multiplications on zeros inserted by the expander. Also, note the unit delay and addition at the right of Figure 12d. This explicit delay and addition isn’t really necessary because the output can be obtained by merely interleaving (time multiplexing) the two filter outputs.
M-Channel Filter Banks
The 2-channel QMF bank shown in Figure 9a can be effectively expanded to an M-channel bank using a tree structure as shown in Figure 13.
Figure 13. Example of a tree-structured filter bank: (a) a uniform implementation, (b) a non-uniform implementation.
This method splits the input signal into multiple bands while maintaining the characteristics of the original two-channel QMF bank (Vaidyanathan, 1993, pp.254-255). It is also flexible in that filter uniformity is not required, as evident from the three octave structure in Figure 13b.
Clearly the tree-structure is not a particularly efficient method. As one would expect, there exist more efficient M-channel designs of which the two-channel QMF bank is just a special case. The generalized M-channel multirate filter bank has the form shown in Figure 14. It is often called an M-channel QMF bank, which is a bit of a misnomer since the quadrature aspects of the filter bank are gone.
Figure 14. A generalized M-channel multirate filter bank.
The output of this system can be expressed as
(33)
where
(34)
and W represents the phase term, e-j2p/M (Vaidyanathan, 1993a). The alias terms are readily identified as X(z× Wp) since they represent identical, but frequency shifted versions of X(z). Gp(z), then, is the associated gain factor for a given alias term. Thus, the filter bank is free from aliasing only if
(35)
Once again, this alias free system can be represented as a single transfer function of slightly different form than that of the two-channel QMF case.
(36)
The criteria for amplitude and phase distortion are the same. If G0(z) is not allpass, the filter bank suffers from amplitude distortion. If G0(z) does not have linear phase, the filter bank suffers from phase distortion. Again, when the filter bank is free from aliasing, amplitude distortion, and phase distortion, it is called a PR filter bank.
M-channel banks lend themselves to matrix representations which are useful in the design of specific filters. Figures 15a and b illustrate the analysis and synthesis filter matrix equations in polyphase form (from Equations 27 and 31). Figure 15c illustrates the new M-channel filter bank after simplifying with the noble identities.
Figure 15. The polyphase representation for an M-channel (a) analysis bank, A(z) = E(zM)× d(z), and (b) synthesis bank, ST(z) = z-(M-1)× dT(z-1)× R(zM). (c) The M-channel filter bank after simplifying with the noble identities.
Notice the two new matrix equations this representation yields.
(37)
and
(38)
where A and S represent the analysis and synthesis matrices, respectively, and d represents the delay chain vector.
The bulk of the material covered in this paper will concentrate on the specific case where M=2. Figure 16 illustrates the associated polyphase matrices for this case.
Figure 16. The polyphase matrix representation of a two-channel (a) analysis bank and (b) synthesis bank and (c) the polyphase system after simplification.
Perfect Reconstruction Filter Banks
It can be shown that the system illustrated in Figure 15c exhibits perfect reconstruction if
(39)
or, more generally, if
(40)
for some integer, r, between 0 and M-1, some integer, m, and some non-zero constant, c. If one of these conditions holds, y(n) = c× x(n-n0) where n0 = M× m + r + M - 1 regardless of whether the system is FIR or IIR (Vaidyanathan 1993). Subsequently, if Equation 40 is satisfied,
(41)
for some constant, c, and some integer, k. If the analysis and synthesis filters are FIR, then their coefficient matrices and determinants are FIR. Thus, every FIR PR system must then satisfy
(42)
for constant, a, b, k0, and k1 (Vaidyanathan, 1993a, p. 238).
Vaidyanathan (1987) has shown that causal FIR matrices demonstrating paraunitariness satisfy Equation 42 and, therefore, yield perfect reconstruction filter banks. The paraunitary property stems from the unitary property for lossless matrices. A matrix A exhibits the paraunitary property if,
(43)
where c is a constant. The carat notation (^) represents paraconjugation. Paraconjugation involves transposing the matrix, conjugating the coefficients, and replacing z with z-1. For the polyphase representation of Equation 40, this implies that
(44)
Notice that if the analysis filters and E(z) are stable and IIR, then, from Equation 44, the synthesis filter and R(z) are unstable because the poles of the reciprocal conjugates of E(z) fall outside the unit circle. There are methods to create nearly PR IIR filter banks which will be explored in the final section of this chapter.
Under the constraint of paraunitariness, two channel FIR PR filter banks can be designed via a zero-phase half-band FIR filters, A(z), where A(ejw) is real and greater than or equal to zero for all w. However, problems arise when computing a spectral factor, A0(z). The spectral factor is defined by
(45)
Essentially, the spectral factor is a half-band filter with zeros outside the unit circle and multiple zeros on the unit circle removed. This ensures that the transfer function has a non-negative frequency response for all w, which is necessary for perfect reconstruction (Vaidyanathan, 1993a, p. 204). Direct computation of the spectral factor by finding and selecting zeros is possible, but a direct implementation of A0(z) is very susceptible to coefficient quantization. In any event, once A0(z) is known, the conditions imposed by the paraunitary property require
(46)
for A0(z) of order N.
The QMF Lattice
As an alternative to the spectral factor calculation, Vaidyanathan and Hoang (1988) have proposed the so-called QMF lattice structure. This structure functions explicitly as a robust implementation scheme and implicitly as an iterative design methodology. The lattice is derived from a factorization of the polyphase component by the Givens rotation and d(z)× I. Summarily, the two multiplier QMF lattice is shown in Figure 17.
Figure 17. The QMF lattice (a) analysis bank and (b) synthesis bank for real, causal, perfect reconstruction filters.
First, the filter order, J, is selected. Then the coefficients, ai, are computed based on an iterative minimization of stopband energy. The coefficients are related to the transfer function by
(47)
(48)
where Ai(m) is the transfer function up to "Stage m,"
(49)
and S is a scaling factor dependent on the coefficient set. Equations 46 and 47 imply one of several properties the QMF lattice holds. Namely, the lattice is hierarchical. If the lattice is ended prior to the final stage, it retains its paraunitary property. Also, the analysis and synthesis filters have the same length, the perfect reconstruction property is preserved regardless of coefficient quantization, the computational complexity is the lowest for paraunitary E(z), and A0(z) is power symmetric (Â0(z)× A(z) is a half-band filter) (Vaidyanathan 1993, pp. 302-313). A 64-tap sample analysis bank from Vaidyanathan and Hoang (1988) is shown in Figure 18 (Filter #64D in the reference).
(a)
(b)
(c)
Figure 18. Vaidyanathan and Hoang’s Filter #64D analysis bank (a) magnitude response, (b) phase response, and (c) group delay derived from their QMF lattice.
One important aspect of the QMF lattice design is that the analysis and synthesis filters do not necessarily exhibit a linear phase response or a reasonably constant group delay , which can pose difficulty in digital audio applications. Another is that, since it is an FIR design, the order and subsequent delay of the filters is significant. The next section presents an alternative to the lattice design that is not as susceptible to these shortcomings.
Filter Banks with Minimized Amplitude Distortion
From Equations 20 and 22 it is clear that if
(50)
then the aliasing term, X(-z), cancels and the transfer function for the entire filter bank becomes
(51)
This structure could introduce phase distortion and amplitude distortion. If A0(z) is FIR and has linear phase, then H(z) will have linear phase, so phase distortion is eliminated. This means that A0(z) is symmetric. That is, a0(n) = a0(N - n) for a filter of order N. Then,
(52)
where R(w) is real for all w. From this and the observation that |A0(ejw)| is even,
(53)
(Vaidyanathan 1993a). In order to avoid severe distortion around w = p, N must be even. Therefore, with Equation 50,
(54)
Since this transfer function determines the amplitude distortion present in the signal, it would be desirable to find filter coefficients such that
(55)
Johnston (1980) has devised a technique to minimize the amplitude distortion based on well-known multivariable optimization routines. Essentially, the filter coefficients are used to calculate the value of an objective function that represents the combined passband ripple and stopband energy. The objective function is given by E = Er + a× Es where
(56)
(57)
(Johnston 1980). With the help of a computer and the proper minimization algorithm, the coefficients can be modified so that the objective function is minimized and Equation 55 holds approximately true across the transition band of the filters. Figure 19 illustrates an example Johnston filter and the associated amplitude distortion. Clearly, if some very small passband distortion ( < .01 dB) is acceptable, then the Johnston filters provide a linear phase alternative to the QMF lattice described above.
(a)
(b)
(c)
Figure 19. Johnston’s Filter #64D analysis bank (a) magnitude response, (b) distortion characteristic, H(ejw), and (c) group delay.
IIR Approximation of Linear Phase Perfect Reconstruction Filter Banks
Ekanayake and Premaratne (1995) have proposed a design methodology for creating nearly linear phase IIR analysis and synthesis filters, which have the additional benefits of lower complexity and less sensitivity to quantization.
The design procedure involves applying a balanced reduction to the state-space representation of a suitable linear phase FIR prototype filter. A typical prototype is a minimized amplitude distortion (Johnston) filter such as those described above. Once the reduced IIR filter with approximately the same magnitude and phase responses is developed, the residual magnitude response and group delay error can be further minimized with numerical optimization techniques. Although the design process is somewhat tedious and significantly more complex than that of the QMF lattice or Johnston filter, the resultant IIR filters do exhibit approximately linear phase and constant group delay, good stopband attenuation, lower implementation complexity, and lower sensitivity than comparable FIR or lattice filters. An optimized analysis bank of order 32 is shown in Figure 20.
(a)
(b)
(c)
Figure 20. Ekanayake and Premaratne’s 32nd order IIR analysis bank with approximately linear phase. Plots are (a) magnitude response, (b) phase response, and (c) group delay.
Figures 20b and c indicate that, although the phase response is nearly linear, its associated group delay varies slightly in the transition band. Even so, the variation is less than 0.02 sample, which is acceptable for most, if not all, applications. Although filter banks comprised of these IIR filters only approximate perfect reconstruction, they are superior to the QMF lattice or AMD minimized designs with respect to complexity, attenuation, phase response, group delay, and stability.