Patent ID: 8601045

Claim:
A split-radix-2/8 (SR-2/8) Fast Fourier Transform (FFT) apparatus, comprising: a memory, comprising a plurality of memory banks, for receiving 2 M pieces of input data each having an original address, M being a positive integer; a split-radix Fast Fourier Transform (SRFFT) processor for performing a decimation in time (DIT) SR butterfly computation; and a control unit, comprising: an input control block for determining a first order according to numbers of the memory banks and bit-reversed addresses of the original addresses, and for controlling the memory to load the memory banks corresponding to the first order with the input data in the first order, such that the SRFFT processor is able to retrieve data from the memory banks simultaneously in a single clock cycle; an SRFFT control block for determining a decomposition structure of a 2 M -point FFT corresponding to the 2 M pieces of input data, and for controlling the SRFFT processor to repeatedly perform the butterfly computation along the decomposition structure, wherein the order of the input data of each butterfly computation fits in with the first order, and the SRFFT control block is further used for controlling output results of each butterfly computation to be written back into the memory banks corresponding to the input data; and an output control block for determining a second order according to the numbers of the memory banks and original addresses of 2 M pieces of output data after the DIT SR butterfly computation is finished, and for controlling the output results written and stored in the memory banks to be outputted in the second order as the 2 M pieces of output data, the output results comprised in the 2 M pieces of output data sequentially corresponding to the 2 M pieces of input data in the first order.