Finite-Length Sequences and the DWT Matrix2.52002/01/142003/01/17PhilSchniterschniter@ee.eng.ohio-state.eduCharletReedstromcharlet@rice.eduPhilSchniterschniter@ee.eng.ohio-state.educircular convolutionDWTDWT matrixfast circular convolutionlinear convolutionmultiresolutionunitary matrixwaveletsDiscrete-time implementation of the DWT.
The wavelet transform, viewed from a filterbank perspective,
consists of iterated 2-channel analysis stages like the one in
.
First consider a very long (i.e., practically infinite-length)
sequence
ckmm. For every pair of input samples
ck2nck2n1 that enter the
kth
filterbank stage, exactly one pair of output samples
ck+1ndk+1n are generated. In other words, the number of output
equals the number of input during a fixed time interval. This
property is convenient from a real-time processing
perspective.
For a short sequence
ckmm0…M1, however, linear convolution requires that we make
an assumption about the tails of our finite-length sequence.
One assumption could be
mm0…M1ckm0
In this case, the linear convolution implies that
M nonzero inputs yield
MN21 outputs from each branch, for a total of
2MN21MN2M outputs. Here we have assumed that both
Hz and
Gz have impulse response lengths of
N2, and that M and
N are both even. The fact that
each filterbank stage produces more outputs than inputs is
very disadvantageous in many applications.
A more convenient assumption regarding the tails of
ckmm0…M1 is that the data outside of the time window
0…M1 is a cyclic extension of data inside the time
window. In other words, given a
length-M sequence, the points
outside the sequence are related to
points inside the sequences via
ckmckmM
Recall that a linear convolution with an
M-cyclic input is equivalent to
a circular convolution with one
M-sample period of the input
sequences. Furthermore, the output of this circular
convolution is itself M-cyclic,
implying our 2-downsampled branch outputs are cyclic with
period
M2. Thus, given an
M-length input sequence, the
total filterbank output consists of exactly
M values.
It is instructive to write the circular-convolution analysis
fiterbank operation in matrix form. In we give an example for filter length
N4, sequence length
N8, and causal synthesis filters
Hz and
Gz.
ck+10ck+11ck+12ck+13dk+10dk+11dk+12dk+13h0h1h2h3000000h0h1h2h3000000h0h1h2h3h2h30000h0h1g0g1g2g3000000g0g1g2g3000000g0g1g2g3g2g30000g0g1ck0ck1ck2ck3ck4ck5ck6ck7
where
ck+1dk+1ck+10ck+11ck+12ck+13dk+10dk+11dk+12dk+13HMGMh0h1h2h3000000h0h1h2h3000000h0h1h2h3h2h30000h0h1g0g1g2g3000000g0g1g2g3000000g0g1g2g3g2g30000g0g1ckck0ck1ck2ck3ck4ck5ck6ck7
The matrices
HM
and
GM
have interesting properties. For example, the conditions
δmnnhnhn2mgn-1nhN1n
imply that
HMGMHMGMHMGMHMGMIM
where
IM
denotes the
MxM
identity matrix. Thus, it makes sense to define the
MxMDWT matrix as
TMHMGM
whose transpose constitutes the
MxMinverse DWT matrix:
TMTM
Since the synthesis filterbank ()
gives perfect reconstruction, and since the cascade of matrix
operations
TMTM also corresponds to perfect reconstruction, we
expect that the matrix operation
TM describes the action of the synthesis filterbank.
This is readily confirmed by writing the upsampled circular
convolutions in matrix form:
ck0ck1ck2ck3ck4ck5ck6ck7h000h2g000g2h100h3g100g3h2h000g2g000h3h100g3g1000h2h000g2g000h3h100g3g1000h2h000g2g000h3h100g3g1ck+10ck+11ck+12ck+13dk+10dk+11dk+12dk+13
where
HMGMTMh000h2g000g2h100h3g100g3h2h000g2g000h3h100g3g1000h2h000g2g000h3h100g3g1000h2h000g2g000h3h100g3g1
So far we have concentrated on one stage in the wavelet
decomposition; a two-stage decomposition is illustrated in
.
The two-stage analysis operation (assuming circular
convolution) can be expressed in matrix form as
ck+2dk+2dk+1TM200IM2ck+1dk+1TM200IM2TMck
Similarly, a three-stage analysis could be implemented via
ck+3dk+3dk+2dk+1TM4000IM4000IM2TM200IM2TMck
It should now be evident how to extend this procedure to
3 stages. As noted earlier, the corresponding
synthesis operations are accomplished by transposing the
matrix products used in the analysis.