| 摘要 |
The discrete Fourier transform (DFT) is computed in a plurality of parallel processors. A DFT of length N is divided into r partial DFTs of length (N/r), in which the r partial DFTs are calculated in separate parallel processors and then combined in a combination phase to form a complete DFT of length (N). The r partial FFTs are able to be computed in parallel multiprocessors by defining the mathematical model of the combination phase in such manner so as to allow the r parallel processors to operate independently and simultaneously. A second embodiment presents a radix-r fast Fourier algorithm that reduces the computational effort as measured by the number of multiplications and permits the N/r parallel processors to operate simultaneously and with a single instruction sequence.
|
