Patent ID: 7395293
Filing Date: 2008-07-01
Classification: G06F

Abstract:
1. A method for performing a fast-Fourier transform (FFT) of N input data elements using a radix K decomposition of the FFT, wherein K is greater than or equal to 2, and N is greater than or equal to 8, comprising: writing N/K input data elements to respective ones of K addressable memories; performing N/K*log (a) generating K respective addresses for the K addressable memories; (b) reading K data elements in parallel from the K addressable memories using the respective addresses, the K data elements being in a first order corresponding to the respective memories; (c) permuting the first order of K data elements into a second order of K data elements; (d) performing a radix K calculation on the second order of K data elements, resulting in corresponding result data elements in the second order; (e) permuting the second order of K result data elements into the first order; and (f) writing the K result data elements in parallel to the corresponding K addressable memories using the respective addresses; and reading N/K data elements from respective ones of K addressable memories.