Patent ID: 6088714
Filing Date: 2000-07-11
Classification: G06F

Abstract:
A method for calculating a fast Fourier transform (FFT) on a computer system for input data that is stored into a memory as an array X, wherein the computer system uses a cache during its operation and the input data is oriented into a square format of a plurality of squares; the method comprising the steps of:(a) transposing the data in each respective square across a diagonal of the respective square such that a datum at location i,j becomes the datum at location j,i;(b) performing a FFT on the data in each respective square;(c) transposing the data in each respective square across a diagonal of the respective square such that a datum at location i,j becomes the datum at location j,i;orienting the data in the squares into a column format of a plurality of one dimensional columns;(d) multiplying the data of each respective column with a respective column of scaling coefficients of a plurality of columns of scaling coefficients, which are stored in array U in memory, with a result maintained in cache as column vector y;(e) performing a FFT on the data in each respective column vector y;(f) transposing the data in each respective column vector y such that a datum at location i,j becomes the datum at location j,i in array X, and orienting the results into the square format; and(g) transposing the data in each respective square across a diagonal of the respective square such that a datum at location i,j becomes the datum at location j,i.