Method and apparatus for use in booth-encoded multiplication
AssigneeAnalog Devices, Inc.
InventorJieming Qi
Life of this patent
Estimating the term…
Abstract
A new partial product bit generator is used to generate a partial product bit PPji. In some embodiments, the partial product bit generator generates the partial product bit PPji from intermediate signals that are able to be generated concurrently, for example in two levels of combinatorial logic. The partial product bit PPji is then able to be generated from the intermediate signal, for example in only one level of combinatorial logic. In such embodiments, a long series of combinatorial logic operations is not required.
Claims43
A partial product bit generator circuit for use in performing multiplication to generate a product of a multiplicand and a multiplier, the multiplicand being represented by a digital signal having a plurality of bits, the multiplier being represented by a digital signal having a plurality of bits, the partial product bit generator circuit receiving a group of the multiplicand bits and a group of the multiplier bits and providing a partial product bit in response thereto, wherein the partial product bit generator circuit comprises less than six levels of combinatorial logic and further comprises:
- a first circuit, responsive to a group of the multiplicand bits and a first subset of a group of the multiplier bits, to output at least three digital signals;
- a second circuit, responsive to a second subset of the group of multiplier bits, to output at least three select signals, each of the at least three select signals being associated with a respective one of the at least three digital signals, only one of the at least three select signals having a logic state that is asserted;
- and
- a third circuit, to output a partial product bit in response to the digital signal that is associated with the select signal having the asserted logic state.
A method for use in performing multiplication to generate a product of a multiplicand and a multiplier, the multiplicand being represented by a digital signal having a plurality of bits, the multiplier being represented by a digital signal having a plurality of bits, the method comprising:
- receiving a group of the multiplicand bits;
- receiving a group of the multiplier bits;
- generating a partial product bit signal in response to the group of multiplicand bits and the group of multiplier bits using less than six levels of combinatorial logic, wherein generating comprises:
- generating at least three digital signals in response to the group of multiplicand bits and a first subset of the group of multiplier bits;
- generating at least three select signals in response to a second subset of the group of multiplier bits, each of the at least three select signals being associated with a respective one of the at least three digital signals, only one of the select signals having a logic state that is asserted;
- and
- generating a partial product bit in response to the digital signal associated with the select signal having the asserted logic state.
A method for use in performing multiplication to generate a product of a multiplicand and a multiplier, the multiplicand being represented by a plurality of bits, the multiplier being represented by a plurality of bits, the method comprising:
- receiving a group of the multiplicand bits;
- receiving a group of the multiplier bits;
- generating at least three digital signals in response to the group of multiplicand bits and a first subset of the group of multiplier bits;
- generating at least three select signals in response to a second subset of the group of multiplier bits, each of the at least three select signals being associated with a respective one of the at least three digital signals, only one of the select signals having a logic state that is asserted;
- and
- generating a partial product bit in response to the digital signal associated with the select signal having the asserted logic state.
Apparatus for use in performing multiplication to generate a product of a multiplicand and a multiplier, the multiplicand being represented by a digital signal having a plurality of bits, the multiplier being represented by a digital signal having a plurality of bits, the apparatus comprising:
- a first circuit, responsive to a group of the multiplicand bits and a first subset of a group of the multiplier bits, to output at least three digital signals;
- a second circuit, responsive to a second subset of the group of multiplier bits, to output at least three select signals, each of the at least three select signals being associated with a respective one of the at least three digital signals, only one of the at least three select signals having a logic state that is asserted;
- and
- a third circuit, to output a partial product bit in response to the digital signal that is associated with the select signal having the asserted logic state.
A partial product bit generator circuit for use in performing multiplication to generate a product of a multiplicand and a multiplier, the multiplicand being represented by a digital signal having a plurality of bits, the multiplier being represented by a digital signal having a plurality of bits, the partial product bit generator circuit receiving a group of the multiplicand bits and a group of the multiplier bits, the partial product bit generator circuit comprising:
- a first circuit, responsive to the group of multiplicand bits and a first subset of the group of multiplier bits, to output a first set of output signals;
- a second circuit, responsive to a second subset of the group of multiplier bits to output a second set of output signals, the second subset of the group of multiplier bits being disjoint from the first subset of the group of multiplier bits ;
- and
- a third circuit, responsive to the first set of output signals and the second set of output signals to output a partial product bit signal.
A method for use in performing multiplication to generate a product of a multiplicand and a multiplier, the multiplicand being represented by a digital signal having a plurality of bits, the multiplier being represented by a digital signal having a plurality of bits, the method comprising:
- receiving a group of the multiplicand bits;
- receiving a group of the multiplier bits;
- generating a first set of output signals in response to the group of multiplicand bits and a first subset of the group of multiplier bits;
- generating a second set of output signals in response to a second subset of the group of multiplier bits, the second subset of the group of multiplier bits being disjoint from the first subset of the group of multiplier bits;
- and
- generating a partial product bit signal in response to the first set of output signals and the second set of output signals.
An apparatus for use in performing multiplication to generate a product of a multiplicand and a multiplier, the multiplicand being represented by a plurality of bits, the multiplier being represented by a plurality of bits, the method comprising:
- means for generating at least three digital signals in response to a group of the multiplicand bits and a first subset of a group of multiplier bits;
- means for generating at least three select signals in response to a second subset of the group of multiplier bits, each of the at least three select signals being associated with a respective one of the at least three digital signals, only one of the select signals having a logic state that is asserted;
- and
- means for generating a partial product bit in response to the digital signal associated with the select signal having the asserted logic state.
A partial product bit generator for use in performing multiplication to generate a product of a multiplicand and a multiplier, the multiplicand being represented by a digital signal having a plurality of bits, the multiplier being represented by a digital signal having a plurality of bits, the partial product bit generator circuit receiving a group of the multiplicand bits and a group of the multiplier bits, the partial product bit generator circuit comprising:
- means for generating a first set of output signals in response to the group of multiplicand bits and a first subset of the group of multiplier bits;
- means for generating a second set of output signals in response to a second subset of the group of multiplier bits, the second subset of the group of multiplier bits being disjoint from the first subset of the group of multiplier bits;
- and
- means for generating a partial product bit signal in response to the first set of output signals and the second set of output signals.
A partial product bit generator that receives three multiplier bits, bj+1, bj, bj−1, and two multiplicand bits, ai, ai-1, and outputs a partial product bit, wherein a longest delay path through the partial product bit generator circuit is substantially equivalent to an XOR gate and a three input pass transistor multiplexer.
Dependencies are inferred from the claim text.