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

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.
• J(M) denotes |det(M)| which is also equals to number of k in the determined range.

Above expression changes in multidimensional case, In 2-D case M matrix becomes 2x2 and the region becomes parallel-ogram which is defined as:

$M[0,0]\cdot w_{0}+M[1,0]\cdot w_{1}$ will be in the range of $[-\pi ,\pi )$ and $M[0,1]\cdot w_{0}+M[1,1]\cdot w_{1}$ will be in the range of $[-\pi ,\pi )$

• 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.

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. The complexity of non-separable filters increase with increasing number of dimension. Design procedure and example:

1. Design a one dimensional low pass filter $P(w)$, whose response will be similar to the figure of 1-D frequency response .
2. Construct the separable MD filter $h^{(s)}(n)$ from $p(n)$, which is constructed from one dimensional low pass filter $P(w)$.
3. Decimate $h^{(s)}(n)$ by M and scale it to find $h(n)$.

In detail, By using prototype filter $P(w)$, MD multirate filter can be defined as;

for k=D-1, where D represents number of dimensions:

$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, where D represents number of dimensions:

$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:

$M\cdot n=J(M)\cdot M^{-1}\cdot n=J(M)\cdot 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.

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)$, transfer function of MD FIR filter, becomes,

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

where $R_{i}$ represents type II polyphase filter of the filter of $X(z)$ 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$ and Where $E_{i,l}$ represents type I polyphase filter.