1. Field of the Invention
The present invention relates to a Fourier transform used in various types of digital signal processes, and more particularly, to a program, method and apparatus for processing a fast Fourier transform.
2. Description of the Related Art
A one-dimensional Fourier transform, and a multi-dimensional Fourier transform of two dimensions or more is widely used in various types of technical fields. Especially, a process for the multi-dimensional Fourier transform such as a three-dimensional Fourier transform has been frequently performed with a vector computer in recent years (see Japanese Patent Publication No. HEI7-6160 “Complex Fast Fourier Transform Processing Method Using Vector Computer”).
Three-dimensional Fourier transform algorithms intended for such a vector computer have been developed with the goal of increasing a vector length as much as possible. Processes for the first and the second dimensions can be executed in parallel, and an algorithm for implementing a vector length as n1 (the first dimension)×n2 (the second dimension) is adopted to improve machine performance with a sequential access.
However, if the value of n1 or n2 becomes large, data overflows from a cache when a memory is accessed to load the data, and the cache performance cannot be fully utilized.
In the meantime, hardware advances of a scalar processor have been remarkably made in recent years, and it is expected to improve process performance by executing a Fourier transform process with the scalar processor. However, an algorithm intended for a vector processor, which has been the mainstream in recent years, is unavailable to the scalar processor unchanged, and a new algorithm for improving the speed of a Fourier transform process with the scalar processor is required.
USPTO Backgrounds
USPTO Backgrounds