Patent ID: 7454452

Claim:
The method of performing an N-point radix-R Fast Fourier Transform in a data processing apparatus having a data cache comprising the steps of: comparing the data set of input data and twiddle factors with the size of the data cache; if said data set is smaller than said data cache, performing said Fast Fourier Transform in log R N stages on all the data set in one pass; and if said data set is larger than said data cache but smaller than R times the data cache dividing said input data into R continuous data sets where each of said R continuous data sets fit within the data cache; disposing said input data into memory, each R continuous data set in continuous memory locations with a space in memory locations from an end of one continuous data set to a beginning of a next continuous data set equal to the size of a cache line; separately and independently performing a first stage radix-R butterfly computations on all the R continuous data sets thereby producing R independent intermediate data sets in a first pass each of which fits within the data cache; and successively performing second and all subsequent stage butterfly computations on each independent intermediate data set in turn producing corresponding output data in second passes.