News Column

Patent Issued for Calculation of Trigonometric Functions in an Integrated Circuit Device

September 3, 2014



By a News Reporter-Staff News Editor at Journal of Engineering -- From Alexandria, Virginia, VerticalNews journalists report that a patent by the inventor Langhammer, Martin (Salisbury, GB), filed on June 14, 2011, was published online on August 19, 2014.

The patent's assignee for patent number 8812573 is Altera Corporation (San Jose, CA).

News editors obtained the following quote from the background information supplied by the inventors: "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.degree., or 0-2.pi. radians. For angular values above 2.pi., the values of the trigonometric functions repeat. Indeed, one could restrict the range to 0-.pi./2, because various trigonometric identities can be used to derive values for trigonometric functions of any angle between .pi./2 and 2.pi. from trigonometric functions of angles between 0 and .pi./2.

"One method that may be used in integrated circuit devices for calculating trigonometric functions is the CORDIC algorithm, which uses the following three recurrence equations: x.sub.n+1=x.sub.n-d.sub.ny.sub.n2.sup.-n y.sub.n+1=y.sub.n+d.sub.nx.sub.n2.sup.-n z.sub.n+1=z.sub.n-d.sub.n tan.sup.-1(2.sup.-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 d.sub.n, which is .+-.1--if z.sub.n is positive, then so is d.sub.n, as the goal is to bring z closer to 0; if z.sub.n is negative, then so is d.sub.n, 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:

".infin..times..times..times..times. ##EQU00001## The initial x is therefore be set to 1/1.64677 . . . =0.607252935 . . . .

"However, CORDIC may become inaccurate as the inputs become small. For example, the actual value of sin(.theta.) approaches .theta. as .theta. approaches 0 (and therefore sin(.theta.) approaches 0), and the actual value of cos(.theta.) approaches 1 as .theta. approaches 0. However, the magnitude of the error between the calculated and actual values increases as .theta. decreases.

"Moreover, while CORDIC on initial consideration appears to be easily implemented in integrated circuit devices such as FPGAs, closer analysis shows inefficiencies, at least in part because of multiple, deep arithmetic structures, with each level containing a wide adder. Common FPGA architectures may 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."

As a supplement to the background information on this patent, VerticalNews correspondents also obtained the inventor's summary information for this patent: "According to embodiments of the present invention, different trigonometric functions may be computed using various modified implementations that are based on different trigonometric identities that can be applied.

"For sine and cosine functions, a modified CORDIC implementation changes small input angles to larger angles for which the CORDIC results are more accurate. This may be done by using .pi./2-.theta. instead of .theta. for small .theta. (e.g., for .theta.<.pi./4). As discussed above, CORDIC accuracy suffers for smaller angles, but a standard CORDIC implementation may be used for larger angles. A multiplexer can select between the input value .theta. and the output of a subtractor whose subtrahend and minuend inputs are, respectively, .pi./2 and the input value .theta.. A comparison of the input .theta. to a threshold can be used to control the multiplexer to make the selection. Both sine and cosine are computed by the x and y datapaths of the CORDIC implementation and the desired output path can be selected using another multiplexer, which may be controlled by the same comparison output as the input multiplexer. When .pi./2-.theta. has been used as the input, the identities cos(.theta.)=sin(.pi./2-.theta.) and sin(.theta.)=cos(.pi./2-.theta.) can be used to derive the desired result.

"For the tangent function, the input angle can be broken up into the sum of different ranges of bits of the input angle, using trigonometric identities for the tangent of a sum of angles. Because some of the component ranges will be small, the identities will be simplified relative to those component ranges. The identities can be implemented in appropriate circuitry.

"For the inverse tangent (i.e., arctan or tan.sup.-1) function, the problem is that the potential input range is between negative infinity and positive infinity (unlike, e.g., inverse sine or inverse cosine, where the potential input range is between -1 and +1). In accordance with the invention, trigonometric identities involving the inverse tangent function can be used to break up the input into different ranges, with the most complicated portion of the identity having a contribution below the least significant bit of the result, so that it can be ignored. The identities can be implemented in appropriate circuitry.

"For inverse cosine (i.e., arccos or cos.sup.-1), the following identity may be used:

".times..function. ##EQU00002## which may be reduced to:

".times..function. ##EQU00003## The inverse tangent portion may be calculated as discussed above, simplified because the input range for inverse cosine is limited to between 0 and 1. Known techniques may be used to calculate the inverse square root. For inverse sine (i.e., arcsin or sin.sup.-1), which also has an input range limited to between 0 and 1, the inverse cosine can be calculated and then subtracted from .pi./2, based on the identity arcsin(x)=.pi./2-arccos(x).

"Therefore, in accordance with the present invention there is provided circuitry for computing a trigonometric function of an input. The circuitry includes circuitry for relating the input to another value to generate an intermediate value, circuitry for selecting one of the input and the intermediate value as a trigonometric input value, circuitry for determining respective initial values of a plurality of trigonometric functions for the trigonometric input value, and circuitry for deriving, based at least in part on a trigonometric identity, a final value of the first trigonometric function from the respective initial values of the plurality of trigonometric functions.

"A corresponding method for configuring an integrated circuit device as such circuitry is also provided. Further, a machine-readable data storage medium encoded with instructions for performing the method of configuring an integrated circuit device is provided."

For additional information on this patent, see: Langhammer, Martin. Calculation of Trigonometric Functions in an Integrated Circuit Device. U.S. Patent Number 8812573, filed June 14, 2011, and published online on August 19, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8812573.PN.&OS=PN/8812573RS=PN/8812573

Keywords for this news article include: Altera Corporation.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Journal of Engineering


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters