Reduced computation system for wavelet transforms

Details Reduced computation system for wavelet transforms Reduced computation system for wavelet transforms

1999-09-02

2002-10-15

Mai, Tan V. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S400000

Reexamination Certificate

active

06466957

ABSTRACT:

BACKGROUND OF THE INVENTION
1. The Field of the Invention
This invention relates generally to computation and implementation of discrete wavelet transforms and architectures associated therewith.
2. Present State of the Art
Until the mid-1960s, it was known that the discrete Fourier transform (DFT) was fundamental to a number of applications, but the computational complexity (and therefore cost) was considered prohibitively high. The DFT did not gain widespread acceptance until a fast algorithm was developed by Cooley and Turkey in 1965. The Cooley-Turkey discovery triggered enormous, for that time, research activity, both in the applications of the DFT, as well as in efficient algorithms for its computation. At present, the DFT is most often implemented using digital signal processors (DSPs), and DSP architecture is specifically tailored to enable the fast computation of the DFT.
The advance of filter banks and wavelet transforms in the 1980s similarly triggered enormous research activity. It is well known and appreciated by now that the wavelet transform provides numerous advantages. Its main applications are in signal compression and, more recently, multicarrier modulation. In every respect the wavelet transform provides superior performance compared with other orthogonal transforms like the discrete cosine transform (DCT) and the discrete Fourier transform (DFT). Wavelets will play a very important role in the converged communication networks of the future. The only disadvantage of wavelets is complexity. They cost more to implement than the DCT or the DFT. As a result, the vast majority of multicarrier modulation modems for high-speed communications over copper wire use the DFT and the majority of commercially available video compressors are DCT-based. It is certain that companies which are able to reduce the cost of implementing wavelets will be able to offer superior products at attractive prices and therefore reap the benefits that wavelets offer.
Thus the problem of efficient implementation of the wavelet transform is of huge practical importance and a significant amount of research has been devoted to it.
W. Lawton in U.S. Pat. No. 4,974,187, assigned to Aware, Inc., of Cambridge, Mass. presents a modular DSP system for calculating the wavelet transform. This system takes into consideration the multirate operations decimation and interpolation. Since every other sample is discarded away, the circuit developed by Lawton does not compute it. This approach is obviously suitable to all types of filter banks (perfect or approximate reconstruction, orthogonal or biorthogonal etc.).
Another relevant work is described in U.S. Pat. No. 4,815,023, assigned to the General Electric Company of Schenectady, N.Y. This patent describes a technique where the phases of the decimations are staggered and is specifically targeted at approximate-reconstruction filter banks, enabling odd-tap filters to be used.
Other prior work is also described in U.S. Pat. No. 5,706,220, assigned to LSI Logic Corp., of Milpitas, Calif. It is targeted to image compression systems and is based on shifting a pair of image pixels into a shift register, followed by quadrature mirror filter (QMF) bank, which provides a dual high-pass/low-pass output and eliminates the need for decimation.
An integrated systolic architecture is developed in U.S. Pat. No. 5,875,122 assigned to Intel Corp., of Santa Clara, Calif. It represents a uniform connection of identical processing cells, which avoid the computation of discarded components to achieve full utilization of the circuit.
Images are often processed using separable filter banks for the rows and columns. Thus four-band analysis and synthesis filter banks are involved. An efficient circuit for this case is described in U.S. Pat. No. 5,420,891, assigned to NEC Corp., of Tokyo, Japan.
A. Akansu in U.S. Pat. No. 5,420,891 describes a multiplierless two-channel orthogonal filter bank which is obviously efficient. This patent is limited in applicability since design routines do not generally produce multiplierless filter banks.
Thus, what is needed is a system and method that enables an efficient implementation of the wavelet transform thereby enabling the incorporation of wavelet transforms into widespread computational applications. Therefore, it would be an advance to provide a method and system that is capable of reducing the computational complexity of the calculation of a discrete wavelet transform.
SUMMARY AND OBJECTS OF THE INVENTION
In this invention, the characteristics of orthogonal filter banks, namely that the highpass filter coefficients are the time-reversed coefficients of the lowpass filter with alternating sign changes, is exploited. 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 percent. This invention can be combined with previous inventions to achieve even more efficient implementations. For example, it can be used with a multiplierless filter bank to reduce the number of additions.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or maybe learned by the practice of the invention. The objects and advantages of the invention maybe realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims.
These and other objects and features of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter.


REFERENCES:
patent: 4799179 (1989-01-01), Masson et al.
patent: 4815023 (1989-03-01), Arbeiter
patent: 4829378 (1989-05-01), LeGall
patent: 4839889 (1989-06-01), Gockler
patent: 4974187 (1990-11-01), Lawton
patent: 5297236 (1994-03-01), Antill et al.
patent: 5347479 (1994-09-01), Miyazaki
patent: 5384725 (1995-01-01), Coifman et al.
patent: 5420891 (1995-05-01), Akansu
patent: 5495554 (1996-02-01), Edwards et al.
patent: 5526299 (1996-06-01), Coifman et al.
patent: 5706220 (1998-01-01), Vafai et al.
patent: 5729483 (1998-03-01), Brown
patent: 5751615 (1998-05-01), Brown
patent: 5875122 (1999-02-01), Acharya
patent: 5943642 (1999-08-01), Choi
patent: 6018753 (2000-01-01), Kovacevic et al.
patent: 6182102 (2001-01-01), Ramachandran et al.
patent: 6216145 (2001-04-01), Zandi et al.
patent: 6278753 (2001-08-01), Suarez et al.
The Recursive Pyramid Algorithm for the Discrete Wavelet Transform; Vishwanath;IEEE Transactions on Signal Processing, vol. 42, No. 3, Mar. 1994, p. 673.
VLSI Architectures for the Discrete Wavelet Transform; Vishwanath et al;IEEE Transactions on Circuits and Systems-I: Analog and Digital Signal Processing, vol. 42, No. 5, May 1995, p. 305.
VLSI Architectures for Lattice Structure Based Orthonormal Discrete Wavelet Transform; Grzeszczak et al.;IEEE Transactions on a Very Large Scale Integration(VLSI)Systems, vol. 4, No. 4, Dec. 1996, p. 421.
VLSI Architectures for Lattice Structure Based Orthonormal Discrete Wavelet Transforms; Denk et al.;IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, vol. 44, No. 2, Feb. 1997, p. 129.
A High Speed Reconfigurable Integrated Architecture for DWT; Acharya;IEEE, 1997, p. 669.
Scalable VLSI Architectures for Lattice Structure-Based Discrete Wavelet Transform,IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, vol. 45, No. 8, Aug. 1998, p. 1031.

Affiliated with

Also associated with

Rating

Reduced computation system for wavelet transforms does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reduced computation system for wavelet transforms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reduced computation system for wavelet transforms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2926755