Split array binary multiplication
AssigneeAdvanced Micro Devices, Inc.
InventorsJon C. Gibbons, Simon Y. C. Lau, Marvin N. Fox
Life of this patent
Estimating the term…
Abstract
A system for binary multiplication based upon the modified Booth algorithm incorporating a Booth multiplex decoder, partial modified Booth arrays and partial product reduction adders. The system is comprised of Booth multiplexer cells, Booth multiplexer and adder cells, sign extension cells, and full adder cells interconnected such that the total adder delay through the system is n/4+1 adder delays where n is the number of bits in the multiplier.
Claims17
A system for digital unsigned and signed modified Booth binary multiplication of a multiplicand and a n bit multiplier, n being equal to or greater than the number of bits in an 8 bit unsigned binary number, and said multiplier consisting of n.sub.1 least significant bits and n.sub.2 most significant bits, comprising:
- a first source of signals representing said multiplicand;
- a second source of signals representing said multiplier;
- a first array, operatively connected to said first and second source of signals, for generating a first multiplicity of partial product signals resulting from the modified Booth multiplication of said multiplicand and said n.sub.1 least significant bits of said multiplier by said first array;
- wherein said first array is comprised of n/4 rows and further wherein:
- a first row of said first array is comprised of multiplexer cells;
- a second row through an n/4 rows are each comprised of cells wherein each cell comprises a multiplexer and a full adder;
- and
- means for operatively interconnecting said cells in said first array so that said first array generates said first multiplicity of partial product signals;
- a second array, operatively connected to said first and second sources of signals, for generating a second multiplicity of partial product signals resulting from the modified Booth multiplication of said multiplicand and said n.sub.2 most significant bits of said multiplier by said second array;
- wherein:
- said second array is comprised of n/4+1 rows and further wherein:
- a first row and a second row of said second array are comprised of multiplexer cells;
- a third row through a n/4+1 row of said second array are each comprised of cells wherein each cell comprises a multiplexer and a full adder;
- means for operatively interconnecting said cells in said second array so that said second array generates said second multiplicity of partial product signals;
- and
- said first array and second array each simultaneously and independently generate said first and second multiplicities of partial product signals, respectively.
A system for digital unsigned and signed modified Booth binary multiplication of a multiplicand and a n bit multiplier, n being less than the number of bits in an 8 bit unsigned binary number, and said multiplier consisting of n1 least significant bits and n.sub.2 most significant bits, comprising:
- a first source of signals representing said multiplicand;
- a second source of signals representing said multiplier;
- a first array, operatively connected to said first and second source of signals, for generating a first multiplicity of partial product signals resulting from the modified Booth multiplication of said multiplicand and said n.sub.1 least significant bits of said multiplier by said first array;
- wherein said first array is comprised of n/4 rows and further wherein:
- a first row of said first array is comprised of multiplexer cells;
- a second row through a n/4 row are each comprised of cells wherein each cell comprises a multiplexer and a full adder;
- and
- means for operatively interconnecting said cells in said first array so that said first array generates said first multiplicity of partial product signals;
- a second array, operatively connected to said first and second sources of signals, for generating a second multiplicity of partial product signals resulting from the modified Booth multiplication of said multiplicand and said n.sub.2 most significant bits of said multiplier by said second array;
- wherein:
- said second array is comprised of n/4+1 rows and further wherein;
- a first row of said second array is comprised of multiplexer cells;
- and
- a second row through a n/4+1 row of said second array are each comprised of cells wherein each cell comprises a multiplexer and a full adder;
- and
- means for operatively interconnecting said cells in said second array so that said second array generates said second multiplicity of partial product signals;
- and
- said first array and second array each simultaneously and independently generate said first and second multiplicity of partial product signals, respectively.
A system for digital unsigned and signed modified Booth binary multiplication of a multiplicand and a n bit multiplier consisting of n.sub.1 least significant bits and n.sub.2 most significant bits, the product of the multiplication having m bits comprising:
- a first source of signals representing said multiplicand;
- a second source of signals representing said multiplier;
- a first array, operatively connected to said first and second source of signals, for generating a first multiplicity of partial product signals resulting from the modified Booth multiplication of said multiplicand and said n.sub.1 least significant bits of said multiplier by sad first array;
- a second array, operatively connected to said first and second sources of signals, for generating a second multiplicity of partial product signals resulting from the modified Booth multiplication of said multiplicand and said n.sub.2 most significant bits of said multiplier by said second array;
- and
- means, operatively connected to said first array, for generating the n/2 least significant bits of the product of said multiplication wherein:
- said first array and second array each simultaneously and independently generate said first and second multiplicities of partial product signals, respectively.
A system for digital unsigned and signed modified Booth binary multiplication of a multiplicand and an n bit multiplier consisting of n.sub.1 least significant bits and n.sub.2 most significant bits wherein n is equal to or greater than the number of bits in an 8 bit unsigned binary number and the product of said multiplication having m bits comprising:
- a first source of signals representing said multiplicand;
- a second source of signals representing said multiplier;
- a first array, operatively coupled to said first source of signals and to said second source of signals, for generating a first multiplicity of partial product signals consisting of the modified Booth multiplication of said multiplicand add the n.sub.1 least significant bits of said multiplier, said first array including:
- a first row of multiplexer cells;
- a second row through a n/4 row of cells, each cell comprising a multiplexer and a pull adder;
- and
- means for operatively interconnecting said cells so that said first array generates a first multiplicity of partial product signals;
- a second array, operatively connected to said first source of signals and to said second source of signals, for generating a second multiplicity of partial product signals consisting of the modified Booth multiplication of said multiplicand and the n.sub.2 most significant bits of said multiplier, said second array including:
- a first row and second row having multiplexer cells;
- a third row through a n/4+1 rowcells, each cell comprising a multiplexer and a full adder;
- and
- means for operatively interconnecting said cells so that said second array generates a second multiplicity of partial product signals;
- a multiplicity of four term adders, operatively connected to said first array, each four term adder, in response to partial product signals from said first array, providing at least one bit of the n/2 least significant bits of said product of said multiplication;
- and
- a multiplicity of full adders, operatively connected to said first and second arrays, to receive said first and second multiplicity of partial product signals and generate a multiplicity of sum and carry signals.
A system for digital unsigned and signed modified Booth binary multiplication of a multiplicand and an n bit multiplier consisting of n1 least significant bits and n.sub.2 most significant bits, wherein n is less than the number of bits in an 8 bit unsigned binary number and the product of said multiplication having m bits, comprising:
- a first source of signals representing said multiplicand;
- a second source of signals representing said multiplier;
- a first array, operatively coupled to said first source of signals and to said second source of signals, for generating a first multiplicity of partial product signals consisting of the modified Booth multiplication of said multiplicand and the n.sub.1 least significant bits of said multiplier, said first array including:
- a first row of multiplexer cells;
- a second row through a n/4 row cells, each cell comprising a multiplexer and a full adder;
- and
- means for operatively interconnecting said cells so that said first array generates said first multiplicity of partial product signals;
- a second array, operatively connected to said first source of signals an to said second source of signals, for generating a second multiplicity of partial product signals consisting of the modified Booth multiplication of said multiplicand and the n.sub.2 most significant bits of said multiplier, said second array including:
- a first row of multiplexer cells;
- a second row through a n/4+1 row of cells, each cell comprising a multiplexer and a full adder;
- and
- means for operatively interconnecting said cells so that said second array generates said second multiplicity of partial product signals;
- a multiplicity of four term adders, operatively connected to said first array, each four term adder, in response to partial product signals from said first array, providing at least one bit of the n/2 least significant bits of said product of said product of said multiplication;
- and
- a multiplicity of full adders, operatively connected to said first and second arrays, to receive said first and second multiplicities of partial product signals, and generate a multiplicity of sum and carry signals.
Dependencies are inferred from the claim text.