Squaring circuit for binary numbers
AssigneeSGS-Thomson Microelectronics S.A.
InventorsAlain Pirson, Jean-Michel Bard, Mohamed Daoudi
Life of this patent
Estimating the term…
Abstract
A circuit for squaring a binary number X of n bits, x.sub.0 to x.sub.n-1, includes pre-processing circuits to form a group of all the products x.sub.i y.sub.j of the bits of number X, where i and j vary between 0 and n-1 such that i.ltoreq.j. The outputs of the pre-processing circuits provide words such that each word is formed by a succession, as complete as possible, of products selected among the products remaining from the group of products after forming the preceding word, each product x.sub.i y.sub.j of this succession being affected with a weight i+j+1 of the word if i is different from j, or with a weight 2i if i=j. Adders are connected to sum the words as the square of the number X.
Claims31
A squaring circuit for squaring a binary number X of n bits, the bits having values x.sub.0 to x.sub.n-1, the squaring circuit comprising:
- a plurality of pre-processing circuits constructed to form a plurality of products x.sub.i x.sub.j of the bits of number X, wherein i and j range between 0 and n-1 such that i.ltoreq.j, each product x.sub.i x.sub.j being affected with one of a weight i+j+1, if i is different from j, and a weight 2i if i=j, wherein said products are provided in a plurality of groups, each group representing a digital word;
- and
- at least one adder connected to form the sum of the digital words as a square of the number X;
- wherein the pre-processing circuits include means for forming a sum of two products that differ from each other, each of the two products corresponding to a bit, having a same weight, in one of two digital words, said sum replacing one of the two products in its corresponding one of the two digital words, a carry bit of said sum being provided as a higher order bit of one of the digital words, so as to reduce at least one of a number of digital words that are added to form the square of the number X and a length of one of the two digital words.
A squaring circuit for squaring a binary number X of n bits, the bits having values x.sub.0 to x.sub.n-1, the squaring circuit comprising:
- a plurality of pre-processing circuits constructed to form a plurality of products x.sub.i x.sub.j of the bits of number X, wherein i and j range between 0 and n-1 such that i.ltoreq.j, each product x.sub.i x.sub.j being affected with one of a weight i+j+1, if i is different from j, and a weight 2i if i=j, wherein said products are provided in a plurality of groups, each group representing a digital word;
- and
- at least one adder connected to form the sum of the digital words as a square of the number X;
- wherein the pre-processing circuits include means for forming a sum of two products havinga same weight, said sum being provided as one bit of a digital word, a carry bit being provided as a higher order bit of the digital word, so as to reduce a number of digital words that are added to form the square of the number X;
- wherein the number X is a signed binary number, the n bits including m bits and one sign bit;
- wherein said pre-processing circuits include means for generating
- 1 word having a weight m+1;
- x.sub.m words having a weight m;
- and
- words including the complements of products x.sub.i y.sub.m, where i ranges from 0 to m-1, each complement of a product being arranged at a weight i+m+1.
A squaring circuit for squaring a binary number X of n bits, the bits having values x.sub.0 to x.sub.n-1, the squaring circuit comprising:
- a plurality of pre-processing circuits constructed to form a plurality of products x.sub.i x.sub.j of the bits of number X, wherein i and j range between 0 and n-1 such that i.ltoreq.j, each product x.sub.i x.sub.j being affected with one of a weight i+j+1, if i is different from j, and a weight 2i if i=j, wherein said products are provided in a plurality of groups, each group representing a digital word;
- and
- at least one adder connected to form the sum of the digital words as a square of the number X, wherein the at least one adder includes at least one cascaded carry-save adder;
- wherein the pre-processing circuits include means for forming a sum of two products having a same weight, said sum being provided as one bit of a digital word, a carry bit being provided as a higher order bit of the digital word, so as to reduce a number of digital words that are added to form the square of the number X;
- wherein the number X is a signed binary number, the n bits including m bits and one sign bit;
- wherein said pre-processing circuits include means for generating
- 1 word having a weight m+1;
- x.sub.m words having a weight m;
- and
- words including the complements of products x.sub.i y.sub.m, where i ranges from 0 to m-1, each complement of a product being arranged at a weight i+m+1.
A method for generating a square of a binary number X, the number X being represented as a sequence of binary signals, the method comprising the steps of:
- A) generating a plurality of product signals each representing a product of bits of the number X and each being weighted by one of a plurality of orders, wherein an order is indicative of a power of two;
- B) generating at least one combination signal, the at least one combination signal being equal to a sum of at least two product signals that differ from each other, each of the at least two product signals having one of the plurality of orders;
- C) grouping the product signals and the at least one combination signal in groups of one order each;
- and
- D) adding the product signals and the at least one combination signal to generate a binary signal indicative of X.sup.2.
A method for generating a square of a binary number X, the number X being represented as a sequence of binary signals, comprising the steps of:
- A) generating a plurality of product signals each representing a product of bits of the number X and each being weighted by one of a plurality of orders, wherein an order is indicative of a power of two;
- B) generating at least one combination signal, the combination signal being equal to a sum of product signals and having one of the plurality of orders;
- C) grouping the product signals and at least one combination signal in groups of one order each;
- and
- D) adding the product signals and at least one combination signal to generate a binary signal indicative of X.sup.2 ;
- wherein the number X is a 2's compliment binary number, and wherein the step A of generating product signals includes generating a plurality of complimented product signals.
A circuit for calculating a square of a binary number X having a plurality of bits, the circuit comprising:
- a plurality of pre-processing circuits for combining the bits of the number X in accordance with a predetermined standard to generate a plurality of combination signals, the combination signals including a plurality of products of bits of the number X and at least one sum of products of bits of the number X that differ from each other;
- and
- at least one adder circuit for adding at least two of the combination signals to generate a binary signal indicative of the square of X.
A circuit for calculating a square of a binary number, X, having a plurality of bits, the circuit comprising:
- a plurality of pre-processing circuits for combining the bits of the number X in accordance with a predetermined standard to generate a plurality of combination signals, the combination signals including a plurality of products of bits of the number X and at least one sum of products of bits of the number X;
- and
- at least one adder circuit for adding at least two of the combination signals to generate a binary signal indicative of the square of X;
- wherein the number X is a signed, 2's compliment binary number, and wherein the pre-processing circuits further include inverting circuits for generating inverted combination signals.
A circuit for generating a square of a binary number X, wherein X includes a plurality of bits, the circuit comprising:
- means for generating a plurality of combination signals from the bits of the number X;
- means for grouping the combination signals in accordance with a predetermined standard;
- and
- means for adding the grouped combination signals to generate the value X.sup.2 ;
- wherein the combination signals include a plurality of products of the bits of the number X and at least one sum of products of bits of the number X that differ from each other.
A circuit for generating a square of a binary number X, wherein X includes a plurality of bits, the circuit comprising:
- means for generating a plurality of combination signals from the bits of the number X;
- means for grouping the combination signals in accordance with a predetermined standard;
- and
- means for adding the grouped combination signals to generate the value X.sup.2 ;
- wherein the combination signals include a plurality of products of the bits of the number X and at least one sum of products of the bits of the number X;
- wherein the number X is a signed 2's compliment binary number, and wherein the means for generating includes means for generating inverted combination signals.
A squaring circuit for squaring a binary number X of n bits, the bits having values x.sub.0 to x.sub.n-1, the squaring circuit comprising:
- a plurality of pre-processing circuits constructed to form a plurality of products x.sub.i x.sub.j of the bits of number X, wherein i and j range between 0 and n-1 such that i.ltoreq.j, each product x.sub.i x.sub.j being affected with one of a weight i+j+1, if i is different from j, and a weight 2i if i=j, wherein said products are provided in a plurality of groups, each group representing a digital word;
- and
- at least one adder connected to form the sum of the digital words as a square of the number X;
- wherein the pre-processing circuits include means for forming a sum of three products that each correspond to a respective bit in one of three digital words, the three products having a same weight in the three digital words, said sum replacing one of the three products in its corresponding one of the three digital words, a carry bit of said sum being provided as a higher order bit of one of the digital words to reduce at least one of a number of digital words that are added to form the square of the number X and a length of one of the three digital words.
Dependencies are inferred from the claim text.