Patent ID: 7062523
Filing Date: 2006-06-13
Classification: G06F

Abstract:
1. A method of computing a fast Fourier transform in a plurality of computation stages, the method comprising: (a) receiving N time-ordered first data values; (b) sequentially storing in a first memory each of said N time-ordered first data values in the time-order; (c) storing in a second memory a plurality of twiddle factors in a bit reversed order; (d) reading a predetermined number R of input butterfly data values of said N first data values, wherein said predetermined number R of input butterfly data values are separated by N/R first data values in said N time-ordered first data values; (e) performing a radix R butterfly calculation on said predetermined number R of input butterfly data values using at least one of the plurality of twiddle factors stored in the second memory to generate R output butterfly data values; (f) storing said R output butterfly data values in sequential memory locations of a third memory; and (g) performing said steps (c)–(f) N/R×2 times, wherein the predetermined number R is the same predetermined number each time the steps (d)−(f) are performed, wherein said reading step (d) includes reading the R output butterfly data values from said third memory, wherein the memory store operation performed in said storing step (f) has a unity stride, thereby allowing R output butterfly data values to be read from contiguous memory locations each time the R output butterfly data values are read from said third memory, and wherein said steps (a)–(g) are performed in each one of the plurality of computation stages.