Two's complement multiplication with a sign magnitude multiplier

Claim 2

In a system for multiplying a binary digital multiplicand operand X by a binary digital multiplier operand Y, X and Y both being either sign magnitude or complemented binary numbers, an improvement for multiplying said operands without pre- or post- complementation, said improvement comprising: storage means for holding two n-bit operands, X and Y, the bits of each operand being in a sequence in which bit significance decreases from a most significant bit to a least significant bit, each operand including at least one sign bit; overlapped scanning means connected to said storage means for multiplying operand X with a sequence of multiplier bit groups obtained from operand Y, each group including s successive bits of Y and overlapping an adjacent group by at least one bit, s being greater than 3; matrix assembly means connected to said overlapped scanning means and responsive to successive scans of X for producing a sequence of partial products assembled into a matrix including m+1 offset rows, where m=INT[(n-1)/(s-1)], each row including one of said partial products; sign encoding means in said matrix assembly means and connected to said overlapped scanning means and responsive to said sequence of multiplier bit groups or to a multiplicand sign bit for appending sign encoding bits onto said partial products to complete said rows; and means connected to said matrix assembly means for adding said partial products, with said sign encoding bits appended, to produce a product of X multiplied by Y.

Claim 3

The improvement of claim 1 wherein said complemented binary numbers are binary digits with n-(s-1) bits in a sequence of descending significance from respective sign bits, X O and Y O , to respective least significant bits, X n-s and Y n-s , said improvement further including: first and second registers in said storage means, each of said registers for storing an n-bit sign magnitude number in significance sequence from most to least significant bit or for storing an n-(s-1)-bit complemented binary number, said complemented binary number being stored in significance sequence from sign to least significant bit where the least significant n-(s-1) bits of said magnitude number are stored; and connected to each of said first and second registers, sign extension means for entering s-1 replications of the sign bit of a signed binary number where the most significant s-1 bits of a sign magnitude number are stored.

Claim 4

The improvement of claim 2 wherein X and Y are complemented binary numbers, and the first bit group of said sequence contains only bits identical to the sign of Y.

Claim 5

The improvement of claim 3, wherein said matrix, identified as P, is defined by: ##EQU26## where Φ j is a row of P produced by multiplying X with a multiplier bit group (Y k- (s-2) Y k- (s-1) . . . Y.sub.(k) Y.sub.(k±1)) and where Φj=S j X|W j |, |W j | signifying the absolute value of W j , W j being a coefficient by which X is multiplied to produce said jth row, and S j being the sign of said coefficient, where: S.sub.j =(Y.sub.k-(s-2))-W(0) such that: -W(0)=(Y.sub.k-(s-2) Y.sub.k-(s-1) Y.sub.(k-s) . . . Y.sub.(k) Y.sub.(k+1))+(-Y.sub.k-(s-2) -Y.sub.k-(s-1) -Y.sub.(k-s) . . . -Y.sub.k -Y.sub.(k+1)) + being logical "or", juxtaposition of terms being their logical "AND", and - indicating the logical complement.

Claim 6

The improvement of claim 4 wherein for the j-th row of said matrix, 2≦j≦m, said sign encoding means appends a sequence of s-1 sign extension bits on the jth partial product, said sign extension bits including s-2 ones followed by a last bit, b, having a value determined by: b=→[(X.sub.sign V S.sub.j)W(0)] where X sign is the sign bit of X and V denotes the "exclusive OR" operation.

Claim 7

The improvement of claim 5 wherein each of said partial products has a most significant end and said (s-1) sign extension bits are appended to the most significant end of each of said partial products, said bit b being adjacent the most significant partial product bit.

Claim 8

The improvement of claim 6 wherein a sequence of s sign extension bits is appended to the most significant end of the last row of said matrix, the first of said s sign extension bits being determined by: bit=→[(X.sub.sign V Sj)→W(0)] and each of the next s-1 of said sign extension bits being determined by: bits=[(X.sub.sign V S.sub.j)·W(0)].

Claim 9

In a multi-bit overlapped scanning multiplier for multiplying n-bit sign magnitude operands X and Y to produce a product, said multiplier including means for producing an overlapped scan matrix having m+1 rows in which each row includes a partial product produced by multiplying X with one of a sequence of bit groups of Y, each bit group overlapping an adjacent bit group, each bit group including s bits, an improvement for multiplying a pair of two's complement binary operands X tc and Y tc each including n-(s-1) bits arranged in significance sequence from a bit 0, a sign bit, through bit n-s, said improvement comprising: extension means for extending the sign bits of X tc and Y tc by appending to X tc s-1 replications of X 0 , the sign bit of X, and by appending to Y tc s-1 replications of Y 0 , the sign bit of Y; matrix means connected to said extension means for producing a banded matrix of overlapped rows, each row including a respective partial product of n+1 bits produced by multiplying X tc with a respective s-bit group of Y tc said bit group including bits Y.sub.(k-s-2) Y.sub.(k-s-1) Y.sub.(k-s) . . . Y.sub.(k) Y.sub.(k+1), in significance sequence, and said s-bit group overlapping a next s-bit group by Y k+1 , said matrix including m+1 rows, where: m=INT[(n-1)/(s-1)] and said matrix including j middle rows, 2≦j≦m, in which each row Φ j , is given by: Φ.sub.j =S.sub.j X.sub.tc |W.sub.j | where S j is the sign of the jth row and |W j | is the absolute value of a coefficient W j by which X tc is multiplied to produce said jth row; and sign means for computing the sign S j of the jth row of said matrix according to: S.sub.j =Y.sub.(k-s-2) -W(o) where: W(o)=(Y.sub.(k-s-2) Y.sub.(k-s-1)Y(k-s) . . . Y.sub.(k) Y.sub.(k+1))+(-Y.sub.(k-s-2) -Y.sub.(k-s-1) -Y.sub.(k-s) . . . -Y.sub.(k) -Y.sub.(k+1)).

Claim 10

In a multi-bit overlapped scanning multiplier for multiplying n-bit sign magnitude operands X and Y to produce a product, said multiplier including means for producing an overlapped scan matrix having m+1 rows in which each row includes a partial product produced by multiplying X with one of a sequence of bit groups of Y, each bit group overlapping an adjacent bit group, each bit group including s bits, an improvement for multiplying a pair of two's complement binary operands X tc and Y tc each including n-(s-1) bits arranged in significance sequence from a bit 0, a sign bit, through bit n-s, said improvement comprising: extension means for extending the sign bits of X tc and Y tc by appending to X tc s-1 replications of X 0 , the sign bit of X, and by appending to Y tc s-1 replications of Y 0 , the sign bit of Y; matrix means connected to said extension means for producing a banded matrix of overlapped rows, each row including a respective partial product of n+1 bits produced by multiplying X tc with a respective s-bit group of Y tc said bit group including bits Y.sub.(k-s-2) Y.sub.(k-s-1) Y.sub.(k-s) . . . Y.sub.(k) Y.sub.(k+1), in significance sequence, and said s-bit group overlapping a next s-bit group by Y k+1 , said matrix including m+1 rows, where: m=INT[(n-1)/(s-1)] and said matrix including j middle rows, 2≦j≦m, in which each row Φ j , is given by: Φ.sub.j =S.sub.j X.sub.tc |W.sub.j | where S j is the sign of the jth row and |W j | is the absolute value of a coefficient W j by which X tc is multiplied to produce said jth row; and sign means for computing the sign S j of the jth row of said matrix according to: S.sub.j =Y.sub.(k-s-2) -W(o) where: W(o)=(Y.sub.(k-s-2) Y.sub.(k-s-1)Y(k-s) . . . Y.sub.(k) Y.sub.(k+1))+(-Y.sub.(k-s-2) -Y.sub.(k-s-1) -Y.sub.(k-s) . . . -Y.sub.(k) -Y.sub.(k+1)).