Patent ID: 6728742
Filing Date: 2004-04-27
Classification: G06F

Abstract:
A method of performing a FFT of a sequence of N=Bn numbers, where B is a power of 2 and n is a positive integer, comprising the steps of:(a) recursively selecting a pattern of storage locations for the Bn numbers in M in-place memories, M being a power of 2 that is less than B, wherein, if n=1, each said in-place memory has storage locations for a different B/M of the B numbers, and wherein, if n is greater than 1, said pattern for storing Bn numbers is a concatenation of B said patterns for storing Bnâˆ’1 numbers, there being B/M successive sets of said patterns for storing Bnâˆ’1 numbers in said pattern for storing Bn numbers when n is greater than 1, said patterns, for storing Bnâˆ’1 numbers, within each of said B/M successive sets, being mutually identical and being different from said patterns, for storing Bnâˆ’1 numbers, of any other said set; (b) storing the numbers in said storage locations; (c) performing an in-place radix-B DFT on each of N/B groups of values stored in said storage locations; and (d) if n is greater than 1, performing a length N/B DFT on each of B groups of N/B values stored in said storage locations, each said group including NI(MB) values stored in each of said in-place memories.