Sine/cosine generator and method

• US RE36,388 E
• Filed: 03/08/1995
• Issued: 11/09/1999
• Est. Priority Date: 08/14/1992
• Status: Expired due to Term

• Current Assignee: Intersil Corporation (Renesas Electronics Corporation)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Fox, James G., Chester, David B., Young, William R.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US08/400,811
• Time in Patent Office: 1,707 Days
• Field of Search: 364/721, 364/729
• US Class Current: 708/276
• CPC Class Codes: G06F 1/0353 by using symmetrical properties of the function, e.g. using most significant bits for quadrant control
• CPC Class Codes: G06F 1/0356 by using two or more smaller tables, e.g. addressed by parts of the argument
• CPC Class Codes: G06F 2101/04 Trigonometric functions
• CPC Class Codes: G06F 7/49994 Sign extension
• CPC Class Codes: G06F 7/5338 each bitgroup having two new bits, e.g. 2nd order MBA

Abstract

A sine/cosine generator with coarse and fine angles having compressed sine and cosine read only memories (ROMS) by use of symmetry of coarse angles about π/4 and, optionally, symmetry of fine angles about 0. The output of the ROMs directly feed multiplexers for utilization of the compressed storage. Addressing of complementary coarse angles is with one'"'"'s complementing of the address and of complementary fine angles is with two'"'"'s commplementing of the address. Fine sines and cosines are stored in recoded version for direct use in multipliers for computations using the sum of angles formulas.

Claims

1. A sin/cos generator, comprising:

(a) a coarse memory storing sines and cosines of coarse angles with said coarse angles within the first octant;

(b) a fine memory storing sines .[.and cosines.]. of fine angles with the magnitudes of said fine angles within .Iadd.half .Iaddend.the difference between successive coarse angles;

(c) a phase input decoder, said decoder decoding an input phase to yield a coarse memory address and a fine memory address; and

(d) arithmetic circuitry .[.coupling said first and second memories with addition, multiplication, and sign circuitry whereby.]. .Iadd.coupled to said memories for computing .Iaddend.the sine and cosine of an angle encoded by said input phase .[.is computed.]. using .[.the.]. trigonometric formulas .[.sin(A+B)=sin(A)cos(B)+cos(A)sin(B) and cos(A+B)=cos(A)cos(B)-sin(A)sin(B).]..

2. The sin/cos generator of claim 1, wherein.[.:

(a).]. said decoder partitions an input phase of 2+N+M bits into 2 quadrant bits, N coarse phase bits, and M fine phase bits.[.; and

(b) when said N coarse phase bits encode a coarse angle in the second octant, said decoder one'"'"'s complements the least significant N-1 bits of said N coarse phase bits to provide an address for said coarse memory which encodes a complementary angle in the first octant.]..

3. The sin/cos generator of claim 2, wherein:

(a) said fine angles include both positive and negative angles; and

(b) said fine memory stores sines .[.and cosines.]. of only nonpositive fine angles.

4. The sin/cos generator of claim 3, wherein:

(a) when said M fine phase bits encode a positive fine angle, said decoder two'"'"'s complements said M fine phase bits to provide an address for said fine memory which encodes a negative angle.

5. The sin/cos generator of claim 4, wherein:

(a) the default address of said fine memory stores the sine of one fine angle, and all other fine angles are in symmetric pairs.

6. The sin/cos generator of claim 4, wherein:

(a) said 2 quadrant bits, the MSB of said N coarse phase bits, and the MSB of said M fine phase bits determine signs and sine-cosine exchanges used in said trigonometric formulas.

7. The sin/cos generator of claim 2, wherein:

(a) N equals 8; and

(b) M equals 8.

8. The sin/cos generator of claim 2, wherein:

(a) said fine angles includes only nonnegative angles.

9. The sin/cos generator of claim 1, wherein:

(a) said arithmetic circuitry includes a multiplier using a recoded input and Wallace tree plus final adder for addition of partial products; and

(b) said fine sines are stored in recoded format in said fine memory.

10. The sin/cos generator of claim 9, wherein:

(a) said recoded format is bit pairwise recoding as follows;

space="preserve" listing-type="tabular">______________________________________ Original Original Carry next more Recoded Carry Bit Pair in significant Bit Pair out "+" "-" ______________________________________ 00 0 ** 00 0 0 0 00 1 ** 01 0 0 1 01 0 ** 01 0 0 1 01 1 ** 10 0 0 1 10 0 *0/0* 10 0 0 1 10 0 11 10 1 1 0 10 1 ** 01 1 1 0 11 0 ** 01 1 1 0 11 1 ** 00 1 0 0. ______________________________________

11. The sin/cos generator of claim 10, wherein:

(a) said arithmetic circuitry has multiplexers for partial product insertion into said Wallace trees which each include;

a first AND gate with inputs the MSB of the recoded bit pair and the N-1 bit of the multiplicand, a second AND gate with inputs the LSB of the recoded bit pair and the N bit of the multiplicand, a NOR gate with inputs connected to the outputs of said first and second AND gates, and an exclusive NOR gate with inputs connected to the output of said NOR gate and the "+" associated with the recoded bit pair.

12. The sin/cos generator of claim 11, wherein:

a) said arithmetic circuitry has sign extension word circuitry with the bits S_j of the sign extension word output by;

for S₀ the NOR of (i) the AND of signal "M" and the sign of the multiplicand and (ii) the AND of signal "N" and the complement of the sign of the multiplicand with "N" and "M" as in the following table;

for S₁ the NAND of (i) 0th recoded bit pair is 10 and (ii) the OR of (a) the AND of the signal "+" for the 0th recoded bit pair and the sign of the multiplicand and (b) the NOR of the signal "+" for the 0th recoded bit pair and the sign of the multiplicand;

for S_n the NAND of (i) nth recoded bit pair is 01 and (ii) the OR of (a) the AND of the signal "+" for the nth recoded bit pair and the sign of the multiplicand and (b) the NOR of the signal "+" for the nth recoded bit pair and the sign of the multiplicand;

for S_n+1 the NAND of (i) nth recoded bit pair is 10 and (ii) the OR of (a) the AND of the signal "+" for the nth recoded bit pair and the sign of the multiplicand and (b) the NOR of the signal "+" for the nth recoded bit pair and the sign of the multiplicand; and

(b) the the "N" and "M" signals are as follows and stored with the least significant partial product multiplier;

space="preserve" listing-type="tabular">______________________________________ Least significant Sign Extension Multiplicand partial product Word least Sign multiplier value significant bit N M ______________________________________ 0 0 1 0 0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 -1 0 1 0 1 -1 1 1 0 0 2 0 1 0 1 2 1 1 0 0 -2 1 0 1 1 -2 0 0 1. ______________________________________

17. The generator of claim 1 wherein said fine memory stores values of one minus the cosines of said fine angles. .Iaddend..Iadd.18. The generator of claim 1 wherein said trigonometric formulas are sin(A+B)=sin(A)-Dsin(A)+cos(A)sin(B) and cos(A+B)=cos(A)-Dcos(A)-sin(A)sin(B), where A is one of said coarse angles, B is one of said fine angles, and D is one minus cos(B). .Iaddend..Iadd.19. The generator of claim 18 wherein said cos(B) is set to the value one. .Iaddend..Iadd.20. The generator of claim 18 wherein cos(B) is 1-(a_x 2^-x +a_x+1 2^-(x+1) + . . . ), and wherein said fine memory stores at least a_x. .Iaddend..Iadd.21. The generator of claim 1 wherein said sines and cosines are stored in said coarse memory as positive numbers. .Iaddend..Iadd.22. The generator of claim 21 wherein said sines and cosines in said coarse memory are scaled by a scale factor slightly less than one. .Iaddend..Iadd.23. The generator of claim 22 wherein said scale factor is no greater than (1-2^-x), where x is a predetermined number related to the desired precision of the sine and cosine computed by said arithmetic circuitry. .Iaddend..Iadd.24. The generator of claim 1 wherein said fine memory stores cosines of fine angles. .Iaddend..Iadd.25. The generator of claim 1 wherein when said N coarse phase bits encode one of said coarse angles in the second octant, said decoder one'"'"'s complements the least significant bits to provide an address for said coarse memory which encodes a complementary angle in the

18. first octant. .Iaddend..Iadd.26. The generator of claim 1 wherein said fine memory stores sines of fine angles with the magnitude of said fine angles within one-half the difference between successive coarse angles. .Iaddend..Iadd.27. The method of claim 13 wherein the second lookup table includes the values of one minus the cosine of fine angles. .Iaddend..Iadd.28. The method of claim 13 wherein the step of combining comprises use of the trigonometric formulas sin(A+B)=sin(A)-Dsin(A)+cos(A)sin(B) and cos(A+B)=cos(A)-Dcos(A)sin(A)sin(B), where A is one of the coarse angles, B is one of the fine angles, and D is one minus cos(B). .Iaddend..Iadd.29. The method of claim 13 wherein the cosines of fine angles are in the second lookup table. .Iaddend..Iadd.30. A method of providing sines and cosines of phase angles input to a sin/cos generator, each of the input angles including a quadrant indicator, a coarse angle and a fine angle within the difference between successive coarse angles, the method comprising the steps of:

(a) providing sines and cosines of the coarse angles within the first octant from a coarse memory;

(b) providing sines of the fine angles from a fine memory;

(c) determining whether the cosine of each of the fine angles is the value one, or the value (1-D), where D is a predetermined number related to the precision of the fine angles; and

(d) computing sines and cosines of input angles according to the quadrant indicator using trigonometric formulae that include multiplications of sines and cosines from the memories and the determined fine angle cosine value. .Iaddend..Iadd.31. The method of claim 30 where, in the event a multiplication of a fine angle sine produces a first product with a sign extension word, and a multiplication of a fine angle cosine produces a D partial product with a sign extension word, further comprising the step of,

combining the sign extension words from the first and D partial products.

13. A method of generating the sine and cosine of an angle, comprising the steps of:

(a) partitioning an input angle into an input quadrant indicator, an input coarse angle, and an input fine angle where said input coarse angle is one of a plurality of coarse angles located in the first quadrant and said input fine angle is one of a plurality of fine angles located .[.in a range of extent equal to the difference.]. between successive coarse angles;

(b) providing a first lookup table of sines and cosines of coarse angles for coarse angles in the first octant;

(c) using said first lookup table to find the sine and cosine of said input coarse angle, and when said input coarse angle is in the second octant its complementary angle is used in said first lookup table;

(d) providing a second lookup table of sines .[.and cosines.]. of fine angles;

(e) using said second lookup table to find the sine .[.and cosine.]. of said input fine angle; and

(f) combining said sine and cosine of said input coarse angle and said sine and .Iadd.a .Iaddend.cosine of said fine angle according to said quadrant indicator to yield the sine .Iadd.and cosine .Iaddend.of said input angle.

14. The method of claim 13, wherein:

said fine angles include both positive and negative angles and said second lookup table contains .[.only.]. sines .[.and cosines.]. of nonpositive fine .[∠

]. .Iadd.angles.Iaddend., and when said input fine angle is positive its .[.true'"'"'s.]. .Iadd.two'"'"'s .Iaddend.complement is used in said second lookup table.

15. The method of claim 13, wherein:

said fine angles are nonnegative.

16. The method of claim 15, wherein:

said input angle is encoded as a 2+N+M bit phase, and the 2 most significant bits form said quadrant indicator, the N next most significant bits encode said coarse angle, and the M least significant bits encode the fine angle, and said N bits provide addressing for said first lookup table and said M bits provide addressing for said second lookup table. .Iadd.

19. Iaddend..Iadd.32. In a circuit having means for computing the sine and cosine of any phase angle 0°

to 360°

using trigonometric formulas and means for storing values related to phase angles, the improvement wherein said computing means comprises means for performing calculations using trigonometric formulas (1) sin(A+B)=sin(A)-Dsin(A)+cos(A)sin(B) and (2) cos(A+B)=cos(A)-Dcos(A)-sin(A)sin(B), where A is one of said coarse angles, B is one of said fine angles, and D is one minus cos(B). .Iaddend..Iadd.33. The circuit of claim 32 wherein said means for storing values related to phase angles is limited to values within a contiguous

20. 45°

. .Iaddend..Iadd.34. The circuit of claim 32 wherein said means for storing values includes a coarse memory for coarse angles within said contiguous 45° and

a fine memory for fine angles within one-half of the difference between successive coarse angles. .Iaddend..Iadd.35. The circuit of claim 34 wherein said fine memory stores values of one minus the cosines of said fine angles. .Iaddend..Iadd.36. In a sin/cos generator having input means for receiving an input signal related to a selected one of 360°

phase angles, storage means for storing data related to the sin/cos of phase angles within a contiguous 45°

of the 360°

, and circuit means for calculating the sin/cos of any selected phase angle of the 360°

using the data from said storage means, the improvement wherein said calculating means includes means for calculating any selected angle of the 360°

using only said input signal and the stored data related to the sin/cos of the phase angles within said contiguous 45°

. .Iaddend.