Skip to content Skip to navigation

Connexions

You are here: Home » Content » Filter Banks and the Discrete Wavelet Transform

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Filter Banks and the Discrete Wavelet Transform

Module by: Ramesh Gopinath. E-mail the author

In many applications, one never has to deal directly with the scaling functions or wavelets. Only the coefficients h(n)h(n) and h1(n)h1(n) in the defining equations (Reference) and (Reference) and c(k)c(k) and dj(k)dj(k) in the expansions (Reference), (Reference), and (Reference) need be considered, and they can be viewed as digital filters and digital signals respectively [7], [26]. While it is possible to develop most of the results of wavelet theory using only filter banks, we feel that both the signal expansion point of view and the filter bank point of view are necessary for a real understanding of this new tool.

Analysis – From Fine Scale to Coarse Scale

In order to work directly with the wavelet transform coefficients, we will derive the relationship between the expansion coefficients at a lower scale level in terms of those at a higher scale. Starting with the basic recursion equation from (Reference)

φ ( t ) = ∑ n h ( n ) 2 φ ( 2 t - n ) φ ( t ) = ∑ n h ( n ) 2 φ ( 2 t - n )
(1)

and assuming a unique solution exists, we scale and translate the time variable to give

φ ( 2 j t - k ) = ∑ n h ( n ) 2 φ ( 2 ( 2 j t - k ) - n ) = ∑ n h ( n ) 2 φ ( 2 j + 1 t - 2 k - n ) φ ( 2 j t - k ) = ∑ n h ( n ) 2 φ ( 2 ( 2 j t - k ) - n ) = ∑ n h ( n ) 2 φ ( 2 j + 1 t - 2 k - n )
(2)

which, after changing variables m=2k+nm=2k+n, becomes

φ ( 2 j t - k ) = ∑ m h ( m - 2 k ) 2 φ ( 2 j + 1 t - m ) . φ ( 2 j t - k ) = ∑ m h ( m - 2 k ) 2 φ ( 2 j + 1 t - m ) .
(3)

If we denote VjVj as

V j = Span k { 2 j / 2 φ ( 2 j t - k ) } V j = Span k { 2 j / 2 φ ( 2 j t - k ) }
(4)

then

f ( t ) ∈ V j + 1 ⇒ f ( t ) = ∑ k c j + 1 ( k ) 2 ( j + 1 ) / 2 φ ( 2 j + 1 t - k ) f ( t ) ∈ V j + 1 ⇒ f ( t ) = ∑ k c j + 1 ( k ) 2 ( j + 1 ) / 2 φ ( 2 j + 1 t - k )
(5)

is expressible at a scale of j+1j+1 with scaling functions only and no wavelets. At one scale lower resolution, wavelets are necessary for the “detail" not available at a scale of jj. We have

f ( t ) = ∑ k c j ( k ) 2 j / 2 φ ( 2 j t - k ) + ∑ k d j ( k ) 2 j / 2 ψ ( 2 j t - k ) f ( t ) = ∑ k c j ( k ) 2 j / 2 φ ( 2 j t - k ) + ∑ k d j ( k ) 2 j / 2 ψ ( 2 j t - k )
(6)

where the 2j/22j/2 terms maintain the unity norm of the basis functions at various scales. If φj,k(t)φj,k(t) and ψj,k(t)ψj,k(t) are orthonormal or a tight frame, the jj level scaling coefficients are found by taking the inner product

c j ( k ) = 〈 f ( t ) , φ j , k ( t ) 〉 = ∫ f ( t ) 2 j / 2 φ ( 2 j t - k ) d t c j ( k ) = 〈 f ( t ) , φ j , k ( t ) 〉 = ∫ f ( t ) 2 j / 2 φ ( 2 j t - k ) d t
(7)

which, by using Equation 3 and interchanging the sum and integral, can be written as

c j ( k ) = ∑ m h ( m - 2 k ) ∫ f ( t ) 2 ( j + 1 ) / 2 φ ( 2 j + 1 t - m ) d t c j ( k ) = ∑ m h ( m - 2 k ) ∫ f ( t ) 2 ( j + 1 ) / 2 φ ( 2 j + 1 t - m ) d t
(8)

but the integral is the inner product with the scaling function at a scale of j+1j+1 giving

c j ( k ) = ∑ m h ( m - 2 k ) c j + 1 ( m ) . c j ( k ) = ∑ m h ( m - 2 k ) c j + 1 ( m ) .
(9)

The corresponding relationship for the wavelet coefficients is

d j ( k ) = ∑ m h 1 ( m - 2 k ) c j + 1 ( m ) . d j ( k ) = ∑ m h 1 ( m - 2 k ) c j + 1 ( m ) .
(10)

Filtering and Down-Sampling or Decimating

In the discipline of digital signal processing, the “filtering" of a sequence of numbers (the input signal) is achieved by convolving the sequence with another set of numbers called the filter coefficients, taps, weights, or impulse response. This makes intuitive sense if you think of a moving average with the coefficients being the weights. For an input sequence x(n)x(n) and filter coefficients h(n)h(n), the output sequence y(n)y(n) is given by

y ( n ) = ∑ k = 0 N - 1 h ( k ) x ( n - k ) y ( n ) = ∑ k = 0 N - 1 h ( k ) x ( n - k )
(11)

There is a large literature on digital filters and how to design them [19], [18]. If the number of filter coefficients NN is finite, the filter is called a Finite Impulse Response (FIR) filter. If the number is infinite, it is called an Infinite Impulse (IIR) filter. The design problem is the choice of the h(n)h(n) to obtain some desired effect, often to remove noise or separate signals [18], [19].

Figure 1: The Down Sampler of Decimator
The Down Sampler of Decimator

In multirate digital filters, there is an assumed relation between the integer index nn in the signal x(n)x(n) and time. Often the sequence of numbers are simply evenly spaced samples of a function of time. Two basic operations in multirate filters are the down-sampler and the up-sampler. The down-sampler (sometimes simply called a sampler or a decimator) takes a signal x(n)x(n) as an input and produces an output of y(n)=x(2n)y(n)=x(2n). This is symbolically shown in Figure 1. In some cases, the down-sampling is by a factor other than two and in some cases, the output is the odd index terms y(n)=x(2n+1)y(n)=x(2n+1), but this will be explicitly stated if it is important.

In down-sampling, there is clearly the possibility of losing information since half of the data is discarded. The effect in the frequency domain (Fourier transform) is called aliasing which states that the result of this loss of information is a mixing up of frequency components [19], [18]. Only if the original signal is band-limited (half of the Fourier coefficients are zero) is there no loss of information caused by down-sampling.

We talk about digital filtering and down-sampling because that is exactly what Equation 9 and Equation 10 do. These equations show that the scaling and wavelet coefficients at different levels of scale can be obtained by convolving the expansion coefficients at scale jj by the time-reversed recursion coefficients h(-n)h(-n) and h1(-n)h1(-n) then down-sampling or decimating (taking every other term, the even terms) to give the expansion coefficients at the next level of j-1j-1. In other words, the scale-jj coefficients are “filtered" by two FIR digital filters with coefficients h(-n)h(-n) and h1(-n)h1(-n) after which down-sampling gives the next coarser scaling and wavelet coefficients. These structures implement Mallat's algorithm [16], [15] and have been developed in the engineering literature on filter banks, quadrature mirror filters (QMF), conjugate filters, and perfect reconstruction filter banks [20], [21], [27], [29], [28], [25], [26] and are expanded somewhat in Chapter: Filter Banks and Transmultiplexers of this book. Mallat, Daubechies, and others showed the relation of wavelet coefficient calculation and filter banks. The implementation of Equation 9 and Equation 10 is illustrated in Figure 2 where the down-pointing arrows denote a decimation or down-sampling by two and the other boxes denote FIR filtering or a convolution by h(-n)h(-n) or h1(-n)h1(-n). To ease notation, we use both h(n)h(n) and h0(n)h0(n) to denote the scaling function coefficients for the dilation equation (Reference).

Figure 2: Two-Band Analysis Bank
Two-Band Analysis Bank
Figure 3: Two-Stage Two-Band Analysis Tree
Two-Stage Two-Band Analysis Tree

As we will see in Chapter: The Scaling Function and Scaling Coefficients, Wavelet and Wavelet Coefficients , the FIR filter implemented by h(-n)h(-n) is a lowpass filter, and the one implemented by h1(-n)h1(-n) is a highpass filter. Note the average number of data points out of this system is the same as the number in. The number is doubled by having two filters; then it is halved by the decimation back to the original number. This means there is the possibility that no information has been lost and it will be possible to completely recover the original signal. As we shall see, that is indeed the case. The aliasing occurring in the upper bank can be “undone" or cancelled by using the signal from the lower bank. This is the idea behind perfect reconstruction in filter bank theory [26], [6].

This splitting, filtering, and decimation can be repeated on the scaling coefficients to give the two-scale structure in Figure 3. Repeating this on the scaling coefficients is called iterating the filter bank. Iterating the filter bank again gives us the three-scale structure in Figure 4.

The frequency response of a digital filter is the discrete-time Fourier transform of its impulse response (coefficients) h(n)h(n). That is given by

H ( ω ) = ∑ n = - ∞ ∞ h ( n ) e i ω n . H ( ω ) = ∑ n = - ∞ ∞ h ( n ) e i ω n .
(12)

The magnitude of this complex-valued function gives the ratio of the output to the input of the filter for a sampled sinusoid at a frequency of ωω in radians per seconds. The angle of H(ω)H(ω) is the phase shift between the output and input.

The first stage of two banks divides the spectrum of cj+1(k)cj+1(k) into a lowpass and highpass band, resulting in the scaling coefficients and wavelet coefficients at lower scale cj(k)cj(k) and dj(k)dj(k). The second stage then divides that lowpass band into another lower lowpass band and a bandpass band. The first stage divides the spectrum into two equal parts. The second stage divides the lower half into quarters and so on. This results in a logarithmic set of bandwidths as illustrated in Figure 5. These are called “constant-Q" filters in filter bank language because the ratio of the band width to the center frequency of the band is constant. It is also interesting to note that a musical scale defines octaves in a similar way and that the ear responds to frequencies in a similar logarithmic fashion.

For any practical signal that is bandlimited, there will be an upper scale j=Jj=J, above which the wavelet coefficients, dj(k)dj(k), are negligibly small [9]. By starting with a high resolution description of a signal in terms of the scaling coefficients cJcJ, the analysis tree calculates the DWT

down to as low a resolution, j=j0j=j0, as desired by having J-j0J-j0 stages. So, for f(t)∈VJf(t)∈VJ, using (Reference) we have

f ( t ) = ∑ k c J ( k ) φ J , k ( t ) = ∑ k c J - 1 ( k ) φ J - 1 , k ( t ) + ∑ k d J - 1 ( k ) ψ J - 1 , k ( t ) f ( t ) = ∑ k c J - 2 ( k ) φ J - 2 , k ( t ) + ∑ k ∑ j = J - 2 J - 1 d j ( k ) ψ j , k ( t ) f ( t ) = ∑ k c j 0 ( k ) φ j 0 , k ( t ) + ∑ k ∑ j = j 0 J - 1 d j ( k ) ψ j , k ( t ) f ( t ) = ∑ k c J ( k ) φ J , k ( t ) = ∑ k c J - 1 ( k ) φ J - 1 , k ( t ) + ∑ k d J - 1 ( k ) ψ J - 1 , k ( t ) f ( t ) = ∑ k c J - 2 ( k ) φ J - 2 , k ( t ) + ∑ k ∑ j = J - 2 J - 1 d j ( k ) ψ j , k ( t ) f ( t ) = ∑ k c j 0 ( k ) φ j 0 , k ( t ) + ∑ k ∑ j = j 0 J - 1 d j ( k ) ψ j , k ( t )
(13)

which is a finite scale version of (Reference). We will discuss the choice of j0j0 and JJ further in Chapter: Calculation of the Discrete Wavelet Transform.

Figure 4: Three-Stage Two-Band Analysis Tree
Three-Stage Two-Band Analysis Tree
Figure 5: Frequency Bands for the Analysis Tree
Frequency Bands for the Analysis Tree

Synthesis – From Coarse Scale to Fine Scale

As one would expect, a reconstruction of the original fine scale coefficients of the signal can be made from a combination of the scaling function and wavelet coefficients at a coarse resolution. This is derived by considering a signal in the j+1j+1 scaling function space f(t)∈Vj+1f(t)∈Vj+1. This function can be written in terms of the scaling function as

f ( t ) = ∑ k c j + 1 ( k ) 2 ( j + 1 ) / 2 φ ( 2 j + 1 t - k ) f ( t ) = ∑ k c j + 1 ( k ) 2 ( j + 1 ) / 2 φ ( 2 j + 1 t - k )
(14)

or in terms of the next scale (which also requires wavelets) as

f ( t ) = ∑ k c j ( k ) 2 j / 2 φ ( 2 j t - k ) + ∑ k d j ( k ) 2 j / 2 ψ ( 2 j t - k ) . f ( t ) = ∑ k c j ( k ) 2 j / 2 φ ( 2 j t - k ) + ∑ k d j ( k ) 2 j / 2 ψ ( 2 j t - k ) .
(15)

Substituting Equation 1 and (Reference) into Equation 15 gives

f ( t ) = ∑ k c j ( k ) ∑ n h ( n ) 2 ( j + 1 ) / 2 φ ( 2 j + 1 t - 2 k - n ) + ∑ k d j ( k ) ∑ n h 1 ( n ) 2 ( j + 1 ) / 2 φ ( 2 j + 1 t - 2 k - n ) . f ( t ) = ∑ k c j ( k ) ∑ n h ( n ) 2 ( j + 1 ) / 2 φ ( 2 j + 1 t - 2 k - n ) + ∑ k d j ( k ) ∑ n h 1 ( n ) 2 ( j + 1 ) / 2 φ ( 2 j + 1 t - 2 k - n ) .
(16)

Because all of these functions are orthonormal, multiplying Equation 14 and Equation 16 by φ(2j+1t-k')φ(2j+1t-k') and integrating evaluates the coefficient as

c j + 1 ( k ) = ∑ m c j ( m ) h ( k - 2 m ) + ∑ m d j ( m ) h 1 ( k - 2 m ) . c j + 1 ( k ) = ∑ m c j ( m ) h ( k - 2 m ) + ∑ m d j ( m ) h 1 ( k - 2 m ) .
(17)

Filtering and Up-Sampling or Stretching

For synthesis in the filter bank we have a sequence of first up-sampling or stretching, then filtering. This means that the input to the filter has zeros inserted between each of the original terms. In other words,

y ( 2 n ) = x ( n ) and y ( 2 n + 1 ) = 0 y ( 2 n ) = x ( n ) and y ( 2 n + 1 ) = 0
(18)

where the input signal is stretched to twice its original length and zeros are inserted. Clearly this up-sampling or stretching could be done with factors other than two, and the two equation above could have the x(n)x(n) and 0 reversed. It is also clear that up-sampling does not lose any information. If you first up-sample then down-sample, you are back where you started. However, if you first down-sample then up-sample, you are not generally back where you started.

Our reason for discussing filtering and up-sampling here is that is exactly what the synthesis operation Equation 17 does. This equation is evaluated by up-sampling the jj scale coefficient sequence cj(k)cj(k), which means double its length by inserting zeros between each term, then convolving it with the scaling coefficients h(n)h(n). The same is done to the jj level wavelet coefficient sequence and the results are added to give the j+1j+1 level scaling function coefficients. This structure is illustrated in Figure 6 where g0(n)=h(n)g0(n)=h(n) and g1(n)=h1(n)g1(n)=h1(n). This combining process can be continued to any level by combining the appropriate scale wavelet coefficients. The resulting two-scale tree is shown in Figure 7.

Figure 6: Two-Band Synthesis Bank
Two-Band Synthesis Bank
Figure 7: Two-Stage Two-Band Synthesis Tree
Two-Stage Two-Band Synthesis Tree

Input Coefficients

One might wonder how the input set of scaling coefficients cj+1cj+1 are obtained from the signal to use in the systems of Figure 2 and Figure 3. For high enough scale, the scaling functions act as “delta functions" with the inner product to calculate the high scale coefficients as simply a sampling of f(t)f(t)[8], [17]. If the samples of f(t)f(t) are above the Nyquist rate, they are good approximations to the scaling coefficients at that scale, meaning no wavelet coefficients are necessary at that scale. This approximation is particularly good if moments of the scaling function are zero or small. These ideas are further explained in Section: Approximation of Scaling Coefficients by Samples of the Signal and Chapter: Calculation of the Discrete Wavelet Transform.

An alternative approach is to “prefilter" the signal samples to make them a better approximation to the expansion coefficients. This is discussed in [22].

This set of analysis and synthesis operations is known as Mallat's algorithm [16], [15]. The analysis filter bank efficiently calculates the DWT using banks of digital filters and down-samplers, and the synthesis filter bank calculates the inverse DWT to reconstruct the signal from the transform. Although presented here as a method of calculating the DWT, the filter bank description also gives insight into the transform itself and suggests modifications and generalizations that would be difficult to see directly from the wavelet expansion point of view. Filter banks will be used more extensively in the remainder of this book. A more general development of filter banks is presented in Section: Multiplicity-M (M-Band) Scaling Functions and Wavelets.

Although a pure wavelet expansion is possible as indicated in (Reference) and (Reference), properties of the wavelet are best developed and understood through the scaling function. This is certainly true if the scaling function has compact support because then the wavelet is composed of a finite sum of scaling functions given in (Reference).

In a practical situation where the wavelet expansion or transform is being used as a computational tool in signal processing or numerical analysis, the expansion can be made finite. If the basis functions have finite support, only a finite number of additions over kk are necessary. If the scaling function is included as indicated in (Reference) or Equation 6, the lower limit on the summation over jj is finite. If the signal is essentially bandlimited, there is a scale above which there is little or no energy and the upper limit can be made finite. That is described in Chapter: Calculation of the Discrete Wavelet Transform.

Lattices and Lifting

An alternative to using the basic two-band tree-structured filter bank is a lattice-structured filter bank. Because of the relationship between the scaling filter h(n)h(n) and the wavelet filter h1(h)h1(h) given in (Reference), some of the calculation can be done together with a significant savings in arithmetic. This is developed in Chapter: Calculation of the Discrete Wavelet Transform [26].

Still another approach to the calculation of discrete wavelet transforms and to the calculations of the scaling functions and wavelets themselves is called “lifting." Although it is related to several other schemes [13], [14], [4], [11], this idea was first explained by Wim Sweldens as a time-domain construction based on interpolation [23]. Lifting does not use Fourier methods and can be applied to more general problems (e.g., nonuniform sampling) than the approach in this chapter. It was first applied to the biorthogonal system [24] and then extended to orthogonal systems [5]. The application of lifting to biorthogonal is introduced in Section: Biorthogonal Wavelet Systems later in this book. Implementations based on lifting also achieve the same improvement in arithmetic efficiency as the lattice structure do.

Different Points of View

Multiresolution versus Time-Frequency Analysis

The development of wavelet decomposition and the DWT has thus far been in terms of multiresolution where the higher scale wavelet components are considered the “detail" on a lower scale signal or image. This is indeed a powerful point of view and an accurate model for many signals and images, but there are other cases where the components of a composite signal at different scales and/or time are independent or, at least, not details of each other. If you think of a musical score as a wavelet decomposition, the higher frequency notes are not details on a lower frequency note; they are independent notes. This second point of view is more one of the time-frequency or time-scale analysis methods [2], [3], [10], [1], [12] and may be better developed with wavelet packets (see Section: Wavelet Packets), M-band wavelets (see Section: Multiplicity-M (M-band) Scaling Functions and Wavelets), or a redundant representation (see Section: Overcomplete Representations, Frames, Redundant Transforms, and Adaptive Bases), but would still be implemented by some sort of filter bank.

Periodic versus Nonperiodic Discrete Wavelet Transforms

Unlike the Fourier series, the DWT can be formulated as a periodic or a nonperiodic transform. Up until now, we have considered a nonperiodic series expansion (Reference) over -∞<t<∞-∞<t<∞ with the calculations made by the filter banks being an on-going string of coefficients at each of the scales. If the input to the filter bank has a certain rate, the output at the next lower scale will be two sequences, one of scaling function coefficients cj-1,k-1cj-1,k-1 and one of wavelet coefficients dj-1,k-1dj-1,k-1, each, after down-sampling, being at half the rate of the input. At the next lower scale, the same process is done on the scaling coefficients to give a total output of three strings, one at half rate and two at quarter rate. In other words, the calculation of the wavelet transform coefficients is a multirate filter bank producing sequences of coefficients at different rates but with the average number at any stage being the same. This approach can be applied to any signal, finite or infinite in length, periodic or nonperiodic. Note that while the average output rate is the same as the average input rate, the number of output coefficients is greater than the number of input coefficients because the length of the output of convolution is greater than the length of the input.

An alternative formulation that can be applied to finite duration signals or periodic signals (much as the Fourier series) is to make all of the filter bank filters cyclic or periodic convolution which is defined by

y ( n ) = ∑ ℓ = 0 N - 1 h ( ℓ ) x ( n - ℓ ) , y ( n ) = ∑ ℓ = 0 N - 1 h ( ℓ ) x ( n - ℓ ) ,
(19)

for n,ℓ=0,1,⋯,N-1n,ℓ=0,1,⋯,N-1 and all indices and arguments are evaluated modulo NN. For a length NN input at scale j=Jj=J, we have after one stage two length N/2N/2 sequences, after two stages, one length N/2N/2 and two length N/4N/4 sequences, and so on. If N=2JN=2J, this can be repeated JJ times with the last stage being length one; one scaling function coefficient and one wavelet coefficient. An example of how the periodic DWT of a length 8 can be seen Figure 8.

Figure 8: The length-8 DWT vector
c j (k) c j (k) d j (k) d j (k) d j+1 (k) d j+1 (k+1) d j+1 (k) d j+1 (k+1) d j+2 (k) d j+2 (k+1) d j+2 (k+2) d j+2 (k+3) d j+2 (k) d j+2 (k+1) d j+2 (k+2) d j+2 (k+3)

The details of this periodic approach are developed in Chapter: Calculation of the Discrete Wavelet Transform showing the aliasing that takes place in this system because of the cyclic convolution Equation 19. This formulation is particularly clean because there are the same number of terms in the transform as in the signal. It can be represented by a square matrix with a simple inverse that has interesting structure. It can be efficiently calculated by an FFT although that is not needed for most applications.

For most of the theoretical developments or for conceptual purposes, there is little difference in these two formulations. However, for actual calculations and in applications, you should make sure you know which one you want or which one your software package calculates. As for the Fourier case, you can use the periodic form to calculate the nonperiodic transform by padding the signal with zeros but that wastes some of the efficiency that the periodic formulation was set up to provide.

The Discrete Wavelet Transform versus the Discrete-Time Wavelet Transform

Two more points of view concern looking at the signal processing methods in this book as based on an expansion of a signal or on multirate digital filtering. One can look at Mallat's algorithm either as a way of calculating expansion coefficients at various scales or as a filter bank for processing discrete-time signals. The first is analogous to use of the Fourier series (FS) where a continuous function is transformed into a discrete sequence of coefficients. The second is analogous to the discrete Fourier transform (DFT) where a discrete function is transformed into a discrete function. Indeed, the DFT (through the FFT) is often used to calculate the Fourier series coefficients, but care must be taken to avoid or minimize aliasing. The difference in these views comes partly from the background of the various researchers (i.e., whether they are “wavelet people" or “filter bank people"). However, there are subtle differences between using the series expansion of the signal (using the discrete wavelet transform (DWT)) and using a multirate digital filter bank on samples of the signal (using the discrete-time wavelet transform (DTWT)). Generally, using both views gives more insight into a problem than either achieves alone. The series expansion is the main approach of this book but filter banks and the DTWT are also developed in Section: Discrete Multiresolution Analysis and the Discrete-Time wavelet Transform and Chapter: Filter Banks and Transmultiplexers .

Numerical Complexity of the Discrete Wavelet Transform

Analysis of the number of mathematical operations (floating-point multiplications and additions) shows that calculating the DTWT of a length-NN sequence of numbers using Mallat's algorithm with filter banks requires O(N)O(N) operations. In other words, the number of operations is linear with the length of the signal. What is more, the constant of linearity is relatively small. This is in contrast to the FFT algorithm for calculating the DFT where the complexity is O(Nlog(N))O(Nlog(N)) or calculating a DFT directly requires O(N2)O(N2) operations. It is often said that the FFT algorithm is based on a “divide and conquer" scheme, but that is misleading. The process is better described as a “organize and share" scheme. The efficiency (in fact, optimal efficiency) is based on organizing the calculations so that redundant operations can be shared. The cascaded filtering (convolution) and down-sampling of Mallat's algorithm do the same thing.

One should not make too much of this difference between the complexity of the FFT and DTWT. It comes from the DTWT having a logarithmic division of frequency bands and the FFT having a uniform division. This logarithmic scale is appropriate for many signals but if a uniform division is used for the wavelet system such as is done for wavelet packets (see Section: Wavelet Packets) or the redundant DWT (see Section: Overcomplete Representations, Frames, Redundant Transforms, and Adaptive Bases), the complexity of the wavelet system becomes O(Nlog(N))O(Nlog(N)).

If you are interested in more details of the discrete wavelet transform and the discrete-time wavelet transform, relations between them, methods of calculating them, further properties of them, or examples, see Section: Discrete Multiresolution Analysis, the Discrete-Time Wavelet and Chapter: Calculation of the Discrete Wavelet Transform.

References

  1. (1992). Time-Frequency Signal Analysis. [Result of 1990 Special Converence on Time-Frequency Analysis, Gold Coast, Australia.]. New York: Wiley, Halsted Press.
  2. Cohen, L. (1989). Time-frequency Distributions - A Review. Proceedings of the IEEE, 77(7), 941–981.
  3. Cohen, Leon. (1995). Time–Frequency Analysis. Upper Saddle River, NJ: Prentice Hall.
  4. Dyck, R. E. Van and Marshall, Jr., T. G. (1993). Ladder Realizations of Fast Subband/VQ Coders with Diamond Structures. In Proceedings of IEEE International Symposium on Circuits and Systems. (p. III:177–180). ISCAS
  5. Daubechies, Ingrid and Sweldens, Wim. (1996, September). Factoring Wavelet Transforms into Lifting Steps. [Preprint]. Technical report. NJ: Princeton and Lucent Technologies.
  6. Fliege, F. J. (1994). Multirate Digital Signal Processing: Multrirate Systems, Filter Banks, and Wavelets. New York: Wiley & Sons.
  7. Gopinath, R. A. and Burrus, C. S. (1992). Wavelet Transforms and Filter Banks. In Wavelets: A Tutorial in Theory and Applications. (p. 603–655). [Volume 2 in the series: Wavelet Analysis and its Applications]. San Diego, CA: Academic Press.
  8. Gopinath, R. A. and Odegard, J. E. and Burrus, C. S. (1992, May). On the Correlation Structure of Multiplicity Scaling Functions and Wavelets. In Proceedings of the IEEE International Symposium on Circuits and Systems. (Vol. 2, p. 959–962). ISCAS-92, San Diego, CA
  9. Gopinath, R. A. and Odegard, J. E. and Burrus, C. S. (1994, April). Optimal Wavelet Representation of Signals and the Wavelet Sampling Theorem. [Also a Tech. Report No. CML TR-92-05, April 1992, revised Aug. 1993.]. IEEE Transactions on Circuits and Systems II, 41(4), 262–277.
  10. Hlawatsch, F. and Boudreaux-Bartels, G. F. (1992, April). Linear and Quadratic Time-Frequency Signal Representations. IEEE Signal Processing Magazine, 9(2), 21–67.
  11. Kalker, A. A. A. C. and Shah, Imran. (1992). Ladder Structures for Multidimensional Linear Phase Perfect Reconstruction Filter Banks and Wavelets. In Proceedings of SPIE Conference 1818 on Visual Communications and Image Processing. (Vol. 1818).
  12. (1989). Time and Frequency Representation of Signals and Systems. [CISM Courses and Lectures No. 309]. Wien – New York: Springer-Verlag.
  13. Marshall, Jr., T. G. (1992). Predictive and Ladder Realizations of Subband Coders. In Proceedings of IEEE Workshop on Visual Signal Processing and Communication. Raleigh, NC
  14. Marshall, Jr., T. G. (1993). A Fast Wavelet Transform Based on the Eucledean Algorithm. In Proceedings of Conference on Information Sciences and Systems. Johns Hopkins University
  15. Mallat, S. G. (1989, July). A Theory for Multiresolution Signal Decomposition: The Wavelet Representation. IEEE Transactions on Pattern Recognition and Machine Intelligence, 11(7), 674–693.
  16. Mallat, S. G. (1989). Multiresolution Approximation and Wavelet Orthonormal Bases of. Transactions of the American Mathematical Society, 315, 69-87.
  17. Odegard, J. E. and Gopinath, R. A. and Burrus, C. S. (1992, March). Optimal Wavelets for Signal Decomposition and the Existence of Scale Limited Signals. In Proceedings of the IEEE International Conference on Signal Processing. (Vol. 4, p. IV 597–600). ICASSP-92, San Francisco, CA
  18. Oppenheim, A. V. and Schafer, R. W. (1989). Discrete-Time Signal Processing. Englewood Cliffs, NJ: Prentice-Hall.
  19. Parks, T. W. and Burrus, C. S. (1987). Digital Filter Design. New York: John Wiley & Sons.
  20. Smith, M. J. and Barnwell, T. P. (1986, June). Exact Reconstruction Techniques for Tree-Structured Subband Coders. IEEE Transactions on Acoustics, Speech, and Signal Processing, 34, 434–441.
  21. Smith, M. J. and Barnwell, T. P. (1987, March). A New Filter Bank Theory for Time-Frequency Representation. IEEE Transactions on Acoustics, Speech, and Signal Processing, 35, 314–327.
  22. Strang, Gilbert. (1986). Introduction to Applied Mathematics. Wellesley, MA: Wellesley-Cambridge Press.
  23. Sweldens, Wim. (1995, May). The Lifting Scheme: A Construction of Second Generation Wavelets. (TR-1995-6). Technical report. Math Dept. University of South Carolina.
  24. Sweldens, Wim. (1996). The Lifting Scheme: A Custom-Design Construction of Biorthogonal Wavelets. [Also a technical report, math dept. Univ. SC, April 1995]. Applied and Computational Harmonic Analysis, 3(2), 186–200.
  25. Vaidyanathan, P. P. (1987, July). Quadrature Mirror Filter Banks, M–Band Extensions and Perfect–Reconstruction Techniques. IEEE Acoustics, Speech, and Signal Processing Magazine, 4(3), 4–20.
  26. Vaidyanathan, P. P. (1992). Multirate Systems and Filter Banks. Englewood Cliffs, NJ: Prentice-Hall.
  27. Vetterli, Martin. (1986, April). Filter Banks Allowing Perfect Reconstruction. Signal Processing, 10(3), 219–244.
  28. Vetterli, Martin. (1987, March). A Theory of Multirate Filter Banks. IEEE Transactions on Acoustics, Speech, and Signal Processing, 35(3), 356–372.
  29. Vetterli, Martin and Gall, Didier Le. (1989, July). Perfect Reconstruction FIR Filter Banks: Some Properties and Factorizations. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(7), 1057–1071.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks