Patent US1361504A successfully refreshed from Google Patents.
Patent US4918639A successfully refreshed from Google Patents.
US4918639A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Overlapped multiple-bit scanning multiplication system with banded partial product matrix
Assignee: International Business Machines Corp
•
Filing: 1987-11-03
•
Granted: 1990-04-17
•
Expires: 2007-11-03
Abstract
Abstract A multi-bit overlapped scanning multiplication system assembles modified partial products in a reduced, non-rectangular banded matrix. The rows of the matrix except for the first and last, are extended with bands of encoded extensions of limited length at the right and left ends of the partial product terms. The width of the significant bits of each partial product term is equal to q-1+S-2, where q is the width of the significant bits plus sign of the multiplicand and S is the number of bits which are overlapped scanned. Each partial product term is shifted S-1 bits from adjacent terms and is banded by encoded extensions to the terms. S-1 bits of encode are placed to the right of every terms except the last, the encode being based on the sign of the next partial product term; and S-1 bits of encoded sign extension are placed to the left of every term except the first, which has no sign extension, and last, to the left of which is placed an S bit encode. The bits of negative partial product terms are inverted, and a "hot 1" is encoded in the right extension in the previous row. The first bit of the multiplier is forced to zero so that the first partial product term is always positive or zero. Carry save adder trees are used to reduce each column of the matrix to two terms. When inputs to a carry save adder are known, the logic of the carry save adder is simplified to save chip space.
Inventors
- 👤 Eric M. Schwarz
- 👤 Stamatis Vassiliadis
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 08:18
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/38; G06F7/48; G06F7/52; G06F7/523; G06F7/533; G06F7/5334; G06F7/5336; G06F7/499; G06F7/49994
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
169 words
In a system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is greater than three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial product matrix, said partial products having q-1+S-2 bit positions, where q is the width of the significant bits plus the sign of said multiplicand in binary two's complement form which includes bit 0 with the least significant bit bit being the (q-1)th bit; and means for adding said modified partial products in parallel.
Claim 2
Dependent Claim
169 words
In a system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is greater than three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial product matrix, said partial products having q-1+S-2 bit positions, where q is the width of the significant bits plus the sign of said multiplicand in binary two's complement form which includes bit 0 with the least significant bit bit being the (q-1)th bit; and means for adding said modified partial products in parallel.
Claim 3
Dependent Claim
145 words
In a system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is greater than three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial product matrix, said assembly means providing all but the first of said modified partial products with encoded sign extensions; and means for adding said modified partial products in parallel.
Claim 4
Dependent Claim
145 words
In a system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is greater than three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial product matrix, said assembly means providing all but the first of said modified partial products with encoded sign extensions; and means for adding said modified partial products in parallel.
Claim 5
Dependent Claim
39 words
In a system as recited in claim 2, wherein said assembly means inverts the bits of any modified partial product whose sign is negative and appends an encoded hot "1" extension to the partial product in the previous row.
Claim 6
Dependent Claim
46 words
In a system as recited in claim 3, further comprising means for forcing the first bit of said multiplier to zero, whereby the first partial product will always be either zero or positive to avoid the need for a hot "1", there being no previous row.
Claim 7
Dependent Claim
82 words
In a system as recited in claim 3, wherein each row except the last contains a coded sign extension of S-1 bit positions appended to the right of said partial product, if the partial product in a given row is positive, said S-1 bit positions appended to the previous row being "0" bits and if the partial product in said given row is negative, said S-1 bit positions appended to said previous row being S-2 "0" bits followed by a "1" bit.
Claim 8
Dependent Claim
136 words
In the system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is greater than three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial matrix, said partial products being modified by adding S-2+2(S-1) bits; and means for adding said modified partial products in parallel.
Claim 9
Dependent Claim
136 words
In the system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is greater than three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial matrix, said partial products being modified by adding S-2+2(S-1) bits; and means for adding said modified partial products in parallel.
Claim 10
Dependent Claim
192 words
In the system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is greater than three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial matrix, all but the first of said modified partial products having encoded sign extensions, and wherein, in all rows but the first and last row, if said partial product is positive, said partial product having an encoded sign extension of (S-1) "1" bits and, if said partial product is negative, said partial product having (S-2) "1" bits followed by a "0" bit in the (S-1)st position; and means for adding said modified partial products in parallel.
Claim 11
Dependent Claim
192 words
In the system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is greater than three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial matrix, all but the first of said modified partial products having encoded sign extensions, and wherein, in all rows but the first and last row, if said partial product is positive, said partial product having an encoded sign extension of (S-1) "1" bits and, if said partial product is negative, said partial product having (S-2) "1" bits followed by a "0" bit in the (S-1)st position; and means for adding said modified partial products in parallel.
Claim 12
Dependent Claim
52 words
In a system as recited in claim 7, wherein in said last row said encoded sign extension comprises S bits, and wherein if said partial product is positive, comprises a "1" bit followed by S-1 "0" bits, and if said partial product is negative, comprises a "1" bit followed by S-1 bits.
Claim 13
Dependent Claim
22 words
In the system as recited in claim 7, wherein said coded sign extensions are appended to the left of said partial products.
Claim 14
Dependent Claim
22 words
In a system as recited in claim 7, wherein the last row contains a coded extension to the left of S bits.
Claim 15
Dependent Claim
41 words
In a system as recited in claim 7, wherein with the exception of the first and last rows, each row contains coded extensions on the left of S-1 bits and on the right of S-1 bits, and contains q+3S-5 bit positions.
Claim 16
Dependent Claim
22 words
In a system as recited in claim 7, wherein the first row contains a coded extension to the right of S-1 bits.
Claim 17
Dependent Claim
148 words
In a system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is greater than three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial product matrix; and means for adding said modified partial products in parallel, said means for adding the modified partial products comprising a carry save adder tree for each column of said matrix.
Claim 18
Dependent Claim
148 words
In a system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is greater than three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial product matrix; and means for adding said modified partial products in parallel, said means for adding the modified partial products comprising a carry save adder tree for each column of said matrix.
Claim 19
Dependent Claim
33 words
A system as recited in claim 13, wherein said means for adding said partial products further comprises two to one addition means for adding the results produced by said carry save adder trees.
Claim 20
Dependent Claim
81 words
In a system as recited in claim 13, wherein each carry save adder tree comprises a plurality of carry save adder logic means, each receiving three inputs, and wherein when all the three inputs of a carry save adder means are unknown, said carry save adder means being a carry save adder logic circuit, and wherein when at least one of the three inputs of a carry save adder means is known, said carry save adder means being simplified logic means.
Claim 21
Dependent Claim
127 words
In a system as recited in claim 15, wherein when all three inputs to a carry save adder means are known to be "0", the carry and save outputs of the carry save adder means are hardwired by being tied down to "0"; when two of the three inputs are known to be "0" and the other input is know to be "1", the carry output is tied down to "0" and the save output is tied to "1"; when two of the inputs are known to be "1", the carry output is tied up to "1" and the save output is tied down to "0"; and when all of the inputs are known to be "1", the carry and save outputs are tied up to "1".
Claim 22
Dependent Claim
105 words
In a system as recited in claim 15, wherein when one of said inputs to a carry save adder means is known to be "0" and the other inputs are unknown, said carry save adder means comprises a 2-way AND gate for the carry output and a 2-way Exclusive OR gate for the save output and wherein when said one of said inputs is known to be "1" and the other inputs to a said carry save adder means are unknown, said carry save adder means comprises a 2-way OR gate for the carry output and a 2-way Exclusive NOR gate for the save output.
Claim 23
Dependent Claim
138 words
In a system as recited in claim 15, wherein when two of said inputs to a carry save adder means are known to be "0" and one input is unknown, said carry save adder means comprises a hardwired "0" carry output and a save output hardwired to the one input, when one of the inputs is known to be "1", one of the inputs is known to be "0", and the third input is unknown, said carry output is hardwired to the third input and the save input is connected to the third input through an inverter, and when two of the inputs to a carry save adder means are known to be "1" and the other input is unknown, the carry output is hardwired to be "1" and the save output is hardwired to the other input.
Claim 24
Dependent Claim
286 words
In a system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S=4; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial product matrix, said assembly means comprising means for computing partial products of X, 2X, 4X and 0 of said multiplicand, means for computing the partial product 3X of said multiplicand, means for computing boundary bits to be used in coded extensions of said partial products, decode means for deriving first code terms, second code terms and third code terms from said scanned bits of each said scan, multiplexor means selecting one of said X, 2X, 4X and 0 partial products of said multiplicand in response to said first code terms, selection means selecting one of said selected partial products from said multiplexor means and said partial product 3X and selecting the sign of the partial product in response to said second code terms, and means responsive to said third code terms of the current and next scan for selecting said boundary bits for a row of said matrix and for inverting the bits of the selected partial product if the selected sign is negative; and means for adding said modified partial products in parallel.
Claim 25
Dependent Claim
286 words
In a system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S=4; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial product matrix, said assembly means comprising means for computing partial products of X, 2X, 4X and 0 of said multiplicand, means for computing the partial product 3X of said multiplicand, means for computing boundary bits to be used in coded extensions of said partial products, decode means for deriving first code terms, second code terms and third code terms from said scanned bits of each said scan, multiplexor means selecting one of said X, 2X, 4X and 0 partial products of said multiplicand in response to said first code terms, selection means selecting one of said selected partial products from said multiplexor means and said partial product 3X and selecting the sign of the partial product in response to said second code terms, and means responsive to said third code terms of the current and next scan for selecting said boundary bits for a row of said matrix and for inverting the bits of the selected partial product if the selected sign is negative; and means for adding said modified partial products in parallel.
Claim 26
Dependent Claim
33 words
In a system as recited in claim 19, wherein a coded extension signifying a hot "1" is appended to the right of the previous partial product row when said selected sign is negative.
Claim 27
Dependent Claim
67 words
In a system as recited in claim 19, wherein each row contains a coded sign extension of three bit positions, if the partial product in a given row is positive, said three bit positions appended to the previous row being "0"s and if the partial product in said given row is negative, said three bit positions appended to said previous row being two "0"s followed by "1".
Claim 28
Dependent Claim
208 words
In a system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is at least three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial product matrix, wherein all but the first of said modified partial products have encoded sign extensions, wherein, in all rows but the first and last row, if said partial product is positive, said partial product has an encoded sign extension of (S-1) "1" bits and, if said partial product is negative, said partial product has (S-2) "1" bits followed by a "0" bit in the (S-1)st position, and wherein the last row contains a coded extension to the left of S bits; and means for adding said modified partial products in parallel.
Claim 29
Dependent Claim
208 words
In a system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is at least three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial product matrix, wherein all but the first of said modified partial products have encoded sign extensions, wherein, in all rows but the first and last row, if said partial product is positive, said partial product has an encoded sign extension of (S-1) "1" bits and, if said partial product is negative, said partial product has (S-2) "1" bits followed by a "0" bit in the (S-1)st position, and wherein the last row contains a coded extension to the left of S bits; and means for adding said modified partial products in parallel.
Claim 30
Dependent Claim
43 words
In a system as recited in claim 22, wherein said last row, if said partial product is positive, comprises a "1" bit followed by S-1 "0" bits, and if said partial product is negative, comprises a "1" bit followed by S-1 "1" bits.
Claim 31
Dependent Claim
212 words
In a system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is at least three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial product matrix; and means for adding said modified partial products in parallel comprising a carry save adder tree for each column of said matrix, each carry save adder tree comprising a plurality of carry save adder logic means, each receiving three inputs, and wherein when all the three inputs of a carry save adder means are unknown, said carry save adder means being a carry save adder logic circuit, and wherein when at least one of the three inputs of a carry save adder means is known, said carry save adder means being simplified logic means.
Claim 32
Dependent Claim
212 words
In a system for multiplying a multiplicand X by a multiplier Y, each of which is either a floating point sign magnitude number in binary notation including a sign, a fraction, and an exponent, or an unsigned number in binary notation, means for multiplying the fractions of said sign magnitude numbers or said unsigned numbers, comprising: overlapped scanning means for scanning said multiplier with S successive bits at a time, each scan overlapping one of the bits of the previous scan, wherein S is at least three; assembly means responsive to said successive scanned bits to select and encode modified partial products of said multiplicand for assembly in a plurality of rows of a banded partial product matrix; and means for adding said modified partial products in parallel comprising a carry save adder tree for each column of said matrix, each carry save adder tree comprising a plurality of carry save adder logic means, each receiving three inputs, and wherein when all the three inputs of a carry save adder means are unknown, said carry save adder means being a carry save adder logic circuit, and wherein when at least one of the three inputs of a carry save adder means is known, said carry save adder means being simplified logic means.
Claim 33
Dependent Claim
128 words
In a system as recited in claim 24, wherein when all three inputs to a carry save adder means are known to be "0", the carry and save outputs of the carry save adder means are hardwired by being tied down to "0"; when two of the three inputs are known to be "0" and the other input is known to be "1", the carry output is tied down to "0" and the save output is tied up to "1"; when two of the inputs are known to be "1", the carry output is tied up to "1" and the save output is tied down to "0"; and when all of the inputs are known to be "1", the carry and save outputs are tied up to "1".
Claim 34
Dependent Claim
105 words
In a system as recited in claim 24, wherein when one of said inputs to a carry save adder means is known to be "0" and the other inputs are unknown, said carry save adder means comprises a 2-way AND gate for the carry output and a 2-way Exclusive OR gate for the save output and wherein when said one of said inputs is known to be "1" and the other inputs to a said carry save adder means are unknown, said carry save adder means comprises a 2-way OR gate for the carry output and a 2-way Exclusive NOR gate for the save output.
Claim 35
Dependent Claim
138 words
In a system as recited in claim 24, wherein when two of said inputs to a carry save adder means are known to be "0" and one input is unknown, said carry save adder means comprises a hardwired "0" carry output and a save output hardwired to the one input, when one of the inputs is known to be "1", one of the inputs is known to be "0", and the third input is unknown, said carry output is hardwired to the third input and the save input is connected to the third input through an inverter, and when two of the inputs to a carry save adder means are known to be "1" and the other input is unknown, the carry output is hardwired to the "1" and the save output is hardwired to the other input.
References Cited (Backward Citations)
US4748582A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-04-16 | 1993-10-16 | 1994-04-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-04-16 | 1997-10-16 | 1998-04-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-04-16 | 2001-10-16 | 2002-04-17 | $7700.00 | Window Closed / Lapsed |