Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-06-21
2003-03-11
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06532484
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the field of digital computer systems, and more particularly to systems and method for performing fast Fourier transforms (FFT's) in parallel on a digital computer system comprising a plurality of processors.
BACKGROUND OF THE INVENTION
The Fourier transform is used in many applications, including, for example, seismic signal analysis and signal processing. A Fourier transform of a sequence of, for example, spatial or temporal data, in which the data identifies the amplitude of a signal as a function of space or time, transforms the data into the frequency domain. The transformed data identifies the amplitudes of various frequencies which, when signals of those frequencies are added together, would correspond to the original data signal, and thus identifies the spectral components of the original data signal and the amplitude of each of those components in the original data signal. The spectral information can be processed, using an inverse Fourier transform, to regenerate the original data signal. A Fourier transform can be useful in, for example, removing high- and/or low-frequency noise from a data signal, since the data signal can be transformed to the spectral domain, low- and/or high-frequency components removed, and an inverse Fourier transform applied to the remaining components to generate a filtered data signal which does not contain the removed frequency components. In addition, a Fourier transform can be used in generating a time- or frequency-scaled version of the data signal, as well as the convolution of, or correlation between, two data signals.
Generation of a Fourier transform on a digital computer can be accelerated by use of one of several so-called “FFT” (“fast Fourier transform”) algorithms popularized by J. W. Coolly and J. W. Tukey, as described in, for example, W. Press,
Numerical Algorithms in Fortran
(1992: Cambridge University Press), chapter 12. Often the time required to generate a Fourier transform, and the data storage requirements therefor, can be reduced by using so-called “real-to-complex” (“rc-FFT”) or “complex-to-real” (“cr-FFT”) FFT algorithms. Serial methodologies have been developed for performing an rc-FFT operation on, for example, a single processor in a computer or in a single process. However, it would be preferable to perform the rc-FFT operation on a plurality of processors in a like plurality of processes, or threads of a single process in parallel, to reduce the time required to perform the rc-FFT operation.
SUMMARY OF THE INVENTION
The invention provides a new and improved system and method for performing an FFT operation on a computer comprising a plurality of processors in parallel.
In brief summary, the invention provides a parallel FFT generating system for generating a FFT of an input vector. The parallel FFT generating system comprises a plurality of processes configured to receive the input vector and process the input vector in parallel in relation to a set of twiddle factors to generate an output vector, the output vector comprising a Fourier transform representation of the input vector.
REFERENCES:
patent: 3754128 (1973-08-01), Corinthios
patent: 5297070 (1994-03-01), Hua et al.
patent: 5717620 (1998-02-01), Williams
patent: 5835392 (1998-11-01), Dulong et al.
patent: 5941940 (1999-08-01), Prasad et al.
patent: 6006245 (1999-12-01), Thayes
patent: 6081821 (2000-06-01), Hopkinson et al.
patent: 6304887 (2001-10-01), Ju et al.
Kivlin B. Noäl
Mai Tan V.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Sun Microsystems Inc.
LandOfFree
Parallel system and method for performing fast fourier... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel system and method for performing fast fourier..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel system and method for performing fast fourier... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3032735