Patent ID: 8417753

Claim:
A pipelined FFT circuit used for processing a sequential input data with a set of N samples comprising: a data division unit used for dividing the sequential input data into a first input data stream and a second input data stream; a data-preprocessing unit receiving the first and second input data streams and ordering the first input data stream to an odd number-index data stream, the second input data stream to an even number-index data stream respectively; M sets of data computation unit, each of the data computation units having a data switch and a butterfly computator connected with the data switch, wherein M=log 2 N, the data switch of the first data computation unit is connected with the data-preprocessing unit; and an output sequence transforming unit connected from the data switch of the M th data computation unit to the butterfly computator of the M th data computation unit, the output sequence transforming unit directly generating an output result in normal order via M times of data computation without extra temporary storage.