Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-12-13
2004-08-31
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C382S248000
Reexamination Certificate
active
06785700
ABSTRACT:
BACKGROUND TO THE INVENTION
1. Field of the Invention
This invention relates to implementation of wavelet analysis in hardware.
Wavelet analysis provides a powerful method for analysing time-varying signals. Conceptually, wavelet analysis can be considered as being related to Fourier analysis. As is well-known, Fourier analysis can transform a signal varying in amplitude in the time domain into a signal that varies in the frequency domain. Fourier analysis thereby provides an indication of the frequency content of the signal. Commonly, Fourier analysis uses sine and cosine as basis functions, whereby the transform is indicative of the sine and cosine content of the original signal across a frequency range.
An important limitation of a Fourier transform is that it is applied across the entire time extent of the original signal: all time information is lost in the transformed signal. This means that any variation in the character of the original signal with time cannot be deduced from the transform. Moreover, a Fourier transform cannot be used to analyse discrete time segments in a continuous signal. For example, if the signal is a continuous speech signal, a Fourier transform cannot be used to perform a frequency analysis on a time-limited segment such as a single word within the speech signal.
Wavelet analysis has been evolved as a more powerful analysis tool. Two features of wavelet functions contribute in particular to their power.
First, wavelet analysis can be performed over a part of the original signal that is limited in time. Moreover, the time over which the analysis operates can be varied simply by making relatively small changes to the analysis procedure. This allows the analysis to be tuned to give results that are more accurate in either their resolution in frequency or in time, as best suits the objective of the analysis (although, it should be noted, that an increase in accuracy in one domain will inevitably result in a decrease in accuracy in the other).
Second, wavelet analysis can be based on an arbitrary basis function (referred to as a “mother wavelet”. It might be used to express the frequency content of a time-varying signal in terms of its frequency-domain content of, for example, sine and cosine waves, square waves, triangular waves, or any other arbitrary wave shape. The basis functions can be chosen to give the most useful result based upon the content and nature of the original function and upon the result that is being sought in performing the analysis.
More formally, it can be said that a continuous wavelet transform (CWT) analyses a signal x(t) in terms of shifts and translates of the mother wavelet. This is represented as follows:
CTWT
(
b
,
a
)
=
1
a
∫
h
*
(
t
-
b
a
)
x
(
t
)
ⅆ
t
(
1
)
The wavelet transform performs a decomposition of the signal x(t) into a weighted set of basis functions h(t), which are typically time-limited, finite energy signals that oscillate like waves (hence the term “wavelets”).
As will be appreciated, this transform is complex, and consumes a considerable amount of computer power if it is to be performed by a computer executing a software program.
This may be acceptable if it is to be used where real time processing is of lesser importance. For example, wavelet transforms are used in software compression or decompression of files representing still images. However, where speed in performing the analysis is critical, this can cause the method to become, for practical purposes, unworkable. For example, if the analysis is to be applied to compression or decompression of moving images in real time, the cost of providing sufficiently powerful computers may be prohibitive. It has therefore been recognised that there may be significant advantage in implementing the transform directly in hardware, for example, for incorporation into an ASIC or FPGA design, or as a core for inclusion in a signal processing hardware system.
As a first step to this end, it has been shown that a discrete representation of the wavelet function allows the transform to be calculated by a small number of relatively simple components, namely, a high-pass filter and a low-pass filter, each filter being followed by a downsampler (otherwise known as a decimator) with a factor of 2. As will be recognised, each of these components can be implemented in hardware in a reasonably straightforward manner. Mathematically, a discrete wavelet transform (DWT) of the discrete function x(n) is represented in Equation 2, below:
DWT
x
(
n
)
=
{
c
j
,
k
=
∑
x
[
n
]
h
j
*
[
n
-
2
j
k
]
s
j
,
k
=
∑
x
[
n
]
g
j
*
[
n
-
2
j
k
]
(
2
)
The coefficients c
j,k
describe the detailed components in the signal and the coefficients s
j,k
refer to the approximation components in the signal. The transfer functions h(n) and g(n) in this equation represent the coefficients of the high-pass and the low-pass filters and are derived from the wavelet function and the inverse (scaling) function respectively. The low-pass filtered and downsampled output of each stage is fed forward to the following stage, which gives a successively reduced time resolution and increased frequency resolution after each stage. Several stages can therefore be cascaded to provide transform outputs at several levels of resolution.
Wavelet packet decomposition is an important development of wavelet analysis. The principle behind these decompositions is to selectively choose the basis function (mother wavelet) and the frequency bands to be decomposed. This basic structure of hardware for performing wavelet packet decomposition is sown in FIG.
12
. Improved results in the area of speech and image coding, as well as signal detection and identification, have been reported using this kind of wavelet analysis. There are two issues related to the implementation of wavelet packet transforms. The first is the choice of a different wavelet function for each filter bank and the second relates to the arbitrary connection between the outputs of a filter bank stage to the inputs of the succeeding stages. As will be seen, the characteristic arrangement of a filter followed by a downsampler is clearly present in this circuit as illustrated at 1210.
2. Summary of the Prior Art
A hardware implementation of a DWT is most typically based upon the filter bank arrangement defined in Equation 2. A typical hardware implementation of such a three-level DWT is shown schematically in FIG.
1
.
110
′,
110
″ and
110
′″ represent, respectively, a low-pass filter of the first, second and third stages,
112
′,
112
″ and
112
′″ represent, respectively, a high-pass filter of the first, second and third stages, and
114
′,
114
″ and
114
′″ represent, respectively, downsamplers of the first, second and third stages. Each of the filters
110
,
112
of the circuit shown in
FIG. 1
has a general form shown in
FIG. 2
, comprising, in each of a plurality of stages, a multiplier
210
, a delay line
212
and an adder
214
. The characteristics of such a filter (which has a structure very familiar to those skilled in the technical field) is determined by a set of coefficients C
1
. . . Cn applied respectively to each of the multipliers. Variation of the values of these coefficients, therefore allows the designer to control the characteristics of the wavelet transform operation.
This circuit is typically quite demanding in terms of circuit area requirement. The decreasing sampling rate (a result of the downsampling operations) and increasing word length (a result of the filtering operations) as the stages progress, add to the complexity of the circuit design. In particular, each multiplier
210
represents a considerable demand upon resources.
It has previously been proposed that the design of such hardware might be optimised through production of custom designs which typically use various data organisation formats such as bit-serial and digit-serial designs. However, in most cases, the
Masud Shahid
McCanny John Vincent
Amphion Semiconductor Limited
Harrington Curtis L.
Malzahn David H.
LandOfFree
Implementation of wavelet functions in hardware does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Implementation of wavelet functions in hardware, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implementation of wavelet functions in hardware will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3333879