Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-09-07
2003-04-29
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06557019
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to the field of electronic circuit devices, and more particularly to an apparatus and method for performing both forward and inverse compact Haar Transforms.
2. Description of the Related Art
The characteristics and behavior of electronic signals can be expressed in a number of different ways, but perhaps the most common way of representing a signal is by plotting its amplitude as a function of time, or as a function of distance from a point, or as a function of some other variable relevant to the signal. Mathematically speaking, the domain of the signal corresponds to the relevant variable, say, time. The range of the signal corresponds to its amplitude. Consequently, signals are classified according to their domain. For example, a signal having time as its domain is known as a time domain signal.
The expression and manipulation of signals in the time domain are performed every day in virtually every electronic product. This is because real events affecting most electronic products occur in real time. Radio signals are modulated by electronic modulators in real-time, modulated signals are transmitted in real time, transmitted signals are received and demodulated in real time, demodulated signals are converted by electronic transducers into audio tones in real time, and audio tones are heard by listeners in real time.
Time domain signals are useful and familiar, but many applications, specifically applications that handle or manipulate lots of data, can be better served by transforming a time domain signal into another form, that is, representing the signal within another domain. For example, some operations or computations by an electronic product may require less logic or may be performed much faster on signals that have been transformed into another domain. More specifically, a signal in an original domain, say time, is first transformed into a representation of the signal in a transform domain, say frequency. Next, desired operations or computations are performed on the frequency domain signal to produce a frequency domain output. Finally, an inverse transformation is performed on the frequency domain output to yield a time domain output.
The Fourier transform is perhaps the most well-known transform that is used within electronic products for purposes described above. Executing a Fourier transform on a time domain signal so that it is represented in the frequency domain immediately provides two benefits that cannot easily be achieved in the time domain: 1) the frequency characteristics of the signal, that is, which frequencies are stronger and which are weaker, can be clearly observed from a frequency domain plot of the signal; and 2) convolution of the signal with another signal to produce a result becomes a simple multiplication operation. In the first case for example, it is difficult to determine from a time domain representation of a 25 Hz sinusoidal waveform that its fundamental frequency is 25 Hz. Yet, after transformation to the frequency domain, the 25-Hz fundamental frequency is immediately apparent. In the second case, passing a time domain signal through a low pass filter produces an output signal. But to determine the structure of the output signal requires that a convolution integral be computed using the time domain signal and the impulse response of the low pass filter. A convolution calculation is a very tedious and complex process. Yet, the filter output can more easily be determined by multiplying the Fourier transform of the input signal by the Fourier transform of the filter impulse response, and then performing an inverse transform on the result of the multiplication.
There are many other types of transforms used in electronic products today. Typically, a specific transform is used for a specific application because it provides certain benefits such as speed, observation of some signal parameter, or reduction in logic. One particular transform that provides both logic reduction benefits as well as computational ease is the Haar transform. A class of signals, smooth signals, require less logic within an electronic device to store and manipulate when they are represented in the Haar domain as opposed to their original domain. Effectively, less bits are required to store a Haar domain parameters than would be required to store signal parameters in the original domain, thus compressing the signal data.
That data compression is achieved for smooth signals using Haar transform techniques is not inconsequential because reduction in the logic required to store signal parameters in electronic devices directly reduces the amount of power required to operate the devices. In addition, logic reduction typically reduces the cost of a product because it uses less components. This is very important when one considers the vast number of hand-held and portable products in use today because these devices are powered by batteries. Consequently, reducing the number of logic cells within a portable device means that it can operate longer, or that a smaller battery can be used to achieve equivalent operating time.
But the Haar transform is not used in many applications where data compression can be achieved because the number of bits that are required to express a signal in the Haar domain increases in proportion to the number of data samples that are transformed from the original domain to the Haar domain. More specifically, for a sequence of 256 samples of a signal where each of the samples requires 10 bits to express in the original domain requires 18-bit registers to compute the 256 Haar parameters needed to express the signal in the Haar domain. Once the signal is transformed into the Haar domain, if it is sufficiently smooth, one finds that most of the Haar parameters that result have zeros in most of the bit positions of the parameter registers. But in order to compute the parameters in the first place, 18-bit registers are required.
In general, the number of bits required to compute Haar parameters is equal to the base
2
log of the number of input samples plus the number of bits required to express each of the input samples. For M n-bit data samples, computation of corresponding Haar parameters requires registers that are log
2
M+n bits wide. In the case of 1,024 10-bit samples, the register size required to compute corresponding Haar parameters is twice the size of that required to store the original samples.
Therefore, what is needed is a forward Haar transform apparatus that does not require an excessive number of bits for computation of Haar parameters corresponding to an input sequence of data samples.
In addition, what is needed is an inverse Haar transform apparatus that can perform an inverse Haar transform on a set of bit-limited Haar parameters to produce an output in the original domain.
Furthermore, what is need is a method for performing forward and inverse Haar transforms on a sequence of n-bit data samples, where calculation of the corresponding Haar parameters requires at most n+1-bit registers.
SUMMARY OF THE INVENTION
To address the above-detailed deficiencies, it is an object of the present invention to provide a forward Haar transform apparatus that requires at most n+1-bit registers to compute Haar parameters corresponding to an input sequence of n-bit data samples. Accordingly, in the attainment of the aforementioned object, it is a feature of the present invention to provide a compact Haar transform apparatus, for executing a spectral transformation corresponding to a sequence of n-bit samples. The compact Haar transform apparatus includes sum-and-truncate logic and a plurality of coefficient generators. The sum-and-truncate logic generates a plurality of n-bit intermediate terms where the sum-and-truncate logic truncates the least significant bit of a generated n+1-bit sum to form an associated n-bit intermediate term. The a plurality of coefficient generators is coupled to the sum-and-truncate logic. The plurality of coefficient ge
Huffman James W.
Huffman Richard K.
Ngo Chuong Dinh
Spectral Logic Design
LandOfFree
Apparatus and method for compact Haar transform does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for compact Haar transform, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for compact Haar transform will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3098901