Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-03-11
2002-04-02
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06366937
ABSTRACT:
FIELD OF THE INVENTION
This present invention relates generally to an implementation of a fast fourier transform operation in a microprocessor system, and more particularly to a system and method for performing a fast fourier transform using a matrix-vector multiply instruction.
BACKGROUND OF THE INVENTION
A fourier transform is a mathematical tool that is used to analyze continuous waveforms for repeating patterns. In particular, a fourier transform is based on the analysis of waveforms by breaking up the waveform into sinusoid functions. Sinusoid functions have a “wavy” pattern that repeats at a given frequency.
In digital systems, digital waveforms are no longer continuous but are represented by a set of samples or points. A technique called a fast fourier transform (FFT) is used to analyze the digital waveforms for repeating patterns. The FFT is applied to the input samples or points, referred to as
xi
and generates a set of output points, referred to as Xi. The FFT requires a certain number of calculations and uses a large amount of processor time. In a radix-2 FFT, the total number of complex multiplications and additions is N log
2
N, where N is the number of samples or points in the waveform. For example, an analysis of a 1,024 point waveform uses about 10,000 complex additions and multiplications. Therefore a method and system that reduces the amount of processor and computation time to perform the FFT operation is desirable.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an improved apparatus for and method of performing a fast fourier transform that reduces the computation time.
It is a further object of the invention to provide an improved method and apparatus for performing the fast fourier transform using a matrix vector multiply instruction.
It is a related object of the invention to provide a new method and apparatus for performing an inverse discrete cosine transform operation that reduces computation time using the matrix vector multiply instruction.
These and other objectives and advantages of the present invention are achieved by utilizing a matrix vector multiply instruction referred to as an FTRV instruction in a processor to perform the FFT operation. For the FFT operation, the input data and coefficients of the FFT are rearranged and stored in a vector register and matrix register, respectively. The FTRV instruction is then used to perform a butterfly operation of the FFT.
More particularly, a processor executes a butterfly operation for a fast fourier transform operation. In the butterfly operation, a first set of inputs are defined as r1+j i1 and r2+j i2, and a twiddle factor, called Wn, is defined as Wn=e
−j2&pgr;/N
=cos(2&pgr;/N)−j sin(2&pgr;/N)=a+jb. A first set of registers store r1, i1, r2 and i2; and matrix registers store the twiddle factor. A matrix vector multiply operation is executed between the matrix registers and the first set of registers.
Other features and advantages of the present invention would become apparent to a person of skill in the art who studies the present invention disclosure. Therefore, a more detailed description of a preferred embodiment of the invention is given with respect to the following drawings.
REFERENCES:
patent: 4275452 (1981-06-01), White
patent: 4689762 (1987-08-01), Thibodeau, Jr.
patent: 4787055 (1988-11-01), Bergeon et al.
patent: 5371696 (1994-12-01), Sundararajam et al.
Saha Arindam
Shridhar Avadhani
Flehr Hohbach Test Albritton & Herbert LLP
Hitachi America Ltd.
Malzahn David H.
LandOfFree
System and method for performing a fast fourier 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 System and method for performing a fast fourier transform..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for performing a fast fourier transform... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2869558