Fast fourier transform circuit and fast fourier transform method

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 n points of input data each of a predetermined number of bits n, n being a natural number greater than 0, and calculating 2 n computation result data points with numbers of bits larger than the predetermined number of bits n;

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.

2. The fast Fourier transform circuit of claim 1 , wherein the effective range is specified in accordance with a position of a bit that is a ‘1’ closest to a most significant side of the input data to which butterfly computation is applied by the computation component.

3. The fast Fourier transform circuit of claim 2 , further comprising an extraction range table that associates positions of the bit that is a ‘1’ closest to the most significant side with effective ranges,

wherein the effective range is determined by reference to the extraction range table.

4. The fast Fourier transform circuit of claim 1 wherein, in a case in which the input data is data of a terrestrial digital broadcast, the computation component shifts the effective range toward a least significant bit with progress of the steps.

5. A fast Fourier transform method comprising:

electrically inputting data to a data storage element of a fast Fourier transform circuit;

electrically outputting data from the data storage element to a fast Fourier transform element within the fast Fourier transform circuit;

extracting data from computation result data when a discrete-time Fourier transform computation is being performed by the fast Fourier transform element by division of computations between a plurality of steps, the computations performing butterfly computations on 2 n points of input data each of a predetermined number of bits n, n being a natural number greater than 0, and calculating 2 n computation result data points with numbers of bits larger than the predetermined number of bits n,

including extracting, at each step, from the computation result data points that have been calculated, 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;

setting the data points of the predetermined number of bits n which have been extracted to serve as input data when butterfly computations of a next step are to be performed; and

electrically outputting the extracted data in the pre-specified range from the fast Fourier transform circuit.

6. The fast Fourier transform method of claim 5 , wherein the effective range is specified in accordance with a position of a bit that is a ‘1’ closest to a most significant side of the input data to which butterfly computation is applied.

7. The fast Fourier transform method of claim 6 , wherein the effective range is determined by reference to an extraction range table,

the extraction range table associating positions of the bit that is a ‘1’ closest to the most significant side with effective ranges.

8. The fast Fourier transform method of claim 5 wherein, in a case in which the input data is data of a terrestrial digital broadcast, the effective range shifts toward a least significant bit with progress of the steps.

9. A fast Fourier transform method comprising:

electrically inputting data to a data storage element of a fast Fourier transform circuit;

electrically outputting data from the data storage element to a fast Fourier transform element within the fast Fourier transform circuit;

performing a butterfly computation on data output from the data storage element and outputting a butterfly computation result of m bits, m being a natural number of at least 2;

extracting a predetermined n bits of the m bit butterfly computation result, n being a natural number smaller than m and larger than 0;

performing a butterfly computation using the extracted predetermined n bits of the butterfly computation result; and

electrically outputting the extracted predetermined n bits of the butterfly computation result from the fast Fourier transform circuit.

10. The fast Fourier transform method of claim 9 , wherein a position of the predetermined n bits is specified in accordance with a position of a bit that is a ‘1’ closest to a most significant side of the inputted data.

11. The fast Fourier transform method of claim 10 , wherein the predetermined n bits is determined by reference to an extraction range table,

the extraction range table associating positions of the bit that is a ‘1’ closest to the most significant side with effective ranges.