Multidimensional Multirate Systems

Multidimensional Multirate systems find applications in image compression and coding. Several applications such as conversion between progressive video signals require usage of multidimensional multirate systems. In multidimensional multirate systems, the basic building blocks are decimation matrix (M) ,expansion matrix(L) and Multidimensional digital filters. The decimation and expansion matrices have dimension of D x D, where D represents the dimension. To extend the one dimensional (1-D) multirate results, there are two different ways which are based on the structure of decimation and expansion matrices. If these matrices are diagonal, separable approaches can be used, which are separable operations in each dimension. Although separable approaches might serve less complexity, non-separable methods, with non-diagonal expansion and decimation matrices, provide much better performance. The difficult part in non-separable methods is to create results in MD case by extend the 1-D case. Polyphase decomposition and maximally decimated reconstruction systems are already carried out.

MD decimation / interpolation filters derived from 1-D filters and maximally decimated filter banks are widely used and constitute important steps in the design of multidimensional multirate systems.

Basic Building Blocks of MD Multirate Systems

Decimation and interpolation are necessary steps to create multidimensional multirate systems. In the one dimensional system, decimation and interpolation can be seen in the figure.

a)1-D Decimation b)1-D Interpolation

Theoretically, explanations of decimation and interpolation are:

• Decimation (Down-sampling):

The M times decimated version of x(n) is defined as y(n)= x(Mn), where M is a nonsingular integer matrix called decimation matrix.

In the frequency domain, relation becomes

$Y[w]={\frac {1}{J(M)}}\sum _{k\mathop {\in } S}X(M(w-2\cdot \pi \cdot k))$

where k is in the range of S which is set of all integer vectors in the form of M^Tx. Also J(M) denotes |det(M)| which is also equals to number of k in the determined range.

• Expansion (Up-sampling):

The L times up sampled version of x(n) defined as Y(n)= x(L⁻¹ . n) ,where n is in the range of lattice generated by L which is L*m. The matrix L is called expansion matrix.

MD Multirate Filters Derived from 1-D Filters

In the one dimensional systems, the decimator term is used for decimation filter and expander term is used for interpolation filter. The decimator filters generally have the range of [-π / M, π / M], where M is decimation matrix. In the multidimensional decimation and expansion, the passband changes to:

$w=\pi \cdot (M-T)\cdot x$

where x in the range of [-1, 1)D

When M matrix is not diagonal, the filters are not separable. And complexity of non-separable filters is increasing with increasing number of dimension. Design procedure and example:

1. Design an one dimensional low pass filter PF(ω), whose response will be similar to the figure of 1-D frequency response .

1-D frequency response

1. Construct the separable MD filter h(s)(n) from p(n).
2. Decimate h(s)(n) by M and scale it to find h(n).

In detail, By using prototype filter P(ω), it can be defined as;

for k=D-1:

$H_{s}(w)=P(w_{0})\cdot P(w_{1})...P(w_{k})$

This is separable low pass filter and its impulse response will be;

where k=D-1

$h_{s}(n)=p(n_{0})\cdot p(n_{1})\dots p(n_{k})=\prod _{i=0}^{k}{\frac {sin{\frac {\pi \cdot n_{i}}{J(M)}}}{(\pi \cdot n_{i})}}$

Now, considering h(s)(Mn), M times decimated version of h(s)(n), since Mn = J(M) M-1 n = J(M)m, we get:

$={\frac {1}{J(M)^{D}}}\prod _{i=0}^{k}{\frac {sin(\pi \cdot m_{i})}{\pi \cdot m_{i}}}$

This process basically shows how to derive MD multirate filter from 1-D filter.

MD Maximally Decimated Filter Banks

When the number of channel is equal to J(M), this is called a maximally decimated filter bank. To analyze filter banks, polyphase decomposition is used.

Maximally Decimated Filter Bank

Polyphase decomposition:

The polyphase components of x(n) with respect to the given M,

$r_{i}(n)=x(Mn-k_{i})$

Where k_i can takes the values of k₀,k₁,…k_J(M)-1. In the z domain, X(z) becomes,

$X(z)=\sum _{k\mathop {\in } S}z^{-k_{i}}\cdot R_{i}\cdot (z^{M})$

So using polyphase decomposition, filters can be represented as,

$H_{l}(z)=\sum _{k\mathop {\in } S}z^{-k_{i}}\cdot E_{i,l}\cdot (z^{M})$

$l=0,1,\dots ,J(M)-1$