SYSTEM AND METHOD FOR OPTIMIZING THE OPERATION OF AN OVERSAMPLED DISCRETE FOURIER TRANSFORM FILTER BANK

The invention is directed, in general, to digital filters and, more particularly, to a system and method for optimizing the operation of an oversampled discrete Fourier transform (DFT) filter bank. BACKGROUND

Modulated filter banks have been a fundamental tool in many signal processing applications (e.g., data compression and subband adaptive filtering), mainly because they can be efficiently implemented as a polyphase digital finite impulse response (FIR) filter using the well-known discrete cosine transform (DCT) or discrete Fourier transform (DFT) for signal transformation. Modulated filter banks have been adopted in modern multimedia standards, including the Moving Picture Experts Group (MPEG) standard (see, e.g., http://www.mpeg.org), which is one of the most successful signal processing schemes in use today.

Critically sampled modulated filter banks have in general proven to be well-suited for signal compression applications in which processing of subband samples involves only quantizing coefficients, since that minimal amount of processing does not significantly increase aliasing between adjacent bands. However, for applications that require extensive subband sample processing, e.g., subband adaptive filtering (see Chapter 7 of Haykin, "Adaptive Filter Theory," 4th edition, Prentice Hall, 2002), and subband dynamic range compression (see, Brenna, et al., "A Flexible Interbank Structure for Extensive Signal Manipulations in Digital Hearing Aids," IEEE International Symposium on Circuits and Systems (ISCAS), vol. 6, pp. 569-572, 1998), oversampling is necessary to mitigate aliasing.

Modulated filter banks commonly operate with two windows: an analysis window and a synthesis window. The relative placement and shape of these windows determine the operation of the modulated filter bank. Portnoff, "Time-Frequency Representation of Digital Signal and Systems Based on Short-Time Fourier Analysis," IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. ASSP-28, No. 1, pp. 55-69, February 1980 (incorporated herein by reference), addressed the uniform DFT filter bank and described what is known in the art as "perfect reconstruction conditions" for it. (Those skilled in the art

understand that "perfect" is a term of art, and does not mean absolute perfection in the colloquial sense.) Crochiere, "A Weighted Overlap- Add Method of Short-Time Fourier Transform," IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. ASSP-28, No. 1, pp. 99-102, February 1980, set forth a relatively efficient implementation of a DFT filter bank using a synthesis window overlap-add technique. Subsequent works (e.g., Shapiro, et al., "Design of Filters for the Discrete Short-Time Fourier Transform Synthesis," IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 1985; Shapiro, et al., "An Algebraic Approach to Discrete Short-Time Fourier Transform Analysis and Synthesis," ICASSP, pp. 804-807, 1984; and Bolsckei, et al., "Oversampled FIR and HR Filter Banks and Weyl-Heisenberg Frames," ICASSP, Vol. 3, pp. 1391-1394, 1996) address the design of the synthesis window. Although the problem of designing the synthesis window is relatively old, the techniques disclosed in these works were usually the "minimum-norm" solution. For example, Shapiro, et al., "Design of Filters...," and Shapiro, et al., "An Algebraic Approach...," both supra, proposed a minimum-norm solution for different orders of the analysis window, when the subband samples are processed, after formulating the problem as a least-square problem. In Bolsckei, et al., supra, a frame- theoretic technique was described for the design of the synthesis window using para-unitary prototypes.

Accordingly, what is needed in the art is a better technique for optimizing the operation of an oversampled DFT filter bank. What is also needed in the art is a DFT filter bank that has been optimized by the technique thereby to yield improved operation. SUMMARY

To address the above-discussed deficiencies of the prior art, the invention provides, in one aspect, a system for optimizing an operation of an oversampled filter bank. In one embodiment, the system includes: (1) a null space generator configured to produce a basis of a null space of a perfect reconstruction condition matrix based on a first window of the oversampled filter bank and (2) an optimizer associated with the null space generator and configured to employ the basis and an optimization criterion to construct a second window of the oversampled filter bank.

In another aspect, the invention provides a method of optimizing an operation of an oversampled filter bank. In one embodiment, the method includes: (1) producing a basis of a null space of a perfect reconstruction condition matrix based on a first window of the oversampled filter bank and (2) employing the basis and an optimization criterion to construct a second window of the oversampled filter bank.

In yet another aspect, the invention provides an oversampled DFT filter bank, hi one embodiment, the DFT filter bank includes a plurality of lowpass filters configured to process an input signal to yield an output signal based in part on coefficients that describe a second window designed by: (1) producing a basis of a null space of a perfect reconstruction condition matrix based on a first window of the oversampled filter bank and (2) employing the basis and an optimization criterion to construct the second window.

The foregoing has outlined preferred and alternative features of the invention so that those skilled in the pertinent art may better understand the detailed description of the invention that follows. Additional features of the invention will be described hereinafter that form the subject of the claims of the invention. Those skilled in the pertinent art should appreciate that they can readily use the disclosed conception and specific embodiment as a basis for designing or modifying other structures for carrying out the same purposes of the invention. Those skilled in the pertinent art should also realize that such equivalent constructions do not depart from the spirit and scope of the invention. BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 illustrates a schematic diagram of an oversampled filter bank in which a downsampling factor is less than the number of bands in the filter bank and constructed according to the principles of the invention;

FIG. 2 illustrates a graph of a zero-phase low pass filter having a cutoff frequency of 2π IM designed using windowing with a Kaiser window;

FIG. 3 illustrates a graph of reconstruction mean-square error for different orders of the synthesis window for the analysis window of FIG. 2;

FIG. 4 illustrates a graph of a minimum-order synthesis window;

FIGS. 5 A and 5B respectively illustrate time and frequency responses of a synthesis window and a minimum-norm synthesis window for L _{ = 56 ;

FIGS. 6A and 6B respectively illustrate time and frequency responses of a synthesis window and a minimum-norm synthesis window for L _f = 96 ;

FIGS. 7A and 7B respectively illustrate least-square synthesis windows corresponding to sinusoid and white noise templates;

FIG. 8 illustrates a flow diagram of one embodiment of a method of optimizing the operation of an oversampled filter bank carried out according to the principles of the invention;

FIG. 9 illustrates a graph of reconstruction signal-to-noise ratio (SNR) for rounding and minimum quantization error solutions; and

FIG. 10 illustrates a block diagram of one embodiment of a system for optimizing the operation of an oversampled filter bank implemented in a digital signal processor (DSP) and constructed according to the principles of the invention. DETAILED DESCRIPTION OF THE EMBODIMENTS

As those skilled in the pertinent art understand and as stated above, oversampled filter banks have an analysis window and a synthesis window. The analysis window is usually designed to meet one or more predefined criteria pertaining to the use to which the filter bank is to be put. The synthesis window is almost always designed based on the design of the analysis window. A novel, general formulation by which the synthesis window may be designed given an analysis window will be introduced herein. The general formulation uses the null space of a perfect reconstruction condition matrix to determine the optimal synthesis window design and contrasts sharply with conventional techniques, which are uniformly directed to the "minimum-norm" solution of the synthesis window. Different optimization criteria of the synthesis window will be disclosed, and explicit, closed-form solutions of the different optimization criteria will be set forth.

The focus herein will be on a synthesis window design technique that satisfies perfect reconstruction conditions. The algebraic approach described in Portnoff, supra, and Shapiro, et al., "Design of Filters...," supra, will be used herein rather than the frame-theoretic approach, as it is more illustrative of the optimization objective functions that will be set forth below.

Oversampling yields extra degrees of freedom that can be exploited in different ways. In particular, oversampling can produce a non-zero null space of the perfect reconstruction condition matrix. This null space can be exploited to optimize the objective function of different criteria without sacrificing the perfect reconstruction. Closed-form solutions of the synthesis window design will be described for the following optimization criteria:

1. Minimum delay design. Minimum delay design produces the smallest output lag of the causal implementation of synthesis window and represents the minimum- order filter that requires the least computation resources.

2. Minimum out-of-band design. Minimum out-of-band design produces the best frequency selectivity.

3. Least-square design. Least-square design produces the closest synthesis window to a given template.

4. Minimum quantization-error design. Minimum quantization-error design minimizes the quantization error for a fixed-point implementation.

The perfect reconstruction conditions will first be reviewed. Then, a general optimization model for the synthesis window using the minimum-norm solution and the basis of the null space of the perfect reconstruction condition matrix will be described. Next, the different optimization criteria will be set forth and an example given for each of the criteria using a template low pass analysis window.

Optimization Model

FIG. 1 illustrates a schematic diagram of an over sampled filter bank 100 in which a downsampling factor D is less than a number M of bands (e.g., 110, 120, 130) in the filter bank and constructed according to the principles of the invention. The filter bank 100 is a so- called "perfect reconstruction, or PR, filter bank, meaning that the filter bank 100 operates by decomposing an input signal X(z) 140 by filtering and subsampling and then reconstructing to yield an output signal X(z) 150 by inserting zeroes, filtering and summation. For a discussion of PR filter banks in general, see, e.g., http://cas.ensmp.fr/~chaplaisAVavetourjDresentation/filtres/ Perfect_Reconstruction.html. If H(z) and F(z) represent prototype analysis and synthesis filters (respectively), the k"' band analysis and synthesis filters are:

H _k (z) = H(zW£),wd , i.e., h _k (ή) = h(ή) ^■ W^" and f _k (n) = /O) • W ^'1 "' , assuming that support(h(n)) e [—L _h ,L _h ] and support (/(ή))≡ The reconstructed signal X(z) has the form:

where

A ₁ [Z) -F(Z-Wl), with / = O,1,...,£>-1.

(2)

According to Portnoff, supra, the necessary and sufficient conditions for perfect reconstruction are:

1. Perfect reconstruction condition:

Yh(ID-H)- f(n-lD) = U M, for O≤n ≤D-l, and

(3)

2. Aliasing canceling condition:

YhID -n + rM)- /(«- ZD) = O, for O≤n ≤D-l.

(4)

In the following, different (yet equivalent) perfect reconstruction conditions will be used that are more illustrative. From Equations (1) and (2), the perfect reconstruction conditions can be derived as:

A ₁ (z) = £[/]

This condition can be expressed as: £f(m)-h(-m)=£, m=~L, M

(5)

and

in other words:

T W£ ^lm -f{m)-h{rM-m) = — δ(l,r), for 0 ≤ l ≤ D- 1, and 1 <| r |< A,+£ _/ m=— Z M

It is straightforward to show the equivalence of the two perfect reconstruction

L _h +L _f conditions. From Equation (5), a total of D ^■ (1 + 2 ) conditions exist. Some of the

M conditions (at the filter edges) may be dependent. The perfect reconstruction conditions can be put in a matrix form as: H-f = z ,

(6) where / = [f(-L _f ),f(-L _f + ϊ),...,f(O),...,f(L _f )] is the synthesis window,

^ ₍₁₊₂ .[ ₍₁ ,, _+Z . _)/λ/ J) _x(2 i ₊ i ₎ i ^{s me} conditions matrix (which is constructed from the conditions in Equation (5)), z = [D/ M, 0,0,...,O] . Note that:

(7)

The minimum-norm solution / ^# is calculated as:

£ = H* -z ,

(8) where H ^# is the pseudo-inverse of the condition matrix H (see, e.g., Chapter 5 of Golub, et al., Matrix Computation, 3rd edition, The John Hopkins University Press, 1996). The dimension of the null space of H is: K = 2L _f +l-rank(H) .

If the basis of the null space is {v,} _l=iK , a general formula for a synthesis window / that satisfies the perfect reconstruction conditions is:

/ = / + ∑Vv, .

1=1

(9) where {c,} _ι=ικ are scalars. Equation (9) represents the general model for optimization that will be used below.

No vectors in the null space of H interfere with the perfect reconstruction conditions set forth in Equation (5). Therefore, any vector v in the null space satisfies the following condition:

V ¹ ϊ L ₁ , + L wτ/- ^~ /'« ^{m YY D v(m) - h(rM~m) = 0, for 0 < / ≤ D-l, and 0 <] r |< 7 m=— L M}

(10)

No structure for h is assumed in the above discussion, hi fact, even if h is an arbitrary vector, the above perfect reconstruction formula still applies. However, in most practical applications, h is a lowpass filter having a bandwidth of 2πl M .

Note that in the perfect reconstruction conditions set forth in Equation (5), h and / may be exchanged without affecting the perfect reconstruction, i.e., the synthesis window

may be designed first and then the analysis window chosen that satisfies the perfect reconstruction condition using substantially the same procedure.

Optimization Criteria

Various optimization criteria for constructing a synthesis window / that satisfies

Equation (9) will now be described. With each criterion, the objective is to find {c,.}, _=llK in

Equation (9) that optimize a certain objective function. This optimization is possible whenever a nonzero null space of the condition matrix H exists. Redundancy may be exploited by reducing the order of the synthesis window as described below rather than optimizing its design. The optimization examples described herein may be extended to other filter design optimizations using the model described in Equation (9).

To illustrate the different optimization criteria better, a design example will be included with each criterion. In all the examples, the following filter bank parameter settings will be used: M = 32, D = S and L _h - 64. The analysis window is as shown in FIG. 2, namely a zero-phase low pass filter curve 200 having a cutoff frequency of 2nl M that is designed using windowing with a Kaiser window.

Least-Order Solution

The smallest order of the synthesis window is directly related to the rank of the condition matrix H . If the synthesis window order equals rank{H) , H is a full rank square matrix and we have only one solution, i.e., the redundancy is exploited by reducing the order of the window rather than optimizing the design as in Equation (9). Therefore the least order of the synthesis window satisfies the condition:

L ₁ , + L ,

2L _f + 1 = mnk(H) ≤ D - (1 + 2 ) •

M

(H)

L _j is evaluated and approximated to the nearest upper integer (which may result in increasing the dimension of the null space of H to one). After approximation, rank(k) = 2L _f +1 , H = H ^~ , and the null space of H contains only the zero vector. Longer synthesis window results in larger null space dimensions, which allows more degrees

of freedom. All subsequent optimization criteria assume that the synthesis window order is larger than L _f .

If the order is less than L _f , perfect reconstruction is no longer possible. However, the least-square solution of Equation (6) yields the best possible reconstruction for a given order. FIG. 3 shows a reconstruction mean-square error curve 300 for different orders of the synthesis window for the analysis window of FIG. 2 where L _f = 20.

For the minimum-order synthesis window, .

FIG. 4 shows a synthesis window 400. In this case, the dimension of the null space is one (because of the upper integer approximation).

For causal systems, the least order solution is equivalent to the minimum delay solution, a desirable feature in many real-time applications, e.g., subband adaptive filtering.

Minimum-Norm Solution

Note that {v,} _!=1M in Equation (9) are orthogonal to the columns of H ^# . As a result:

Therefore, the minimum-norm solution is f = f ^# .

C. Minimum out-of-band Energy Solution

If a lowpass filter prototype is used, the bandwidth of the analysis/synthesis window is 2πl M . If the DFT of / is denoted by f(e ^jω ) , the objective function becomes:

(12)

If the DFT of each of the base vectors v, is F, , then Equation (9) yields the following:

Assuming the length of the DFT is N , only the first JV/ 2+1 components are retained (because of the real symmetry), i.e., F_ , F_ ^# , and (F ₁ . } are arrays of size JV/2 + 1 . If A is a diagonal matrix of size (JV / 2 + 1) x (JV / 2 + 1) such that a _{ . = 0 for z < ^■ $ ^■ and a. _j = 1 otherwise, V _(jm+1)xκ - is a matrix that has {F,.} as its columns and c = [c _x ,...,c _M ] ^τ , the objective function can be approximated as:

J(c) = F ^H - A- F = ⁽ ¥ ^# + y _c ) ^H A -(t +\) , and

= F ^m - A - F* + b ^H - c+c ^H -b + c ^H - G.c . where b = V ^H AF_ ⁿ and G ~ V ^H AV . Differentiating with respect to c yields:

^ = b + G -c . dc

Therefore the optimal solution in this case is: c = -(V ^H AVy ^x - V ^H A≠ ■

(13)

Note that V ^H AV is KxK matrix, and a necessary condition for V ^H AV to have full rank is %+l—$ > K .

The minimum out-of-band power design will be illustrated by two examples with L _f = 56 and L _f = 96 , respectively. FIGS. 5A and 5B show the time and frequency responses of the synthesis windows compared with the minimum-norm synthesis window for L _j = 56 , and FIGS. 6 A and 6B show the time and frequency responses of the synthesis windows compared with the minimum-norm synthesis window for Zy = 96. FIGS. 5A, 5B,

6 A and 6B show a reduction of more than 30 dB in the out-of-band power. This significant reduction results in a better frequency-selective window, a desirable feature in practical applications in which the original signal is usually contaminated with noise.

Least-Square Solution

In this case, the objective is to minimize the difference between the synthesis window and a window template g , i.e., the objective function is:

^min lz ^~ i|| •

(14) If:

^λ (2£+1)Xλ: = (∑ι >∑2>->∑κ) > (15) the cost function has the form:

Ac) = (Z +λc-g) ^H - (/ + Ac-g) . Therefore:

3J = A _\ H ^H ( ,f r# -g) + A ^H Ac . dc Hence, the optimal solution in this case is:

By noting that A" A = I and A ^{H ■} f ^# = 0 (because / ^# is in the row space of H ), the above relation can be simplified to: c = -A» -g .

(16)

To illustrate the significance of the least-square solution, the template g is chosen to be significantly different from / in two extreme examples. In the first example, g is chosen to be a sine wave. In the second example, g is chosen to be an arbitrary sequence.

The resulting synthesis windows are illustrated in FIGS. 7 A and 7B. In both examples, L _f = 96.

Minimum Quantization-Error Solution

In practical applications, the synthesis window will be implemented using finite- precision arithmetic. Therefore, coefficients quantization error is an important design criterion. The best quantization of each component in / (to the upper or lower integer) such that the overall quantization error is minimized will now be considered. In other words, the

best quantized solution in the neighborhood of an existing solution / will be examined. The objective function in this case is: min||β(/)| ² ,

(17) where β(-) is the quantization error function defined as:

(18) and where [_-J is the floor integer function, λ is as defined in Equation (15), a is an

(2Zy -1) binary vector that represents the quantization approximation, i.e., if Q{f _t ) = \_f _t \, then CC ₁ = 0 , and if Q(ft - [/•], then CC ₁ = 1. Note that Equation (18) contains two unknown vectors, c and a . If e denotes the initial quantization error, then: e = f- \ f \ . The objective function can be written in the form: min||λ- c + (e-tf)|| ² .

(19)

For any value of a , the value of c that yields the least square solution of Equation (19) is: c = -λ ^H - (e - α) .

For this reason, the objective function of Equation (19) can be written in the form: (e-a) ^H - P- (e- a) ,

(20) where P = (I- λλ ^H ) ^H (I - λλ ^H ) . This is an integer programming problem with a quadratic objective function. A simulated annealing technique (see, e.g., Chapter 12 of Rardin, Optimization in Operations Research, Prentice Hall, 1998, incorporated herein by reference) may be used to solve it. The simulated annealing technique Rardin discloses has the following seven steps:

1. Starting with a feasible solution a ^φ) , compute the corresponding value of the objective function. Set this value as the incumbent solution a and the pivot solution a .

2. Define a set ω , of all feasible moves that lead to another feasible solution.

3. Arbitrarily choose a move δα ^(/) e ω, and compute the new solution a ^{i) = a+Aa ^{t) , and compute the new objective function obj ⁰⁾ .

4. If δo; improves the incumbent solution with probability e ^{ohj ° ^~obj ' ^)lq (where q is an algorithm parameter), set a = a ^(l) .

5. If obf ^ύ is better than the incumbent solution, set a = a ⁰⁾ .

6. Reduce q after a sufficient number of iterations.

7. Repeat for t ≤ t _max .

The maximum weight of any move in ω may be restricted, e.g., to five. The initial solution is set to the rounding solution, i.e., a ^{0) =| / + 0.5 1 — | / 1.

In one embodiment, the simulated annealing technique may be slightly modified such that once a new optimum is found in step (5), all neighboring solutions within a Hamming distance of one are investigated before arbitrarily selecting from the moving list.

Although the above description is largely directed to a DFT filter bank, the principles of the invention readily apply to other types of oversampled filter banks. The condition matrix has a different structure but the redundancy resulting from oversampling can exploited without departing from the scope of the invention.

FIG. 8 illustrates a flow diagram of one embodiment of a method of optimizing the operation of an oversampled filter bank carried out according to the principles of the invention. The method begins in a start step. In a step 810, a null space of a perfect reconstruction condition matrix is produced based on a first window of the oversampled filter bank. In a step 820, the null space and an optimization criterion are employed to construct a second window of the oversampled filter bank. In a step 830, filter coefficients that describe the first and second window are stored in a memory associated with a DSP. The filter

coefficients are then available to be employed in a filter bank associated with the DSP. The method ends in an end step.

FIG. 9 illustrates the performance of a disclosed embodiment of the invention versus a rounding solution (which is conventionally used for fixed-point systems). The test data is arbitrary signals with unity variance. The number of iterations ( t _m2CK ) equals 10 ⁵ , and

L _f = 96 . FIG. 9 indicates up to an 18 dB improvement without the need to increase resolution. This is equivalent to adding three bits of resolution to the DFT filter bank.

FIG. 10 illustrates a block diagram of one embodiment of a system, generally designated 1000, for optimizing the operation of an oversampled filter bank implemented in a DSP, generally designated 1010, and constructed according to the principles of the invention. The oversampled filter bank includes a plurality of lowpass filters (not shown in FIG. 10, but shown in FIG. 1) configured to process an input signal to yield an output signal based in part on coefficients that describe a first window and in part on coefficients that describe a second window. The first window may be an analysis window, and the second window may be a synthesis window.

A null space generator 1020 within the system 1000 is configured to produce the basis of the null space of a perfect reconstruction condition matrix based on the first window. An optimizer 1030 is associated with the null space generator 1020. The optimizer 1030 is configured to employ the basis and an optimization criterion to construct the second window. The result of this process is a plurality of filter coefficients that are caused to be stored in a memory 1040 associated with the DSP 1010. The filter coefficients are then made available from the memory 1040 to an oversampled filter bank 1050 during operation of the DSP 1010.

Although the invention has been described in detail, those skilled in the pertinent art should understand that they can make variations, substitutions and alterations to the example embodiments described herein without departing from the scope of the claimed invention in its broadest form.