Arithmetic method and function arithmetic circuit for a fast fourier transform

• US 7,634,524 B2
• Filed: 04/14/2004
• Issued: 12/15/2009
• Est. Priority Date: 12/12/2003
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Okutani, Shigeaki, Morita, Noboru, Nakazuru, Toshiro
• Primary Examiner(s): Bullock, Jr.; Lewis A
• Assistant Examiner(s): YAARY, MICHAEL D
• Application Number:
  US10/823,570
• Publication Number:
  US 20050131975A1
• Time in Patent Office: 2,071 Days
• Field of Search: 708400-420, 708/276, 708/270
• US Class Current: 708/270
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm

Abstract

A cyclic equation setting unit transforms and sets a Taylor series equation for calculating a sine function into a single cyclic equation common to terms of the Taylor series equation, the single cyclic equation having a new known number Q that is defined by multiplying a known number Q and the square of a variable X, shifting the result by a shift number S and then adding a constant K thereto. An adjustment unit adjusts and prepares the shift number S such that within a variation range of the variable X the variable X has a maximum value 1 with the constant K being not greater than 1. A cyclic equation executing unit inputs and converts angle information i to the variable X, and executing the cyclic equation in sequence from higher order term to lower order term for the number of terms of the Taylor series equation to derive a sine function of the angle information i.

Claims

1. A function arithmetic method comprising:

a cyclic equation setting step performed by an arithmetic unit of a circuit for transforming and setting a Taylor series equation for calculating a sine function into a single cyclic equation common to terms of the Taylor series equation, the single cyclic equation having a new known number Q that is defined by multiplying a known number Q and the square of a variable X, shifting the result by a shift number S and then adding a constant K thereto;

an adjustment step performed by an adjustment unit of said circuit for adjusting and preparing the shift number S such that within a variation range of the variable X the variable X has a maximum value 1 with the constant K being not greater than 1;

a cyclic equation executing step preformed by the adjustment unit of said circuit for inputting and converting angle information i to the variable X, and executing the cyclic equation in sequence from higher order term to lower order term for the number of terms of the Taylor series equation to derive a sine function of the angle information i; and

an output step outputting the sine function for a fast Fourier transform.

2. The function arithmetic method according to claim 1, wherein the cyclic equation executing step performed by the adjustment unit of said circuit includes executing the arithmetic process of the known number Q, the variable X, an intermediate value after the shifting and the constant K of the cyclic equation with the number of bits that is obtained by adding the number of protect bits to the final number of the bits.

3. A function arithmetic method comprising:

a cyclic equation setting step performed by an arithmetic unit of a circuit for transforming and setting a Taylor series equation for calculating a cosine function into a single cyclic equation common to terms of the Taylor series equation, the single cyclic equation having a new known number Q that is defined by multiplying a known number Q and the square of a variable X, shifting the result by a shift number S and then adding a constant K thereto;

an adjustment step performed by an adjustment unit of said circuit for adjusting and preparing the shift number S such that within a variation range of the variable X the variable X has a maximum value 1 with the constant K being not greater than 1;

a cyclic equation executing step performed by the adjustment unit of said circuit for inputting and converting angle information i to the variable X, and executing the cyclic equation in sequence from higher order term to lower order term for the number of terms of the Taylor series equation to derive a cosine function of the angle information i; and

an output step outputting the cosine function for a fast Fourier transform.

4. The function arithmetic method according to claim 3, wherein the cyclic equation executing step performed by the adjustment unit of said circuit includes executing the arithmetic process of the known number Q, the variable X, an intermediate value after the shifting and the constant K of the cyclic equation with the number of bits that is obtained by adding the number of protect bits to the final number of the bits.

5. A computer including a function arithmetic circuit comprising:

a cyclic equation arithmetic unit calculating a cyclic equation that is obtained by transforming a Taylor series equation for calculating a sine function, the cyclic equation having a new known number Q that is defined by multiplying a known number Q and the square of a variable X, shifting the result by a shift number S and then adding a constant K thereto;

a conversion adjustment unit converting input angle information i into the variable X, as well as adjusting and outputting the shift number S such that the variable X has a maximum value 1 within a variation range of the variable X;

a constant table finding in advance and holding constants K corresponding to terms of a Taylor series equation for calculating a sine function and the shift numbers adjusted such that the constants K becomes not greater than 1;

an arithmetic control unit causing the cyclic equation arithmetic unit to perform a cyclic arithmetic in sequence, based on the selection of the constant K and the shift number S of the constant table, from higher order term to lower order term for the number of terms of the Taylor series equation defined in advance when the variable X is output from the conversion adjustment unit, to thereby derive a sine function of the angle information i; and

an output unit outputting the sine function for a fast Fourier transform.

6. The function arithmetic circuit according to claim 5, wherein the cyclic equation arithmetic unit executes the arithmetic process of the known number Q, the variable X, an intermediate value after the shifting and the constant K of the cyclic equation with the number of bits that is obtained by adding the number of protect bits to the final number of the bits.

7. A computer including a function arithmetic circuit comprising:

a cyclic equation arithmetic unit calculating a cyclic equation that is obtained by transforming a Taylor series equation for calculating a cosine function, the cyclic equation having a new known number Q that is defined by multiplying a known number Q and the square of a variable X, shifting the result by a shift number S and then adding a constant K thereto;

a conversion adjustment unit converting input angle information i into the variable X, as well as adjusting and outputting the shift number S such that the variable X has a maximum value 1 within a variation range of the variable X;

a constant table finding in advance and holding constants K corresponding to terms of the Taylor series equation for calculating a cosine function and the shift numbers adjusted such that the constants K become not greater than 1;

an arithmetic control unit causing the cyclic equation arithmetic unit to perform a cyclic arithmetic in sequence, based on the selection of the constant K and the shift number S of the constant table, from higher order term to lower order term for the number of terms of the Taylor series equation defined in advance when the variable X is output from the conversion adjustment unit, to thereby derive a cosine function of the angle information i; and

an output unit outputting the cosine function for a fast Fourier transform.

8. The function arithmetic circuit according to claim 7, wherein the cyclic equation arithmetic unit executes the arithmetic process of the known number Q, the variable X, an intermediate value after the shifting and the constant K of the cyclic equation with the number of bits that is obtained by adding the number of protect bits to the final number of the bits.

9. A computer including a function arithmetic circuit comprising:

a pipeline arithmetic unit forming a pipeline connection which includes cyclic equation arithmetic units each provided for each term and calculating a cyclic equation obtained by transforming a Taylor series equation for calculating a sine function, the cyclic equation having a new known number Q that is defined by multiplying a known number Q and the square of a variable X, shifting the result by a shift number S and then adding a constant K thereto;

a conversion adjustment unit converting input angle information i into the variable X and adjusting the shift number S such that the variable X has a maximum value 1 within a variation range of the variable X for the output to the pipeline arithmetic unit;

a constant table finding in advance and holding the constants K corresponding to terms of the Taylor series equation for calculating a sine function and the shift numbers adjusted such that the constants K become not greater than 1;

a pipeline control unit causing the cyclic equation arithmetic units of the pipeline arithmetic unit to select the constant K and the shift number S of the corresponding term of the Taylor series equation from the constant table, to calculate in parallel and to derive a sine function of the angle information i based on the output of the cyclic equation arithmetic unit at the final stage, each time the variable X is output from the conversion adjustment unit; and

an output unit outputting the sine function for a fast Fourier transform.

10. The function arithmetic circuit according to claim 9, wherein the cyclic equation arithmetic units of the pipeline arithmetic unit execute the arithmetic process of the known number Q, the variable X, an intermediate value after the shifting and the constant K of the cyclic equation with the number of bits that is obtained by adding the number of protect bits to the final number of the bits.

11. A computer including a function arithmetic circuit comprising:

a pipeline arithmetic unit forming a pipeline connection which includes cyclic equation arithmetic units each provided for each term and calculating a cyclic equation obtained by transforming a Taylor series equation for calculating a cosine function, the cyclic equation having a new known number Q that is defined by multiplying a known number Q and the square of a variable X, shifting the result by a shift number S and then adding a constant K thereto;

a conversion adjustment unit converting input angle information i into the variable X and adjusting the shift number S such that the variable X has a maximum value 1 within a variation range of the variable X for the output to the pipeline arithmetic unit;

a constant table finding in advance and holding the constants K corresponding to terms of the Taylor series equation for calculating a cosine function and the shift numbers adjusted such that the constants K become not greater than 1;

a pipeline control unit causing the cyclic equation arithmetic units of the pipeline arithmetic unit to select the constant K and the shift number S of the corresponding term of the Taylor series equation from the constant table, to calculate in parallel and to derive a cosine function of the angle information i based on the output of the cyclic equation arithmetic unit at the final stage, each time the variable X is output from the conversion adjustment unit; and

an output unit outputting the cosine function for a fast Fourier transform.

12. The function arithmetic circuit according to claim 11, wherein the cyclic equation arithmetic units of the pipeline arithmetic unit execute the arithmetic process of the known number Q, the variable X, an intermediate value after the shifting and the constant K of the cyclic equation with the number of bits that is obtained by adding the number of protect bits to the final number of the bits.

13. A computer including a function arithmetic circuit comprising a sine function arithmetic circuit and a cosine function arithmetic circuit,

the sine function arithmetic circuit including:

a pipeline arithmetic unit forming a pipeline connection which includes cyclic equation arithmetic units each provided for each term and calculating a cyclic equation obtained by transforming a Taylor series equation for calculating a sine function, the cyclic equation having a new known number Q that is defined by multiplying a known number Q and the square of a variable X, shifting the result by a shift number S and then adding a constant K thereto;

a conversion adjustment unit converting input angle information i into the variable X and adjusting the shift number S such that the variable X has a maximum value 1 within a variation range of the variable X for the output to the pipeline arithmetic unit;

a constant table finding in advance and holding the constants K corresponding to terms of the Taylor series equation for calculating a sine function and the shift numbers adjusted such that the constants K become not greater than 1;

a pipeline control unit causing the cyclic equation arithmetic units of the pipeline arithmetic unit to select the constant K and the shift number S of the corresponding term of the Taylor series equation from the constant table, to calculate in parallel and to derive a sine function of the angle information i based on the output of the cyclic equation arithmetic unit at the final stage, each time the variable X is output from the conversion adjustment unit; and

a sine function outputting unit outputting the sine function, and wherein

the cosine function arithmetic circuit including;

a pipeline arithmetic unit forming a pipeline connection which includes cyclic equation arithmetic units each provided for each term and calculating a cyclic equation obtained by transforming a Taylor series equation for calculating a cosine function, the cyclic equation having a new known number Q that is defined by multiplying a known number Q and the square of a variable X, shifting the result by a shift number S and then adding a constant K thereto;

a conversion adjustment unit converting input angle information i into the variable X and adjusting the shift number S such that the variable X has a maximum value 1 within a variation range of the variable X for the output to the pipeline arithmetic unit;

a constant table finding in advance and holding the constants K corresponding to terms of the Taylor series equation for calculating a cosine function and the shift numbers adjusted such that the constants K become not greater than 1;

a pipeline control unit causing the cyclic equation arithmetic units of the pipeline arithmetic unit to select the constant K and the shift number S of the corresponding term of the Taylor series equation from the constant table, to calculate in parallel and to derive a cosine function of the angle information i based on the output of the cyclic equation arithmetic unit at the final stage, each time the variable X is output from the conversion adjustment unit; and

a cosine function outputting unit outputting the cosine function for a fast Fourier transform.

14. The function arithmetic circuit according to claim 13, wherein the cyclic equation arithmetic units of the pipeline arithmetic unit execute the arithmetic process of the known number Q, the variable X, an intermediate value after the shifting and the constant K of the cyclic equation with the number of bits that is obtained by adding the number of protect bits to the final number of the bits.

15. The function arithmetic circuit according to claim 13, wherein twist coefficient values of a plurality of butterfly stages provided in a pipeline fast Fourier transform apparatus whose radix is 2 are calculated based on the sine function and cosine function of the input information i.

16. A function arithmetic method comprising:

a cyclic equation setting step performed by an arithmetic unit of a circuit for transforming and setting a Taylor series equation for calculating a transcendental function into a single cyclic equation common to terms of the Taylor series equation, the cyclic equation having a new known number Q that is defined by multiplying a known number Q and a variable X, shifting the result by a shift number S and then adding a constant K thereto;

an adjustment step performed by an adjustment unit of said circuit for adjusting and preparing the shift number S such that within a variation range of the variable X the variable X has a maximum value 1 with the constant K being not greater than 1;

a cyclic equation executing step performed by the adjustment unit of said circuit for converting input information to the variable X and executing the cyclic equation in sequence from higher order term to lower order term for the number of terms of the Taylor series equation to thereby derive a transcendental function of the input information; and

an outputting step outputting the transcendental function for a fast Fourier transform.