Patent ID: 7752249

Claim:
A memory-based Fast Fourier Transform (FFT) device, comprising: a processor; a plurality of single port random access memory (RAM) units for storing data; a sequence value generator for providing a sequence value; a sequence value modifier for adjusting the sequence value and outputting an adjusted sequence value; an address controller, which generates a write shift amount and a read shift amount according to the adjusted sequence value and generates bank addresses for memory banks; and a plurality of switches, which reads the data to be processed from one of the single port RAM units to the processor according to the write shift amount in order to perform a Fast Fourier Transform, and writes the data to be processed from the processor to another of the single port RAM units according to the read shift amount, wherein the number of the single port RAM units is two, and the data to be processed uses a bank index B(n) and an address value A(n) of memory cells to indicate memory addresses, where B(n) is implemented as: if (n R−1 <r/2) B ( n )=( n 0 +n 1 + . . . +n R−1 )mod r; else B ( n )=( n 0 +n 1 + . . . +n R−1 )mod r+r; and A(n) is implemented as: if (n R−1 <r/2) A ( n )= n 1 ·r 0 +n 2 ·r 1 + . . . +n R−1 ·r R−2 ; else A ⁡ ( n ) = n 1 · r 0 + n 2 · r 1 + … + n R - 1 · r R - 2 - N 2 ⁢ r ; where R=log r N, N is a total number of the data to be processed, r is a number of data input ports of the processor, and n is indexes of the data to be processed.