Squaring circuit for binary numbers

• US 5,337,267 A
• Filed: 11/02/1992
• Issued: 08/09/1994
• Est. Priority Date: 11/05/1991
• Status: Expired

• Current Assignee: SGS-Thomson Microelectronics (STMicroelectronics NV)
• Original Assignee: SGS-Thomson Microelectronics (STMicroelectronics NV)
• Inventors: Colavin, Osvaldo
• Primary Examiner(s): NGO, CHUONG D
• Application Number:
  US07/970,139
• Time in Patent Office: 645 Days
• Field of Search: 364/753, 364/754, 364/757, 364/758, 364/735
• US Class Current: 708/606
• CPC Class Codes: G06F 1/035 Reduction of table size G06F1/0314 takes precedence
• CPC Class Codes: G06F 2101/08 Powers or roots

Abstract

A squaring circuit for a binary number X of n bits x₀ to x_n-1, includes a table of the squares of numbers p constituted by bits x₁ to x_n-2. An adder for adding numbers of 2n-3 bits receives at a first input a number constituted by bit x_n-1, positioned on the left of the square p² provided by the table. A first switching element receives the number p and provides same to the n-2 low weight lines of a second input of the adder if bit x₀ is equal to 1. A second switching element receives number p and provides same to the n-2 high weight lines of the second input if bit x_n-1 is equal to 1. An AND gate is connected to the remaining line of the second input and receives the bits x₀ and x_n-1. The square X² of X is constituted by the adder output, to which a bit 0 and the bit x₀ are positioned on the right.

Claims

1. A squaring circuit for raising to the second power a first binary number X of n bits, each bit having a weight assigned thereto, wherein the weights increase from 0 to n-1, the circuit comprising:

a circuit responsive to a second binary number P including bits of weight 1 to n-2 of the first number X, for generating the square P² of the second binary number, the circuit arrangement includes a table stored in a memory having at least one bit of the P² ;

an adder, coupled to the circuit, receiving at a first multi-bit input thereof, a number including bits of the square P² of the second binary number and a bit of weight n-1 of the first number X;

a first switching element, coupled between the memory and the adder, receiving the second number P and providing the second number P to n-2 lines of low weight of a second input of the adder if the bit of weight 0 of the first number X is equal to b 1;

a second switching element, coupled between the memory and the adder, receiving the second number P and providing P to n-2 high weight lines of the second input of the adder if the bit of weight n-1 of the first number X is equal to 1; and

a third switching element, coupled between the memory and the adder, providing a 1 to a remaining line of the second input of the adder if bits of weight 0 and n-1 of the first number X are both equal to 1, wherein l represents a first predetermined logic level;

wherein the square X² of the first number X is provided by an output of the adder, and to the output of the adder are added at predetermined positions a bit 0 and the bit of weight 0 of the first number X.

2. A circuit as claimed in claim 1 wherein the adder adds numbers of 2n-3 bits.

3. A circuit as claimed in claim 2 wherein the number constituted by the bit of weight n-1 of the first number X is added at a first predetermined position of P².

4. A circuit as claimed in claim 1 wherein the table includes 2(n-2)-2 high weight bits of the square P², which are provided by an output of the memory, and to the output of the memory are added at predetermined positions thereof a bit 0 and bit of weight 1 of the first number X to generate P².

5. A circuit as claimed in claim 1, wherein the first switching element includes n-2 AND gates, the n-2 AND gates having first inputs which receive the bit of weight 0 of the first number X and second inputs which receive one of the bits of the second number P.

6. A circuit as claimed in claim 1, wherein the second switching element includes n-2 AND gates, the n-2 AND gates having first inputs which receive the bit of weight n-1 of the first number X and second inputs which receive one of the bits of the second number P.

7. A circuit as claimed in claim 6, wherein the second switching element includes n-2 AND gates, the n-2 AND gates having first inputs which receive the bit of weight n-1 of the first number X and second inputs which receive one of the bits of the second number P.

8. A circuit as claimed in claim 1, wherein the third switching element includes an AND gate which receives bits of weights 0 and n-1 of the first number X.

9. A circuit as claimed in claim 8, wherein the third switching element includes an AND gate which receives bits of weights 0 and n-1 of the first number X.

10. A squaring circuit for raising to the second power a first binary number X of n bits, each bit having a weight assigned thereto, wherein the weights increase from 0 to n-1, the circuit comprising:

means responsive to a second binary number P including bits of weight 1 to n-2 of the first number X, for generating the square P² of the second binary number, the means for generating including means for storing at least one bit of the P² ;

means for adding numbers, coupled to the means for generating, receiving at a first multi-bit input thereof, a number constituted by the bit of weight n-1 of the first number X and bits of the square P² ;

a first means for switching, coupled between the means for storing and the means for adding, receiving the second number P and providing the second number P to n-2 lines of low weight of a second input of the adder if a lowest weight bit of the first number X is equal to 1;

a second means for switching, coupled between the means for storing and the means for adding, receiving the second number P and providing P to n-2 high weight lines of the second input of the adder if a bit of weight n-1 of the first number X is equal to 1; and

a third means for switching, coupled between the means for storing and the means for adding, providing a l to a remaining line of the second input of the adder if bits of weight 0 and n-1 of the first number X are both equal to 1, wherein l represents a first predetermined logic level;

wherein the square X² of the first number X is provided by an output of the means for adding, and to the output of the means for adding are added at predetermined positions thereof a bit 0 and lowest weight bit of the first number X.

11. A circuit as claimed in claim 10 wherein the means for adding adds numbers of 2n-3 bits.

12. A circuit as claimed in claim 11 wherein the bit of weight n-1 of the first number X is added at a first predetermined position of P².

13. A circuit as claimed in claim 10 wherein the means for storing includes a memory element which stores 2(n-2)-2 high weight bits of the square P² which are is provided by an output of the memory, and to the output of the memory are added at predetermined positions a bit 0 and bit of weight 1 of the first number X.

14. A circuit as claimed in claim 10, wherein the first means for switching includes n-2 AND gates, the n-2 AND gates having first inputs which receive a lowest weight bit of the first number X and second inputs which receive one of the bits of the second number P.

15. A circuit as claimed in claim 10, wherein the second means for switching includes n-2 AND gates, the n=2 AND gates having first inputs which receive a bit of weight n-1 of the first number X and second inputs which receive one of the bits of the second number P.

16. A circuit as claimed in claim 15, wherein the second means for switching includes n-2 AND gates, the n-2 AND ages having first inputs which receive a bit of weight n-1 of the first number X and second inputs which receive one of the bits of the second number P.

17. A circuit as claimed in claim 10, wherein the third means for switching includes an AND gate which receives bits of weights 0 and n-1 of the first number X.

18. A circuit as claimed in claim 17, wherein the third means for switching includes an AND gate which receives bits of weights 0 and n-1 of the first number X.

19. A squaring circuit comprising:

a circuit responsive to a second binary number P, wherein each number P includes bits of weight 1 to n-2 of a binary number X to be squared, wherein binary number X has n bits, each bit having a weight assigned thereto, wherein the weights increase from 0 to n-1, the circuit for generating the square P² of the second binary number and including a table stored in a membory having at least one bit of the P² ;

an adder, coupled to the circuit, receiving at a first multi-bit input thereof, a bit of weight n-1 of the first number X and bits of the square P² of the second binary number;

a first switching element, coupled between the memory and the adder, receiving the second number P and providing the second number P to n-2 lines of low weight of a second input of the adder if a lowest weight bit of the first number X is equal to 1, wherein l is a predetermined logic level;

a second switching element, coupled between the memory and the adder, receiving the second number P and providing P to n-2 high weight lines of the second input of the adder if a bit of weight n-1 of the first number X is equal to 1; and

a third switching element, coupled between the memory and the adder, providing 1 to a remaining line of the second input of the adder if bits of weight 0 and n-1 of the first number X are both equal to 1;

wherein the square X² of the first number X is provided by an output of the adder, and to the output of the adder are added at predetermined positions at bit 0 and lowest weight bit of the first number X.

20. A circuit as claimed in claim 19 wherein the adder adds numbers of 2n-3 bits.

21. A circuit as claimed in claim 20 wherein the bit of weight n-1 of the first number X is added at a predetermined position of the square P² of the second number P.