Puneet Varma (Editor)

Multidimensional Multirate Systems

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
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.

Contents

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.

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 ] = 1 J ( M ) ∑ k ∈ S X ( M ( w − 2 ⋅ π ⋅ k ) )

where

  • k is in the range of S which is set of all integer vectors in the form of MTx.
  • 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 ] ⋅ w 0 + M [ 1 , 0 ] ⋅ w 1 will be in the range of [ − π , π ) and M [ 0 , 1 ] ⋅ w 0 + M [ 1 , 1 ] ⋅ w 1 will be in the range of [ − π , π )

    • Expansion (Up-sampling):

    The L times up sampled version of x(n) defined as Y(n)= x(L−1 . 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 = π ⋅ ( M − T ) ⋅ 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 ) ⋅ 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 ) ⋅ p ( n 1 ) … p ( n k ) = ∏ i = 0 k s i n π ⋅ n i J ( M ) ( π ⋅ n i )

    Now, considering h ( s ) ( M n ) , M times decimated version of h ( s ) ( n ) , since:

    M ⋅ n = J ( M ) ⋅ M − 1 ⋅ n = J ( M ) ⋅ m

    we get:

    = 1 J ( M ) D ∏ i = 0 k s i n ( π ⋅ m i ) π ⋅ 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.

    Polyphase decomposition:

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

    r i ( n ) = x ( M n − k i )

    Where ki can takes the values of k0,k1,…kJ(M)-1. In the z domain, X ( z ) , transfer function of MD FIR filter, becomes,

    X ( z ) = ∑ k ∈ S z − k i ⋅ R i ⋅ ( 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 ) = ∑ k ∈ S z − k i ⋅ E i , l ⋅ ( z M )

    l = 0 , 1 , … , J ( M ) − 1 and Where E i , l represents type I polyphase filter.

    References

    Multidimensional Multirate Systems Wikipedia
    (Text) CC BY-SA