Books in black and white
 Books Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics

# - Acharya T.

Acharya T. - John Wiley & Sons, 2000. - 292 p.
ISBN 0-471-48422-9 Previous << 1 .. 35 36 37 38 39 40 < 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  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  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. Previous << 1 .. 35 36 37 38 39 40 < 41 > 42 43 44 45 46 47 .. 100 >> Next 