Patent ID: 7577698

Claim:
A Fast Fourier Transform computing device for transforming time domain input digital data to frequency domain output digital data, said computing device comprising: a computing unit selecting R data items for performing radix-R butterfly computation with respect to said R data items to generate R rotated data items and output a sum in frequency domain of said R rotated data items, said R data items being selected from said input digital data and a set of transition-stage data; a first storage device for storing twiddle factors of an N-point FFT; a multiplier for sequentially multiplying said sum in frequency domain from said computing unit with a corresponding twiddle factor from said first storage device, and outputting a transition-stage data item; and a second storage device for receiving and storing said transition-stage data item sequentially, and outputting another set transition-stage data to said computing unit; wherein said computing unit further comprises: a multiplexer for selecting said R data items from said input digital data and the transition-stage data from said second storage device; a first data processing unit for receiving a first set of R/2 data items from said R data items, rotating said first set of R/2 data items with a first angle, and outputting a first set of rotated R/2 data items sequentially; a second data processing and multiplexing unit for receiving said R data items and said first set of rotated R/2 data items, then either selecting said R data items within a first preset duration or selecting a second set of R/2 data items from said R data items for combining with said first set of rotated R/2 data items to form a new set of R data items within a second preset duration, rotating said R data items or said new set of R data items with a second angle, and outputting said R rotated data items sequentially; and an adder for adding said R rotated data items sequentially, and outputting a sum in frequency domain of said R rotated data items.