Patent ID: 8032576
Filing Date: 2011-10-04
Classification: G06F

Abstract:
1. A fast Fourier transform circuit comprising: a circuit including a data storage element; a circuit computation component that performs a discrete-time Fourier transform computation on data from the data storage element by dividing computations between a plurality of steps, the computations performing butterfly computations on 2 an extraction component that, at each step, extracts, from the computation result data points calculated by the computation component, data in a pre-specified range with a number of bits the same as the predetermined number of bits n, which is an effective range for the butterfly computations; a setting component that sets the data points of the predetermined number of bits n which have been extracted by the extraction component to serve as input data when butterfly computations of a next step are to be performed by the computation component; and an electrical output for electrically outputting the extracted data in the pre-specified range from the fast Fourier transform circuit.