Sine/cosine generator and method

• US 5,276,633 A
• Filed: 08/14/1992
• Issued: 01/04/1994
• Est. Priority Date: 08/14/1992
• Status: Expired

• Current Assignee: Intersil Corporation (Renesas Electronics Corporation)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Chester, David B., Fox, James G., Young, William R.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US07/930,926
• Time in Patent Office: 508 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 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 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. ______________________________________

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 cosine of said fine angle according to said quadrant indicator to yield the sine 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 angle, and when said input fine angle is positive its true'"'"'s 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.