Filter bank

A bank of receivers can be created by performing a sequence of FFTs on overlapping segments of the input data stream. A weighting function (aka window function) is applied to each segment to control the shape of the frequency responses of the filters. The wider the shape, the more often the FFTs have to be done to satisfy the Nyquist sampling criteria. For a fixed segment length, the amount of overlap determines how often the FFTs are done (and vice versa). Also, the wider the shape of the filters, the fewer filters that are needed to span the input bandwidth. Eliminating unnecessary filters (i.e. decimation in frequency) is efficiently done by treating each weighted segment as a sequence of smaller blocks, and the FFT is performed on only the sum of the blocks. This has been referred to as weight overlap-add (WOLA) and weighted pre-sum FFT. (see ) A special case occurs when, by design, the length of the blocks is an integer multiple of the interval between FFTs. Then the FFT filter bank can be described in terms of one or more polyphase filter structures where the phases are recombined by an FFT instead of a simple summation. The number of blocks per segment is the impulse response length (or depth) of each filter. The computational efficiencies of the FFT and polyphase structures, on a general purpose processor, are identical. Synthesis (i.e. recombining the outputs of multiple receivers) is basically a matter of upsampling each one at a rate commensurate with the total bandwidth to be created, translating each channel to its new center frequency, and summing the streams of samples. In that context, the interpolation filter associated with upsampling is called synthesis filter. The net frequency response of each channel is the product of the synthesis filter with the frequency response of the filter bank (analysis filter). Ideally, the frequency responses of adjacent channels sum to a constant value at every frequency between the channel centers. That condition is known as perfect reconstruction. ==Filter banks as time–frequency distributions==

In time–frequency signal processing, a filter bank is a special quadratic time–frequency distribution (TFD) that represents the signal in a joint time–frequency domain. It is related to the Wigner–Ville distribution by a two-dimensional filtering that defines the class of quadratic (or bilinear) time–frequency distributions. The filter bank and the spectrogram are the two simplest ways of producing a quadratic TFD; they are in essence similar as one (the spectrogram) is obtained by dividing the time domain into slices and then taking a Fourier transform, while the other (the filter bank) is obtained by dividing the frequency domain in slices forming bandpass filters that are excited by the signal under analysis. ==Multirate filter bank==

A multirate filter bank divides a signal into a number of subbands, which can be analysed at different rates corresponding to the bandwidth of the frequency bands. The implementation makes use of downsampling (decimation) and upsampling (expansion). See and for additional insight into the effects of those operations in the transform domains. Narrow lowpass filter One can define a narrow lowpass filter as a lowpass filter with a narrow passband. In order to create a multirate narrow lowpass FIR filter, one can replace the time-invariant FIR filter with a lowpass antialiasing filter and 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. The lowpass filter consists of two polyphase filters, one for the decimator and one for the interpolator. A filter bank divides the input signal x\left(n\right) into a set of signals 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 x\left(n\right). In this process it can be possible for the regions overlap (or not, based on application). The generated signals x_{1}(n),x_{2}(n),x_{3}(n),... can be generated via a collection of set of bandpass filters with bandwidths \rm BW_{1},BW_{2},BW_{3},... and center frequencies 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, an analysis-synthesis system can be used. The signal would split with the help of four filters 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 F_{k}(z) for k = 0,1,2,3. Finally, the outputs of these four filters are added. Statistically optimized filter bank (Eigen filter bank) A discrete-time filter bank framework allows inclusion of desired input signal dependent features in the design in addition to the more traditional perfect reconstruction property. The information theoretic features like maximized energy compaction, perfect de-correlation of sub-band signals and other characteristics for the given input covariance/correlation structure are incorporated in the design of optimal filter banks. These filter banks resemble the signal dependent Karhunen–Loève transform (KLT) that is the optimal block transform where the length L of basis functions (filters) and the subspace dimension M are the same. ==Multidimensional filter banks==

Multidimensional filtering, downsampling, and upsampling are the main parts of multirate systems and filter banks. A complete filter bank consists of the analysis and synthesis side. The analysis filter bank divides an input signal to different subbands with different frequency spectra. The synthesis part reassembles the different subband signals and generates a reconstructed signal. Two of the basic building blocks are the decimator and expander. For example, the input divides into four directional sub bands that each of them covers one of the wedge-shaped frequency regions. In 1D systems, M-fold decimators keep only those samples that are multiples of M and discard the rest. while in multi-dimensional systems the decimators are D × D nonsingular integer matrix. it considers only those samples that are on the lattice generated by the decimator. Commonly used decimator is the quincunx decimator whose lattice is generated from the Quincunx matrix which is defined by \begin{bmatrix}\;\;\,1 & 1 \\-1 & 1 \end{bmatrix} The quincunx lattice generated by quincunx matrix is as shown; the synthesis part is dual to the analysis part. Filter banks can be analyzed from a frequency-domain perspective in terms of subband decomposition and reconstruction. However, equally important is Hilbert-space interpretation of filter banks, which plays a key role in geometrical signal representations. For generic K-channel filter bank, with analysis filters \left\{ h_{k}[n]\right\} _{k=1}^{K} , synthesis filters \left\{ g_{k}[n]\right\} _{k=1}^{K}, and sampling matrices \left\{ M_{k}[n]\right\} _{k=1}^{K} . In the analysis side, we can define vectors in ''\ell^{2}(\mathbf{Z}^{d}) '' as :\varphi_{k,m}[n]\stackrel{\rm def}{=}h_{k}^{*}[M_{k}m-n], each index by two parameters: 1\leq k\leq K and m\in \mathbf{Z}^{2}. Similarly, for the synthesis filters g_{k}[n] we can define \psi_{k,m}[n]\stackrel{\rm def}{=}g_{k}^{*}[M_{k}m-n]. Considering the definition of analysis/synthesis sides we can verify that c_{k}[m]=\langle x[n],\varphi_{k,m}[n] \rangle and for reconstruction part: :\hat{x}[n]=\sum_{1\leq k\leq K,m\in \mathbf{Z}^{2}}c_{k}[m]\psi_{k,m}[n]. In other words, the analysis filter bank calculate the inner product of the input signal and the vector from analysis set. Moreover, the reconstructed signal in the combination of the vectors from the synthesis set, and the combination coefficients of the computed inner products, meaning that :\hat{x}[n]=\sum_{1\leq k\leq K,m\in \mathbf{Z}^{2}}\langle x[n],\varphi_{k,m}[n] \rangle\psi_{k,m}[n] If there is no loss in the decomposition and the subsequent reconstruction, the filter bank is called perfect reconstruction. (in that case we would have x[n]=\hat{x[n]}. Figure shows a general multidimensional filter bank with N channels and a common sampling matrix M. The analysis part transforms the input signal x[n] into N filtered and downsampled outputs y_{j}[n], j=0,1,...,N-1. The synthesis part recovers the original signal from y_{j}[n] by upsampling and filtering. This kind of setup is used in many applications such as subband coding, multichannel acquisition, and discrete wavelet transforms. Perfect reconstruction filter banks We can use polyphase representation, so input signal x[n] can be represented by a vector of its polyphase components x(z)\stackrel{\rm def}{=}(X_{0}(z),...,X_=G(z)H(z) which means that G(z) is a left inverse of H(z). ==Multidimensional filter design==

1-D filter banks have been well developed until today. However, many signals, such as image, video, 3D sound, radar, sonar, are multidimensional, and require the design of multidimensional filter banks. With the fast development of communication technology, signal processing system needs more room to store data during the processing, transmission and reception. In order to reduce the data to be processed, save storage and lower the complexity, multirate sampling techniques were introduced to achieve these goals. Filter banks can be used in various areas, such as image coding, voice coding, radar and so on. Many 1D filter issues were well studied and researchers proposed many 1D filter bank design approaches. But there are still many multidimensional filter bank design problems that need to be solved. Some methods may not well reconstruct the signal, some methods are complex and hard to implement. The simplest approach to design a multi-dimensional filter bank is to cascade 1D filter banks in the form of a tree structure where the decimation matrix is diagonal and data is processed in each dimension separately. Such systems are referred to as separable systems. However, the region of support for the filter banks might not be separable. In that case designing of filter bank gets complex. In most cases we deal with non-separable systems. A filter bank consists of an analysis stage and a synthesis stage. Each stage consists of a set of filters in parallel. The filter bank design is the design of the filters in the analysis and synthesis stages. The analysis filters divide the signal into overlapping or non-overlapping subbands depending on the application requirements. The synthesis filters should be designed to reconstruct the input signal back from the subbands when the outputs of these filters are combined. Processing is typically performed after the analysis stage. These filter banks can be designed as Infinite impulse response (IIR) or Finite impulse response (FIR). In order to reduce the data rate, downsampling and upsampling are performed in the analysis and synthesis stages, respectively. Existing approaches Below are several approaches on the design of multidimensional filter banks. For more details, please check the ORIGINAL references. Multidimensional perfect-reconstruction filter banks When it is necessary to reconstruct the divided signal back to the original one, perfect-reconstruction (PR) filter banks may be used. 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: A(z)=1/2(H0(-z) F0 (z)+H1 (-z) F1 (z)); T(z)=1/2(H0 (z) F0 (z)+H1 (z) F1 (z)), where H0 and H1 are decomposition filters, and F0 and F1 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 two-channel filter bank is relatively easy to implement. But two channels sometimes are not enough. Two-channel filter banks can be cascaded to generate multi-channel filter banks. Multidimensional directional filter banks and surfacelets 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 w1,...,wM respectively axes. After that, the input signal is further decomposed by a series of 2-D iteratively resampled checkerboard filter banks IRCli(Li)(i=2,3,...,M), where IRCli(Li)operates on 2-D slices of the input signal represented by the dimension pair (n1,ni) 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(L1+...+LN) output channels. Multidimensional oversampled 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. For IIR oversampled filter bank, perfect reconstruction have been studied in Wolovich and Kailath. 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. However, the Euclidean algorithm fails for multidimensional (MD) filters. For MD filter, we can convert the FIR representation into a polynomial representation. In Charo, 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 H(z) and G(z) of size N\times M and M\times N, where N is the number of channels and M\stackrel{\rm def}{=}|M| is the absolute value of the determinant of the sampling matrix. Also H(z) and 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: :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: :G(z)H(z)=I_. In the multidimensional case with multivariate polynomials we need to use the theory and algorithms of Gröbner bases. 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. The Gröbner-basis computation can be considered equivalently as Gaussian elimination for solving the polynomial matrix equation G(z)H(z)=I_. If we have set of polynomial vectors :\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 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 \left\{ b_{1}(z),...,b_{N}(z)\right\}, it can be obtained from \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 b_{i}(z) in terms of the original vectors h_{j}(z) through a K\times N transformation matrix W_{ij}(z) as: :b_{i}(z)=\sum_{j=1}^{N}W_{ij}(z)h_{j}(z),i=1,...,K Mapping-based multidimensional filter banks 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. 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 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 H_{0}(\xi) and G_{0}(\xi). (Note that the other two filters H_{1}(\xi) and G_{1}(\xi) are supported on complementary regions.) All the frequency regions in Figure can be critically sampled by the rectangular lattice spanned by 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. 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. Filter-bank design in the frequency domain When perfect reconstruction is not needed, the design problem can be simplified by working in frequency domain instead of using FIR filters. Note that the frequency domain method is not limited to the design of nonsubsampled filter banks (read ). Direct frequency-domain optimization 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. In Nguyen, and Lu. In Nguyen's paper, In Lee's 1999 paper, In this paper, the authors proposed that the FIR filter with 128 taps be 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. ==Directional filter banks==

Bamberger and Smith proposed a 2D directional filter bank (DFB). The DFB is efficiently implemented via an l-level tree-structured decomposition that leads to 2^{l} subbands with wedge-shaped frequency partition (see Figure). The original construction of the DFB involves modulating the input signal and using diamond-shaped filters. Moreover, in order to obtain the desired frequency partition, a complicated tree expanding rule has to be followed. As a result, the frequency regions for the resulting subbands do not follow a simple ordering as shown in Figure 9 based on the channel indices. The first advantage of DFB is that not only it is not a redundant transform but also it offers perfect reconstruction. Another advantage of DFB is its directional-selectivity and efficient structure. This advantage makes DFB an appropriate approach for many signal and image processing usage. (e.g., Laplacian pyramid, constructed the contourlets, sparse image representation, medical imaging, etc.). Directional Filter Banks can be developed to higher dimensions. It can be use in 3-D to achieve the frequency sectioning. ==Filter-bank transceiver==

Filter banks are important elements for the physical layer in wideband wireless communication, where the problem is efficient base-band processing of multiple channels. A filter-bank-based transceiver architecture eliminates the scalability and efficiency issues observed by previous schemes in case of non-contiguous channels. Appropriate filter design is necessary to reduce performance degradation caused by the filter bank. In order to obtain universally applicable designs, mild assumptions can be made about waveform format, channel statistics and the coding/decoding scheme. Both heuristic and optimal design methodologies can be used, and excellent performance is possible with low complexity as long as the transceiver operates with a reasonably large oversampling factor. A practical application is OFDM transmission, where they provide very good performance with small additional complexity. ==Notes==