Serial-parallel multiplier using booth{3 s algorithm with combined carry-borrow feature

Claim 2

A digital multiplier of the type taking multiplicand bits in parallel, said multiplicand bits in two''s complement notation, numbered in a bit position hierarchy as follows, XM , . . . , Xm 1 , Xm , XM 1 , . . . X1 , X0 where M is a number designating the position of the most significant X bit, m is a number designating the position of the mth bit, and 0 is a number designating the position of the least significant X bit, said multiplier taking multiplier bits serially least significant bit first with multiplier bits in two''s complement notation, numbered in a time interval hierarchy as follows, YN , . . . , Yn 1 , Yn , Yn 1 , . . . Y1 , Y0 , where N is a number designating the time of occurrence of the least significant Y bit, and n is a number deSignating the time of occurrence of the nth bit, comprising, a plurality of connected multiplier cells, each of said cells corresponding to a multiplicand bit position, each cell being substantially identical and having input means for receiving a parallel input multiplicand bit Xm, a serial input multiplier bit Yn, and a partial product bit from an adjoining higher order cell, Sm 1,n 1, each cell further having first circuit means for forming a borrow-carry bit, Cm,n and second circuit means for forming a partial product bit, Sm,n, said first and second circuit means including logic gate means and storage means arranged in a configuration with respect to said carryborrow bit Cm,n as defined by the equation: Cm,n ((Xm . (Yn + Yn 1)) + Cm,n 1) . (Sm 1,n 1 + Yn) and with respect to said partial product bit Sm,n as defined by the equation: Sm,n Sm 1,n 1 + (Xm . (Yn + Yn 1)) said cell having means for outputting said partial product but Sm,n .

Claim 3

A digital multiplier of the type taking multiplicand bits in parallel, said multiplicand bits in two''s complement notation, numbered in a bit position hierarchy as follows, XM , . . . , Xm 1 , Xm , XM 1 , . . . X1 , X0 where M is a number designating the position of the most significant X bit, m is a number designating the position of the mth bit, and 0 is a number designating the position of the least significant X bit, said multiplier taking multiplier bits serially least significant bit first with multiplier bits in two''s complement notation, numbered in a time interval hierarchy as follows, YN , . . . , Yn 1 , Yn , Yn 1 , . . . Y1 , Y0 , where N is a number designating the time of occurrence of the least significant Y bit, and n is a number deSignating the time of occurrence of the nth bit, comprising, a plurality of connected multiplier cells, each of said cells corresponding to a multiplicand bit position, each cell being substantially identical and having input means for receiving a parallel input multiplicand bit Xm, a serial input multiplier bit Yn, and a partial product bit from an adjoining higher order cell, Sm 1,n 1, each cell further having first circuit means for forming a borrow-carry bit, Cm,n and second circuit means for forming a partial product bit, Sm,n, said first and second circuit means including logic gate means and storage means arranged in a configuration with respect to said carry-borrow bit Cm,n as defined by the equation: Cm,n ((Xm . (Yn + Yn 1)) + Cm,n 1) . (Sm 1,n 1 + Yn) and with respect to said partial product bit Sm,n as defined by the equation: Sm,n Sm 1,n 1 + (Xm . (Yn + Yn 1)) said cell having means for outputting said partial product but Sm,n .

Claim 4

A digital multiplier of the type taking multiplicand bits in parallel, said multiplicand bits in two''s complement notation, numbered in a bit position hierarchy as follows, XM , . . . , Xm 1 , Xm , XM 1 , . . . X1 , X0 where M is a number designating the position of the most significant X bit, m is a number designating the position of the mth bit, and 0 is a number designating the position of the least significant X bit, said multiplier taking multiplier bits serially least significant bit first with multiplier bits in two''s complement notation, numbered in a time interval hierarchy as follows, YN , . . . , Yn 1 , Yn , Yn 1 , . . . Y1 , Y0 , where N is a number designating the time of occurrence of the least significant Y bit, and n is a number deSignating the time of occurrence of the nth bit, comprising, a plurality of connected multiplier cells, each of said cells corresponding to a multiplicand bit position, each cell being substantially identical and having input means for receiving a parallel input multiplicand bit Xm, a serial input multiplier bit Yn, and a partial product bit from an adjoining higher order cell, Sm 1,n 1, each cell further having first circuit means for forming a borrow-carry bit, Cm,n and second circuit means for forming a partial product bit, Sm,n, said first and second circuit means including logic gate means and storage means arranged in a configuration with respect to said carry-borrow bit Cm,n as defined by the equation: Cm,n ((Xm . (Yn + Yn 1)) + Cm,n 1) . (Sm 1,n 1 + Yn) and with respect to said partial product bit Sm,n as defined by the equation: Sm,n Sm 1,n 1 + (Xm . (Yn + Yn 1)) said cell having means for outputting said partial product but Sm,n .

Claim 5

The apparatus of claim 1 including a cell corresponding to the most significant bit position with means for multiplication of both signed and unsigned numbers.

Claim 6

The apparatus of claim 2 wherein said means for multiplication of both signed and unsigned numbers includes exclusive-or gate means having as one input a mode control and as another input an incoming sum signal and having an output connected to said first circuit means of the most significant bit cell position, said exclusive-or gate means for inverting said incoming sum signal thereby placing a negative arithmetic weight on the X input.

Claim 7

The apparatus of claim 1 wherein said first circuit means includes a second storage means for receiving said carry-borrow bit Cm,n from said logic gates forming Cm,n, said second storage means having an output bit Cm,n 1, connected to said logic gates forming both Cm,n and Sm,n.

Claim 8

The apparatus of claim 1 wherein said means for outputting said partial product bit Sm,n of each of a number of said cells is connected to said first and second circuit means of an adjoining cell corresponding to a lower order bit position thereby forming a multicell unit.

Claim 9

The apparatus of claim 5 wherein all cells in each multicell unit are identical except for the most significant bit cell of the unit.

Claim 10

The apparatus of claim 5 wherein multicell units are connected together with the partial product bit from a cell corresponding to the least significant bit position of a first multicell unit connected to said first and second circuit means of a cell corresponding to the most significant bit position of a second multicell unit, said second multicell unit receiving lower order parallel Xm inputs relative to said first multicell unit.

Claim 11

A digital multiplier of the type taking a numerical multiplier serially, with multiplier bits in two''s complement notation, numbered in a time interval hierarchy as follows, YN , . . . , Yn 1 , Yn , Yn 1 , . . . Y1 , Y0 , where N is a number designating the time of occurrence of the most significant Y bit, and n is a number designating the time of occurrence of the nth bit, said digital multiplier taking multiplicand bits in parallel, with multiplicand bits in two''s complement notation, numbered in a bit position hierarchy as follows, XM , . . ., Xm 1 , Xm, Xm 1 , . . . X1 , X0 where M is a number designating the position of the most significant X bit, m is a number designating the position of the mth bit, and 0 is a number designating the position of the least significaNt X bit comprising, a. a first input means for receiving a serial stream of multiplier bits, YN , . . . , Yn , . . . Y0 presented in time least significant bit first, b. first logic gate means connected to said first input means, having an input for receiving said serial multiplicand bit stream and first storage means connected to said input, said first logic gate means forming the intermediate term Yn + Yn 1, and having a first output means for transmitting said intermediate product, c. at least one multiplier cell connected to said first output means and said first input means, said cell including: i. second input means for receiving a multiplier bit, Xm, ii. a third input means for receiving a partial product bit, Sm 1,n 1, where m+1 indicates a cell position origin and n-1 indicates a time of origin of said partial product sum bit, iii. first circuit means connected to said second and third input means and having second logic gate means for logically combining said intermediate term, Yn + Yn 1, with said multiplicand bit, Xm, and said partial product bit, Sm 1,n 1 into a borrow-carry bit, Cm,n, said second logic gates terminating in a borrow-carry bit output connected to a second storage means having an output bit designated Cm,n 1, wherein said second logic gates are arranged in combination with respect to said borrow-carry bit Cm,n as defined by the equation: Cm,n ((Xm . (Yn + Yn 1)) + Cm,n 1) . (Sm 1,n 1+ Yn) iv. second circuit means connected to said second and third input means and to said output of said second storage means and having third logic gate means for logically combining said intermediate term Yn + Yn 1, with said multiplicand bit Xm, said partial product sum bit, Sm 1,n 1 and said stored borrow-carry bit Cm,n 1 into a new partial sum bit, Sm,n, wherein said second logic gates are arranged in combination with respect to new partial product bit Sm,n as defined by the equation: Sm,n Sm 1,n 1 + Cm,n 1 + (Xm . (Yn + Yn 1)), and v. a second output means connected to said third circuit means for transmitting said new partial product bit, Sm,n.

Claim 12

A digital multiplier of the type taking a numerical multiplier serially, with multiplier bits in two''s complement notation, numbered in a time interval hierarchy as follows, YN , . . . , Yn 1 , Yn , Yn 1 , . . . Y1 , Y0 , where N is a number designating the time of occurrence of the most significant Y bit, and n is a number designating the time of occurrence of the nth bit, said digital multiplier taking multiplicand bits in parallel, with multiplicand bits in two''s complement notation, numbered in a bit position hierarchy as follows, XM , . . ., Xm 1 , Xm, Xm 1 , . . . X1 , X0 where M is a number designating the position of the most significant X bit, m is a number designating the position of the mth bit, and 0 is a number designating the position of the least significaNt X bit comprising, a. a first input means for receiving a serial stream of multiplier bits, YN , . . . , Yn , . . . Y0 presented in time least significant bit first, b. first logic gate means connected to said first input means, having an input for receiving said serial multiplicand bit stream and first storage means connected to said input, said first logic gate means forming the intermediate term Yn + Yn 1, and having a first output means for transmitting said intermediate product, c. at least one multiplier cell connected to said first output means and said first input means, said cell including: i. second input means for receiving a multiplier bit, Xm, ii. a third input means for receiving a partial product bit, Sm 1,n 1, where m+1 indicates a cell position origin and n-1 indicates a time of origin of said partial product sum bit, iii. first circuit means connected to said second and third input means and having second logic gate means for logically combining said intermediate term, Yn + Yn 1, with said multiplicand bit, Xm, and said partial product bit, Sm 1,n 1 into a borrow-carry bit, Cm,n, said second logic gates terminating in a borrow-carry bit output connected to a second storage means having an output bit designated Cm,n 1, wherein said second logic gates are arranged in combination with respect to said borrow-carry bit Cm,n as defined by the equation: Cm,n ((Xm . (Yn + Yn 1)) + Cm,n 1) . (Sm 1,n 1+ Yn) iv. second circuit means connected to said second and third input means and to said output of said second storage means and having third logic gate means for logically combining said intermediate term Yn + Yn 1, with said multiplicand bit Xm, said partial product sum bit, Sm 1,n 1 and said stored borrow-carry bit Cm,n 1 into a new partial sum bit, Sm,n, wherein said second logic gates are arranged in combination with respect to new partial product bit Sm,n as defined by the equation: Sm,n Sm 1,n 1 + Cm,n 1 + (Xm . (Yn + Yn 1)), and v. a second output means connected to said third circuit means for transmitting said new partial product bit, Sm,n.

Claim 13

The apparatus of claim 8 wherein a plurality of multiplier cells are connected with the second output means of each higher order cell connected to a respective third input means of a neighboring lower order cell.

Claim 14

The apparatus of claim 8 further including clock means connected to said first, second and third storage means.

Claim 15

The apparatus of claim 8 including, in a cell corresponding to the most significant bit position, means for multiplication of both signed and unsigned numbers.