# - Acharya T.

ISBN 0-471-48422-9

**Download**(direct link)

**:**

**41**> 42 43 44 45 46 47 .. 100 >> Next

a{z) = b(z)q(z) + r(z). (4-26)

4.4.2 Euclidean Algorithm for Laurent Polynomials

The Euclidean algorithm can be used to find the greatest common divisor (gcd) of two Laurent polynomials a(z) and b(s). If b(z) ^ 0 and |a(z)| > |6(z)|, we can state the algorithm as follows. By operations ‘/’ and ‘%’ in the algorithm, we mean to find the quotient and remainder of the division.

begin

end.

k = 0;

ak{z) = a(z); bk{z) = b{z); while bk(z) ^ 0 do {

ûfc+l = frfc(-z),

6fc+i = ak{z)%bk{z)\ qk+1 = ak{z)/bk{z)\ k = k + 1

}

gcd = ak(z);

^From the above algorithm, it is clear that the greatest common divisor (gcd) of a(z) and b(z) is an, where n is the smallest integer for which bn(z) = 0. The number of iterations by the while loop in the above algorithms is bounded by n < \n(z) \ + 1. From the above algorithm, we can establish that

üi+l(z) ' 0 1 ' ai{z)

_ bi+i{z) . 1 -<li{z) j bi{z) _

(4.27)

which can be rewritten as

ai(z) qi(z) 1 ^i + l (-2)

. bi(Z) . 1 0 . bl+l(z) _

(4.28)

Thus,

94

INTRODUCTION TO DISCRETE WAVELET TRANSFORM

a0(z) ' 9o(z) 1 ' ai(z) ’ Qo{z) 1 ’ Qi{z) 1 ' d2(z)

_ b0(z) _ 1 0 1 0 1 0 . M*) .

(4.29)

Since ao(z) — a(z) and b0(z) = b(z), we obtain the following factorization after iterating the above equation:

a(z)

b(z)

n

fc = l

Qi(z) 1 1 0

&n(z)

0

(4.30)

The above factorization algorithm will be used in Section 4.4.4.3 to show how the polyphase matrix for a filter pair can be factorized into lifting sequences.

4.4.3 Perfect Reconstruction and Polyphase Representation of Filters

For any practical signal transformation technique from one domain to another, the transformation should be reversible. For example, the Fourier transform converts a signal from the time domain to the frequency domain. When inverse Fourier transform is applied on the signal in frequency domain, the signal is converted back to the time domain. Ideally, if there is no additional processing or manipulation done in the frequency domain data after the transformation (i.e., if there is no loss of data or information at any form), the reconstructed signal after inverse Fourier transform should be an exact replica of the original one. The same principle applies for the DWT as well. Hence we need to choose the filter bank for DWT in such a way that perfect reconstruction is achieved. For the filter bank in Figure 4.6, the conditions for perfect reconstruction of a signal [14] are given by

h{z)h{z~l) + g(z)g(z~l) = 2 Ï

. > (4-31)

h(z)h(-z~l) + g(z)g(-z~l) = 0 J

where h(z) is the ^-transform of the FIR filter h.

The polyphase representation of a filter h is expressed as

h(z) = he(z2) + z~lh0(z2) (4-32)

where he contains the even filter coefficients and ha contains the odd filter coefficients of the FIR filter h. In general by polyphase representation, we mean to split a sequence into several subsequences for possible parallel processing of the subsequences. From Eq. 4.32, we can intuitively split the filter into two smaller filters — one (he) with the even filter coefficients and the other (h0) with the odd filter coefficients delayed by a clock cycle, whose Z-transform can be expressed as

LIFTING IMPLEMENTATION OF THE DISCRETE WAVELET TRANSFORM

95

he{z) = h2kz k, h0(z) = Y h2k+\z' k k

and we can define a polyphase matrix for the filter h as

P(z) =

he(z) ge(z) h0(z) g0(z)

(4.33)

(4.34)

Based on the discussion above, the polyphase representation of the filters g{z), h(z), and g(z) is expressed as follows:

g(z) = ge(z2) + z 1g0(z2) ' h(z) = he{z2) 4- z~lh0(z2) q(z) = 9e{z2) -f z~1ga(z2) y

(4.35)

Based on the above formulation, we can define two polyphase matrices as follows:

he(z) h0(z) 9e(z) 9o(z)

P(z) =

he(z) ge(z) h0(z) ga(z)

(4.36)

Often the polyphase matrix P(z) is called the dual of the polyphase matrix P(z). For perfect reconstruction, these two polyphase matrices P(z) and P(z) satisfy the following relation in Eq. 4.37,

P(z)P(z~1)

l\T

(4.37)

where I is the 2x2 identity matrix. Now based on the above formulation, the wavelet transform in terms of the polyphase matrix can be expressed as

Vl(z)

Vh(z)

= P(z)

Xe(z)

z~lXo(z)

for the forward DWT and

xe(z)

~1Xo(z)

P(z)

Vl{z)

Vh(z)

(4.38)

(4.39)

for the inverse DWT.

If the determinant of the polyphase matrix P(z) is unity (i.e., |-P(z)| = he(z)g0(z) — ge(z)h0(z) = 1), then the matrix P(z) is invertible. Hence we can apply the Cramer’s rule [14] in Eq. 4.37 as follows:

P(z~l) =P(z)-1

9o{z) -ge(z) -h0(z) he(z)

\P(z)\

9o(z) -ge(z) —h0(z) he(z)

(4.40)

96

INTRODUCTION TO DISCRETE WAVELET TRANSFORM

From Eq. 4.36, we find that

(4.41)

From Eqs. 4.40 and 4.41, we can conclude that

he{z) = 5o(2-1),

h0(z) = ~9e{z_1),

ge(z) = -hoiz-1), 9o(z) = heiz-1)

(4.42)

which implies that

h(z) = -z lg{-z J), g(z) = z lh{-z x)

(4.43)

and hence

h(z) = —z lg{-z x), g(z) = z lh(-z J). (4.44)

When the determinant of P(z) is unity, the synthesis filter pair (h,g) is called complementary and so is the analysis filter pair (h,g). When {h,g)=(h,g), the wavelet transformation is called orthogonal; otherwise it is biorthogonal.

**41**> 42 43 44 45 46 47 .. 100 >> Next