Arithmetic method and function arithmetic circuit for a fast fourier transform

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
3Forward
Citations 
0
Petitions 
1
Assignment
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
8 Citations
View as Search Results
Trigonometric wave generation circuit using series expansion  
Patent #
US 20050262175A1
Filed 05/18/2005

Current Assignee
ROHM Co. Ltd.

Sponsoring Entity
ROHM Co. Ltd.

Processor for realizing at least two categories of functions  
Patent #
US 10,372,359 B2
Filed 05/10/2017

Current Assignee
ChengDu HaiCun IP Technology LLC

Sponsoring Entity
ChengDu HaiCun IP Technology LLC

Configurable processor with inpackage lookup table  
Patent #
US 10,445,067 B2
Filed 11/28/2018

Current Assignee
Hangzhou Haicun Information Technology Co. Ltd.

Sponsoring Entity
Hangzhou Haicun Information Technology Co. Ltd.

Computer system and method for parallel computations using table approximation methods  
Patent #
US 6,363,405 B1
Filed 12/24/1998

Current Assignee
Elbrus International Limited

Sponsoring Entity
Elbrus International Limited

High resolution phase to sine amplitude conversion  
Patent #
US 4,905,177 A
Filed 01/19/1988

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

Apparatus for rapidly determining the trigonometric functions of an input angle  
Patent #
US 4,077,063 A
Filed 08/11/1976

Current Assignee
Hughes Aircraft Company

Sponsoring Entity
Singer PLC

MAGNETICALLY COUPLED IMPLANTABLE SERVOMECHANISM  
Patent #
US 3,569,894 A
Filed 04/14/1969

Current Assignee
George F. Schwoboda, Lee R. Bolduc

Sponsoring Entity
George F. Schwoboda, Lee R. Bolduc

DIGITAL DIFFERENTIAL ANALYZER  
Patent #
US 3,564,223 A
Filed 06/04/1968

Current Assignee
Harris Robert Herbert, Owen Phillip Lance

Sponsoring Entity
Harris Robert Herbert, Owen Phillip Lance

16 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.  View Dependent Claims (2)
 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.  View Dependent Claims (4)
 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.  View Dependent Claims (6)
 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.  View Dependent Claims (8)
 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.  View Dependent Claims (10)
 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.  View Dependent Claims (12)
 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.  View Dependent Claims (14, 15)
 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.
1 Specification
1. Field of the Invention
The present invention relates generally to a function calculation method and a function arithmetic circuit for calculating a sine function and a cosine function with the Taylor series equation and, more particularly, to a function calculation method and a function arithmetic circuit for calculating for use a sine function and a cosine function in synchronism with an arithmetic cycle of fast Fourier transform.
2. Description of the Related Arts
Traditionally, in information processing apparatuses using computers, sine functions and cosine functions calculated from angle information are sometimes used. Especially, when signal processes such as Fourier transform are performed by hardware, values of a sine function and a cosine function are found using angle information as an address and are used in an arithmetic process.
By the way, traditionally, as a method for finding a sine function and a cosine function corresponding to the angle information indicating the address, a lookup table 210 of
θi=2πi/N
The Taylor series of the sine and the cosine for this ith angle θi is as follows.
However, in these conventional methods for finding a sine function and a cosine function with the use of Taylor series equations, there are following problems. First, as shown in
According to the present invention there are provided a function arithmetic method and a function arithmetic circuit for calculating a sine function and a cosine function at a high speed utilizing the Taylor series equation. The present invention aims at providing a function arithmetic method and apparatus for calculating a sine function and a cosine function at a high speed utilizing the Taylor series equation, without using lookup table memory, for use in calculation of a twist coefficient of fast Fourier transform.
The present invention provides a function arithmetic method for calculating a sine function sin θ i using a Taylor series equation. The function arithmetic method comprises a cyclic equation setting step, with a cyclic equation setting unit, transforming and setting a Taylor series equation for calculating a sine function into a single cyclic equation (Q=K+S·X^{2}·Q) 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, with an adjustment unit, 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; and a cyclic equation executing step, with a cyclic equation execution unit, 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. In this case, the cyclic equation executing step 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.
The present invention provides a function arithmetic method for calculating a cosine function cos θ i using a Taylor series equation. The function arithmetic method comprises a cyclic equation setting step, with a cyclic equation setting unit, transforming and setting a Taylor series equation for calculating a cosine function into a single cyclic equation (Q=K+S·X^{2}·Q) 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, with an adjustment unit, 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; and a cyclic equation executing step, with a cyclic equation execution unit, 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. In this case as well, the cyclic equation executing step 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.
The present invention provides a function arithmetic circuit for calculating a sine function sine θ i using a Taylor series equation. The function arithmetic circuit comprises a cyclic equation arithmetic unit calculating a cyclic equation (Q=K+S·X^{2}·Q) 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; and 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. In this case, 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.
The present invention provides a function arithmetic circuit for calculating a cosine function cos θ i using a Taylor series equation. The function arithmetic circuit comprises a cyclic equation arithmetic unit calculating a cyclic equation (Q=K+S·X^{2}·Q) 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; and 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. In this case, 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.
The present invention provides a function arithmetic circuit for pipeline calculating a sine function sin θ i using a Taylor series equation. The function arithmetic circuit comprises a pipeline arithmetic unit forming a pipeline connection which includes cyclic equation arithmetic units each provided for each term and calculating a cyclic equation (Q=K+S·X^{2}·Q) 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; and 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. In this case, 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.
The present invention provides a function arithmetic circuit for pipeline calculating a cosine function cos θ i using a Taylor series equation. The function arithmetic circuit comprises a pipeline arithmetic unit forming a pipeline connection which includes cyclic equation arithmetic units each provided for each term and calculating a cyclic equation (Q=K+S·X^{2 }·Q) 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; and 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. In this case as well, 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.
The present invention provides a function arithmetic circuit for pipeline calculating a sine function and a cosine function, suitable for a fast Fourier transform apparatus. The function arithmetic circuit comprises a sine function arithmetic circuit and a cosine function arithmetic circuit. The sine function arithmetic circuit includes a pipeline arithmetic unit forming a pipeline connection which includes cyclic equation arithmetic units each provided for each term and calculating a cyclic equation (Q=K+S·X^{2}·Q) 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; and 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. The cosine function arithmetic circuit includes a pipeline arithmetic unit forming a pipeline connection which includes cyclic equation arithmetic units each provided for each term and calculating a cyclic equation (Q=K+S·X^{2}·Q) 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; and 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. In this case, 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.
In this function arithmetic circuit, 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.
The present invention provides a function arithmetic method for calculating, using a Taylor series equation, general transcendental functions including sine functions and cosine functions, i.e., transcendental functions that are defined as functions that cannot be expressed in the form of polynomials, such as trigonometric functions, logarithms and exponential functions. The function arithmetic method comprises a cyclic equation setting step, with a cyclic equation setting unit, transforming and setting a Taylor series equation for calculating a transcendental function into a single cyclic equation (Q=K+S·X^{2}·Q) 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, with an adjustment unit, 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; and a cyclic equation executing step, with a cyclic equation execution unit, 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.
Thus, according to the present invention, by transforming a Taylor series equation into one (1) cyclic equation which is common to terms of the Taylor series equation, details of arithmetic which is performed from higher order to lower order can be standardized, and in both cases of performing cyclic calculation and performing pipeline calculation, an arithmetic algorithm is simplified; a processing load is reduced in software; a circuit structure is simplified in hardware; and a higher speed can be achieved in both. Also, by introducing shift operations of bits, even with the same minimum small number of arithmetic bits, necessary arithmetic bit accuracy can be ensured. As a result, without using floatingpoint arithmetic or an arithmetic circuit with the large number of bits, fixedpoint arithmetic circuit with the small number of bits can be used, and function calculation with small hardware can be easily achieved. Further, by applying a pipeline function arithmetic circuit of the present invention to a fast Fourier transform apparatus, a twist coefficient can be calculated in real time, and conventional memory for holding the twist coefficient is unnecessary, and if the number of fast Fourier transform points becomes larger, the twist coefficient can be accurately generated by smaller hardware than the case of using the twist coefficient memory.
Consequently, although the conventional Fourier transform apparatus is constructed by integrating butterfly arithmetic circuits and others into LSI and using external memory for the twist coefficient, it is possible to relatively easily construct it with LSI only, by using the pipeline function arithmetic circuit of the present invention.
The above and other objects, features and advantages of the present invention will become more apparent from the following detailed description with reference to the drawings.
Qd=Kd+S(d+2)·Xi^{2}·[Q(d+2)] (1)
In the cyclic equation (1), the Taylor series equation is to multiply known number Q(d+2) by a squared variable Xi and shift the result by a shift number S(d+2). A transform process from this Taylor series equation to the cyclic equation is clarified in description below. For the cyclic equation of equation (1), the adjustment unit 14 adjusts the variable Xi such that a maximum value of the variable Xi becomes 1 within a transform range and the shift number S(d+2) such that the a constant Kd will be not greater than 1 and prepares this in the constant table 16 in advance. In the case that the sine function and the cosine function are calculated for angles of 0 to 45 degrees and the case that calculated for angles of 0 to 90 degrees. An example of the constant Kd and the shift number Sd stored in the constant table 16 are shown in
In the constant table 16 of
In this function arithmetic process, after a setting process of the cyclic equation of the equation (1) is performed in step S1, by adjusting the shift number Sd in order to optimize the variable Xi and the constant Kd in step 2, the table 16 such as shown in
cos(α+β)=cos α·cos β−sin α·sin β
sin(α+β)=cos α·sin β+sin α·cos β
can be used to derive these. These formulas of trigonometric functions are transformed into following equations.
cos(90°+β)=cos 90°·cos β−sin 90°·sin β=0·cos β−1·sin β=−sin β
sin(90°+β)=cos 90°·sin β+sin 90°·cos β=0·sin β+1·cos β=cos β
For example, in the case of an angle of 120 degrees, since 90°+β=120°, β=30° is derived.
Therefore:
cos 120°=−sin 30°; and
sin 120°=cos 30°
can be found. The sine function and the cosine function in the range of angles 45 to 90 degrees can also be easily found from the sine function and the cosine function of angles 0 to 45 degrees which is found by the function arithmetic of the present invention. In other words, these can be derived from following equations which are formulas of trigonometric functions.
cos(α−β)=cos α·cos β+sin α·sin β
sin(α−β)=−cos α·sin β+sin α·cos β
These formulas of trigonometric functions are transformed into following equations.
cos(90°−β)=cos 90°·cos β+sin 90°·sin β=0·cos β+1·sin β=sin β
sin(90°−β)=−cos 90°·sin β+sin 90°·cos β=−0·sin β+1·cos β=cos β
For example, in the case that the sine function and the cosine function of an angle of 60 degree, since 90°−β=60°, β=30° is derived.
Therefore:
cos 60°=sin 30°; and
sin 60°=cos 30°
can be found.
Described here is transformation to the cyclic equation in the case that the sine function and the cosine function for angles 0 to 45 degrees are found. Since the angle address i is within the range of angles 0 to 45 degrees, the value of the address varies from 0 to N/8. Since the address i represents the ith angle θ i in the case that angles 0 to 360 degrees are divided equally into N, this is given by following equation.
θi=2πi/N (2)
Using the equation (2) which indicates the angle θ i, the Taylor series equation is developed as follows.
In this development of the Taylor series equation, a first row is the original Taylor series equation, and in a second row, the value of θ i of the equation (2) is substituted in the equation. In third and fourth rows of the equation, by substituting N=8(N/8), it is transformed into exponentiation of 2. In fifth and sixth rows, portions in brackets are divided into the variable portions and the constant portions.
In the present invention, the constant Kd of the cyclic equation of the equation (1) will be a value which is not greater than 1 and close to 1 as much as possible. For example, by dividing 2π=6.28 in the first term of fifth and sixth rows in the transformed equation of the Taylor series equation by 2^{3}=8, K1=0.785 can be derived. In other words, if 2π=6.28 is divided by 2^{2}=4, K1=1.57 is derived, which can not be adopted because this is greater than 1, and if divided by 2^{4}=16,K1=0.3925 is derived, which is far from 1, and therefore, by dividing by 2^{3}=8,the constant K1 can be a value which is not greater than 1 and close to 1 as much as possible. The constants of the transformed equation of the Taylor series equation can be summarized as following equation.
For this equation, the constants K1,K3,K5 and K7 are defined as follows.
K1=[2π/2^{3}]
K3=−[(2π)^{3}/(3!·2^{6})]
K5=[(2π)^{5}/(5!·2^{7})]
K7=−[(2π)^{7}/(7!·2^{7})]
By transforming, using the constants K1, K3, K5 and K7,following equation can be obtained.
In this transformed equation, the constants K1, K3,K5 and K7 are substituted in a first row, and {i/(N/8)} are bundled out for the portion in brackets in a second row. In third and fourth rows, 2^{−3 }is bundled for first and second terms in braces on the right side. In fifth and sixth rows, 2^{−5 }is further bundled for the second term and subsequent terms in that. Finally, in a seventh row, 2^{−6 }is bundled for the third term. For the above transformed equation, when as variable Xi:
Xi=i/(N/8)
is defined, and as bit shift numbers S3,S5 and S7:
S3=2^{−3 }
S5=2^{−5 }
S7=2^{−6 }
are defined, and as known numbers Q7,Q5,Q3 and Q1:
Q7=K7+ . . .
Q5=K5+S7·Xi^{2}·[Q7]
Q3=K3+S5·Xi^{2}·[Q5]
Q1=K1+S3·Xi^{2}·[Q3]
are defined, following equation can be obtained.
The cyclic portion of the sine function in this transformed equation takes values of d=1, 3, 5, 7 . . . ,and following equation is given, which is the same as the equation (1).
Qd=Kd+S(d+2)·Xi^{2}·[Q(d+2)]
Therefore, in calculation of sin θ unit with the use of this cyclic equation, the sine function sin θ i can be found by sequentially calculating the cyclic equation in the order of d=7, 5, 3 and 1 to find Q7,Q5,Q3 and Q1 and finally multiplying by Xi. For Q7 as an initial value, the constant K7 is used.
Similarly, transform from the Taylor series equation to the cyclic equation for the cosine function Is described as follows. By substituting the equation (2) in the Taylor series equation of cos θ i, the transformed equation becomes as follows.
By defining constants K0,K2,K4 and K6 as:
K0=1
K2=−[(2π)^{2}/(2!·2^{5})]
K4=[(2π)^{4}/(4!·2^{7})]
K6=−[(2π)^{6}/(6!·2^{7})]
and transforming, following equation is given.
At this point, by defining the variable Xi as:
Xi=i/(N/8)
and the shift numbers S2,S4 and S6 as:
S2=2^{−1 }
S4=2^{−4 }
S6=2^{−6 }
and the known number Q6,Q4,Q2 and Q0 as:
Q6=K6+ . . .
Q4=K4+S6·Xi^{2}·[Q6]
Q2=K2+S4·Xi^{2}·[Q4]
Q0=K0+S2·Xi^{2}·[Q2]
it is possible to transform to following equation.
The cyclic portion of the cosine function in this transformed equation of the Taylor series equation takes values of d=0, 2, 4, 6. . . , and the cyclic equation which is common to terms of the Taylor series equation is:
Qd=Kd+S(d+2)·Xi^{2}·[Q(d+2)]
which is the same as the equation (1).
Step S1: Input the address i which indicates angles.
Step S2: Since calculation from 0 to 45 degrees is performed with the address i, define the variable Xi as Xi=i/(N/8) and normalize such that the maximum value results in 1.
Step S3: Calculate the square of the variable Xi.
Step S4: Set d=7 which is the number of terms indicating termination of the Taylor series equation, find the constant K(7) from the constant table 16 of
Step S5: Define d as d=d−2.
Step S6: Check whether d is not less than 1. If it is not less than 1,proceed to step S7, and if less than 1,proceed to step S8.
Step S7: Sequentially calculate the cyclic equation in the order of D=5, 3, 1,through the route of steps S5 to S7, for the known number Q5, Q3 and Q1.
Step S8: This is the case that arithmetic of the cyclic equation is terminated because d becomes less than 1,and therefore, by multiplying the known number Q(1) by the variable Xi, sin θ i is calculated.
Step S9: Output the calculated value of sin θ i.
Step S1: Input the address i which indicates angles.
Step S2: Divide the address i by (N/8) to find the variable Xi which is normalized such that the maximum value becomes 1.
Step S3: Calculate the square of the variable Xi.
Step S4: Set d=6 and substitute the constant K(d) pick up from t=6 on the cosine side of
Step S5: Calculate d=d−2.
Step S6: Check whether d is not less than 0. If it is not less than 0,proceed to step S7, and if it is minus, proceed to step S8.
Step S7: Sequentially calculate the cyclic equation for d=4, 2, 0, through the route process of steps S5 to S7, to sequentially find Q(4), Q(2) and Q(0).
Step S8: This is the case that arithmetic of the cyclic equation is terminated because d becomes minus, and in this case, Q(0) which is found at the last in steps S5 to S7 is considered as cos θ i.
Step S9: Output the value of cos θ i found by the arithmetic process.
Constant Qd=sb.bbbb bbbb gg
Variable Xi=b.bbbb bbbb gg
Square of variable Xi=b.bbbb bbbb gg
Constant Kd=sb.bbbb bbbb gg
In the constant table 16 of
Step S1: Input the address i.
Step S2: Find the variable Xi by the shift process of the address i. At this point, two (2) bits of the protect bits are added to the variable Xi.
Step S3: Square the variable Xi and round the result with half adjust.
Step S4: Set d=7 and define the known number Q(d) as the constant K(7) which is read from the constant table 16 of
Step S5: Calculate d=d−2. d is varied to 5, 3, 1 and 0 by the cyclic process.
Step S6: Check whether d is not less than 1. If it is not less than 1,proceed to step S7, and if less than 1,proceed to step S8.
Step S7: Multiply the variable Xi^{2 }by the known number Q(b+2) and round the results with half adjust to obtain the intermediate value W. Perform the shift process of the intermediate value W with the shift number S(d+2). Round the value obtained by adding the constant K(d) to the intermediate value W with half adjust to obtain new known number Q(d). This calculation is repeated three (3) times for d=5, 3, 1.
Step S8: This is the case that the cyclic calculation is terminated because d becomes less than 1,and sin θ i is found by multiplying Q(1) by the variable Xi, and the value of the final number of bits is found by rounding the results with half adjust.
Step S9: Output sin θ i as the arithmetic result.
Step S1: Input the address i.
Step S2: Find the variable Xi by the shifting address I by (N/8). At this point, two (2) bits are added to the variable Xi as the protect bits.
Step S3: Find the square of the variable Xi^{2 }and round it with half adjust.
Step S4: Set d=6 and define the known number Q(6) as the constant K(6) which is found from the constant table 16 of
Step S5: Calculate d=d−2. In this case, d is varied to d=4, 2, 0.
Step S6: Check whether d is not less than 0. If it is not less than 0,proceed to step S7, and if it is minus, proceed to step S8.
Step S7: Multiply the variable Xi^{2 }by the known number Q(b+2) and find the intermediate value W by rounding with half adjust. Then, after performing the shift process of the intermediate value W with the shift number S(d+2), add the constant K(d) and perform rounding with half adjust to find new known number Q(d). This arithmetic process is executed three (3) times for Q(4), Q(2) and Q(0) through the loop process from S5 to S7.
Step S8: This is the case that the cyclic arithmetic is terminated because d becomes minus, and cos θ i with the final number of bits is found by rounding Q(0) found in step S7 with half adjust.
Step S9: Output cos θ i as the arithmetic result.
For rounding in the processes of
In
Referring again to
Multiplication of these twist coefficients and each of data on each stage of
(The first stage) X0 (8)·W^{0}, X0 (9)·W^{0}, X0 (10)·W^{0}, X0 (11)·W^{0}, X0 (12)·W^{0}, X0 (13)·W^{0}, X0 (14)·W^{0}, X0 (15)·W^{0 }
(The second stage) X1 (4)·W^{0}, X1 (5)·W^{0}, X1 (6)·W^{0}, X1 (7)·W^{0},
X1 (12)·W^{4}, X1 (13)·W^{4}, X1 (14)·W^{4}, X1 (15)·W^{4 }
(The third stage) X2 (2)·W^{0}, X2 (3)·W^{0},
X2 (6)·W^{4}, X2 (7)·W^{4},
X2 (10)·W^{2}, X2 (11)·W^{2},
X2 (14)·W^{6}, X2(15)·W^{6 }
(The fourth stage) X3 (1)·W^{0},
X3 (3)·W^{4},
X3 (5)·W^{2},
X3 (7)·W^{6},
X3 (9)·W^{1},
X3 (11)·W^{5},
X3 (13)·W^{3},
X3 (15)·W^{7 }
These twist coefficients used in the butterfly arithmetic units 122, 132, 136 and 140 are calculated in each of function arithmetic units 1441 and 1442 in real time, based on the address i given from address calculation units 1421 and 1422. Each of the twist coefficient arithmetic units 1441 and 1442 is provided with the sine function pipeline arithmetic circuit 253 shown in
W^{p}=e^{−j2πp/N}=cos(2πp/N)−j·sin(2πp/N)
In this multiplication of complex numbers, the cosine function and the sine function must be calculated with an address p as an input, and this is achieved by the pipeline cosine function arithmetic circuit and sine function arithmetic circuit of the present invention. The twist coefficient arithmetic unit 1441 calculates the necessary twist coefficients by the arithmetic timing of the butterfly arithmetic of each stage in the fast Fourier transform and stores these into the buffer 145, 146, 148 and 150. In other words, the twist coefficient arithmetic unit 1441 calculates W^{0}, W^{0}, W^{4}, W^{0}, W^{2}, W^{4 }and W^{6 }as a twist coefficient sequence 300 as time t elapses and stores the twist coefficients indicated by black borders into the buffer registers 145, 146 and 148 such that one (1) type is stored for the first stage, two (2) types for the second stage and four (4) types for the fourth stage. The twist coefficient arithmetic unit 1442 is provided exclusively for the fourthstage butterfly arithmetic unit 140, sequentially calculates W^{0}, W^{4}, W^{2}, W^{6}, W^{1}, W^{5}, W^{3 }and W^{7 }as a twist coefficient sequence 302 as time t elapses and stores this into the buffer 150. Then, the butterfly multiplication will be performed, in which the underside input data of sets of two (2) input data shown on the first stage to the fourth stage of
A twist coefficient arithmetic circuit of
In above embodiments, the sine function and the cosine function are taken as an example of the arithmetic process which is processed by transforming the Taylor series equation into the cyclic equation, but it is possible to apply to other trigonometric functions, such as a tangent function, a cosecant function, a secant function and cotangent function, and a logarithmic function and an exponential function included in general transcendental functions other than trigonometric functions to which the Taylor series equation is applied. When the Taylor series equation for the general transcendental functions other than trigonometric functions are transformed into the cyclic type of the present invention, the variable may be simply defined as X, rather than X^{2}, and the Taylor series equation may be transformed into the cyclic equation which multiplies the known number Q and the variable X, shifts the result by the shift number S and then adds variable K to obtain new known number Q.
The present invention has been described such that the hardware circuit can be easily achieved by defining the variable Xi such that its maximum value becomes 1 and the constant Kd to be not greater then 1,but considering the configuration of the arithmetic processing circuit or movement of the decimal point position, it is not limited to this value. In the case of hardware using the floatingpoint arithmetic circuit or the case of the software process by CPU or DSP which can use the floatingpoint arithmetic, by only transforming the Taylor series equation into the cyclic equation, it is possible to cut down the number of times of arithmetic, to reduce the processing load and to achieve the highspeed processing.
Although in the above embodiments the case has been taken as an example where the arithmetic results of the sine function and the cosine function are applied to the fast Fourier transform, the present invention is not limited thereto but is directly applicable to any suitable apparatuses which utilize the arithmetic results of the sine function and the cosine function.