Multirate Digital Filters, Filter Banks,
`Polyphase Networks, and Applications:
`A Tutorial
`
`P. P. VAIDYANATHAN, SENIOR MEMBER, IEEE
`
`Mu/tirate digital filters and filter banks find application in com(cid:173)
`munications, speech processing, image compression, antenna sys(cid:173)
`tems, analog voice privacy systems, and in the digital audio indus(cid:173)
`try. During the last several years there has been substantial progress
`in multirate system research. This includes design of decimation
`and interpolation filters, analysis/synthesis filter banks (also called
`quadrature mirror filters, or QMF), and the development of new
`sampling theorems. First, the basic concepts and building blocks
`in mu/tirate digital signal processing (DSP), including the digital
`polyphase representation, are reviewed. Next, recent progress as
`reported by several authors in this area is discussed. Several appli(cid:173)
`cations are described, including the following: subband coding of
`waveforms, voice privacy systems, integral and fractional sampling
`rate conversion (such as in digital audio), digital crossover net(cid:173)
`works, and multi rate coding of narrow-band filter coefficients. The
`M-band QMF bank is discussed in considerable detail, including
`an analysis of various errors and imperfections. Recent techniques
`for perfect signal reconstruction in such systems are reviewed. The
`connection between QMF banks and other related topics, such as
`block digital filtering and periodically time-varying systems, based
`on a pseudo-circulant matrix framework, is covered. Unconven(cid:173)
`tional applications of the polyphase concept are discussed.
`
`I.
`
`INTRODUCTION
`
`In recent years there has been tremendous progress in
`the multirate processing of digital signals. Unlike the sin(cid:173)
`gle-rate system, the sample spacing in a multirate system
`can vary from point to point[1], [2]. This often results in more
`efficient processing of signals because the sampling rates
`at various internal points can be kept as small as possible.
`Unfortunately, this also results in the introduction of a new
`type of error, i.e., aliasing, which should somehow be can(cid:173)
`celed eventually.
`The basic building blocks in a multi rate digital signal pro(cid:173)
`cessing (DSP) system are decimators and interpolators. In
`1981, an excellent tutorial article on decimation and inter(cid:173)
`polation appeared in [3]. Subsequent to this a text on the
`subject of multi rate systems has also been published by the
`same authors [4]. Since then, a number of new develop(cid:173)
`ments have taken place in the area, particularly in multi rate
`
`Manuscript received October 12, 1988; revised june 13, 1989. This
`work was supported in part by the National Science Foundation
`under grants DCI 8552579 and MIP 8604456.
`The author is with the Department of Electrical Engineering, Cal(cid:173)
`ifornia Institute of Technology, Pasadena, CA 91125, USA.
`IEEE Log Number 8933329.
`
`digital filter bank designs. A short summary of some of these
`developments was reported recently by this author at an
`IEEE international conference [5]. The purpose of this article
`is to provide a self-contained and more complete exposure
`to many recent contributions on multi rate systems, includ(cid:173)
`ing filter bank design.
`As mentioned in [3], multirate systems find application
`in communications, speech processing, spectrum analysis
`[6], radar systems, and antenna systems. In this tutorial, two
`sections are devoted to a review of applications. In Section
`Ill, we point out applications in digital audio systems, in
`subband coding techniques (used in speech and image
`compression), and in analog voice privacy systems (for stan(cid:173)
`dard telephone communications). In Section V-E, appli(cid:173)
`cations of special transfer functions (such as complemen(cid:173)
`tary functions) in digital audio is reviewed. In Section IX,
`several unconventional applications of multirate systems
`and polyphase theory are indicated. These include a) deri(cid:173)
`vation of new sampling theorems for efficient compression
`of signals, b) derivation of new techniques for efficient cod(cid:173)
`ing of impulse response sequences of narrow band filters,
`c) design of FIR filters with adjustable multilevel responses,
`and d) adaptive filtering in subbands.
`
`A. Paper Outline
`
`In section II, basic tools, such as decimators, interpola(cid:173)
`tors, decimation and interpolation filters, and digital filter
`banks, are reviewed, along with the interconnection prop(cid:173)
`erties of the building blocks. In section Ill, some applica(cid:173)
`tions of multirate DSP are indicated, in digital audio sys(cid:173)
`tems, in subband coding, and in voice privacy systems.
`Section IV reviews the digital polyphase decomposition due
`to Bellanger, along with applications such as the uniform
`DFT filter bank. The concept of multilevel polyphase
`decomposition is also introduced here as a tool for efficient
`implementation of fractional decimation filters. Several
`special types of filter banks, such as Nyquist filters, power(cid:173)
`complementary systems and Euclidean filter-banks, are
`studied in section V.ln section VI, the two-band QMF bank
`is studied in sufficient detail along with procedures for
`eliminating aliasing in such systems. Procedures for elim(cid:173)
`ination of amplitude and/or phase distortion are discussed.
`
`0018-9219/90/0100-0056$01.00 © 1990 IEEE
`
`56
`
`PROCEEDINGS OF THE IEEE, VOL. 78, NO. 1, JANUARY 1990
`
`Petitioner Apple Inc.
`Ex. 1010, p. 56
`
`

`
`The most crucial property of W that finds repeated use in
`multirate OSP is the following:
`[M
`'
`O,
`
`k = integer multiple of M
`
`otherwise.
`
`(1c)
`
`M-1
`2:; wkn =
`n=O
`
`Perfect-reconstruction two-channel QMF banks are intro(cid:173)
`duced by blending the polyphase concept with the classical
`network-theoretic concept of losslessness.
`The relation between M-band QMF banks and two other
`related topics (block filtering and periodically time-varying
`systems) is reviewed in section VII, based on an algebraic
`structure called the pseudo-circulant matrix. In section VIII,
`M-band QMF banks are discussed in greater detail, and
`techniques for elimination of aliasing, amplitude, and phase
`distortions are reviewed. Section IX discusses unconven(cid:173)
`tional applications, and Section X discusses some exten(cid:173)
`sions of multirate ideas to cases of multidimensional sig(cid:173)
`nals. The paper concludes with a discussion of open
`problems in multirate OSP.
`
`B. Notations and Terminology
`
`The variables nand ware used as frequency variables for
`continuous-time and discrete-time cases, respectively. In
`the discrete-time case the term normalized frequency is
`used to denote f = w/21r. The frequency response of a trans(cid:173)
`fer function H(z) is expressed as H(eiw) = IH(eiw)l e i<P<wl, where
`I H(eiw)l is the magnitude response and cf>(w) the phase
`response. The quantity T(w) = -dcf>(w)/dw is the group delay
`of H(z). If IH(eiw)l is constant for all w, H(z) is all-pass. If cf>(w)
`has the form k 0 - k1 w, then H(z) is said to have linear phase
`and the group delay is a constant k1; physically, if the input
`to such a filter H(z) has energy only in the passband of H(z),
`then the output is a delayed version of the input, by k1 sam(cid:173)
`ples. Unless mentioned otherwise, a low-pass filter has real
`coefficients, so that IH(eiw)l is symmetric and cf>(w) is anti(cid:173)
`symmetric with respect tow = 0. Usually IH(eiw)l is plotted
`for 0 s f s 0.5 (i.e., for 0 s w s 1r). If wp and w5 denote the
`passband and stopband edges of a low-pass filter, the quan(cid:173)
`tity we = (wp + w5)/2 is said to be the cutoff frequency.
`Bold-faced quantities denote matrices and vectors, as in
`A, H(z) etc. The symbollk denotes the k x k identity matrix
`(with subscript often omitted). The quantitiesAr,At and A*
`denote, respectively, the transpose, transpose conjugate,
`and conjugate of A. For functions H(z), the notation H*(z)
`denotes conjugation of the coefficients without conjugat(cid:173)
`, then H*(z) =a* +
`ing z. For example if H(z) = a + bz- 1
`b*z- 1
`• Thus, H*(z) = H*(z*). The notation H(z) stands for
`H~(z- 1). In other words, conjugate the coefficients, take
`transpose (if matrix), and replace z with z- 1• When z = eiw
`(i.e., on the unit circle), we have H(z) = Ht(z). Linear time(cid:173)
`invariant systems [7] are abbreviated as L Tl and linear
`periodically time-varying systems as LPTV. A p x r matrix
`A is said to be unitary (orthogonal if it is real) if AtA = cl,
`c =I= 0. Note that A is not restricted to be square. For exam(cid:173)
`ple, [~~·<~ll is unitary for any real 8. The symbol WM stands
`for e -jzrtM. The subscript M is usually deleted because its
`value is often clear from the context. This quantity appears
`in the definition of the discrete Fourier transform (OFT) [7],
`[8]. Thus an M-point sequence [x0, x1, • • • , xM_ 1] has the
`M-point OFT sequence
`
`M-1
`Xk = 2:; Xn Wkn,
`n=O
`
`0 s k s M- 1.
`
`(1a)
`
`The inverse OFT (lOFT) is given by
`
`(1b)
`
`For any pair of integers k, n, we have w• = wn, if and only
`if k - n is an integer multiple of M. In particular, therefore,
`Wk =1= wn for 0 s k < n s M - 1.
`State Space Descriptions: Consider a discrete time trans(cid:173)
`fer matrix H(z) with input vector u(n) and output vector y(n).
`Suppose we have implemented this transfer matrix using
`a structure, and let N denote the number of delay elements
`used. Label the outputs of the delay elements as the state
`variables xk(n), 0 s k s N - 1, and define the state vector
`x(n) = [x0(n) x1(n) · · · xN_ 1(n)]r. With u(n) and y(n) denoting
`the input and output (vector) sequences to the structure,
`one can always find equations of the form [9]
`
`x(n + 1) = Ax(n) + Bu(n),
`y(n) = Cx(n) + Du(n),
`
`to describe the structure. This is called the state-space
`description of the structure. The matrix A, called the state
`transition matrix, has size N x N, where N is the number
`of delays in the structure. The transfer function H(z) of the
`structure is given by H(z) = D + C(zl- A)- 18. The smallest
`number of delay elements (i.e., z- 1 elements) required to
`implement H(z) is called the McMillan degree (or simply,
`the degree) of H(z). If the number of delays N in the struc(cid:173)
`ture is equal to the degree, then the structure is said to be
`a minimal realization of H(z). This is equivalent to saying
`that A is as small as possible.
`A summary of acronyms and common notations used in
`this paper is found in the Nomenclature, which follows sec(cid:173)
`tion XI.
`
`II. BASIC BUILDING BLOCKS AND TOOLS
`
`In this section we introduce the basic multi rate building
`blocks, along with their frequency-domain characteriza(cid:173)
`tions, and interconnection behaviors.
`
`A. Decimators and Interpolators
`
`Fig. 1 shows block diagrams of these building blocks. The
`decimator is characterized by the input-output relation
`
`y0 (n) = x(Mn)
`
`(2a)
`
`x(n)~Y:r(n)
`
`(b)
`
`Fig. 1. Building blocks. (a) M-fold decimator. (b) L-fold
`interpolator.
`
`which says that the output at time n is equal to the input
`at time Mn. As a consequence, only the input samples with
`sample numbers equal to a multiple of Mare retained. This
`sampling-rate reduction by a factor of M is demonstrated
`in Fig. 2 for the case of M = 2. The L"fold interpolator is char-
`
`VAlDYANATHAN: MULTIRATE DIGITAL FILTERS
`
`57
`
`-----··--------------~
`
`Petitioner Apple Inc.
`Ex. 1010, p. 57
`
`

`
`x(n) L J l l l J I
`
`012345678
`
`'''"' lrlr
`0 1 2 3 4
`Fig. 2. Demonstration of decimation for M = 2.
`
`acterized by the input-output relation
`
`yM ~ [:(z)
`
`if n is a multiple of L
`
`otherwise.
`
`(2b)
`
`That is, the output y1(n) is obtained by inserting L - 1 zero(cid:173)
`valued samples between adjacent samples of x(n), as dem(cid:173)
`onstrated in Fig. 3 for L = 2. The decimator and interpolator
`
`x(n) L lll l J I
`
`012345678
`
`'n
`
`Fig. 3. Demonstration of interpolation for L = 2.
`
`are linear systems even though they are time-varying [4], [5],
`[10].
`The z transform of the interpolator output y1(n) is given
`by [4]:
`
`(3a)
`This means Y1(ei"') = X(ei"'L) i.e., Y1(ei"') is an L-fold com(cid:173)
`pressed version of X(ei"'), as demonstrated in Fig. 4(b). The
`appearance of multiple copies of the basic spectrum in Fig.
`4 is called the imaging effect and the extra copies are the
`images created by the interpolator.
`
`Since decimation corresponds to compression in the time
`domain, one might expect a stretching effect in the fre(cid:173)
`quencydomain. To be more precise, theztransform ofy0 (n)
`is given by
`
`(3b)
`
`1 X(ei(w-hkl/M). The term with
`which means MY0 (ei"') = Ei;l=-0
`k = 0 is indeed theM-fold stretched version of X(ei"'). The
`M - 1 terms with k > 0 are uniformly shifted versions of
`this stretched version. These M terms together make up a
`function with period 21r in w, which is the basic property
`of the Fourier transform of any sequence [8]. Fig. 4(c) dem(cid:173)
`onstrates this effect for M = 2. The terms with k > 0 are
`called the aliasing terms. As long as x(n) is bandlimited to
`lwl < 1riM, there is no overlap of these terms with the k =
`0 term.
`The fundamental difference between aliasing and imag(cid:173)
`ing is important to notice. Aliasing can cause loss of infor(cid:173)
`mation because of the possible overlap of the shifted ver(cid:173)
`sions of the stretched version of X(e 1"'). Imaging, on the other
`hand, does not lead to any loss of information (which is con(cid:173)
`sistent with the fact that no time-domain samples are lost).
`
`B. Interconnections
`
`Fig. 5 shows a cascade connection which is often encoun(cid:173)
`tered in filter-bank systems. The signal v(n) here is equal to
`
`x(n)~v(n)
`
`~ -7t
`
`o
`
`7t
`
`• ro
`
`-1t/M
`1t/M
`Fig. 5. Effect of decimation followed by interpolation.
`
`x(n) whenever n is a multiple of M, and zero otherwise. The
`transform-domain relation is
`1
`V(z) = .:!_ M:i:
`X(zWk)
`M k=O
`
`(4)
`
`~~ro
`
`0
`(a)
`
`1t
`
`27t
`
`-21t
`
`-1t
`
`which means that MV(e1"') is a sum of X(e 1"') with the M -
`1 uniformly shifted versions X(ei(w-hk/Ml). From the figure
`we see that x(n) can be recovered from v(n) by eliminating
`the images by filtering, provided none of the images has an
`overlap with X(ei"'). If such an overlap occurs, it implies
`aliasing and x(n) cannot be recovered. Notice that in order
`for x(n) to be recoverable it is not necessary for X(e 1"') to be
`restricted to lwl < 1riM. It is sufficient for the total band(cid:173)
`width of X(e 1"')to be less than 21r/M. Thus a general bandpass
`signal with energy in the region a :S w :S a + 21r/M can be
`decimated by M without creating overlap of the alias com(cid:173)
`ponents, and the decimated signal in general is a full-band
`signal.
`A different type of cascade is shown in Fig. 6(a). We shall
`have occasion to use this in section IV-B, which concen(cid:173)
`trates on multilevel-polyphase decompositions. It should
`be cautioned that the two building blocks in Fig. 6(a) are not,
`in general, interchangeable, i.e., the systems in Fig. 6(a) and
`6(b) are not equivalent. For example, with M = L, the system
`of Fig. 6(a) is an identity system, whereas the system of Fig.
`&(b) causes a loss of M - 1 out of M samples. It can be shown
`
`~c -21t
`
`-1t
`
`0
`
`1t
`
`27t
`
`(c)
`
`Fig. 4. Transform-domain effects of decimation and inter(cid:173)
`polation. (a) The z transform. (b) l-fold compressed version.
`(c) Demonstration of effect when M = 2.
`
`58
`
`PROCEEDINGS OF THE IEEE, VOL. 78, NO. 1, JANUARY 1990
`
`Petitioner Apple Inc.
`Ex. 1010, p. 58
`
`

`
`x(n)~Y1 (n)
`(a)
`
`x(n)~y2 (n)
`(b)
`Fig. 6. Two ways to cascade decimator and interpolator.
`These are equivalent if and only if M and L are relatively
`prime. (a) Example of identity system. (b) Example of loss of
`M - 1 out of M samples.
`
`(Appendix A) that the systems of Fig. 6(a) and 6(b) are iden(cid:173)
`tical if and only if L and M are relatively prime.
`Decimation Filters and Interpolation Filters: In most
`applications a decimator is preceded by a bandlimiting fil(cid:173)
`ter H(z) whose purpose is to avoid aliasing. For example, a
`low-pass filter with stopband edge w 5 = 1riM can serve as
`such a filter. The cascade shown in Fig. 7(a) is commonly
`called a decimation filter. An interpolation filter, on the
`other hand, is a device which follows an interpolator (Fig.
`7(b)), the purpose being to eliminate the images. The low(cid:173)
`pass filter of Fig. 7(c) again serves as an example (with L =
`M).
`
`The decimation filter
`
`(a)
`
`The interpolation filter
`
`(b)
`
`plished by setting M = 3, L = 2 in Fig. 8(a). The filter H(z)
`is then taken to be low pass, with passband edge at 7r/3 and
`stopband edge at 27f/3. Notice that in this application, the
`transition bandwidth of H(z) need not be unduly narrow.
`The various signals in Fig. 8(a) have transforms as in Fig. 8(c),
`so that Y(e 1w) is a fractionally stretched version of X(e 1w).
`Two Noble Identities: In Fig. 9(a) we have a decimator fol(cid:173)
`lowed by a transfer function G(z). It can be proved, based
`
`~=~
`(b)
`
`(a)
`
`~=~
`~)
`~)
`Fig. 9. Noble identities for multi rate systems. (a} Decimator
`followed by transfer function G(z}. (b) Equivalent cascade.
`(c) Example of transfer function preceding. (d) Equivalent
`cascade.
`
`on (3b), that this cascade is equivalent to the one in Fig. 9(b)
`provided G(z) is a rational transfer function (i.e., a ratio of
`polynomials in z- 1
`). In a similar manner, the two cascades
`in Figs. 9(c) and 9(d) are equivalent (provided G(z) is rational),
`as can be proved from (3a). These identities are very val(cid:173)
`uable in practically all applications for efficient implemen(cid:173)
`tation of filters and filter banks. We shall call these the
`"noble identities."
`
`C. Analysis and Synthesis Banks
`
`These are the two basic types of filter banks. An analysis
`bank is a set of analysis filters Hk(z) which splits a signal into
`M subband signals xk(n) as shown in Fig. 10(a). What we do
`
`(c)
`(a) Decimation filter. (b) Interpolation filter. (c) Low(cid:173)
`Fig. 7.
`pass filter.
`
`x(n)
`
`Fractional Sampling Rate Alterations: Fig. 8(a) shows a
`scheme for reducing the sampling rate by a nonintegral
`(rational) number MIL. Fractional reduction of sampling rate
`often results in data compression without loss of infor(cid:173)
`mation. As an example, if X(eiw) is as in Fig. 8(b), then a frac(cid:173)
`tional reduction by 3/2 is possible. This can be accom-
`
`.
`.
`.
`.
`~xM_,(n) YM_,(n)~x(n)
`
`(a)
`
`(b)
`
`x(n)~y(n)
`
`(a)
`
`~ ,ro
`
`(b)
`
`Fig. 8. Decimation by rational fraction of MIL. (a) General
`structure. (b) Example of band limited signal. (c) Effect of frac(cid:173)
`tional decimation of this signal (L = 2, M = 3).
`
`~ 'OJ
`
`0
`
`1t
`4
`
`21t
`
`(c)
`Fig. 10. Analysis and synthesis filter banks. (a) Analysis
`bank. (b) Synthesis bank. (c) Typical response of uniform
`OFT filter bank; here M = 4.
`
`with the subband signals depends on the application, as we
`shall see in sections Ill, VI, and IX. Next, a synthesis bank
`(Fig. 10(b)) consists of M synthesis filters Fk(z), which com(cid:173)
`bine M signals Yk(n) (possibly from an analysis bank) into
`a reconstructed signal x(n). There are several types of filter
`banks, i.e., the complementary type, the Nyquist type, etc.,
`to be described in Section V along with applications.
`Uniform OFT Filter Banks: An analysis bank with M filters
`(M > 1) is said to be a uniform DFTfilter bank if all the filters
`are derived from H 0(z) according to Hk(z) = H 0(zWk), 0 ~
`k ~ M - 1. Here H 0(z) is called the prototype filter. Note
`
`VAIDYANATHAN: MUlTIRATE DIGITAl FilTERS
`
`59
`
`Petitioner Apple Inc.
`Ex. 1010, p. 59
`
`

`
`that Hk(eiw) = H 0(ei(w-21rk!Ml), which means that the fre(cid:173)
`quency responses of Hk(z) are uniformly shifted versions
`of H 0(eiw). Fig. 10(c) shows a typical set of responses, where
`H0(z) is taken to be low pass. More details can be found in
`section IV-C and in [4] and [11].
`
`Ill. SOME APPLICATIONS OF MULTIRATE SYSTEMS
`
`We shall now review a number of important applications
`of multi rate filters and filter banks, with pointers to the lit(cid:173)
`erature for details, examples, and demonstrations. In sec(cid:173)
`tion IX, several unconventional applications are also out(cid:173)
`lined.
`Applications in the design of transmultiplexers (which
`are devices for conversion between frequency division
`multiplexing (FDM) and time-division multiplexing (TDM))
`are not discussed here in detail, primarily because of the
`excellent treatment already available in [13]. Also see [14]
`for the correspondence between transmultiplexers and
`analysis/synthesis filter banks. The input to a TDM-to-FDM
`converter is a signal y(n), which is the time-multiplexed ver(cid:173)
`sion of M signals yk(n), 0 :s; k :s; M- 1. Given y(n), the com(cid:173)
`ponents yk(n) can easily be separated out by use of a com(cid:173)
`mutator switch [4], [13]. These M signals are then modulated
`using distinct carrier frequencies. The carrier frequencies
`wk, 0 :s; k :s; M- 1 are chosen so that there is sufficient spec(cid:173)
`tral gap between the messages. A sum of these M signals
`(which is the FDM signal) is then transmitted through the
`channel. The total channel bandwidth is therefore required
`to exceed the sum of signal bandwidths because of the safe(cid:173)
`guard gap between adjacent spectra. The gap enables one
`to obtain perfect recovery of the multiplexed signals yk(n)
`at a future point.
`A novel approach to transmultiplexing was suggested in
`[36] and cited in [14], based on synthesis and analysis filter
`banks. This approach permits overlap between the spectra
`of successive messages in the frequency domain. The total
`required channel bandwidth is therefore less than that in
`conventional FDM channels. Conditions are derived under
`which cross-talk can be avoided and the set of M original
`signals can still be recovered from this version. Details can
`be found in reference [36] cited in [14].
`
`A. Digital Audio Systems
`
`In the digital audio industry, it is a common requirement
`to change the sampling rates of band-limited sequences.
`This arises for example when an analog music waveform
`x.(t) is to be digitized. Assuming that the significant infor(cid:173)
`mation is in the band 0 :s; !OI/27r :s; 22kHz [15], a minimum
`sampling rate of 44kHz is suggested (Fig. 11(a)). It is, how(cid:173)
`ever, necessary to perform analog filtering before sampling
`to eliminate aliasing of out-of-band noise. Now the require(cid:173)
`ments on the analog filter H.(j!J) (Fig. 11(b)) are strigent: it
`should have a fairly flat passband (so that x.(j!J) is not dis(cid:173)
`torted) and a narrow transition band (so that only a small
`amount of unwanted energy is let in). Optimal filters forth is
`purpose (such as elliptic filters [9], which are optimal in the
`minimax sense) have a very nonlinear phase response [16,
`page 82] around the bandedge (i.e., around 22kHz). In high(cid:173)
`quality music this is considered to be objectionable [15]. A
`common strategy to solve this problem is to oversample
`x.(t) by a factor of two (and often four). The filter H.(j!J) now
`has a much wider transition band, as in Fig. 11(c), so that
`
`-44
`
`I
`-22
`
`/
`
`-44
`
`-22
`
`!1
`
`0
`
`!1
`
`0
`
`minimum
`sampling rate
`
`over-sampling
`rate
`
`+
`44
`
`/kHz
`88
`
`• kHz
`
`22
`(a)
`
`I
`
`22
`(b)
`
`~ • kHz
`
`44
`
`22
`(c)
`
`Xa(t)
`
`x(n)
`
`(d)
`(a) Spectrum of x.(t). (b) Antialiasing filter response
`Fig. 11.
`for sampling at 44 kHz. (c) Antialiasing filter response for
`sampling at 88kHz. (d) Improved scheme for AID stage of
`digital audio system.
`
`the phase-response nonlinearity is acceptably low. A simple
`analog_Bessel filter (which has linear phase in the passband
`[9]) can be used in practice. The sequence x1(n) so generated
`is then lowpass filtered (Fig. 11(d)) by a digital filter H(z) and
`then decimated by the same factor of two to obtain the final
`digital signal x(n). The crucial point is that since H(z) is dig(cid:173)
`ital, it can be designed to have linear phase [7], [16], [17],
`while at the same time providing the desired degree of
`sharpness.
`A similar problem arises after the D/A conversion stage,
`where the digital music signal y(n) should be converted to
`an analog signal by lowpass filtering. To eliminate the
`images of Y(eiw) in the region outside 22kHz, a sharp cutoff
`(hence nonlinear phase) analog low-pass filter is required.
`This problem is avoided by using an interpolation filter, as
`in Fig. 7(b), which increases the sampling rate digitally. After
`this, D/A conversion is performed followed by analog fil(cid:173)
`tering. The interpolation filter H(z) is once again a linear(cid:173)
`phase FIR low-pass filter and introduces no phase distor(cid:173)
`tion.
`The obvious price paid in these systems is the increased
`internal rate of computation. However, by using the poly(cid:173)
`phase framework (section IV) the efficiency of these mul(cid:173)
`tirate systems can be dramatically improved.
`In digital audio, it is relatively economic (compared to the
`analog case) to produce high-quality copies of material from
`one medium to another [15]. Perhaps to discourage such
`practice, the sampling rates used for various media are often
`made different from each other. It is therefore necessary
`in studios to design efficient non integral sampling rate con(cid:173)
`verters (such as the one in Fig. 8(a)). See section IV-B for
`further details. Further applications of multi rate filter banks
`in digital audio can be found in section V-E.
`
`B. Subband Coding of Speech and Image Signals
`
`In practice, one often encounters signals with energy
`dominantly concentrated in a particular region of fre-
`
`60
`
`PROCEEDINGS OF THE IEEE, VOL. 78, NO. 1, JANUARY 1990
`
`Petitioner Apple Inc.
`Ex. 1010, p. 60
`
`

`
`quency. An extreme example was shown in Fig. 8(b), where
`all the energy is in 0 :S lwl < 27r/3. In this case it is possible
`to compress the signal simply by decimating it by a factor
`of 3/2 (using Fig. 8(a)) or less.
`It is more common, however, to encounter signals that
`are not bandlimited but still have dominant frequency
`bands. An example is shown in Fig. 12(a). The information
`
`~·;~F===
`
`0
`
`I
`
`(b)
`
`(c)
`
`Fig. 12. Splitting a signal into subband signals x0 (n) and
`x, (n). (a) Cas~ of dominant frequency bands. (b) Splitting the
`s1gnal by usmg an analysis bank with M = 2 (Fig. 10(a)). (c)
`Encoding the subband signal.
`
`in lwl > 1r/2 is not small enough to be discarded. And we
`cannot decimate x(n) without causing aliasing either. It does
`seem unfortunate that a small (but not negligible) fraction.
`of energy in the high-frequency region should prevent us
`from obtaining any kind of signal compression at all.
`Butthere is a way to get around this difficulty: we can split
`the signal into two frequency bands by using an analysis
`bank (Fig. 10(a) with M = 2), with responses as in Fig. 12(b).
`The subband signal x1(n) has less energy than x0(n), and so
`can be encoded with fewer bits than x0(n). As an example,
`let x(n) be a 10-kHz signal (10 000 samples/s) normally
`requiring 8 bits per sample so that the data rate is 80 kbits/
`s. Let us assume that the sub band signals x0(n) and x1(n) can
`be represented with 8 bits and 4 bits per sample, respec(cid:173)
`tively. Because these signals are also decimated by two, the
`data rate now works out to be 40 + 20 = 60 kbits/s, which
`is a compression by 4/3. This is the basic principle of sub(cid:173)
`band coding: split the signal into two or more subbands,
`decimate each subband signal, and allocate bits for samples
`in each subband depending on the energy content. This
`strategy is clearly a generalization of the simple decimation
`process (which works only for strictly bandlimited signals).
`In speech coding practice, further use of the perceptive
`properties in each subband is exploited before quantiza(cid:173)
`tion [18]-[21].
`The reconstruction of the full band signal is done using
`the interpolators and synthesis bank filters as in Fig. 13. The
`
`x(n)
`
`Fig. 13. Analysis/synthesis system for subband coding.
`(Also called two-band QMF bank; see text.)
`
`x(n)
`
`interpolators restore the original sampling rate, and the fil(cid:173)
`ters fk(z) eliminate the images. Further generalizations fol(cid:173)
`low immediately: the signal can be split into M subbands
`with each subband signal decimated by M and indepen(cid:173)
`dently quantized.
`Pioneering work on the application of this technique in
`speech coding has been done by Crochiere [18], [19] and
`by Galand and Estaban [21]. The coding in each subband is
`typically more sophisticated than just quantization. For
`example, techniques such as adaptive pulse code modu(cid:173)
`lation (APCM) and adaptive delta pulse code modulation
`(ADPCM) are commonly used [20]. The specific properties
`of speech signals and their relation to human perception
`are carefully exploited in the coding process; the appro(cid:173)
`priate number of subbands and the coding accuracy in each
`subband are judged based on the articulation index. See
`[18]-[20] for complete examples of speech coding, using this
`idea. The quality of subband coders is usually judged by
`what is called the mean opinion score (MOS). This score is
`obtained by performing listening tests with the help of a
`wide variety of unbiased I isteners, and asking them to assign
`a score for the quality of the reproduced signal x(n) (in com(cid:173)
`parison to x(n)). The maximum score is normalized to 5 by
`convention. Subband-coded speech with an average bit rate
`of 16 kbits/s can typically achieve aMOS of 3.1, whereas at
`32 kbits/s a score of 4.3 has been achieved in the past [20,
`chapter 11].
`In video signal processing, subband coding has been
`applied for image compression, and success has been
`reported by several authors [22]-[27]. The results in [22], in
`particular, use vector quantization [28] in each subband to
`obtain a coded image with only 0.48 bits per pixel. (The orig(cid:173)
`inal uncoded picture being an 8 bits per pixel image.)
`Several comments are now in order: first, in orderfor sub(cid:173)
`band coding to work, it is necessary to have some a priori
`knowledge about the energy distribution of X(eiw). In speech
`and image processing, for example, such knowledge is usu(cid:173)
`ally available because of the long history of experience with
`the coding of such signals. Second, the bandsplitting and
`decimation operation inevitably results in aliasing because
`the filters Hk(z) are not ideal. The filters fk(z) should be cho(cid:173)
`sen carefully in such a way that aliasing is actually canceled
`(see section VI, where we include a detailed review of all
`the distortions which arise in the analysis/synthesis sys(cid:173)
`tem).
`
`C. Analog Voice Privacy Systems
`
`These systems [29] are intended to communicate speech
`over standard analog telephone I inks, while at the same time
`ensuring voice privacy. The main idea is to split a signal x(n)
`into M subband signals xk(n) and then divide each subband
`signal into segments in the time domain. These segments
`of sub band signals are then permuted and recombined into
`a single encrypted signal y(n), which can then be trans(cid:173)
`mitted (after D/A conversion). For example, if there are five
`subbands and twenty-five time segments in each subband,
`then there are 125! possible permutations, and unless an
`eavesdropper has the key for decryption, he will be unable
`to perform a pleasant job of eavesdropping. The aims of the
`designer of such a privacy system are: the encrypted mes(cid:173)
`sage should be unintelligible, decryption without a key
`should be very difficult, and the decrypted signal should
`
`VAIDYANATHAN: MULTIRATE DIGITAL FILTERS
`
`61
`
`Petitioner Apple Inc.
`Ex. 1010, p. 61
`
`

`
`be of good quality retaining naturalness and voice char(cid:173)
`acteristics. These features have indeed been achieved by
`Cox eta/. [29].
`At the receiver end, y(n) is again split into subbands, and
`the time-segments of the subbands unshuffled to get xk(n),
`which can then be interpolated and recombined through
`the synthesis filters.
`
`IV. THE POLYPHASE DECOMPOSITION AND ITS APPLICATIONS
`
`The polyphase decomposition, which originated from the
`work by Bellanger eta/. [11], is very fundamental to many
`applications in multi rate DSP. These include efficient real(cid:173)
`time implementation of decimation and interpolation fil(cid:173)
`ters, fractional sampling-rate changing devices, uniform
`DFT filter banks, and perfect-reconstruction analysis/syn(cid:173)
`thesis systems. More recently, the polyphase idea has been
`applied for the derivati