# Patent

## Title
Non-uniform filter bank implementation

## Abstract

A method of searching for a best-match decimation vector of decimation factors for non-uniform filter bank, the best match vector allowing perfect or near-perfect reconstruction of an input signal of the non-uniform filter bank, the method including the steps of: a) selecting a partial decimation vector having a number, l, of decimation factors, where l does not exceed a maximum number, K, of decimation factors of said best-match decimation vector; b) testing said l decimation factors to determine whether said partial decimation vector satisfies a feasibility criterion; c) testing a least common multiplier value of said l decimation factors to determine whether said least common multiplier value is greater than a predetermined value; d) testing a maximum decimation value, Dmax, of said partial decimation vector to determine whether Dmax is less than one; e) testing a minimum decimation value, Dmin, of said partial decimation vector to determine whether Dmin is greater than one; and f) if said feasibility criterion is satisfied and Dmax is not less than one and Dmin is not greater than one, then incrementing by one the number l of decimation factors in the partial decimation vector and repeating steps b) to e) for a plurality of times.

## Background
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a non-uniform filter bank implementation. In particular, the invention relates to a non-uniform filter bank implementation for audio compression having improved coding efficiency.
2. Description of the Related Art
Decomposition of a signal into frequency bands, for analysis or processing, has found useful application in a large number of areas such as audio, speech and video processing. Consider audio compression where the audio signal x(n) is decomposed into frequency components by a bank of K-filters (also sometimes termed as frequency transformation or sub-band coding) to yield K signal-components Xk[n], k ranging over 0 . . . K−1. The data rate at each filter output is equal to the input rate of x(n). This implies an K-fold increase in the overall data-rate. Decimation is therefore performed to bring down the data-rate. Decimation by a factor of ni implies that only one out of ni samples out of the filter is considered. If the input rate of the system is R and the decimation factor at the ith filter is ni, then the output rate from the system is




  R
  ·
  
    
      ∑
      
        i
        =
        0
      
      
        K
        -
        1
      
    
    ⁢
    
      1
      /
      
        
          n
          i
        
        .
      
    
  




Ideally, this should be equal to one (less than one implies a loss of information). When





  
    
      
        ∑
        
          i
          =
          0
        
        
          K
          -
          1
        
      
      ⁢
      
        1
        /
        
          n
          i
        
      
    
    =
    1
  
  ,




the system is said to be maximally decimated. When the decimation factor is ni, the bandwidth of the corresponding filter Hi(z) must be approximately π/ni, to prevent aliasing corruption of the signal. If the decimation factor is the same for all filters, the design is simpler, and it is called a uniform-filter bank. In wavelets, the decimation factors, though not the same, vary only as powers of 2. A truly non-uniform filter bank is one in which each ni can assume any arbitrary value.

Following the decomposition and decimation, the signal is analyzed to find means of reducing the data-rate of the system.
FIG. 1 shows encoder and decoder blocks for an MPEG-I Audio Codec. An input pulse-code modulated audio signal (PCM Audio) in the encoder passes through an analysis filter bank for decimating the signal. The PCM Audio input signal is also passed to a psycho-acoustic model, which computes the masking curve. The masking information is used by the bit-allocation module to determine the number of bits to be used by the quantizer for quantizing each frequency component. The larger the number of bits used for quantization, the greater the accuracy of the representation. The trade-off is that the compression rate decreases with an increase in the number of quantization bits. Based on masking effects, the bit-allocation module computes the number of bits to be allocated to each frequency component such that quantization noise is rendered (masked) inaudible. Ancillary data are added to the quantized input signal and the composite bit stream is formatted before transmission. The ancillary data are used to transmit information about the audio signal such as sampling rate, the number of audio channels, encoder settings and all such meta-data which are necessary for correct decoding and reproduction of the audio signal at the decoder. At the receiver side, the decoder performs an inverse quantization followed by upsampling (with the same decimation factors used by the encoder) and filtering to obtain a closely matching version of the input signal x[n].
In the absence of quantization, it is desirable that the system reproduces the original signal x(n) with almost no distortion. A filter bank which achieves such a low level of distortion is called a Perfect Reconstruction Filter Bank. Compared to the non-uniform case, the theory of perfect reconstruction of a uniform filter bank is well understood and documented, and this explains why most existing codecs (MPEG-I Layer III, MPEG-2 AAC, AC-3) use uniform filter banks. The theory concerning non-uniform perfect reconstruction (PR) filter banks is still in its infancy.
It is noted that analysis by the psychoacoustics model is best when the signal decomposition is performed through a non-uniform filter bank that matches closely the critical frequency bands of the ear. Absence of a good understanding of non-uniform filter banks has in the past forced designers of codecs to settle for the less desirable uniform filter bank. However, recent developments in digital signal processing have enabled further study of this problem.
Consider a non-uniform filter-bank with decimation factors (n0, n1, . . . nK−1). It is well known that an arbitrary set will not necessarily result in a feasible PR system. For maximal-decimation, the condition




  
    
      
        
          
            ∑
            
              i
              =
              0
            
            
              K
              -
              1
            
          
          ⁢
          
            1
            /
            
              n
              i
            
          
        
        =
        1
      
    
    
      
        Condition
        ⁢
        
          
        
        ⁢
        I
      
    
  




must be satisfied.

Let L be the least common multiplier (1 cm) of set




  
    {
    
      n
      i
    
    }
  
  
    i
    =
    0
  
  
    K
    -
    1
  




and let ki=L/ni, iε{0, 1, . . . K−1}. Perfect reconstruction is possible only if





  
    
      
        
          
            (
            
              
                ∑
                
                  i
                  =
                  0
                
                
                  l
                  -
                  1
                
              
              ⁢
              
                k
                i
              
            
            )
          
          ≡
          
            0
            ⁢
            
              
                mod
                ⁢
                k
              
              l
            
          
        
        ,
        
          
            for
            ⁢
            
              
            
            ⁢
            each
            ⁢
            
              
            
            ⁢
            l
          
          ∈
          
            {
            
              1
              ,
              
                
                  ...
                  ⁢
                  
                    
                  
                  ⁢
                  K
                
                -
                1
              
            
            }
          
        
      
    
    
      
        Condition
        ⁢
        
          
        
        ⁢
        II
      
    
  




The symbol ≡ here stands for congruence (e.g., ‘11≡1 mod 5’, since 11−1 equals 10 which is divisible by 5). We shall call condition I the maximal-decimation-condition and condition II the feasibility-condition. A set of numbers satisfying both conditions is called a compatible-set.

Usually, the decimation-vector Vspec=(n0, n1, . . . nK−1)εNK, is defined by the application. Vspec may not satisfy either condition. The problem is to find a vector Vbest—match εNK such that it satisfies both conditions and is the closest match, in terms of a pre-defined measure d( ), to Vspec. That is, for all VεNK such that V satisfies the maximal-decimation and feasibility conditions, d(V, Vbest—match)≧, d(Vspec, Vbest—match).
An exhaustive brute-force search (i.e., by evaluating every possible combination of decimation factors) for Vbest—match over a set S⊂Nk can be extremely computationally expensive. An efficient algorithm is required to perform the search efficiently.
BRIEF SUMMARY OF THE INVENTION
The number of vectors satisfying the maximal-decimation and feasibility conditions is rather small. Suppose the first I components of decimation vector Vpartial are fixed to f0, f1, . . . fl−1, respectively. Rather than trying every different combination on the remaining components and checking each resulting complete vector for compatibility, it would be more efficient to perform some preliminary tests on the partial-vector itself to check if it could ever lead to a compatible set. If tests reveal that no matter what the value of the remaining components, the initial assignment can never lead to a feasible (or acceptable) solution, then it is prudent to abandon that subspace and search in another direction. This would decrease the computational requirements of the search algorithm drastically.
The present invention provides a method of searching for a best-match decimation vector of decimation factors for a non-uniform filter bank, the best-match decimation vector allowing perfect or near-perfect reconstruction of an input signal of the non-uniform filter bank, the method including the steps of:
a) selecting a partial decimation vector having a number, l≧1, of decimation factors, where l does not exceed a maximum number, K, of decimation factors of said best-match decimation vector;
b) processing said l decimation factors to determine whether said partial decimation vector satisfies a feasibility criterion;
c) processing a least common multiplier value of said l decimation factors to determine whether said least common multiplier value is greater than a predetermined value;
d) processing a maximum decimation value, Dmax, of said partial decimation vector to determine whether Dmax is less than one;
e) processing a minimum decimation value, Dmin, of said partial decimation vector to determine whether Dmin is greater than one; and
f) incrementing by one the number of decimation factors in the partial decimation vector and repeating steps b) to e) when said feasibility criterion is satisfied and said least common multiplier value is less than said predetermined value and Dmax is not less than one and Dmin is not greater than one.
In the preferred embodiment, a branch-and-bound method is inserted into the structure of the search procedure. For the bounding condition, four tests are used:
F-Test: A partial-test on feasibility of the partial decimation vector.
L-Test: A check on the growth of the least-common-multiplier value.
Dmin-Test & Dmax-Test: To check on the possibility of convergence to unity of the summation of the reciprocals of the decimation factors (maximal decimation condition).
The above tests are described further below and an example of the improvement in searching efficiency is provided.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram of an encoder and decoder used for audio signal compression; and
FIG. 2 is a block diagram representation of a non-uniform filter bank.



Preferred embodiments of the invention are described hereinafter, by way of example only, with reference to the drawings mentioned above.
DETAILED DESCRIPTION OF THE INVENTION
FIG. 2 shows a non-uniform filter bank structure where x(n) is the input signal to the encoder of FIG. 1 and x′(n) is the output signal from the decoder. Ho(z), . . . ,HK−1(z) and Fo(z), . . . , FK−1(z) are the input and output transfer functions, respectively for the K input and output filters. Ho(z), . . . ,HK−1(z), in combination with the corresponding decimation factors n0, n1, . . . , nK−1, form the analysis filter bank on the encoder side, as shown in FIG. 1, and Fo(z), . . . ,FK−1(z), with the same decimation factors, form the analysis filter bank at the decoder for inverse filtering. A method of a preferred embodiment concerns determining an optimal decimation vector V=(n0, n1, . . . nK−1) to enable perfect reconstruction of the decimated input signal.
Suppose the vector Vspec=(n0, n1, . . . , nK−1)εNK denotes the required set of decimation factors for a non-uniform filter-bank. That is, the decimation factor following the first filter in the bank equals n0, the decimation factor following the second filter is n1, and so on.
If vector Vspec satisfies the maximal-decimation and feasibility conditions, then the filter bank design can proceed according to known methods. If not, a closely matching vector Vbest—matchεNK that satisfies both conditions must be found.
The term ‘closely matching’ must be clearly defined. Suppose we define a measure that computes the difference between two decimation-vectors. Two vectors could then be considered as ‘closely matching’ if the difference computed is quite small. For example, we may define a measure




  
    
      d
      ⁡
      
        (
        
          A
          ,
          B
        
        )
      
    
    =
    
      
        ∑
        i
      
      ⁢
      
        
          
          
            
              a
              i
            
            -
            
              b
              i
            
          
          
        
        
          b
          i
        
      
    
  
  ,




where A=(a0, a1, . . . , ak−1) and B=(b0, b1, . . . , bk−1). This measure is the summation of the relative difference between each component of A and each corresponding component of B.

Therefore, Vbest—match is considered to be the best-matching vector if it satisfies both the maximal-decimation and feasibility conditions and for all VεNK such that V satisfies both conditions, d(V, Vspec)≧d(Vbest—match, Vspec).
Searching the entire space NK is of course impossible. We therefore limit the search to a finite region around Vspec.
Let us define a vector D=(d0, d1, . . . , dk−1)εNK. Using D we define a region around Vspec as S={n0−d0,n0−d0+1, . . . ,n0, . . . n0+d0}×{n1−d1, . . . n1+d1}× . . . ×{nK−1−dK−1, . . . nK−1+dK−1}. The search is now limited to region S. Therefore, rephrasing the earlier statement, d(V, Vspec)≧d(Vbest—match, Vspec), ∀VεS: that maximal-decimation (V) and feasible(V).
A brute-force search over S may not be computationally feasible if it is a large set. For example, there are 25 critical bands in the ear-model. The corresponding decimation-vector is something like (220,220,220,220, . . . 9,6,3). Taking D to be (100, 100, . . . ,5,2,0), the number of vector-evaluations needed by an exhaustive search would be in the order of 1035. Roughly, a single-vector evaluation on an Intel Pentium III processor takes 10−5 sec. Therefore an exhaustive search within even this restricted space would need 2.5×1023 years.
Instead of enumerating each vector in S and checking if it satisfies both conditions, a intelligent methodical search of some sort is required. Here we propose a branch-and-bound based approach to the problem.
The branch-and-bound algorithm proceeds as follows: the search space is divided into a number of branches. Each branch is investigated in a sequential order. For each branch, it is estimated whether its exploration would result in a solution better than the existing one. If a particular branch is predicted not to produce any acceptable solution, or it is predicted that the best solution that it could offer would still be inferior to an existing solution, then further exploration of that branch is abandoned, in other words, that branch is bounded. The search-space is explored recursively and the algorithm is inherently recursive.
Now, the specific search problem is modeled as a branch and bound solution. Suppose we have a partial vector Vpartial=(f0, f1, . . . fl−1, x, . . . , x)ε(N∪{x})K. Here the first l components have been assigned some value. The remaining K−l components are denoted as x, meaning that they have not been assigned any value as yet. If l is equal to K−1, then Vpartial has some value assigned to each component. Vpartial is then checked to see if it satisfies the maximum-decimation and feasibility conditions. If it does, then its closeness to Vspec is measured to see if it is a solution-vector closer than any previously found vector. If so, then Vpartial is assigned to the variable Vbest—match.
Suppose l is less than K−l. We then conduct a number of tests to check if (f0, f1, . . . fl−1, x, . . . , x) can lead to a compatible-set. If any of the tests fail, the partial vector (branch) is terminated prematurely, and the search moves onto the next branch.
F-Test: The first test is that of feasibility. Suppose that the unknowns in Vpartial were resolved to some r1, rl+1, . . . rk−1. Let us check if the feasibility condition would be satisfied.
Let L=lcm(f0, f1, . . . fl−1, rl, rl+1, . . . rK−l) and Lpartial=lcm(f0, f1, . . . fl−1). Now elementary arithmetic tells us that L=Lpartial*Ur, where Ur is some constant. Now, ki=L/fi, therefore ki=(Lpartial/fi)*Ur. Since Lpartial is a multiplier of fi it follows that fi divides Lpartial. Consider the compatibility test,




  
    (
    
      
        ∑
        
          i
          =
          0
        
        
          m
          -
          1
        
      
      ⁢
      
        k
        i
      
    
    )
  
  ≡
  
    0
    ⁢
    
      
        
          mod
          ⁢
          k
        
        m
      
      .
    
  




That is,




  
    (
    
      
        ∑
        
          i
          =
          0
        
        
          m
          -
          1
        
      
      ⁢
      
        
          
            L
            partial
          
          ·
          
            U
            r
          
        
        
          f
          i
        
      
    
    )
  
  ≡
  
    0
    ⁢
    
      
    
    ⁢
    mod
    ⁢
    
      
    
    ⁢
    
      
        
          
            L
            partial
          
          ·
          
            U
            r
          
        
        
          f
          m
        
      
      .
    
  




This is equivalent to




  
    
      (
      
        
          ∑
          
            i
            =
            0
          
          
            m
            -
            1
          
        
        ⁢
        
          
            L
            partial
          
          
            f
            i
          
        
      
      )
    
    ≡
    
      0
      ⁢
      
        
      
      ⁢
      
        m
        ⁢
        od
      
      ⁢
      
        
      
      ⁢
      
        
          L
          partial
        
        
          f
          m
        
      
    
  
  ,
  
    m
    ∈
    
      {
      
        1
        ,
        
          2
          ⁢
          
            
          
          ⁢
          ...
        
        ⁢
        
          
        
        ,
        l
      
      }
    
  




If this condition is satisfied for all m, Vpartial is considered to pass the F-test. From this it can be seen that, even though Vpartial is partially fixed, it is possible to check feasibility for the already fixed components of a partial decimation vector.
L-Test: Next we impose a least common multiplier test (L-test) on Lpartial. It is noted above that L=Lpartial*Ur, i.e., L>Lpartial. A very large lcm (e.g., if f0, f1, . . . fl−1, are all mutually-prime) is not very desirable. To prevent the search from veering into mutually-prime sets, a hard limit is placed on the lcm, Lmax. If Lpartial is greater than Lmax, then no matter what choice is made for rl, rl+1, . . . the composite lcm L would exceed Lmax. Therefore if Lpartial is greater than Lmax, the L-test fails and the search branch is terminated.
The next two tests are designed to test whether




  
    ∑
    
      i
      =
      0
    
    
      K
      -
      1
    
  
  ⁢
  
    1
    /
    
      f
      i
    
  




converges to one. The maximum value for fi is 1/(ni−di) within the defined area around Vspec. Similarly, the minimum value is 1/(ni+di). With (f0, f1, . . . fl−1) fixed, and (rl, rl+1, . . . rK−1) being some arbitrary numbers yet to be fixed, the Dmax-Test (Maximum-Decimation Rate) and Dmin-Test (Minimum-Decimation Rate) compute whether the current fixed assignments f0, f1, . . . fl−1 could ever lead to a convergence value of





  
    ∑
    
      i
      =
      0
    
    
      K
      -
      1
    
  
  ⁢
  
    
  
  ⁢
  
    1
    /
    
      f
      i
    
  




equal to unity.

Dmax-Test (Maximum-Decimation Rate): Let Vpartial=(f0, f1, . . . fl−1, x, . . . , x) ε(N∪{x})K be a partially assigned decimation vector. Define:




  
    
      D
      max
    
    =
    
      
        
          ∑
          
            i
            =
            0
          
          
            l
            -
            1
          
        
        ⁢
        
          
        
        ⁢
        
          1
          /
          
            f
            i
          
        
      
      +
      
        
          ∑
          
            i
            =
            l
          
          
            K
            -
            1
          
        
        ⁢
        
          1
          
            
              n
              i
            
            +
            
              d
              i
            
          
        
      
    
  
  ⁢
  
    
  




If Dmax<1, then





  
    ∑
    
      i
      =
      0
    
    
      K
      -
      1
    
  
  ⁢
  
    
  
  ⁢
  
    1
    /
    
      f
      i
    
  




can never be equal to one, and consequently the test fails.

Dmin-Test (Minimum-Decimation Rate): Define:




  
    
      D
      min
    
    =
    
      
        
          ∑
          
            i
            =
            0
          
          
            l
            -
            1
          
        
        ⁢
        
          
        
        ⁢
        
          1
          /
          
            f
            i
          
        
      
      +
      
        
          ∑
          
            i
            =
            l
          
          
            K
            -
            1
          
        
        ⁢
        
          1
          
            
              n
              i
            
            -
            
              d
              i
            
          
        
      
    
  
  ⁢
  
    
  




If Dmin>1, then Vpartial would always lead to a vector whose sum of reciprocals would exceed unity, i.e.,





  
    ∑
    
      i
      =
      0
    
    
      K
      -
      1
    
  
  ⁢
  
    
  
  ⁢
  
    1
    /
    
      f
      i
    
  




can never be equal to one.

An algorithm for effecting the four tests (F-test, L-test, Dmax-test and Dmin-test) is illustrated in pseudo-code in Appendix 1 hereto.
In table 1 below, the efficiency of the presently described Branch-and-Bound algorithm is compared against the exhaustive Brute-Force method.







TABLE 1







Efficiency Comparison









Number of Evaluations



(~proportional to processor execution time)













Branch and
Branch and
Branch and


K

Bound
Bound
Bound


(number

(Tests: Dmin +
(Tests: Dmin +
(Tests: Dmin +


of Filters)
Brute-Force
Dmax)
Dmax + L)
Dmax + L + F)














3
2,744
211
211
45


4
384,16
2,866
2866
115


5
537,824
36,119
35,807
293


6
7,529,536
401,716
376,924
666


7
105,413,504
6,121,843
3,185,673
1311









In table 2 below, a compatible set of decimation factors which closely match the critical decimation factors (computed from the critical band frequencies) is presented. The critical band frequencies of the human ear are empirically determined and are spread across about 25 distinctly identifiable bands. The bandwidth of each band varies from slightly less than 100 Hz at low frequencies to about one third of an octave at higher audible frequencies (e.g., 1.2 kHz for a center frequency of 10 kHz). The critical bands of the ear are generally continuous such that a tone of an audible frequency has a critical band centered on it.







TABLE 2







Best match decimation vector











Vbest—match


Critical-Band No.
Vspec
(LCM = 2520)












1
220
210


2
220
210


3
220
210


4
220
210


5
200
210


6
183
168


7
158
168


8
148
140


9
138
140


10
116
120


11
105
120


12
92
90


13
79
90


14
70
90


15
59
60


16
49
60


17
40
30


18
32
42


19
25
21


20
20
21


21
17
21


22
12
12


23
9
12


24
6
6


25
3
3









In the above chart, the Vbest—match has decimation factors as shown. The critical band number is the number of a critical frequency base of the human ear.
From the foregoing it will be appreciated that, although specific embodiments of the invention have been described herein for purposes of illustration, various modifications may be made without deviating from the spirit and scope of the invention. Accordingly, the invention is not limited except as by the appended claims.








APPENDIX 1





Initialization:
Vspec = (n0, n1, . . ., nk−1) ∈ NK, D = (d0, d1, . . ., dK−1) ∈ NK, Ls = Limit on LCM,



errorleast = any large number















Algorithm branch_and_bound









input: Vpartial= (f0, f1, . . ., fl−1, x, . . ., x) ∈ (N∪{x})K;








begin



foreach z ∈ {−d1, −d1+ 1, . . . 0,1,2, . . . dl}










Fpartial= (f0, f1, ... fl−1, nl+z, x, . . ., x);
//fl = nl + z










if l.equals. K−1
//one complete solution . . .?



 














  
    if
    ⁢
    
      
    
    ⁢
    
      
        ∑
        
          i
          =
          0
        
        
          K
          -
          1
        
      
      ⁢
      
        1
        /
        
          f
          i
        
      
    
  
  =
  
    1
    ⁢
    
      
    
    .
    and
    .
    
      feasible
      ⁡
      
        (
        
          
            F
            partials
          
          ,
          
            l
            +
            1
          
        
        )
      
    
  




//check feasibility and maximal dec.



 














  
    if
    ⁢
    
      
    
    ⁢
    
      
        ∑
        
          i
          =
          0
        
        
          K
          -
          1
        
      
      ⁢
      
        
          
          
            
              n
              i
            
            -
            
              f
              i
            
          
          
        
        
          n
          i
        
      
    
  
  <
  
    error
    least
  




//is this feasible solution better than



 




// previous one ?



 













  
    
      <
      
        error
        least
      
    
    =
    
      
        ∑
        
          i
          =
          0
        
        
          K
          -
          1
        
      
      ⁢
      
        
          
          
            
              n
              i
            
            -
            
              f
              i
            
          
          
        
        
          n
          i
        
      
    
  
  ,
  
    
      
        F
        best_match
      
      =
      
        F
        partial
      
    
    ;
  







 









endif









endif









else









if l .is greater than. 0










if (.not.feasible(Fpartial, l+1))
//F-Test










.or. (Lpartial> L)
//L-Test



 







  
    .
    or
    .
    
      (
      
        
          
            ∑
            
              i
              =
              0
            
            l
          
          ⁢
          
            1
            
              f
              i
            
          
        
        +
        
          
            ∑
            
              i
              =
              
                l
                +
                1
              
            
            
              K
              -
              1
            
          
          ⁢
          
            1
            
              
                n
                i
              
              +
              
                d
                i
              
            
          
        
      
      )
    
  
  >
  1




//Dmin-Test



 







  
    .
    or
    .
    
      (
      
        
          
            ∑
            
              i
              =
              0
            
            l
          
          ⁢
          
            1
            
              f
              i
            
          
        
        +
        
          
            ∑
            
              i
              =
              
                l
                +
                1
              
            
            
              K
              -
              1
            
          
          ⁢
          
            1
            
              
                n
                i
              
              -
              
                d
                i
              
            
          
        
      
      )
    
  
  <
  1




//Dmax-Test



 



continue;
//since conditions fail, move on







next branch









end










end




branch_and_bound(Fpartial, l+1);
//branch to next child









end







end


Function feasible









input: Fpartial= f0, f1, . . . fl−1, x, . . ., x) ∈(N∪{x})K;







begin










Lpartial = lcm(Fpartial,l)
//lcm of the first l numbers



foreach i ∈ {1,2, . . . l − 1}
//iterate



 













  
    if
    ⁢
    
      
    
    ⁢
    
      (
      
        
          ∑
          
            k
            =
            0
          
          
            i
            -
            1
          
        
        ⁢
        
          
            L
            partial
          
          
            f
            k
          
        
      
      )
    
  
  ≡
  
    0
    ⁢
    
      
    
    ⁢
    
      mod
      ⁡
      
        (
        
          
            L
            partial
          
          
            f
            i
          
        
        )
      
    
  







 









return False









end









return True







End

## Claims

1. A method of searching for a best-match decimation vector of decimation factors for a non-uniform filter bank, the best-match decimation vector allowing reconstruction of an input signal of the non-uniform filter bank, the method comprising:
a) selecting a partial decimation vector having a number l<1, of decimation factors, where l does not exceed a maximum number, K, of decimation factors of said best-match decimation vector;
b) processing said l decimation factors to determine whether said partial decimation vector satisfies a feasibility criterion;
c) processing a least common multiplier value of said l decimation factors to determine whether said least common multiplier value is greater than a predetermined value;
d) processing a maximum decimation value, Dmax, of said partial decimation vector to determine whether Dmax is less than one;
e) processing a minimum decimation value, Dmin, of said partial decimation vector to determine whether Dmin is greater than one; and
f) incrementing by one the number of decimation factors in the partial decimation vector and repeating steps b) to e) when said feasibility criterion is satisfied and said least common multiplier value is less than said predetermined value and Dmax is not less than one and Dmin is not greater than one.

2. The method of claim 1, further including the step of:
g) selecting a new partial decimation vector and repeating steps b) to f) when the feasibility criterion is not satisfied or the least common multiplier is greater than the predetermined value or Dmax is less than one or Dmin is greater than one.

3. The method of claim 2, further including the step of:
h) repeating steps a) to g) until l=K and a best-match decimation vector is located.

4. The method of claim 1, wherein said feasibility criterion is satisfied if




  
    
      (
      
        
          ∑
          
            i
            =
            0
          
          
            m
            -
            1
          
        
        ⁢
        
          
        
        ⁢
        
          
            L
            partial
          
          
            f
            i
          
        
      
      )
    
    ≡
    
      0
      ⁢
      
        
      
      ⁢
      mod
      ⁢
      
        
      
      ⁢
      
        
          L
          partial
        
        
          f
          m
        
      
    
  
  ,
  
    
      for
      ⁢
      
        
      
      ⁢
      all
      ⁢
      
        
      
      ⁢
      m
    
    ∈
    
      {
      
        1
        ,
        2
        ,
        ...
        ⁢
        
          
        
        ,
        l
      
      }
    
  




where Lpartialis said least common multiple value and f0, f1, . . . ,f1 are said decimation factors of said partial decimation vector.

5. The method of claim 1, wherein an ideal set of decimation factors is defined by a vector Vspec=(n0, n1, . . . , nK−1)εNK and a vector D is defined as D=(d0, d1, . . . , dk−1)εNK, such that a region S around Vspec is defined as S={n0−d0,n0−d0+1, . . . ,n0, . . . n0+d0}×{n1−d1, . . . n1+d1}× . . . ×{nK−1−dK−1, . . . nK−1+dK−1} and wherein Dmax is determined by




  
    D
    max
  
  =
  
    
      
        ∑
        
          i
          =
          0
        
        
          l
          -
          1
        
      
      ⁢
      
        
      
      ⁢
      
        1
        /
        
          f
          i
        
      
    
    +
    
      
        ∑
        
          i
          =
          l
        
        
          K
          -
          1
        
      
      ⁢
      
        
          1
          
            
              n
              i
            
            -
            
              d
              i
            
          
        
        .

6. The method of claim 5, wherein Dmin is determined by




  
    
      D
      min
    
    =
    
      
        
          ∑
          
            i
            =
            0
          
          
            l
            -
            1
          
        
        ⁢
        
          
        
        ⁢
        
          1
          /
          
            f
            i
          
        
      
      +
      
        
          ∑
          
            i
            =
            l
          
          
            K
            -
            1
          
        
        ⁢
        
          
            1
            
              
                n
                i
              
              +
              
                d
                i
              
            
          
          .
        
      
    
  
  ⁢

7. A decimation vector generated by a method according to the steps comprising:
a) selecting a partial decimation vector having a number, l≧1, of decimation factors, where l does not exceed a maximum number, K, of decimation factors of said best-match decimation vector;
b) processing said l decimation factors to determine whether said partial decimation vector satisfies a feasibility criterion;
c) processing a maximum decimation value, Dmax, of said partial decimation vector to determine whether Dmax is less than one;
d) processing a minimum decimation value, Dmin, of said partial decimation vector to determine whether Dmin, is greater than one; and
e) incrementing by one the number of decimation factors in the partial decimation vector and repeating steps b) to e) when said feasibility criterion is satisfied and said least common multiplier value is less than said predetermined value and Dmax is not less than one and Dmin is not greater than one.

8. A decimation vector generated by a method according to claim 7, wherein Vbest-match has decimation factors as shown in the following table and where the critical band number is the number of a critical frequency band of the human ear














Vbest—match


Critical-Band No.
Vspec
(LCM = 2520)

















1
220
210


2
220
210


3
220
210


4
220
210


5
200
210


6
183
168


7
158
168


8
148
140


9
138
140


10
116
120


11
105
120


12
92
90


13
79
90


14
70
90


15
59
60


16
49
60


17
40
30


18
32
42


19
25
21


20
20
21


21
17
21


22
12
12


23
9
12


24
6
6


25
3
3.

9. A codec adapted to execute the method comprising:
a) selecting a partial decimation vector having a number, l, of decimation factors, where l does not exceed a maximum number, K, of decimation factors of said best-match decimation vector;
b) testing said l decimation factors to determine whether said partial decimation vector satisfies a feasibility criterion;
c) testing a maximum decimation value, Dmax, of said partial decimation vector to determine whether Dmax is less than one;
d) testing a minimum decimation value, Dmin, of said partial decimation vector to determine whether Dmin is greater than one; and
e) if said feasibility criterion is satisfied and Dmax is not less than one and Dmin is not greater than one, then incrementing by one the number l of decimation factors in the partial decimation vector and repeating steps b) to e) for a plurality of times.

10. The codec according to claim 9, wherein the codec is an audio codec.

11. The codec according to claim 9, wherein the decimation factors are selected based upon the band frequencies identifiable for the human ear.

12. The codec according to claim 9, wherein the bandwidth is different from each other for at least two of the band frequencies and the bandwidth is larger at the highest frequency than it is at the lowest frequency.

13. The codec according to claim 9, wherein the bandwidth at the lowest band frequency is about 100 Hz and the bandwidth at the highest band frequency is above 1 kHz, but less than 8 kHz.

14. The codec according to claim 13, wherein the bandwidth at the highest frequency is less than 3 kHz.

15. The codec according to claim 9, further including:
testing a least common multiplier value of said l decimation factors to determine whether said least common multiplier value is greater than a predetermined value.

16. The codec according to claim 15 further including:
incrementing by one the number l of decimation factors if the least common multiplier value is less than a predetermined value.