Quadrature mirror filter banks and method

I claim:

1. A pseudo-quadrature-mirror filter bank for near-perfect-reconstruction pseudo-quadrature-mirror filtering of an input signal, comprising:

a plurality of analysis filters, each of said plurality of analysis filters including,

a first delay chain, operatively coupled to the input signal, forming a set of 2M parallel paths for buffering the input signal;

a first cascade of 2M polyphase components of an impulse transfer function H(z) of impulse response, h(n), operatively coupled to said first delay chain; and

means, operatively coupled to said first cascade of 2M polyphase components, for generating a 2M-point Discrete Fourier Transform (DFT) to implement a 2M-point Discrete Cosine Transform (DCT) of the input signal,

with each analysis filter having an impulse response, h.sub.k (n), of a k.sup.th analysis filter, where M is the number of subband signals, obtained by cosine-modulating an impulse response, h(n), of a prototype filter with linear phase, according to: ##EQU65## and N is the length of the impulse response, h(n), of the prototype filter;

a plurality of synthesis filters, each of said plurality of synthesis filters including,

a second delay chain, operatively coupled to the input signal, forming a set of 2M parallel paths for buffering the input signal;

a second cascade of 2M polyphase components of an impulse transfer function H(z) of impulse response, h(n), operatively coupled to said second delay chain; and

means, operatively coupled to said second cascade of 2M polyphase components, for generating a 2M-point Discrete Fourier Transform (DFT) to implement a 2-point Discrete Cosine Transform (DCT) of the input signal,

with each of said plurality of synthesis filters operatively coupled to a respective one of said plurality of analysis filters, each synthesis filter having an impulse response, f.sub.k (n), of a k.sup.th synthesis filter, obtained by cosine-modulating the impulse response, h(n), of the prototype filter according to: ##EQU66## and N is the length of the impulse response, h(n), of the prototype filter; and

wherein each impulse response, h(n), is found in accordance with: ##STR5## for even N, where n=2M(m-l)+2m.sub.1 -1 and x is the greatest integer less than x, for x equal to (m+1)/2, and in accordance with: ##STR6## for odd N, where n=2M(m-f)+2m.sub.1 -1 and x is the greatest integer less than x, for x equal to any of 1+m/2 and m/2, where J is an inverse identity matrix, matrix V is defined to be: ##EQU67## wherein each impulse response, h(n), is found to minimize the stopband error: ##EQU68## where P is a real, symmetric and positive definite matrix, with the elements, using a notation .sup.P k,l for denoting a (k,l).sup.th element of matrix P, ##EQU69## where N is even, and where P is a real, symmetric and positive definite matrix, with the elements ##EQU70## where N is odd, and where K is the number of stopbands of H(e.sup.j.omega.), .beta..sub.i are their relative weights and .omega..sub.i,1 and .omega..sub.i,2 are the bandedges of these stopbands, and ##EQU71## and wherein the filter H.sub.k (z) is optimized by finding a least squares optimization h.sub.opt such that: ##EQU72##

2. The pseudo-quadrature-mirror filter bank set forth in claim 1, wherein the impulse response, h(n), provides plurality of analysis filters and the plurality of synthesis filters with a stopband attenuation less than -100 dB and with a reconstruction error less than -100 dB.

3. The pseudo-quadrature-mirror filter bank set forth in claim 1, wherein the stopband error h.sup.t Ph is minimized by subroutine DNOONF of the IMSL Math Library.

4. A pseudo-quadrature-mirror-filter bank for near-perfect-reconstruction pseudo-quadrature-mirror filtering an input signal, constructed by a process comprising the steps of:

finding an impulse response, h(n), of a prototype filter in accordance with: ##EQU73## for even N, where n=2M(m-l)+2m.sub.1 -1 and x is the greatest integer less than x, for x equal to (m+1)/2, and in accordance with: ##EQU74## for odd N, where n=2M(m-l)+2m.sub.1 and x is the greatest integer less than x, for x equal to any of 1+m/2 and m/2, where J is an inverse identity matrix, matrix V is defined to be: ##EQU75## finding the impulse response, h(n), minimizing the stopband error: ##EQU76## wherein P is a real, symmetric, and positive definite matrix, with the elements, using a notation .sup.P k,l for denoting a (k,l).sup.th element of matrix P, ##EQU77## where N is even, and wherein P is a real, symmetric and positive definite matrix, with the elements ##EQU78## where N is odd, with K is the number of stopbands of H(e.sup.j.omega.), .beta..sub.i are their relative weights and .omega..sub.i,1 and .omega..sub.i,2 are the bandedges of these stopbands, and ##EQU79## optimizing, by least squares optimization, H.sub.k (z) such that: ##EQU80## generating a plurality of analysis filters from the impulse response, h(n), each analysis filters having an impulse response, h.sub.k (n), of a k.sup.th analysis filter generated by cosine-modulating the impulse response, h(n), with linear phase, according to: ##EQU81## and N is the length of the impulse response, h(n), of the prototype filter;

generating a plurality of synthesis filters, from the impulse response, h(n), each synthesis filter having an impulse response, f.sub.k (n), of a k.sup.th synthesis filter, of the prototype filter according to: ##EQU82## and N is the length of the impulse response, h(n), of the prototype filter; and

coupling the output of each k.sup.th analysis filter with each k.sup.th synthesis filter, respectively.

5. The pseudo-quadrature-mirror-filter bank constructed by the process set forth in claim 4, wherein the step of finding the impulse response, h(n), minimizing the stopband error: ##EQU83## includes the steps of: computing the stopband error h.sup.t Ph and the gradient of h.sup.t Ph; and

minimizing h.sup.t Ph.

6. The pseudo-quadrature-mirror-filter bank constructed by the process set forth in claim 4, wherein the step of optimizing by least squares optimization includes the steps of:

linearizing a set of quadratic constraints; and

minimizing a cost function .PHI..

7. The Pseudo-quadrature-mirror-filter bank constructed by the process set forth in claim 4, further comprising the steps of:

buffering, using a delay chain, the input signal to form a set of 2M parallel paths;

cascading the buffered input signal using a cascade of 2M polyphase components of H(z); and

implementing a 2M-point Discrete Cosine Transform (DCT) using a 2M-point Discrete Fourier Transform (DFT).

8. A method, using a pseudo-quadrature-mirror-filter bank, for near-perfect-reconstruction pseudo-quadrature-mirror filtering an input signal, comprising the steps of:

finding an impulse response, h(n), of a prototype filter in accordance with: ##STR7## for even N, where n=2M(m-l)+2m.sub.1 -1 and x is the greatest integer less than x, for x equal to (m+1)/2, and in accordance with: ##STR8## for odd N, where n=2M(m-l)+2m.sub.1 and x is the greatest integer less than x, for x equal to any of 1+m/2 and m/2, where J is an inverse identity matrix, matrix V is defined to be: and ##EQU84## finding the impulse response, h(n), minimizing the stopband error: ##EQU85## wherein P is a real, symmetric and positive definite matrix, with the elements, using a notation .sup.P k,l for denoting a (k,l).sup.th element of matrix P, ##EQU86## where N is even, and wherein P is a real, symmetric and positive definite matrix, with the elements ##EQU87## where N is odd, with K is the number of stopbands of H(e.sup.j.omega.), .beta..sub.i are their relative weights and .omega..sub.i,1 and .omega..sub.i,2 are the bandedges of these stopbands, and

optimizing, by least squares optimization, H.sub.k (z) such that: ##EQU88## generating a plurality of analysis filters from the impulse response, h(n), each analysis filters having an impulse response, h.sub.k (n), of a k.sup.th analysis filter generated by cosine-modulating the impulse response, h(n), with linear phase, according to: ##EQU89## and N is the length of the impulse response, h(n), of the prototype filter;

generating a plurality of synthesis filters, from the impulse response, h(n), each synthesis filter having an impulse response, f.sub.k (n), of a k.sup.th synthesis filter, of the prototype filter according to: ##EQU90## and N is the length of the impulse response, h(n), of the prototype filter; and

coupling the output of each k.sup.th analysis filter with each k.sup.th synthesis filter, respectively.

9. The method set forth in claim 8, wherein the step of finding the impulse response, h(n), minimizing the stopband error: ##EQU91## includes the steps of: computing the stopband error h.sup.t Ph and the gradient of h.sup.t Ph; and

minimizing h.sup.t Ph.

10. The method set forth in claim 8, wherein the step of optimizing by least squares optimization includes the steps of:

linearizing a set of quadratic constraints; and

minimizing a cost function .PHI..

11. The method set forth in claim 8, further comprising the steps of:

buffering, using a delay chain, the input signal to form a set of 2M parallel paths;

cascading the buffered input signal using a cascade of 2M polyphase components of H(z); and

implementing a 2M-point Discrete Cosine Transform (DCT) using a 2M-point Discrete Fourier Transform (DFT).

12. A method, using a pseudo-quadrature-mirror-filter bank, for near-perfect-reconstruction pseudo-quadrature-mirror filtering an input signal, comprising the steps of:

finding an impulse response, h(n), of a prototype filter minimizing the stopband error: ##EQU92## optimizing the impulse response, h(n), of the prototype filter; generating a plurality of analysis filters from the impulse response, h(n), each analysis filters having an impulse response, h.sub.k (n), of a k.sup.th analysis filter generated by cosine-modulating the impulse response, h(n), with linear phase, according to: ##EQU93## and N is the length of the impulse response, h(n), of the prototype filter;

generating a plurality of synthesis filters, from the impulse response, h(n), each synthesis filter having an impulse response, f.sub.k (n), of a k.sup.th synthesis filter, of the prototype filter according to: ##EQU94## and N is the length of the impulse response, h(n), of the prototype filter; and

coupling the output of each k.sup.th analysis filter with each k.sup.th synthesis filter, respectively.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

This invention relates to M-channel pseudo-quadrature-mirror-filter banks, and more particularly to analysis filters and synthesis filters with high stopband attenuation, and with small overall distortion and alias level.

DESCRIPTION OF THE RELEVANT ART

Digital filter banks are used in a number of communication applications such as subband coders for speech signals, frequency domain speech scramblers, and image coding, with such applications taught by D. Esteban and C. Galand, "Application of Quadrature Mirror Filters to Split-Band Voice Coding Schemes," PROC. IEEE INT. CONF. ASSP, Hartford, Conn., pp. 191-195, May 1977; R. E. Crochiere and L. R. Rabiner, MULTIRATE SIGNAL PROCESSING, Prentice-Hall, Englewood Cliffs, N.J., 1983; T. P. Barnwell, III, "Subband Coder Design Incorporating Recursire Quadrature Filters and Optimum ADPCM Coders", IEEE TRANS. ON ASSP, Vol. ASSP-30, pp. 751-765, Oct. 1982; R. V. Cox, D. E. Boch, K. B. Bauer, J. D. Johnston, and J. H. Snyder, "The Analog Voice Privacy System," PROC. IEEE INT. CONF. ASSP, pp. 341-344, April 1986; and J. W. Woods and S. P. O'Neil, "Subband Coding of Images," IEEE TRANS. ON ASSP, Vol. ASSP-34, pp. 1278-1288, Oct. 1986.

FIG. 1 illustrates a typical M-channel maximally-decimated parallel filter bank where H.sub.k (z) and F.sub.k (z), 0.ltoreq.k.ltoreq.M-1, are the transfer functions of the analysis filters 51 and synthesis filters 54, respectively. Only finite impulse response (FIR) filters are considered herein. The analysis filters 51, with transfer function H.sub.k (z), channelize an input signal, x(n), into M subband signals by decimating using decimators 52 the input signal by M. In speech compression and transmission applications, the M subband signals are encoded and then transmitted, as taught by D. Esteban et al., supra.; R. E. Crochiere et al., supra; and T. P. Barnwell, III, supra. At the receiving end, the M subband signals are decoded, interpolated by interpolators 53 and recombined using a set of synthesis filters 54, having transfer functions F.sub.k (z). The decimators 52, which decrease the sampling rate of a signal, and the interpolators 53, which increase the sampling rate of the signal, are denoted by the down-arrowed and up-arrowed boxes in FIG. 1, respectively, as in R. E. Crochiere et al., supra.

The theory for perfect reconstruction has recently been established. See M. J. Smith and T. P. Barnwell, III, "Exact Reconstruction Techniques for Tree-Structured Subband Coders," IEEE TRANS. ON ASSP, Vol. ASSP-34, pp. 431-441, June 1986; F. Mintzer, "Filters for Distortion-Free Two-Band Multirate Filter Banks", IEEE TRANS. ON ASSP, pp. 626-630, June 1985; P. P. Vaidyanathan, "Theory and Design of M-Channel Maximally Decimated Quadrature Mirror Filters With Arbitrary M, Having Perfect Reconstruction Property," IEEE TRANS. ON ASSP, Vol. ASSP-35, pp. 476-492, April 1987; M. Vetterli, "A Theory of Multirate Filter Banks," IEEE TRANS. ON ASSP, Vol. ASSP-35, pp. 356-372, March 1987; and T. Q. Nguyen and P. P. Vaidyanathan, "Structures for M-Channel Perfect-Reconstruction FIR QMF Banks Which Yield Linear-Phase Analysis Filters", IEEE TRANS. ON ASSP, pp. 433-446, March 1990.

In all applications where perfect-reconstruction is the crucial requirement for the filter bank, the filters must satisfy the following condition, according to P. P. Vaidyanathan, "Theory and Design of M-Channel Maximally Decimated Quadrature Mirror Filters With Arbitrary M, Having Perfect Reconstruction Property," IEEE TRANS. ON ASSP, Vol. ASSP-35, pp. 476-492, April 1987: ##EQU1## where Q=e.sup.j2.pi./M. Starting from equation (1), one can derive many procedures to find H.sub.k (z) and F.sub.k (z). One such procedure may involves lossless polyphase transfer matrices, as in P. P. Vaidyanathan, "Theory and Design of M-Channel Maximally Decimated Quadrature Mirror Filters With Arbitrary M, Having Perfect Reconstruction Property," IEEE TRANS. ON ASSP, Vol. ASSP-35, pp. 476-492, April 1987; and M. G. Bellanger, G. Bonnerot and M. Coudreuse, "Digital Filtering by Polyphase Network: Application to Sample-Rate Alteration and Filter Banks," IEEE TRANS. ON ASSP, vol. ASSP-24, pp. 109-114, Apr. 1976.

According to P. P. Vaidyanathan, "Theory and Design of M-Channel Maximally Decimated Quadrature Mirror Filters With Arbitrary M, Having Perfect Reconstruction Property," IEEE TRANS. ON ASSP, Vol. ASSP-35, pp. 476-492, April 1987; and Z. Doganata, P. P. Vaidyanathan and T. Q. Nguyen, "General Synthesis Procedures for FIR Lossless Transfer Matrices for Perfect Reconstruction Multirate Filter Bank Application," IEEE TRANS. ON ASSP, pp. 1561-74, Oct. 1988, the lossless transfer matrices are cascades of several lossless lattice building blocks, where one optimizes the lattice coefficients to minimize the cost function: ##EQU2## where the .phi..sub.H.sbsb.k are the stopband errors of .vertline.H.sub.k (.rho..sup.j.omega.).vertline., Once the , H.sub.k (z) are found, F.sub.k (z) can be obtained from F.sub.k (z)=H.sub.k (z.sup.-1).

The drawback of the lattice approach is that the cost function .PHI. in equation (2) is a highly nonlinear function with respect to the lattice coefficients, according to Z. Doganata et al., supra. Consequently, perfect reconstruction filter banks having analysis filters with high stopband attenuation are difficult to obtain. Therefore, instead of optimizing in the lattice coefficient space, it is preferable to use the filter coefficients directly, with the cost function .PHI. of equation (2) and the perfect reconstruction conditions in equation (1) expressed as quadratic functions of the filter coefficients, in order to obtain perfect reconstruction filter banks with high stopband attenuation.

The perfect-reconstruction cosine-modulated filter bank is considered an optimum filter bank with respect to implementation cost and ease of design, as in T. A. Ramstad and, J. P. Tanem, "Cosine-Modulated Analysis-Synthesis Filter Bank With Critical Sampling and Perfect Reconstruction", PROC. IEEE INT. CONF. ASSP, Toronto, Canada, pp. 1789-1792, May 1991; R. D. Koilpillai and P. P. Vaidyanathan, "New Results of Cosine-Modulated FIR Filter Banks Satisfying Perfect Reconstruction", PROC. IEEE INT. CONF. ASSP, Toronto, Canada, pp. 1793-1796, May 1991; R. D. Koilpillai and P. P. Vaidyanathan, "A Spectral Factorization Approach to Pseudo-QMF Design", IEEE INT. SYMP. CAS, Singapore, May 1991; and R. D. Koilpillai and P. P. Vaidyanathan, "New Results on Cosine-Modulated FIR Filter Banks Satisfying Perfect Reconstruction", Technical Report, California Institute of Technology, Nov. 1990. The impulse responses, h.sub.k (n) and f.sub.k (n), Of the analysis and synthesis filters are, respectively, cosine-modulated versions of the impulse response of the prototype filter h(n), as in R. D. Koilpillai and P. P. Vaidyanathan, "New Results of Cosine-Modulated FIR Filter Banks Satisfying Perfect Reconstruction", PROC. IEEE INT. CONF. ASSP, Toronto, Canada, pp. 1793-1796, May 1991. More particularly, the impulse responses of the analysis and synthesis filters are ##EQU3## where N is the length of h(n).

R. D. Koilpillai and P. P. Vaidyanathan, "New Results of Cosine-Modulated FIR Filter Banks Satisfying Perfect Reconstruction" PROC IEEE INT CONF ASSP, Toronto, Canada, pp. 1793-1796, May 1991, shows that the 2M polyphase components of the prototype filter, with transfer function H(z), can be grouped into M power-complementary pairs where each pair is implemented as a two-channel lossless lattice filter bank. See also P. P. Vaidyanathan and P. Q. Hoang, "Lattice Structures for Optimal Design and Robust Implementation of Two-Channel Perfect-Reconstruction QMF banks," IEEE TRANS. ON ASSP, pp. 81-94, Jan. 1988; and R. D. Koilpillai and P. P. Vaidyanathan, "New Results on Cosine-Modulated FIR Filter Banks Satisfying Perfect Reconstruction", Technical Report, California Institute of Technology, Nov. 1990.

The lattice coefficients are optimized to minimize the stopband attenuation of the prototype filter. As demonstrated in R. D. Koilpillai and P. P. Vaidyanathan, "New Results of Cosine-Modulated FIR Filter Banks Satisfying Perfect Reconstruction", PROC. IEEE INT. CONF. ASSP, Toronto, Canada, pp. 1793-1796, May 1991, a 17-channel perfect-reconstruction cosine-modulated filter bank can be designed with -40 dB stopband attenuation. This optimization procedure, however, is very sensitive to changes in the lattice coefficients because of the highly nonlinear relation between the prototype filter, h(n), and the lattice coefficients. As a result, a perfect-reconstruction cosine-modulated filter bank with high stopband attenuation, on the order of -100 dB, is very difficult to design. For more than 2 channels, no example of a perfect-reconstruction cosine-modulated filter bank, where its prototype filter has -100 dB attenuation, has yet been found. Consequently, in order to construct a filter bank with high attenuation, it is judicious to relax the perfect-reconstruction condition. Thus, a filter bank can be constructed, in a practical sense, where the reconstruction error is small, on the order of -100 dB.

The pseudo-QMF banks belong to the family of modulated filter banks. Pseudo-QMF theory is well known and is widely used. See J. H. Rothweiler, "Polyphase Quadrature Filters--A New Subband Coding Technique," IEEE INT. CONF. ASSP, Boston, pp. 1280-1283, 1983; J. Mason and Z. Picel, "Flexible Design of Computationally Efficient Nearly Perfect QMF Filter Banks," IEEE INT. CONF. ASSP, Tampa, Florida, pp. 14.7.1-14.7.4, March 1985; H. J. Nussbaumer, "Pseudo QMF Filter Bank," IBM Technical Disclosure Bulletin, vol. 24, No. 6, pp. 3081-3087, Nov. 1981; and R. V. Cox, "The Design of Uniformly and Non-Uniformly Spaced pseudoquadrature Mirror Filters," IEEE TRANS. ON ASSP, vol. ASSP-34, No. 5, pp. 1090-1096, Oct. 1986. As with the perfect-reconstruction cosine-modulated filter bank of equation (3) above, the analysis and synthesis filters are cosine-modulated versions of a prototype filter. Since the desired analysis and synthesis filters have narrow transition bands and high stopband attenuation, the overlap between non-adjacent filters is negligible. Moreover, J. H. Rothweiler, "Polyphase Quadrature Filters--a New Subband Coding Technique," IEEE INT. CONF. ASSP, Boston, pp. 1280-1283, 1983, shows that the significant aliasing terms from the overlap of the adjacent filters are canceled by the characteristics of the filters. The transfer function, H(z), of the prototype filter is found by minimizing an objective function consisting of the stopband attenuation and the overall distortion. As shown in J. H. Rothweiler, supra; J. Mason et al., supra.; H. J. Nussbaumer, supra.; and R. V. Cox, supra., although it is possible to obtain a pseudo-QMF bank with high attenuation, the overall distortion level might be high, on the order of -40 dB. Accordingly, the overall distortion of the pseudo-QMF bank is not sufficiently small enough for application where a -100 dB error level is required.

R. D. Koilpillai and P. P. Vaidyanathan, "A Spectral Factorization Approach to Pseudo-QMF Design", IEEE INT. SYMP. CAS, Singapore, May 1991, presents an approach to pseudo-QMF design which does not involve any optimization. The prototype filter of a M-channel filter bank is obtained as a spectral factor of a 2M.sup.th band filter, as in F. Mintzer, "On Half-Band, Third-Band and Nth-Band FIR Filters and Their Design," IEEE TRANS. ON ASSP, vol. ASSP-30, pp. 734-738, Oct. 1982; P. P. Vaidyanathan and T. Q. Nguyen, "A `Trick` for the Design of FIR Halfband Filters," IEEE TRANS. CAS, vol. CAS-34, pp. 297-300, Mar. 1987. Since the procedure does not guarantee that transfer function, H(z), is a linear-phase filter, the overall transfer function, To(z), of the analysis filter/synthesis filter system is an approximately flat magnitude response in the frequency region .ltoreq..omega..ltoreq.(.pi.- ). Here, e depends on the transition bandwidth of the prototype filter and 0.ltoreq. .ltoreq..pi./2M. Furthermore, since the prototype filter is a spectral factor of a 2M.sup.th band filter, constructing a filter bank with high attenuation is difficult because of sensitivity in the spectral factor algorithm. Moreover, the overall distortion can be larger near .omega.=0 and .omega.=.pi..

Accordingly, in the prior art, constructing a filter bank with high stopband attenuation of approximately -100 dB, a small overall distortion of approximately -100 dB, and small aliasing of approximately -100 dB is a formidable task. As discussed above, the perfect-reconstruction cosine-modulated filter bank is too restrictive and the pseudo-QMF bank is too loose in their constraints. Consequently, the above filter banks, i.e., the perfect-reconstruction cosine-modulated filter bank of R. D. Koilpillai and P. P. Vaidyanathan, "New Results of Cosine-Modulated FIR Filter Banks Satisfying Perfect Reconstruction", PROC. IEEE INT. CONF. ASSP, Toronto, Canada, pp. 1793-1796, May 1991; and of R. D. Koilpillai and P. P. Vaidyanathan, "New Results on Cosine-Modulated FIR Filter Banks Satisfying Perfect Reconstruction", Technical Report, California Institute of Technology, Nov. 1990; and the spectral-factorized pseudo-QMF filter bank of J. H. Rothweiler, supra.; and of R. D. Koilpillai and P. P. Vaidyanathan, "A Spectral Factorization Approach to Pseudo-QMF Design", IEEE INT. SYMP. CAS, Singapore, May 1991, do not yield satisfactory results.

OBJECTS OF THE INVENTION

A general object of the invention is a pseudo-quadrature-mirror-filter bank and method wherein an overall distortion, i.e. an overall transfer function of analysis filters and synthesis filters, is a delay such that there is no magnitude or phase distortion.

An object of the invention is a pseudo-quadrature-mirror-filter bank and method having analysis filters and synthesis filters each having an impulse response different from previous implementations, with the attained impulse response having any errors disappear from the output of the synthesis filters.

A further object of the invention is a pseudo-quadrature-mirror-filter bank and method for a 32-channel system having analysis filters and synthesis filters with high stopband attenuation, e.g. -100 dB, and having a small reconstruction error, e.g. -100 dB.

Another object of the invention is a pseudo-quadrature-mirror-filter bank and method having a small overall distortion, e.g. -100 dB, and having a small alias level, -100 dB.

An additional object of the invention is a near-perfect-reconstruction pseudo-quadrature-mirror-filter bank which can be implemented using polyphase filters and using a 2M point Discrete Cosine Transform (DCT), such as a 2M-point Fast Fourier Transform (FFT) .

A further object of the invention is a quadrature-mirror-filter bank and method which has an efficient and easy implementation.

An additional object of the invention is a quadratic-mirror-filter bank formulation and method by least-squares quadratic-constrained optimization which has an efficient and easy implementation.

SUMMARY OF THE INVENTION

According to the present invention, as embodied and broadly described herein, a pseudo-quadrature-mirror filter (QMF) bank is provided comprising a plurality of analysis filters and a plurality of synthesis filters. Each of the plurality of analysis filters and synthesis filters uses a prototype filter. The prototype filter has a linear-phase spectral-factor H(z) of a 2M.sup.th band filter. The overall transfer function of the analysis filter/synthesis filter system is a delay, i.e. there is no magnitude or phase distortion. Also, aliasing cancellation causes all the significant aliasing terms to cancel. Consequently, the aliasing level at the output of the pseudo-QMF banks is comparable to the stopband attenuation of the prototype filter, with the error at the output of the analysis filter/synthesis filter system approximately equal to the aliasing error at the level of the stopband attenuation.

Each of the analysis filters has an impulse response, h.sub.k (n). The analysis filters are generated by cosine-modulating an impulse response, h(n), of a prototype filter with linear phase, according to: ##EQU4## and N is the length of the impulse response, h(n), of the prototype filter.

The plurality of synthesis filters are operatively coupled to the plurality of analysis filters. Each synthesis filter has an impulse response, f.sub.k (n), and is formed by cosine-modulating the impulse response, h(n), of the prototype filter according to: ##EQU5## and N is the length of the impulse response, h(n), of the prototype filter.

The impulse response, h(n), of the protype filter is different from previous implementations. The plurality of analysis filters and the plurality of synthesis filters have a stopband attenuation of approximately -100 dB and with a reconstruction error of approximately -100 dB.

Additional objects and advantages of the invention are set forth in part in the description which follows, and in part are obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention also may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate preferred embodiments of the invention, and together with the description serve to explain the principles of the invention.

FIG. 1 illustrates an M-channel maximally-decimated parallel filter bank;

FIG. 2 shows typical ideal responses of analysis filters, H.sub.k (z);

FIG. 3 shows an ideal response of a prototype filter, H(z);

FIG. 4 shows a magnitude response of an optimized prototype filter for a first example;

FIG. 5 shows magnitude response plots of analysis filters, H.sub.k (z), for the first example;

FIG. 6 shows a magnitude response plot for an overall distortion, To(z), for the first example;

FIG. 7 shows magnitude response plots for alias transfer functions, T.sub.k (z), for the first example;

FIG. 8 shows a spectrum of an input signal for the first example;

FIG. 9 shows a spectrum of reconstruction error for the first example;

FIG. 10 shows a magnitude response of an optimized prototype filter, H(z), for a second example;

FIG. 11 shows magnitude response plots for the analysis filters, H.sub.k (z), for the second example;

FIG. 12 shows the magnitude response plot for the overall distortion, T.sub.0 (z), for the second example;

FIG. 13 shows the magnitude response plots for the alias transfer functions, T.sub.k (z), for the second example;

FIG. 14 shows a spectrum of an input signal for the second example;

FIG. 15 shows the reconstruction error of the second example;

FIG. 16 illustrates a magnitude response plot for the prototype filter H(z) using a quadratic-constrained least-squares formulation;

FIG. 17 shows a magnitude response plot of analysis filters H.sub.k (z);

FIG. 18 shows a magnitude response plot of prototype filters H(z) (approximate perfect reconstruction solution) and H.sub.PR (z) (perfect reconstruction solution);

FIG. 19 illustrates a polyphase implementation of the decimated analysis bank of pseudo-QMF bank;

FIG. 20 illustrates an equivalent block diagram of the implementation of FIG. 19;

FIG. 21 illustrates an implementation of a 2M point Discrete Cosine Transform (DCT) using a 2M-point Discrete Fourier Transform (DFT);

FIG. 22 illustrates an implementation of a 2M point DCT using an M-point DCT and an M-point Discrete Sine Transform (DST);

FIGS. 23A-23B illustrate implementations of input signals X.sub.0 (k) and X.sub.1 (k) , respectively, using M-point FFTs for even m; and

FIGS. 24A-24B illustrate implementations of input signals X.sub.0 (k) and X.sub.1 (k) , respectively, using M-point FFTs for odd m.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Reference will now be made in detail to the present preferred embodiments of the invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals indicate like elements throughout the several views.

In the exemplary arrangement shown in FIG. 1, a pseudo-quadrate-mirror filter bank is provided comprising a plurality of analysis filters and a plurality of synthesis filters. Each of the analysis filters has an impulse response, h.sub.k (n). The analysis filters are generated by cosine-modulating an impulse response, h(n), of a prototype filter with linear phase, according to: ##EQU6## and N is the length of the impulse response, h(n), of the prototype filter.

The plurality of synthesis filters are operatively coupled to the plurality of analysis filters. Each synthesis filter has an impulse response, f.sub.k (n), and is formed by cosine-modulating the impulse response, h(n), of the prototype filter according to: ##EQU7## and N is the length of the impulse response, h(n), of the prototype filter.

The impulse response, h(n), of the prototype filter is different from previous implementations. The plurality of analysis filters and the plurality of synthesis filters have a stopband attenuation of approximately -100 dB and with a reconstruction error of approximately -100 dB, as well as have errors disappear at the output of the synthesis filters.

In this discussion, the variable .omega. denotes the frequency variable whereas the term "normalized frequency" denotes f=.omega./2.pi.. Boldfaced quantities denote matrices and column vectors. Upper case letters denote matrices, as in A, and lower case letters denote column vectors, as in h(z), etc. A superscript t stands for matrix transposition, and

H(z).DELTA.H(z.sup.-1).

Moreover [A].sub.k,l and [h].sub.k represent the (k,l).sup.th and k.sup.th element of the matrix A and vector h, respectively. The K.times.K identity matrix is denoted as I.sub.k ; the k.times.k `reverse operator` matrix J.sub.k is defined to be: ##EQU8## and matrix V is defined to be: ##EQU9##

The subscripts of I.sub.k and J.sub.k are often omitted if they are clear from the context. W.sub.M is defined as W.sub.M =e.sup.-j2.pi./M, and, unless mentioned otherwise, W is the same as W.sub.2M.

Pseudo-QMF Banks

Consider the filter bank in FIG. 1 where the ideal frequency responses of the filters H.sub.k (z) are shown in FIG. 2. The reconstructed signal X(z) is: where ##EQU10##

From equation (4), T.sub.0 (z) is the overall distortion transfer function and T.sub.l (z), l-0, are the (M-1) aliasing transfer functions corresponding to:

X(zW.sub.M.sup.l).

Thus, for a perfect-reconstruction system, ##EQU11## where n.sub.O is a positive integer. From a practical perspective, the above conditions in equations (5) are too restrictive; it is sufficient to construct the filter bank such that T.sub.0 (z) is linear-phase and ##EQU12## where .delta.1 and .delta.2 are small numbers (.perspectiveto.-100 dB). In the examples presented later, .delta..sub.1 .ltoreq.1.times.10.sup.-12 and .delta..sub.2 is comparable to the stopband attenuation.

The main properties of pseudo-QMF banks are summarized below:

1. The linear phase prototype filter approximates the frequency response as shown in FIG. 3. A weighted objective function involving the stopband attenuation and the overall magnitude distortion, where the weighted objective function is minimized.

2. The analysis and synthesis filters H.sub.k (z) and F.sub.k (z) are obtained by the modulation of H(z) as follows: ##EQU13## and N is the length of H(z). The impulse response coefficients h.sub.k (n) and f.sub.k (n) are, respectively, given by: ##EQU14##

From equations (6) and (7), the analysis and synthesis filters are related as: ##EQU15##

3. .theta..sub.k are chosen such that ##EQU16## so that all the significant aliasing terms are canceled.

Furthermore, in order to ensure relatively flat overall magnitude distortion, ##EQU17## where l and m are arbitrary integers. Although other choices are possible, the following choice is used in this application: ##EQU18## which satisfies both (8) and (9).

4. The overall transfer function T.sub.0 (z) is ##EQU19##

Note that the above T.sub.O (z) has linear-phase independent of H.sub.k (z ); therefore, the reconstructed signal has no phase distortion.

The main properties of the spectral factorization approach to pseudo-QMF design are summarized as follows:

1. The prototype filter H(z) does not have linear-phase symmetry since it is obtained by spectral factorization. The length N is assumed to be a multiple of M, i.e. N=mM. No optimization procedure is needed. First a 2M.sup.th band filter G'(z) is found, by letting .zeta..sub.2 be the stopband attenuation of G'(z). Form G(z) by G(z) =G'(z)+.zeta..sub.2, then find a spectral factor of G(z) and set the spectral factor to H(z).

2. Let b.sub.k =e.sup.j.phi.k and ##EQU20## then the analysis and synthesis filters H.sub.k (z) and F.sub.k (z) are obtained as follows: ##EQU21##

Note that the above choice for F.sub.k (z) ensures the linearity in the phase response of T.sub.0 (z). The impulse response coefficients h.sub.k (n) and f.sub.k (n) are given by: ##EQU22##

3. In order to ensure cancellation of the significant aliasing terms, .phi..sub.k should satisfy: ##EQU23## where i is an integer.

One of the choices that satisfies equation (11) is ##EQU24##

4. The overall transfer function T.sub.0 (z) is ##EQU25## where P.sub.1 (z) and P.sub.2 (z) cannot be eliminated for any choice of .phi..sub.k. The magnitude response of P.sub.1 (z) is significant only in the region .vertline..omega..vertline.< , whereas the magnitude response of P.sub.2 (z) is significant only in the region (.pi.- )<.vertline..omega..vertline.<(.pi.+ ), where depends on the transition bandwidth of H(z) and ##EQU26##

Consequently, .vertline.T.sub.0 (e.sup.j.omega.).vertline..perspectiveto.constant, with .ltoreq..omega..ltoreq.(.pi.- ), but .vertline.T.sub.0 (e.sup.j.omega.).vertline. can have bumps or dips around .omega.=0 and .omega.=.pi., depending on the values of P.sub.1 (z) and P.sub.2 (z).

The pseudo-QMF bank of the present invention is a hybrid of the above pseudo-QMF constructs. First, the prototype filter H(z) is chosen to be a linear-phase filter. Moreover, H(z) is found such that it is a spectral factor of a 2M.sup.th band filter. The analysis and synthesis filters, h.sub.k (n) and f.sub.k (n), respectively, are cosine-modulated versions of the prototype filter h(n) as in equation (7) with .theta..sub.k chosen as in equation (10).

This choice of modulation yields an efficient implementation for the whole analysis filter/synthesis filter system. Together with the above 2M.sup.th band constraint, it will be shown that T.sub.0 (z).perspectiveto.a delay. Even though H(z) is a spectral factor of a 2M.sup.th band filter, no spectral factorization is needed in the approach of the present invention. In other words, the 2M.sup.th band constraints are imposed approximately.

Properties of the Pseudo-QMF Bank

Let ##EQU27## be the real-coefficient, linear-phase, even length prototype filter of length N. Assume that H(z) is a spectral factor of a 2M.sup.th band filter G(z), i.e.,

G(z)=z.sup.-(N- 1).sub.H (z)H(z)=H.sup.2 (z)

in lieu of the linear phase property of H(z). The analysis and synthesis filters, h.sub.k (n) and f.sub.k (n), respectively, are cosine-modulated versions of h(n), i.e., ##EQU28##

Consequently, H.sub.k (z) and F.sub.k (z) are related as ##EQU29##

Note that the above filter choices are the same as those of the pseudo-QMF bank of J. H. Rothweiler, supra., with the exception that H(z) of the present invention is a spectral factor of a 2M.sup.th band filter. In the following, it will be shown that the overall transfer function ##EQU30## is a delay.

The Overall Transfer Function T.sub.0 (z)

When the .theta..sub.k are chosen as in equation (10), the analysis filter/synthesis filter system is `approximately` alias-free and the overall transfer function T.sub.0 (z) can be expressed as ##EQU31##

Setting R=W.sup.(k+1/2), and substituting (12) into (13) , one obtains ##EQU32## where the linear-phase property of H(z) is used in the last summation of the above equation. After some simplification, one obtains ##EQU33## and since,

a.sub.k.sup.2 =W.sup.M(k+1/2)

and

c.sub.k.sup.2 =W.sup.(N-1)(k+1/2),

after further simplification, the expression in the last summation of equation (14) is 0 for all k, i.e.,

[a.sub.k.sup.2 c.sub.k.sup.2 +(a.sub.k.sup.2 c.sub.k.sup.2)*W.sup.(N-1)(2k+1) ]=0 k. (15)

Substituting (15) into (14) yields ##EQU34##

Since G(z)=z.sup.-(N-1) H(z)H(z.sup.-1) is a 2M.sup.th band filter, i.e., ##EQU35## the final result is ##EQU36##

In summary, as long as the prototype filter H(z) is a linear-phase spectral factor of a 2M.sup.th band filter and the H.sub.k (z) and F.sub.k (z) are obtained as in (12), the overall distortion transfer function T.sub.0 (z) is a delay. A linear-phase filter H(z) is found where G(z)=H.sup.2 (z) is a 2M.sup.th band filter. Furthermore, the method produces a prototype filter H(z) with high stopband attenuation. The following sections focus on the present invention for the cases of even N and odd N, respectively.

The Implementation for Even N

In this section, the implementation of the present invention is provided for the even N case, i.e., N=2 (mM+m.sub.1) where 0.ltoreq.m.sub.1 .ltoreq.M-1, with the odd N case considered in the next section. Defining h to be the vector consisting of the first mM coefficients of h (n), i.e.,

h=[h(0) h(1) . . . h(mM+m.sub.1 -1)].sup.t

and vector e(z) to be

e(z)=[1z.sup.-1. . . z.sup.-(mM+m.sbsp.1.sup.-1) ].sup.t,

then the prototype filter H(z) can be represented as ##EQU37## where the dimensions of both matrices I and J are (mM+m.sub.1).times.(mM+m.sub.1) .

Using the above notation, the 2M.sup.th band filter G(z) is: ##EQU38##

Note that the matrices S.sub.n, in (19) are constant matrices with elements 0 and 1. It can be verified that ##EQU39##

Substituting (19) into (18) the following expression for G (z) results: ##EQU40##

By grouping like powers of z.sup.-1, equation (21) becomes: ##EQU41## which simplifies to: ##EQU42## where D.sub.n depends on S.sub.n and J as follows: ##STR1##

The objective is to find h such that G(z) is a 2M.sup.th band filter, i.e. ##STR2##

Equating the terms with the same power of z.sup.-1 in (21) and using (23) and (24), the following m constraints on h are obtained: ##STR3## where n=2M(m-l)+2m.sub.1 -1, and x is the greatest integer less than x. The notation x is well known in the art for denoting the largest integer that is less than x; for example, 3= 3.5 .

In summary, for even N, given m, m.sub.1 and M, one can calculate S.sub.n as in equation (20) above. The 2M.sup.th band constraint on G(z) becomes the constraints on h as shown in equation (25) above for even N. Suppose that one is able to obtain h such that h satisfies the constraints in equation (25) for even N. Then the resulting prototype filter H(z) found using equation (16) above is a spectral factor of the 2M.sup.th band filter G(z), and further, the linear-phase property of H(z) is structurally imposed on the problem, so the above method finds a spectral factor of a 2M.sup.th band filter without taking the spectral factor.

Besides the above m constraints for even N, h should also yield a prototype filter with good stopband attenuation, i.e., h should minimize the stopband error: ##EQU43## and also satisfy equation (18) above. The eigenfilter method as shown in P. P. Vaidyanathan and T. Q. Nguyen, "Eigenfilters: A New Approach to Least Squares FIR Filter Design and Applications Including Nyquist Filters," IEEE TRANS. CAS, vol. 34, pp. 11-23, Jan. 1987; and in T. Q. Nguyen, "Eigenfilter for the Design of Linear-Phase Filters with Arbitrary Magnitude Response", IEEE CONF. ASSP, Toronto, Canada, pp. 1981-1984, May 1991; may be used to represent equation (26) as a quadratic form, as follows: the stopband error of H(z) is defined to be ##EQU44## where K is the number of stopbands, .beta..sub.i are their relative weighting, and .omega..sub.i,1 and .omega..sub.i,2 are the bandedges of these stopbands. For even N, .rho..sub.s may be expressed in a quadratic form, since, by substituting equation (17) and simplifying, one obtains the quadratic form

.rho..sub.s =h.sup.t ph

where ##EQU45## where P is a real, symmetric and positive definite matrix, with the elements ##EQU46## The notation P.sub.k,l denotes the (k,l) element of the matrix P.

Thus, given N even and .omega..sub.s, one can compute P from equation (27) above, and equation (25) becomes: ##EQU47##

Therefore, the present invention requires finding h such that h.sup.t Ph is minimized and satisfies (25), which may be accomplished very accurately by the nonlinearly constrained minimization algorithm of K. Schittkowski, "On the Convergence of a Sequential Quadratic Programing Method with an Augmented Lagrangian Line Search Function," Mathematik Operationsforschung und Statistik, Serie Optimization, 14, pp. 197-216, 1983; and also K. Schittkowski, "NLPQL: A FORTRAN Subroutine Solving Constrained Nonlinear Programming Problems, (edited by Clyde L. Monma), Annals of Operations Rese