Filter bank

We can define a narrow lowpass filter as a lowpass filter with a narrow passband. In order to create a multirate narrow lowpass FIR filter, we need to replace the time invariant FIR filter with a lowpass antialiasing filter and use a decimator along with an interpolator and lowpass anti-imaging filter

In this way, the resulting multirate system is a time varying linear phase filter via the decimator and interpolator. This process explained in block diagram form where Figure 2 (a) is replaced by Figure 2(b). The lowpass filter consists of two polyphase filters, one for the decimator and one for the interpolator.[5]

A filter bank divides the input signal ${\displaystyle x\left(n\right)}$ into a set of signals ${\displaystyle x_{1}(n),x_{2}(n),x_{3}(n),...}$. In this way each of the generated signals corresponds to a different region in the spectrum of ${\displaystyle x\left(n\right)}$. In this process it can be possible for the regions overlap (or not, based on application). Figure 4 shows an example of a three-band filter bank. The generated signals ${\displaystyle x_{1}(n),x_{2}(n),x_{3}(n),...}$ can be generated via a collection of set of bandpass filters with bandwidths ${\displaystyle {\rm {BW_{1},BW_{2},BW_{3},...}}}$ and center frequencies ${\displaystyle f_{c1},f_{c2},f_{c3},...}$(respectively). A multirate filter bank uses a single input signal and then produces multiple outputs of the signal by filtering and subsampling. In order to split the input signal into two or more signals (see Figure 5) an analysis-synthesis system can be used. In figure 5, only 4 sub-signals are used.

The signal would split with the help of four filters ${\displaystyle H_{k}(z)}$ for k =0,1,2,3 into 4 bands of the same bandwidths (In the analysis bank) and then each sub-signal is decimated by a factor of 4. In each band by dividing the signal in each band, we would have different signal characteristics.

In synthesis section the filter will reconstruct the original signal: First, upsampling the 4 sub-signals at the output of the processing unit by a factor of 4 and then filter by 4 synthesis filters ${\displaystyle F_{k}(z)}$ for k = 0,1,2,3. Finally, the outputs of these four filters are added.

We can use polyphase representation, so input signal ${\displaystyle x[n]}$ can be represented by a vector of its polyphase components ${\displaystyle x(z){\stackrel {\rm {def}}{=}}(X_{0}(z),...,X_{|M|-1}(z))^{T}}$. Denote ${\displaystyle y(z){\stackrel {\rm {def}}{=}}(Y_{0}(z),...,Y_{|N|-1}(z))^{T}.}$
So we would have ${\displaystyle y(z)=H(z)x(z)}$, where ${\displaystyle H_{i,j}(z)}$ denotes the j-th polyphase component of the filter ${\displaystyle H_{i}(z)}$.

Similarly, for the output signal we would have ${\displaystyle {\hat {x}}(z)=G(z)y(z)}$, where ${\displaystyle {\hat {x}}(z){\stackrel {\rm {def}}{=}}({\hat {X}}_{0}(z),...,{\hat {X}}_{|M|-1}(z))^{T}}$. Also G is a matrix where ${\displaystyle G_{i,j}(z)}$ denotes ith polyphase component of the jth synthesis filter Gj(z).

The filter bank has perfect reconstruction if ${\displaystyle x(z)={\hat {x}}(z)}$ for any input, or equivalently ${\displaystyle I_{|M|}=G(z)H(z)}$ which means that G(z) is a left inverse of H(z).

Below are several approaches on the design of multidimensional filter banks. For more details, please check the ORIGINAL references.

In real life, we always want to reconstruct the divided signal back to the original one, which makes PR filter banks very important. Let H(z) be the transfer function of a filter. The size of the filter is defined as the order of corresponding polynomial in every dimension. The symmetry or anti-symmetry of a polynomial determines the linear phase property of the corresponding filter and is related to its size. Like the 1D case, the aliasing term A(z) and transfer function T(z) for a 2 channel filter bank are:[9]

A(z)=1/2(H₀(-z) F₀ (z)+H₁ (-z) F₁ (z)); T(z)=1/2(H₀ (z) F₀ (z)+H₁ (z) F₁ (z)), where H₀ and H₁ are decomposition filters, and F₀ and F₁ are reconstruction filters.

The input signal can be perfectly reconstructed if the alias term is cancelled and T(z) equal to a monomial. So the necessary condition is that T'(z) is generally symmetric and of an odd-by-odd size. Linear phase PR filters are very useful for image processing. This 2-Channel filter bank is relatively easy to implement. But 2 channels sometimes are not enough for use. 2-channel filter banks can be cascaded to generate multi-channel filter banks.

Multidimensional Analysis Filter Banks

M-dimensional directional filter banks (MDFB) are a family of filter banks that can achieve the directional decomposition of arbitrary M-dimensional signals with a simple and efficient tree-structured construction. It has many distinctive properties like: directional decomposition, efficient tree construction, angular resolution and perfect reconstruction. In the general M-dimensional case, the ideal frequency supports of the MDFB are hypercube-based hyperpyramids. The first level of decomposition for MDFB is achieved by an N-channel undecimated filter bank, whose component filters are M-D "hourglass"-shaped filter aligned with the w₁,...,w_M respectively axes. After that, the input signal is further decomposed by a series of 2-D iteratively resampled checkerboard filter banks IRC_li^(Li)(i=2,3,...,M), where IRC_li^(Li)operates on 2-D slices of the input signal represented by the dimension pair (n₁,n_i) and superscript (Li) means the levels of decomposition for the ith level filter bank. Note that, starting from the second level, we attach an IRC filter bank to each output channel from the previous level, and hence the entire filter has a total of 2^{(L₁+...+L_N)} output channels.[10]

Multidimensional Synthesis Filter Banks

Oversampled filter banks are multirate filter banks where the number of output samples at the analysis stage is larger than the number of input samples. It is proposed for robust applications. One particular class of oversampled filter banks is nonsubsampled filter banks without downsampling or upsampling. The perfect reconstruction condition for an oversampled filter bank can be stated as a matrix inverse problem in the polyphase domain.[11]

For IIR oversampled filter bank, perfect reconstruction have been studied in Wolovich[12] and Kailath.[13] in the context of control theory. While for FIR oversampled filter bank we have to use different strategy for 1-D and M-D. FIR filter are more popular since it is easier to implement. For 1-D oversampled FIR filter banks, the Euclidean algorithm plays a key role in the matrix inverse problem.[14] However, the Euclidean algorithm fails for multidimensional (MD) filters. For MD filter, we can convert the FIR representation into a polynomial representation.[15] And then use Algebraic geometry and Gröbner bases to get the framework and the reconstruction condition of the multidimensional oversampled filter banks.[11]

Nonsubsampled filter banks are particular oversampled filter banks without downsampling or upsampling. The perfect reconstruction condition for nonsubsampled FIR filter banks leads to a vector inverse problem: the analysis filters ${\displaystyle \{H_{1},...,H_{N}\}}$ are given and FIR, and the goal is to find a set of FIR synthesis filters ${\displaystyle \{G_{1},...,G_{N}\}}$ satisfying.[11]

Multidimensional M_channel Filter Banks

As multidimensional filter banks can be represented by multivariate rational matrices, this method is a very effective tool that can be used to deal with the multidimensional filter banks.[15]

In Charo,[15] a multivariate polynomial matrix-factorization algorithm is introduced and discussed. The most common problem is the multidimensional filter banks for perfect reconstruction. This paper talks about the method to achieve this goal that satisfies the constrained condition of linear phase.

According to the description of the paper, some new results in factorization are discussed and being applied to issues of multidimensional linear phase perfect reconstruction finite-impulse response filter banks. The basic concept of Gröbner Bases is given in Adams.[16]

This approach based on multivariate matrix factorization can be used in different areas. The algorithmic theory of polynomial ideals and modules can be modified to address problems in processing, compression, transmission, and decoding of multidimensional signals.

The general multidimensional filter bank (Figure 7) can be represented by a pair of analysis and synthesis polyphase matrices ${\displaystyle H(z)}$ and ${\displaystyle G(z)}$ of size ${\displaystyle N\times M}$ and ${\displaystyle M\times N}$, where N is the number of channels and ${\displaystyle M{\stackrel {\rm {def}}{=}}|M|}$ is the absolute value of the determinant of the sampling matrix. Also ${\displaystyle H(z)}$ and ${\displaystyle G(z)}$ are the z-transform of the polyphase components of the analysis and synthesis filters. Therefore, they are multivariate Laurent polynomials, which have the general form:

${\displaystyle F(z)=\sum _{k\in \mathbf {Z} ^{d}}f[k]z^{k}=\sum _{k\in \mathbf {Z} ^{d}}f[k_{1},...,k_{d}]z_{1}^{k_{1}}...z_{d}^{k_{d}}}$.

Laurent polynomial matrix equation need to be solve to design perfect reconstruction filter banks:

${\displaystyle G(z)H(z)=I_{|M|}}$.

In the multidimensional case with multivariate polynomials we need to use the theory and algorithms of Gröbner bases.[17]

Gröbner bases can be used to characterizing perfect reconstruction multidimensional filter banks, but it first need to extend from polynomial matrices to Laurent polynomial matrices.[18][19]

The Gröbner basis computation can be considered equivalently as Gaussian elimination for solving the polynomial matrix equation ${\displaystyle G(z)H(z)=I_{|M|}}$. If we have set of polynomial vectors

${\displaystyle \mathrm {Module} \left\{h_{1}(z),...,h_{N}(z)\right\}{\stackrel {\rm {def}}{=}}\{c_{1}(z)h_{1}(z)+...+c_{N}(z)h_{N}(z)\}}$

where ${\displaystyle c_{1}(z),...,c_{N}(z)}$ are polynomials.

The Module is analogous to the span of a set of vectors in linear algebra. The theory of Gröbner bases implies that the Module has a unique reduced Gröbner basis for a given order of power products in polynomials.

If we define the Gröbner basis as ${\displaystyle \left\{b_{1}(z),...,b_{N}(z)\right\}}$, it can be obtained from ${\displaystyle \left\{h_{1}(z),...,h_{N}(z)\right\}}$ by a finite sequence of reduction (division) steps.

Using reverse engineering, we can compute the basis vectors ${\displaystyle b_{i}(z)}$ in terms of the original vectors ${\displaystyle h_{j}(z)}$ through a ${\displaystyle K\times N}$ transformation matrix ${\displaystyle W_{ij}(z)}$ as:

${\displaystyle b_{i}(z)=\sum _{j=1}^{N}W_{ij}(z)h_{j}(z),i=1,...,K}$

Designing filters with good frequency responses is challenging via Gröbner bases approach.
Mapping based design in popularly used to design nonseparable multidimensional filter banks with good frequency responses.[20][21]

The mapping approaches have certain restrictions on the kind of filters; however, it brings many important advantages, such as efficient implementation via lifting/ladder structures. Here we provide an example of two-channel filter banks in 2D with sampling matrix
${\displaystyle D_{1}=\left[{\begin{array}{cc}2&0\\0&1\end{array}}\right]}$ We would have several possible choices of ideal frequency responses of the channel filter ${\displaystyle H_{0}(\xi )}$ and ${\displaystyle G_{0}(\xi )}$. (Note that the other two filters ${\displaystyle H_{1}(\xi )}$ and ${\displaystyle G_{1}(\xi )}$ are supported on complementary regions.)
All the frequency regions in Figure can be critically sampled by the rectangular lattice spanned by ${\displaystyle D_{1}}$.
So imagine the filter bank achieves perfect reconstruction with FIR filters. Then from the polyphase domain characterization it follows that the filters H1(z) and G1(z) are completely specified by H0(z) and G0(z), respectively. Therefore, we need to design H0(x) and G0(z) which have desired frequency responses and satisfy the polyphase-domain conditions. ${\displaystyle H_{0}(z_{1},z_{2})G_{0}(z_{1},z_{2})+H_{0}(-z_{1},z_{2})G_{0}(-z_{1},z_{2})=2}$
There are different mapping technique that can be used to get above result.[22]

If we do not want perfect reconstruction filter banks using FIR filters, the design problem can be simplified by working in frequency domain instead of using FIR filters.[23][24]
Note that the frequency domain method is not limited to the design of nonsubsampled filter banks (read [25]).

Many of the existing methods for designing 2-channel filter banks are based on transformation of variable technique. For example, McClellan transform can be used to design 1-D 2-channel filter banks. Though the 2-D filter banks have many similar properties with the 1-D prototype, but it is difficult to extend to more than 2-channel cases.[26]

In Nguyen,[26] the authors talk about the design of multidimensional filter banks by direct optimization in the frequency domain. The method proposed here is mainly focused on the M-channel 2D filter banks design. The method is flexible towards frequency support configurations. 2D filter banks designed by optimization in the frequency domain has been used in Wei[27] and Lu.[28] In Nguyen's paper,[26] the proposed method is not limited to two-channel 2D filter banks design; the approach is generalized to M-channel filter banks with any critical subsampling matrix. According to the implementation in the paper, it can be used to achieve up to 8-channel 2D filter banks design.

(6)Reverse Jacket Matrix[29]

In Lee's 1999 paper,[29] the authors talk about the multidimensional filter bank design using Reverse Jacket matrix. According to Wiki article, let H be a Hadamard matrix of order n, the transpose of H is closely related to its inverse. The correct formula is: ${\displaystyle HH^{T}=I_{n}}$, where I_n is the n×n identity matrix and H^T is the transpose of H. In the 1999 paper,[29] the authors generalize the Reverse Jacket matrix [RJ]_N using Hadamard matrices and Weighted Hadamard matrices.[30][31]

In this paper, the authors proposed that the FIR filter with 128 tap is used as a basic filter and decimation factor is computed for RJ matrices. They did simulations based on different parameters and achieve a good quality performances in low decimation factor.

• Harris, Fredric J. (2004). Multirate signal processing for communication systems. Upper Saddle River, NJ: Prentice Hall PTR. ISBN 0-13-146511-2.