When data is fast Fourier transformed using a computer, complex coefficients, known as twiddle factors, are used. A twiddle factor is given by EQU W.sub.n.sup.k =cos (2.pi./n)k-sin (2.pi./n)k
That is, it is composed of the real part of a cosine function and the imaginary part of a sine function. In the above equation, n is the number of data elements to be fast Fourier transformed, k=0, . . . , n-1. FIG. 1 illustrates the algorithm of an FFT performed on 16 points. A butterfly operation is a unit operation of an FFT. The butterfly operation is conducted from left to right in stage 1 of FIG. 1. Then, stages 2 and 3 are handled. Correspondingly, the twiddle factor is quoted in the same order.
An FFT hardware processor may not handle whole data to be Fourier transformed in one FFT processing. In this context, Fourier transform processing involves a fast Fourier transform and transposition of data, or bit reversal. One reason why whole data cannot be Fourier transformed in one FFT processing is that the data cannot be placed into the memory of the processor simultaneously.
In order to take the Fourier transform of such a large quantity of data, it is necessary to provide access to the data in a complicated manner.
FIG. 2 shows the conventional method by which a memory is used to take the Fourier transform of data in large quantities. FIG. 2 also shows the processing. Data exists outside an FFT hardware processor. Where the processor is a host computer, data is stored in an external storage such as a magnetic disk. Where the processor is different from the host computer, data is stored in the memory of the host computer or in an external storage such as a magnetic disk.
If the capacity of the memory of the FFT processor is small, it cannot implement an FFT in one operation. In this case, the processor fetches as much data as possible to the memory as shown in FIG. 2 and performs butterfly operations on the data. The FFT implementation is divided into N (=log.sub.2 n) stages. When each stage is separated into M parts, M times of transfers (fetch and store) of data and M times of butterfly operations must be executed.
When the processing is complex as shown in FIG. 2, fast Fourier transform (FFT) cannot be implemented at a high speed. Furthermore, the twiddle factor table must be extended up to a requisite size. Hence, the cost performance deteriorates.
In the case of FIG. 2, the data is transferred from the external storage to the processor and returned to the external storage from the processor, at each stage. Therefore, the total number of data transferred during the whole FFT implementation is given by EQU 2.times.total amount of data.times.N stages
For this reason, a reduction in the speed cannot be avoided even if double buffering techniques are exploited.
Where data exists in a host computer, bit reversal may be done by the computer and so little problems take place. However, where data exists on an external storage such as a magnetic disk, the speed is reduced considerably for the following reason. Two data elements to be interchanged are placed on a position (x) and on a bit reversal position of the position (x), therefore, some data element pairs cannot be exchanged at a time. That is, one data element must be moved when one transfer instruction is issued. This reduces the transfer speed down to a minimum, where a minimum amount of data, e.g., Y data elements, must be transferred from an external storage such as magnetic disk, a wasteful transfer given by (Y-1).times.4 takes place to interchange the elements of one pair. Since this transfer is conducted for all the data, all the wasteful transfer is given by EQU (Y-1).times.4.times.(n/2)
In this way, wasteful transfer slows down the processing.
As described above, the method illustrated in FIG. 2 enables Fourier transform of data in large quantities, but the processing speed is quite low.
Other conventional methods for FFT of data in large quantities are described in an article entitled "Fast Fourier Transform of Externally Stored Data" by Norman M. Brenner in IEEE Transactions on Audio and Electroacoustics, Vol. AU-17, No. 2, pp. 128-132, June 1969.
In the article, two methods for fast Fourier transform of data in large quantities, named Ryder's method and Granger's method, are disclosed. Both methods have the following problems regarding processing speed.
Ryder's method contains twice reading accesses from the external storage and twice writing accesses to the external storage. When data to be fast Fourier transformed is supposed to consist of data elements of C1 rows and C2 columns, the number of data transferred during whole FFT implementation is estimated as follows: ##EQU1## Ordinarily, since C1&gt;&gt;1, the number of data read from the external storage in the first reading access is quite large. Therefore, the number of data transferred during whole FFT implementation is quite large. Then, it cannot be avoided to lower the processing speed.
On the other hand, Granger's method contains five times of reading accesses from the external storage and five times of writing accesses to the external storage. In the method, the number of data transferred during whole FFT implementation is estimated to 10.times.n. It can be understood that 10 times of reading/writing accesses cause to lower the processing speed.
USPTO Backgrounds
USPTO Backgrounds