Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-01-24
2003-06-17
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S319000, C708S316000
Reexamination Certificate
active
06581081
ABSTRACT:
BACKGROUND OF THE INVENTION
1. The Field of the Invention
This invention relates generally to architectures associated with computation and implementation of the discrete wavelet transform using the Recursive Pyramid Algorithm (RPA). More specifically, the present invention relates to adaptive size filters useful in calculating and implementing wavelet packet trees.
2. The Prior State of the Art
The discrete Fourier transform (DFT) is fundamental to a number of applications, but until the mid-1960s the computational complexity made DFT implementations prohibitively costly. Computational complexity was one factor that contributed to prevent DFT applications from gaining widespread acceptance, until Cooley and Tukey developed a fast algorithm for DFT calculation in 1965. The Cooley-Tukey discovery triggered enormous research activity both in the development of DFT applications and in the development of efficient computation algorithms for the DFT. At present, the DFT is most often implemented using a digital signal processor (DSP); as such, DSP architecture is often specifically tailored to enable the fast computation of the DFT.
The advance of filter banks and transforms in the 1980s resulted in a similar resurgence of research activity related to the DFT, one significant research advance was the development of the Discrete Wavelet Transform (DWT). The DWT or wavelet transform is a multi-resolution decomposition of a signal, where an original signal is decomposed into various signal components at different frequency levels or octave bands. Wavelet transforms provide a time-scale representation of signals as an alternative to traditional time-frequency representations. The wavelet transform is very efficient for multi-resolution sub-band decomposition of signals.
The wavelet transform provides superior performance when compared with other orthogonal transforms like the discrete cosine transform (DCT) and the discrete Fourier transform (DFT). The primary reasons that the DWT is considered better than either a DFT or DCT are because the DWT tiles the time frequency plane in a general fashion and thus possesses inherent scalability.
It is well known and appreciated that the wavelet transform provides numerous advantages. Presently, the main applications for DWT and wavelet transforms are in image and speech signal compression, multi-carrier modulation, and solving partial differential equations. Wavelets will play a very important role in the converged communication networks of the future.
Unfortunately, one of the main disadvantages of the wavelet transform is their complexity; most of the known DWT require intensive computations and parallel processing for real time applications. This means that wavelet transforms generally cost more to implement than the comparable DCT or DFT solutions. As a result, the vast majority of multi-carrier modulation modems for high-speed communications over copper wire use DFT applications and the majority of commercially available video compressors are based on DCT applications. What is needed is an architecture that is able to reduce the cost of implementing wavelet transforms and thereby be able to offer superior products at attractive prices.
DWT can also be viewed as a multi-resolution decomposition of a discrete-time sequence. For example, the DWT decomposes a discrete-time sequence: a={a
0
, a
1
, . . . , a
n−1
} into a high pass sub-band:
b
=
{
b
0
,
b
1
,
…
,
b
n
2
-
1
}
and a low pass sub-band:
c
=
(
c
0
,
c
1
,
…
,
c
n
2
-
1
)
that can be represented as:
b
n
=
∑
k
h
2
n
-
k
a
k
and
c
n
=
∑
k
g
2
n
-
k
a
k
respectively. After the two-channel filter pair or bank is designed, a wavelet packet tree can be obtained by recursively iterating the two-channel construction. In communications applications, equiripple low pass and high pass filters are normally used, because they provide maximum attenuation for a given filter length and transition bandwidth. It is important to note that even though the filters in the two-channel filter bank are equiripple, the resulting filters from the recursive iteration of the filter bank are not. In fact, one skilled in the art realizes that each iteration of the filter bank tree decreases the stop-band attenuation, whereupon the stop-band attenuation for the filter bank tree will eventually not be satisfied. What is needed is a filter bank tree that uses different size filters on each octave level of the tree. Such a device would allow exactly as many coefficients as are necessary to satisfy the specifications for each octave level of the tree.
Finally, what is needed is a system and method that efficiently implements a wavelet packet tree, which uses different filter coefficients on each octave level of the wavelet packet tree. Therefore, it would be an advance to provide a method and system that is capable of reducing the hardware necessary for the implementation of such a wavelet packet tree.
SUMMARY OF THE INVENTION
An advantage of the invention is that it reduces the cost of implementing a wavelet packet tree by using the same hardware for each octave and is thereby able to offer superior products at attractive prices. Using a filter bank that can utilize different size filters on each octave level of the wavelet packet tree, the present invention allows for exactly as many coefficients as are necessary to satisfy the specification for each octave level of the wavelet packet tree. A related advantage of the invention is that it facilitates the implementation of a multi-resolution decomposition or signal analysis and multi-resolution reconstruction or signal synthesis through a wavelet packet tree while recursively using the same hardware for filtration of a representative signal.
In the preferred embodiment of this invention, the advantageous characteristic of orthogonal filter bank trees, which utilize different filters on each octave level of the tree so that the number of multiplications per octave remains approximately constant, is exploited in a hardware implementation. More specifically, this characteristic enables the same hardware to be used in consecutive computations. The preferred embodiment of the present invention also takes advantage of the fact that the total number of all filter coefficients for a given octave will be the same at each octave level. For example, at the first octave a signal may require eight coefficients or taps per filter bank for a total of 16 coefficients. At the second octave, there may be four filters with four coefficients for a net total of 16 coefficients. The third octave may use 8 filters with two coefficients for a total of 16 coefficients. From this example it can be seen that the sum of all filter coefficients for a given octave does not change due to the branching of the filter bank tree between octaves.
The present invention also takes advantage of the properties related to orthogonal filter banks in that the high pass filter coefficients are the time reversed coefficients of the low pass filter with alternating sign changes. This property has not been used in prior two channel orthogonal filter bank implementations and allows a further reduction in the computational complexity by 50%. A detailed description of the appropriate wavelet packet tree using the RPA is described in U.S. patent application Ser. No. 09/388,754, incorporated in its entirety herein by reference.
The present invention further takes advantage of an efficient algorithm called the recursive pyramid algorithm (RPA), one of the most efficient implementations of the DWT for VLSI applications. However, due to the heavy reliance on the structure shown in
FIG. 4
, when implementing a wavelet packet tree as shown in
FIGS. 2 and 5
, the RPA does not function properly due to the decomposition and reconstruction of both the high pass and low pass channels. As shown in
FIG. 2
, decimation or downsampling, as depicted at the output of each fil
Cooklev Todor
Messerly Shayne
3Com Corporation
Mai Tan V.
Workman & Nydegger & Seeley
LandOfFree
Adaptive size filter for efficient computation of wavelet... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive size filter for efficient computation of wavelet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive size filter for efficient computation of wavelet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3162170