Field of the Invention
This invention is concerned with transcendental function evaluation (TFE). More particularly, this invention is concerned with a method and device for digital signal processing evaluation of trigonometric functions.
Background of the Invention
Volder first proposed a CORDIC algorithm to utilize hardware implementation for evaluating trigonometric functions in fixed point arithmetic. The CORDIC computing technique typically utilizes a special arithmetic unit for implementing a prescribed sequence of conditional additions or subtractions for evaluating trigonometric functions.
Walther, in A Unified Algorithm for Elementary Functions, Spring Joint Computer Conference, 1971 describes a generalization of the CORDIC algorithm typically for fixed point arithmetic implementation, and typically implemented in hardware due to dilatory execution when implemented in software.
Utilization of the CORDIC algorithm generally may not be feasible in some hardware systems, and software implementation of the CORDIC algorithm generally provides slow evaluation of trigonometric functions. Thus, an efficient floating point trigonometric function evaluator is needed.
Summary of the Invention
A method and apparatus are provided for substantially processing an input value to provide at least one output trigonometric function value of the input value. A modifier utilizes the input value to generate an approximation value. A first memory device (a first ROM) and a function generator determine a first function value and a second function value, typically a sine function value and a cosine function value, respectively, typically utilizing the first ROM and a second memory device. Clearly, the first ROM and the second memory device may be portions of one memory device, typically a ROM, or may be separate memory devices.
An error generator generates an error value, typically a first difference value of the input value minus the approximation value. A correction evaluator substantially utilizes the error value to determine at least one correction value, typically utilizing at least one predetermined number of at least one predetermined mathematical series. Generally, at least one selected power series is utilized as the at least one predetermined mathematical series.
A combiner utilizes at least one correction value, the first function value, and the second function value to determine at least one output trigonometric function value of the input value. Typically, the combiner determines at least one of: a sine function value, a cosine function value, and a tangent function value, respectively, the reciprocals of those values clearly being readily determined also.
Brief Description of the Drawings
FIG. 1A is a block diagram of a computer hardware implementation of the invention; FIG. 1B sets forth one embodiment of a correction evaluator; and FIG. 1C sets forth one embodiment of a combiner of FIG. 1A.
FIG. 2A is a general flow chart of an implementation of the method of the invention; FIG. 2B sets forth one implementation of a step of determining at least one correction value, CV; and FIG. 2C sets forth one implementation of a step of determining at least one output trigonometric function value, OTF.
Best Mode for Carrying Out the Invention
FIG. 1A, generally depicted by the numeral 100, sets forth one embodiment of a computer hardware implementation of the invention. A modifier (102) utilizes an input value .times. (101) to determine an approximation value, the approximation value being selected from a predetermined set of values. The predetermined set of values typically is a group of approximation values determined by selected rounding algorithms, thereby providing the approximation value as a value having a number of bits less than or equal to a number of bits of precision of the input value.
A first memory device (a first ROM) (106) determines a first function value, typically a sine function value of the approximation value. A function generator (108) determines a second function value, typically a cosine function value of the approximation value, and generally determined by utilizing a memory device as described above. It is clear that the first memory device and the function generator may be reversed, and subsequent output utilizations modified pursuant to that reversal. It is also clear that one or more memory devices may be utilized in the first and second function value determinations.
An error generator (104) utilizes the input value and the approximation value to substantially obtain an error value, c, typically a first difference of the input value minus the approximation value.
The correction evaluator (110), one embodiment of which is set forth in FIG. 1B, numeral 125, substantially obtains at least one correction value. The correction evaluator (110) utilizes at least one of:
a first determiner (114) for utilizing c together with a first predetermined number (1st PN) of terms of a first predetermined mathematical series (FPS), substantially a first power series ##EQU1## where n=1,2,3,4, . . . and c=the error value, to substantially evaluate the 1st PN of terms of the FPS and to substantially sum the evaluated 1st PN of terms obtained thereby, the first sum being substantially a first correction value (CV1);
a second determiner (116) for utilizing c together with a second predetermined number (2nd PN) of terms of a second predetermined mathematical series (SPS), substantially a second power series ##EQU2## where n=1,2,3,4, . . . and c=the error value, to substantially evaluate the 2nd PN of terms of the SPS, and to substantially sum the evaluated 2nd PN of terms obtained thereby, obtaining substantially a second sum, the second sum being substantially a second correction value (CV2); and
a third determiner (118) for utilizing c together with a third predetermined number (3rd PN) of terms of a third predetermined mathematical series (TPS), substantially a third power series, ##EQU3## where n=1,2,3,4, . . . , c=the error value, and B.sub.2n is a 2nth Bernoulli number, to substantially evaluate the 3rd PN of terms of the TPS, and to substantially sum the evaluated 3rd PN of terms obtained thereby, obtaining substantially a third sum, the third sum being substantially a third correction value (CV3).
Examples of the 1st PN, the 2nd PN, and the 3rd PN predeterminations for selected bit multiplication factors (BMFs) are set forth in TABLE 1 below, described more particularly following that table, set forth on the next page:
The 1st PN of terms is substantially a largest first integer less than or equal to a first quotient of {(BMF+1)/2}, where BMF is a bit multiplication factor that is substantially a smallest first integer greater than or equal to a second quotient of a desired number of bits of accuracy in the output trigonometric function value divided by a number of bits of accuracy of a lesser of the first function value and the second function value. The 2nd PN of terms is substantially a largest second integer less than or equal to a third quotient of {BMF/2}, and the 3rd PN of terms is substantially a smallest third integer greater than or equal to a fourth quotient of {(BMF-1)/2}.
The combiner (112), one implementation of which is set forth in FIG. 1C, numeral 150, utilizes at least one correction value, the first function value, and the second function value to determine at least one output trigonometric function value, f(x).apprxeq.OTF, of the input value x. The combiner (112) typically utilizes at least three of:
a second combiner (120) to substantially determine a first combined output value, substantially being at least a first product of the first correction value and the first function value;
a third combiner (130) to substantially determine a second combined output value, substantially being at least a second product of the second correction value and the second function value;
a fourth combiner (122) to substantially determine a third combined output value, substantially being at least a third product of the first correction value and the second function value;
a fifth combiner (128) to substantially determine a fourth combined output value, substantially being at least a fourth product of the second correction value and the first function value;
a sixth combiner (132) to substantially determine a fifth combined output value, substantially being at least a fifth product of the third correction value and first function value;
a seventh combiner (134) to substantially determine a sixth combined output value, substantially being at least a sixth product of the third correction value and the second function value; and
an eighth combiner (124A, 124B, 124C, 124D, 124E) to utilize at least two of: the first combined output value, the second combined output value, the third combined output value, the fourth combined output value, the fifth combined output value, the sixth combined output value, the first function value, and the second function value, substantially determining the at least one output trigonometric function value of the input value.
The eighth combiner (124A, 124B, 124C, 124D, 124E), as set forth in FIG. 2C, numeral 250, includes at least two of:
a first adder (124A) to substantially determine a fourth sum of the first combined output value and the second combined output value, being substantially a sine value of the input value;
a second subtracter (124B) to determine a second difference of the fourth combined output value subtracted from the third combined output value, being substantially a cosine value of the input value;
a third subtracter (124D) to substantially determine a third difference of the fifth combined output value subtracted from the second function value;
a second adder (124C) to substantially determine a fifth sum of the sixth product and the first function value; and
a first divider (124E) to substantially determine a fifth quotient of the fifth sum divided by the third difference, being substantially a tangent value of the input value.
A microprocessor system device can be utilized to implement the above-described invention.
FIG. 2A, generally depicted by the numeral 200, depicts a general flow chart of an implementation of the method of the invention. The best mode of implementing the method of the present invention typically is initiated as follows: a value is input (202), and an approximation value is generated (204), a.apprxeq.mod(x), typically by selecting an approximation value from a predetermined set of values that is generally predetermined by selected rounding algorithms.
An error value, c, is generated (206), typically being substantially a first difference of the input value minus the approximation value, c.apprxeq.x-a. At least one memory device is typically utilized to substantially determine a first function value f1 (208), generally being a first trigonometric function value of the approximation value, a, and a second function value, f2 (208), generally being a second trigonometric function value of the approximation value, a. The first and second trigonometric function values typically are a sine value, and a cosine value, respectively. It is clear that the first and second trigonometric function values may be be selected in reverse, being a cosine value and a sine value, respectively, with subsequent steps being modified to accommodate that reversal.
Further, at least one correction value (CV) is determined (210). In one embodiment, as set forth in FIG. 2B, numeral 225, the step of determining at least one correction value (214) includes at least one of:
utilizing the error value together with a first predetermined number of terms of a first predetermined mathematical series to substantially evaluate the first predetermined number of terms, and to substantially sum the evaluated first predetermined number of terms obtained thereby, obtaining substantially a first sum, the first sum being substantially a first correction value, CV1;
utilizing the error value together with a second predetermined number of terms of a second predetermined mathematical series to substantially evaluate the second predetermined number of terms, and to substantially sum the evaluated predetermined number of terms obtained thereby, obtaining substantially a second sum, the second sum being substantially a second correction value, CV2; and
utilizing the error value together with a third predetermined number of terms of a third predetermined mathematical series to substantially evaluate the third predetermined number of terms, and to substantially sum the evaluated predetermined number of terms obtained thereby, obtaining substantially a third sum, the third sum being substantially a third correction value, CV3.
Typically CV1 (214) is substantially determined by summing a first predetermined number of terms of a first power series of the form: ##EQU4## where the first number of predetermined number of terms is substantially a largest first integer less than or equal to a first quotient of {(BMF+1)/2}, where BMF is a bit multiplication factor that is substantially a smallest first integer greater than or equal to a second quotient of a desired number of bits of accuracy in the output trigonometric function value divided by a number of bits of accuracy of a lesser of the first function value and the second function value. Similarly, CV2 (214) is substantially determined by summing a second predetermined number of terms of a second power series of the form: ##EQU5## where the second number of predetermined number of terms is substantially a largest second integer less than or equal to a third quotient of {BMF/2}, where BMF is a bit multiplication factor that is substantially the smallest first integer greater than or equal to the second quotient of a desired number of bits of accuracy in the output trigonometric function value divided by a number of bits of accuracy of the lesser of the first function value and the second function value. Similarly, CV3 (214) is substantially determined by summing a third predetermined number of terms of a third power series of the form: ##EQU6## where n=1,2,3,4, . . . , c=the error value, and B.sub.2n is a 2nth Bernoulli number, and where the third predetermined number of terms of substantially a a smallest third integer greater than or equal to a fourth quotient of {(BMF-1)/2}, where BMF is a bit multiplication factor that is substantially the smallest first integer greater than or equal to the second quotient of a desired number of bits of accuracy in the output trigonometric function value divided by a number of bits of accuracy of the lesser of the first function value and the second function value.
As set forth in FIG. 2C, numeral 250, in one embodiment the at least one output trigonometric function value (OTF), of the input value is determined (212) by at least three of the following steps:
substantially determining a first combined output value, substantially being at least a first product of the first correction value and the first function value (216);
substantially determining a second combined output value, substantially being at least a second product of the second correction value and the second function value (216);
substantially determining a third combined output value, substantially being at least a third product of the first correction value and the second function value (216);
substantially determining a fourth combined output value, substantially being at least a fourth product of the second correction value and the first function value (216);
substantially determining a fifth combined output value, substantially being at least a fifth product of the third correction value and the first function value (216);
substantially determining a sixth combined output value, substantially being at least a sixth product of sthe third correction value and the second function value (216); and
utilizing at least two of: the first combined output value, the second combined output value, the third combined output value, the fourth combined output value, the fifth combined output value, the sixth combined output value, the first function value, and the second function value to substantially determine the at least one output trigonometric function value of the input value,
where utilizing at least two of the values in the last listed above step substantially includes at least two of:
substantially determining a fourth sum of the first combined output value and the second combined output value (218);
substantially determining a second difference of the fourth combined output value subtracted from the third combined output value (218);
substantially determining a third difference of the fifth combined output value subtracted from the second function value (218);
substantially determining a fifth sum of the sixth product and the first function value (218); and
substantially determining a fifth quotient of the fifth sum divided by the third difference (218).
The fourth sum is substantially a first at least one output trigonometric function value of the input value, being substantially a sine value (218) of the input value.
The second difference is substantially a second at least one output trigonometric function value of the input value, being substantially a cosine value (218) of the input value.
The fifth quotient is substantially a third at least one output trigonometric function value of the input value, being substantially a tangent value (218) of the input value.
Clearly, the cosecant, secant, and cotangent are readily determined with the present invention, one such implementation being obtaining reciprocals of the sine, cosine, and tangent values. Another implementation would utilize power series appropriate to the cosecant, secant, and cotangent for the determination of the error value.