Calculation of trigonometric functions in an integrated circuit device

Circuitry for computing on x and y datapaths a trigonometric function of an input on a z datapath includes a comparison element to determine that the input is at or above a threshold, or below the threshold. The circuitry also includes a first left-shifter for shifting the z datapath by a constant when the input is below the threshold, and a second left-shifter for shifting an initialization value of the x datapath when the input is below the threshold. The circuitry further includes a look-up table including inverse tangent values based on negative powers of 2, and based on negative powers of 2-plus-the-constant and shifted by the constant, for adding to/subtracting from the z datapath, shifters for right-shifting elements of the x and y datapaths by amounts incorporating the constant and respective predetermined shift amounts that are adjusted when the input is below the threshold.

BACKGROUND OF THE INVENTION

This invention relates to calculating trigonometric functions in integrated circuit devices, and particularly in programmable integrated circuit devices such as programmable logic devices (PLDs).

Trigonometric functions are generally defined for the relatively small angular range of 0-360°, or 0-2π radians. For angular values above 2π, the values of the trigonometric functions repeat. Indeed, one could restrict the range to 0-π/2, because various trigonometric identities can be used to derive values for trigonometric functions of any angle between π/2 and 2π from trigonometric functions of angles between 0 and π/2.

One method may that be used in integrated circuit devices for calculating trigonometric functions is the CORDIC algorithm, which uses the following three recurrence equations:
xn+1=xn−dnyn2−n
yn+1=yn+dnxn2−n
zn+1=zn−dntan−1(2−n)
For example, to calculate a sine or cosine of an input, the x value is initialized to “1”, the y value is initialized to “0”, and the Z value is initialized to the angle required. Z is then rotated towards zero, which determines the sign of dn, which is ±1—if znis positive, then so is dn, as the goal is to bring z closer to 0; if znis negative, then so is dn, for the same reason. x and y represent the x and y components of a unit vector, as z rotates, so does that vector, and when z has reached its final rotation to 0, the values of x and y will have converged to the cosine and sine, respectively, of the input angle.

To account for stretching of the unit vector during rotation, a scaling factor is applied to the initial value of x. The scaling factor is:

Although CORDIC appears to be easily implemented in integrated circuit devices such as FPGAs, closer analysis shows inefficient use of logic structures. Common FPGA architectures have 4-6 input functions, followed by a dedicated ripple carry adder, followed by a register. When used for calculating floating-point functions, such as the case of single-precision sine or cosine functions, the number of hardware resources required to generate an accurate result for smaller input values can become large.

In one embodiment of a CORDIC implementation, the number of registers will be the datapath precision, multiplied by 3 (the width of the three datapaths x, y and z), multiplied by the datapath precision (the depth of pipeline must be sufficient to include the contributions all of the bits in the input numbers and the arc-tangent constants). In other words, the approximate size of the pipeline is
R=3W2
where R is the number of registers and W is the datapath precision.

The amount of logic used is proportional to the square of the precision. For single-precision floating-point arithmetic (e.g., in accordance with the IEEE754-1985 standard for floating-point arithmetic), the 23-bit mantissa precision requires a much larger fixed-point CORDIC datapath. Assuming a full-range input (which may be restricted to approximately π/2 as discussed above), 23 bits are needed for the mantissa, plus one bit for the implied leading “1” and one bit for the sign bit position. Further bits may be required to the right of the mantissa, as each successive stage adds a smaller fraction of the other datapath. For example, if 30-bit datapath precision is accurate enough for a full range input, then 41 bits would likely be needed to cover the entire range of possible inputs. Using the 3W2formula, 2700 registers would be needed for a 30-bit datapath, but 5043 registers—almost twice as many—would be needed for a 41-bit datapath.

In addition, in current FPGA architectures, ripple-carry adders are used as discussed above. Although there are some architectural features in some FPGAs to improve the speed of ripple-carry adders, generally the propagation delay of a ripple-carry adder varies linearly with the precision. In a ripple-carry adder, bit0is fixed immediately beside bit1, which in turn is fixed immediately beside bit2, and so on—both at the source and the destination. A large number of wide datapaths with a ripple carry adder at each stage would impose a severe routing constraint, reducing system performance because of routing congestion.

For relatively large angles, accuracy will be better for a given wordlength. Smaller angles will be subject to larger errors, for two reasons principally related to the Z datapath. First, the initial rotations applied may be much larger than the angle represented. For example, the first rotation, where n=0, is by tan−1(1) or 45°. Therefore, a number of iterations will be required just to return the Z datapath to the original input order of magnitude. In addition, for the later, smaller, rotations, they may reduce to zero values before the end of the datapath, affecting accuracy at that end.

SUMMARY OF THE INVENTION

According to embodiments of the present invention, a modified CORDIC implementation treats different ranges of input angles differently. As discussed above, accuracy does not suffer for large angles, so a standard CORDIC implementation may be used. For very small angles (particularly if one restricts inputs to between 0 and π/2 and relies on the aforementioned trigonometric identities for other values), sin(θ) approaches θ as θ approaches 0, so the result can be approximated as sin(θ)=θ. For in-between angles, some number of initial steps of the CORDIC algorithm may be skipped, as discussed in more detail below.

According to embodiments of the invention, “large” angles may be those for which, when expressed as x×2n, n≧0, while small angles are those for which n≦−11, and intermediate angles are therefore those for which −10≦n≦−1. Under the aforementioned IEEE754-1985 standard for floating-point arithmetic, where the exponent may assume any value between 0 and 256, exponents are offset, to facilitate computation, by 127, so that a “real” exponent of 0 becomes an exponent of 127, while a real exponent of 128 becomes 255 and a real exponent of −127 becomes 0. Thus, using IEEE754-1985 floating-point arithmetic, large angles may be those for which n≧127, while small angles are those for which n≦116, and intermediate angles are therefore those for which 117≦n≦126.

As discussed above, for intermediate angles, the initial rotations of a standard CORDIC implementation may exceed the size of the angle itself. Therefore, in accordance with a modified CORDIC implementation according to the invention, the first few rotations may be skipped—i.e., instead of starting with n=0, the CORDIC implementation will start with some higher value of n. However, for every rotation that is skipped, the corresponding term would then be divided out of the aforementioned scaling factor.

In one embodiment of the invention, the number of rotations, or levels of the CORDIC process, that are skipped is always the same. In another embodiment, there may be multiple possible entry points to the CORDIC process. In either embodiment, the input angle may be left-shifted to normalize it to the maximum dynamic range of the available precision of the z datapath. The inverse tangent value is similarly shifted to compensate. No renormalization or denormalization is required at the end of the process because the z value is never actually used in the x or y datapath; z is used only to determine when the process has converged on the result.

In cases where the input angles are restricted to values between 0 and π/2, then the value of x will always be close to 1, meaning that, except for a leading 0 signifying a positive number, there will be a significant number of consecutive ones before the first zero is encountered. To increase accuracy for small angles with a given datapath precision, saturated values may be used in the datapath. Recurrence equations use deterministic methods to correctly reconstruct the contribution of the number discarded past the saturation point of the previous level In accordance with such an embodiment of the invention, x can be left-shifted past some predetermined number of those ones (e.g., 4 or 5) to preserve more precision in the less significant bits. When adding x into y, which, in the 0-to-π/2 quadrant, will be small, a corresponding number of leading bits of x can be zeroed to compensate for the left-shift. No similar adjustment will be needed in the y value for addition/subtraction into x because, in the 0-to-π/2 quadrant, x is close to 1 and y is small.

Known techniques for speeding up CORDIC calculations can be used with embodiments according to the invention. For example, once about halfway through the CORDIC calculation of a sine value, the final value of y can be approximated by multiplying the then-current value of y by the then-current value of z. If this technique is used in conjunction with the embodiments above in which the value of z is shifted, then, notwithstanding that according to the discussion above the shifting of z need not be taken into account in the result, here, because z is used in the calculation of y, the result would have to be right-shifted.

Therefore, in accordance with the present invention there is provided circuitry for computing on x and y datapaths a trigonometric function of an input on a z datapath. The circuitry includes a comparison element to determine that the input is at or above a threshold, or below the threshold. The circuitry also includes a first left-shifter for shifting the z datapath by a constant when the input is below the threshold, and a second left-shifter for shifting an initialization value of the x datapath when the input is below the threshold. The circuitry further includes a look-up table including inverse tangent values based on negative powers of 2, and based on negative powers of 2-plus-the-constant and shifted by the constant, for adding to/subtracting from the z datapath, shifters for right-shifting elements of the x and y datapaths by amounts incorporating the constant and respective predetermined shift amounts that are adjusted when the input is below the threshold.

A corresponding method for computing on x and y datapaths a trigonometric function of an input on a z datapath, a method for configuring an integrated circuit device as such circuitry, and a programmable integrated circuit device so configurable, are also provided. Further, a machine-readable data storage medium encoded with instructions for performing the method of configuring an integrated circuit device is provided.

DETAILED DESCRIPTION OF THE INVENTION

As discussed above, in a standard CORDIC implementation:
xn+1=xn−dnyn2−n
yn+1=yn+dnxn2−n
zn+1=zn−dntan−1(2−n)
As can be seen from these equations, at the first level (for n=0):
x1=x0−y0
y1=y0+x0
z1=z0−tan−1(1)
Similarly, at the second level (for n=1):
x2=x1−d1(y1/2)
y2=y1+d1(x1/2)
z2=z1−d1tan−1(0.5)
It will be understood that this continues for additional n until znconverges to 0, or as close to 0 as required by a particular implementation.

A logical structure100for implementing CORDIC is shown inFIG. 1. Structure100may be implemented as circuitry. As may be observed, the only operations required (if the inverse tangent values have been precomputed) are additions/subtractions. Although there are division operations, they are all division-by-two, which, in binary digital systems, may be implemented by a simple bit shift. Therefore, only adders (which also may function as subtractors) are needed. In some embodiments, structure100may be implemented in a programmable device, such as an FPGA, either in programmable logic, or in a combination of programmable logic and fixed logic (e.g., adders) if provided. For example, FPGAs in the STRATIX® family of FPGAs available from Altera Corporation, of San Jose, Calif., include digital signal processing blocks having multipliers and adders and programmable interconnect for connecting the multipliers and adders. Such an FPGA may be configured to use the adders, as well as any programmable logic that may be needed, to implement structure100. In addition, the aforementioned STRATIX® FPGAs include embedded memories of various sizes which may useful for storing a table of inverse tangent values, as discussed in more detail below.

As shown inFIG. 1, in first level101(n=0), x1=x0−y0is computed at adder/subtractor111and stored in register151. y1=y0+x0is computed at adder/subtractor121and stored in register161. The inverse tangent (represented as “atan”) of 1 is read in at131from table181and subtracted at adder/subtractor141from z0to yield z1and stored in register171. As noted above, the inverse tangent values may be precomputed and stored as a table in a suitable memory such as one of the foregoing memories in the aforementioned STRATIX® FPGA devices. The only inverse tangent values that are necessary are those of negative powers of two (as well as that of 2°). The depth of the table (i.e., the number entries required) is the number likely to be sufficient to reach convergence, which would be close to the bit width of the datapath.

In second level102(n=1), x2=x1−d1(y1/2), where d1is the sign of the value in register171and y1is divided by two by 1-bit shifter182, is computed at adder/subtractor112and y2=y1+d1(x1/2), where x1is divided by two by 1-bit shifter192, is computed at adder/subtractor122. The inverse tangent of 0.5 is read in at132from table181and subtracted at adder/subtractor142from z1to yield z2.

In third level103(n=2), x3=x2−d2(y2/4), where d2is the sign of the value in register172and y2is divided by four by 2-bit shifter183, is computed at adder/subtractor113and y3=y2+d2(x2/4), where x2is divided by four by 2-bit shifter193, is computed at adder/subtractor123. The inverse tangent of 0.25 is read in at133from table181and subtracted at adder/subtractor143from z2to yield z3.

In fourth level104(n=3), x4=x3−d2(y3/8), where d3is the sign of the value in register173and y3is divided by eight by 3-bit shifter184, is computed at adder/subtractor114and y4=y3+d3(x3/8), where x3is divided by eight by 3-bit shifter194, is computed at adder/subtractor124. The inverse tangent of 0.125 is read in at134from table181and subtracted at adder/subtractor144from z3to yield z4.

Additional levels may be provided up to about the bit width of the datapath, as discussed above.

A logical structure200for implementing a first embodiment is shown inFIG. 2. y is input at204. z is input at206and the number of leading zeroes q in z is determined by count-leading-zeroes module207. z is then left-shifted by q by left-shifter208so that it can take advantage of the entire width of the z datapath. At each level n, there is a respective look-up table215,225,235that selects between the inverse tangent of 2−nand the inverse tangent of 2−(n+q)left-shifted by q (because z has been left-shifted as just described), depending on whether traditional CORDIC (as inFIG. 1, for, e.g., a larger input value) or the first embodiment of according to the present invention (for, e.g., a smaller input value) is being used. Alternatively, one large look-up table (not shown), similar to look-up table181ofFIG. 1, can be provided. Either way, the look-up tables must have, for each value of n, inverse tangent values for each possible value of q, left-shifted by q. “q” can have any value up to the precision of the datapath. The larger the range of “q”, the bigger the table, as there will be “q” shifted copies of each value.

As discussed above, if this first embodiment is being used, the scaling factor that has been applied to x has to be adjusted to account for the q levels that are being skipped. q terms must be divided out of the infinite series set forth above, meaning that scaling factor, which is the inverse of the infinite series, must be multiplied by q terms. Thus, if q=1, the corrected scaling factor is 0.607252935 . . . ×(1+2−2×0)0.5=0.8587853 . . . ; if q=2, the corrected scaling factor is 0.607252935 . . . ×(1+2−2×0)0.5×(1+2−2×1)0.5=0.96015119 . . . ; if q=3, the corrected scaling factor is 0.607252935 . . . ×(1+2−2×0)0.5×(1+2−2×1)0.5×(1+2−2×2)0.5=0.989701198 . . . , and so on. The correct scaling factor, based on the value of q, may be stored in look-up table205and used to adjust the input value209of x.

Levels201,202,203ofFIG. 2are otherwise similar to levels101,102,103ofFIG. 1, except that shifters282,283shift by q+1 and q+2, respectively, rather than by 1 and 2, respectively, and level201has shifters284that shift by q where level101has no corresponding shifter. Further levels (not shown) operate similarly.

The embodiment ofFIG. 2allows multiple entry points to the CORDIC implementation, based on the different values of q. A simplified embodiment300shown inFIG. 3provides only one alternative entry point. The z input306is compared at comparator316to a constant. For example, this can be accomplished by simply looking for a minimum of p leading zeroes or ones. If z input306is larger than the constant, embodiment300works like embodiment100ofFIG. 1If z input306is less or equal to than the constant, then a fixed number m of levels of the CORDIC calculation are skipped.

Look-up table305includes two entries for the scaling factor, selected by the output of comparator316. One entry is the unaltered scaling factor represented by the infinite series above. The other entry is the same scaling factor with the first m terms divided out of the infinite series (which, because the scaling factor is the inverse of the infinite series, is the uncorrected scaling factor multiplied by the first m terms of the infinite series).

Similarly, each of the look-up tables315,325,335(and further look-up tables (not shown) in the z datapath) includes two inverse tangent values. One value is the inverse tangent associated with the level to which the look-up table belongs (the same value as in the corresponding level ofFIG. 1). The other value is the inverse tangent of 2−(level+m), which is further left-shifted by m places because the z value itself is left-shifted by shifter308based on the output of count-leading-zeroes module307. Shifters382,383,384shift by either 1, 2, and 0, respectively, or by m+1, m+2 and m, respectively. Further levels (not shown) operate similarly.

According to another embodiment400shown inFIG. 4, the magnitude of the z input is checked at count-leading-zeroes module407, and the z datapath is shifted by the number of leading zeroes r. This can be done for either multiple entry points as in embodiment200, or for a single entry point as in embodiment300. The x and y datapaths are handled based on the realization that, given the assumptions (z has a real exponent between −1 and −10 and is limited to the first quadrant), x will start close to 1.0 and will reduce only slightly, while y will start at 0 and become a small positive number.

The corrected x input in look-up table405is left-shifted by the shift value r of z (in some embodiments, the shifting amount may be different from r but derived from r). As the x input in look up table405is a positive number very close to 1, the left shift operation will saturate the number, i.e. the leading bits will be “1111 . . . ”.

As an example, in one embodiment the maximum value that can be represented as a vector might be 1.9999 . . . , in order that any small overflows near 1 will not generate a negative number. The number 1.9999 . . .10. in a signed number system can be represented by the leading bits “011111 . . .2”. Similarly, the number 1.010is therefore “010000 . . .2.”. A number slightly less than 1.010will be “001111 . . .2.”. From this one knows that the bits shifted into the integer range (and therefore discarded) start with at least two zeroes and a run of ones, where the number of ones equals the shift amount less the number of zeroes (which may be 2).

Using this representation, the value from the x datapath to be added to or subtracted from the y datapath is the fractional number shown in the x datapath, right-shifted by the level, and preceded by a computed number of zeroes and a run of ones of a length such that that length plus the computed number equals level. In an embodiment of this representation, a vector can be defined from two concatenated values as shown at484inFIG. 4. The less-significant of the two concatenated values is the value of the x datapath at the current level. The more-significant of the two concatenated values is different depending on whether one is in the single-entry-point case or the multiple-entry-point case. In the single-entry point case, the more-significant value is level zeroes, because the value of the x datapath is simply right-shifted by level places. In the multiple-entry-point case, the more-significant value is of length r, and includes (level+r) leading zeroes followed by a run of ones. The shift amount of the vector is (level+r). Although the result of concatenation is that the vector includes the discarded portion of x, and is therefore wider than the precision of the x datapath, during synthesis the least significant values of the vector will be discarded to the right and the amount of logic required for the x datapath will not increase.

As y will always be a small positive number, y can be directly added to or subtracted from the x datapath after being shifted by (level+r) or level as appropriate. The first value of y is 0. The first non-zero value of y will be generated by a shifted value of x, and therefore x and y will have the correct magnitudes relative to each other. The y value will have to be shifted by the same amount as the x value at each level, but as the leading bits in the y register will always be 0, and therefore of the same sign as the x value, no treatment of the leading bits of the shifted y value is required.

The foregoing discussion assumes that input values are limited to the 0-to-π/2 quadrant. If input values are not limited, the initial values can be negative, in which case the most significant bits of the x input will be ones and when the value is saturated there will be a large number of leading zeroes. In this case, a count-leading-ones module may be used on the z input instead of a count-leading-zeroes module, to derive a value to shift away most of the leading zeroes in the x input.

Use of embodiment400maximizes use of the datapath widths by allowing more significant bits of z to be used by eliminating the leading zeroes, and by allowing more significant bits of x to be used by eliminating leading ones (remembering that x is close to 1.0 so that its binary representation will start with many ones) so that any zeroes in the less significant bits have a chance to contribute.

Instructions for carrying out a method according to this invention for programming a programmable device to derive range-reduced angular values may be encoded on a machine-readable medium, to be executed by a suitable computer or similar device to implement the method of the invention for programming or configuring PLDs or other programmable devices to perform addition and subtraction operations as described above. For example, a personal computer may be equipped with an interface to which a PLD can be connected, and the personal computer can be used by a user to program the PLD using a suitable software tool, such as the QUARTUS® II software available from Altera Corporation, of San Jose, Calif.

FIG. 5presents a cross section of a magnetic data storage medium800which can be encoded with a machine executable program that can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium800can be a floppy diskette or hard disk, or magnetic tape, having a suitable substrate801, which may be conventional, and a suitable coating802, which may be conventional, on one or both sides, containing magnetic domains (not visible) whose polarity or orientation can be altered magnetically. Except in the case where it is magnetic tape, medium800may also have an opening (not shown) for receiving the spindle of a disk drive or other data storage device.

The magnetic domains of coating802of medium800are polarized or oriented so as to encode, in manner which may be conventional, a machine-executable program, for execution by a programming system such as a personal computer or other computer or similar system, having a socket or peripheral attachment into which the PLD to be programmed may be inserted, to configure appropriate portions of the PLD, including its specialized processing blocks, if any, in accordance with the invention.

FIG. 6shows a cross section of an optically-readable data storage medium810which also can be encoded with such a machine-executable program, which can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium810can be a conventional compact disk read-only memory (CD-ROM) or digital video disk read-only memory (DVD-ROM) or a rewriteable medium such as a CD-R, CD-RW, DVD-R, DVD-RW, DVD+R, DVD+RW, or DVD-RAM or a magneto-optical disk which is optically readable and magneto-optically rewriteable. Medium810preferably has a suitable substrate811, which may be conventional, and a suitable coating812, which may be conventional, usually on one or both sides of substrate811.

In the case of a CD-based or DVD-based medium, as is well known, coating812is reflective and is impressed with a plurality of pits813, arranged on one or more layers, to encode the machine-executable program. The arrangement of pits is read by reflecting laser light off the surface of coating812. A protective coating814, which preferably is substantially transparent, is provided on top of coating812.

In the case of magneto-optical disk, as is well known, coating812has no pits813, but has a plurality of magnetic domains whose polarity or orientation can be changed magnetically when heated above a certain temperature, as by a laser (not shown). The orientation of the domains can be read by measuring the polarization of laser light reflected from coating812. The arrangement of the domains encodes the program as described above.

A PLD90programmed according to the present invention may be used in many kinds of electronic devices. One possible use is in a data processing system900shown inFIG. 7. Data processing system900may include one or more of the following components: a processor901; memory902; I/O circuitry903; and peripheral devices904. These components are coupled together by a system bus905and are populated on a circuit board906which is contained in an end-user system907.

System900can be used in a wide variety of applications, such as computer networking, data networking, instrumentation, video processing, digital signal processing, or any other application where the advantage of using programmable or reprogrammable logic is desirable. PLD90can be used to perform a variety of different logic functions. For example, PLD90can be configured as a processor or controller that works in cooperation with processor901. PLD90may also be used as an arbiter for arbitrating access to a shared resources in system900. In yet another example, PLD90can be configured as an interface between processor901and one of the other components in system900. It should be noted that system900is only exemplary, and that the true scope and spirit of the invention should be indicated by the following claims.

Various technologies can be used to implement PLDs90as described above and incorporating this invention.

It will be understood that the foregoing is only illustrative of the principles of the invention, and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention. For example, the various elements of this invention can be provided on a PLD in any desired number and/or arrangement. One skilled in the art will appreciate that the present invention can be practiced by other than the described embodiments, which are presented for purposes of illustration and not of limitation, and the present invention is limited only by the claims that follow.