Patent US2580347A successfully refreshed from Google Patents.
Patent US5528529A successfully refreshed from Google Patents.
US5528529A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Electronic multiplying and adding apparatus and method
Assignee: ARM Ltd
•
Filing: 1994-09-09
•
Granted: 1996-06-18
•
Expires: 2014-09-09
Abstract
Abstract A multiply-accumulate circuit is described in which upon each multiply iteration some of the accumulate value bits are incorporated into the result with lower order subsequently non-changing bits being latched. In this way, a wide accumulate value can be dealt with without incurring a correspondingly wide data path through the multiply accumulate circuit. Initialisation of the multiply accumulate circuit with one of the carry value and save value as the first partial summand and the other as at least part of the accumulate value is performed to reduce the total number of iterative cycles required to produce the result.
Inventors
- 👤 David J. Seal
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 17:29
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/38; G06F7/48; G06F7/544; G06F7/5443
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
224 words
An electronic multiplying and adding apparatus for multiplying an M-bit multiplicand by an N-bit multiplier and adding an (M+N)-bit accumulate value, said apparatus comprising: (i) means for generating a sequence of partial summands representing multiplication of said M-bit multiplicand and said N-bit multiplier; (ii) means for initialising a carry-save partial result as an initialising carry-save cycle; (iii) means for performing a plurality of carry-save cycles, each carry-save cycle adding one of the partial summands to an input carry-save partial result generated in an immediately preceding carry-save cycle to yield an output carry-save partial result for that carry-save cycle, wherein for each carry-save cycle, said input carry-save partial result has active carry bits that correspond to carry bits in said output carry-save partial result that are dependent upon said partial summand for that carry-save cycle and active save bits that correspond to save bits in said output carry-save partial result that are dependent upon said partial summand for that carry-save cycle a most significant bit of said active save bits having a bit position Y; and (iv) means for adding X bits of said (M+N)-bit accumulate value to said input carry-save partial result on each carry-save cycle at bit positions above a bit position Z, wherein said means for performing a plurality of carry-save cycles increases both Z and Y by X between carry-save cycles.
Claim 2
Dependent Claim
224 words
An electronic multiplying and adding apparatus for multiplying an M-bit multiplicand by an N-bit multiplier and adding an (M+N)-bit accumulate value, said apparatus comprising: (i) means for generating a sequence of partial summands representing multiplication of said M-bit multiplicand and said N-bit multiplier; (ii) means for initialising a carry-save partial result as an initialising carry-save cycle; (iii) means for performing a plurality of carry-save cycles, each carry-save cycle adding one of the partial summands to an input carry-save partial result generated in an immediately preceding carry-save cycle to yield an output carry-save partial result for that carry-save cycle, wherein for each carry-save cycle, said input carry-save partial result has active carry bits that correspond to carry bits in said output carry-save partial result that are dependent upon said partial summand for that carry-save cycle and active save bits that correspond to save bits in said output carry-save partial result that are dependent upon said partial summand for that carry-save cycle a most significant bit of said active save bits having a bit position Y; and (iv) means for adding X bits of said (M+N)-bit accumulate value to said input carry-save partial result on each carry-save cycle at bit positions above a bit position Z, wherein said means for performing a plurality of carry-save cycles increases both Z and Y by X between carry-save cycles.
Claim 3
Dependent Claim
13 words
An electronic multiplying and adding apparatus as claimed in claim 1, wherein X=2.
Claim 4
Dependent Claim
126 words
An electronic multiplying and adding apparatus as claimed in claim 2, wherein said means for adding adds said X bits of said (M+N)-bit accumulate value to said input carry-save partial result using: means for extending said output carry-save partial result on a carry-save cycle with extension save bits at bit positions Z+1 and Z+2 and an extension carry bit at bit position Z+2, said extension save bits being given by the sum of: the Z+1 th bit of said (M+N)-bit accumulate value; the complement of the Z th bit of said active carry bits; and the complement of the Z+1 th bit of said partial summand, and said extension carry bit being given by the complement of the Z+2 th bit of said (M+N)-bit accumulate value.
Claim 5
Dependent Claim
31 words
An electronic multiplying and adding apparatus as claimed in claim 1, wherein said means for generating comprises a Booth encoder, said sequence of partial summands being a sequence of Booth summands.
Claim 6
Dependent Claim
13 words
An electronic multiplying and adding apparatus as claimed in claim 1, wherein M=N.
Claim 7
Dependent Claim
13 words
An electronic multiplying and adding apparatus as claimed in claim 5, wherein M=N=32.
Claim 8
Dependent Claim
42 words
An electronic multiplying and adding apparatus as claimed in claim 1, said apparatus has one or more data buses for carrying said carry-save partial results between carry-save cycles said one or more data buses having a width of less than N+M bits.
Claim 9
Dependent Claim
26 words
An electronic multiplying and adding apparatus as claimed in claim 7, wherein M=N and said one or more data buses have a width of M+3 bits.
Claim 10
Dependent Claim
69 words
An electronic multiplying and adding apparatus as claimed in claim 1, wherein said means for generating a sequence of partial summands is operable such that the Z+1 th bit of the partial summand is either a zero or a sign extension depending upon a sign selecting input, said M-bit multiplicand and said N-bit multiplier being treated as unsigned or signed numbers respectively in dependence upon said sign selecting input.
Claim 11
Dependent Claim
22 words
An integrated circuit central processing unit having a hardware multiplier comprising an electronic multiplying and adding apparatus as claimed in claim 1.
Claim 12
Dependent Claim
42 words
An electronic multiplying and adding apparatus as claimed in claim 1 wherein said means for initialising initialises said carry value and said save value to a respective one of: at least part of said (N+M)-bit accumulate value; and a first partial summand.
Claim 13
Independent Claim
238 words
A method of multiplying and adding within an electronic multiplying and adding apparatus for multiplying an M-bit multiplicand by an N-bit multiplier and adding an (M+N)-bit accumulate value, said method comprising the steps of: (i) generating a sequence of partial summands representing multiplication of said M-bit multiplicand and said N-bit multiplier: initialising a carry-save partial result as an initialising carry-save cycle; (iii) performing a plurality of carry-save cycles, each carry-save cycle adding a respective one of the partial summands to an input carry-save partial result generated in an immediately preceding carry-save cycle to yield an output carry-save partial result for that carry-save cycle, wherein for each carry-save cycle said input carry-save partial result has active carry bits that correspond to carry bits in said output carry-save partial result that are dependent upon said partial summand for that carry-save cycle and active save bits that correspond to save bits in said output carry-save partial result that are dependent upon said partial summand for that carry-save cycle, a most significant bit of said active save bits having a bit position Z and a least significant bit of said active save bits having a bit position Y; and (iv) adding X bits of said (M+N)-bit accumulate value to said input carry-save partial result on each carry-save cycle at bit positions above bit position Z, wherein said performing step is such that Z and Y both increase by X between carry-save cycles.
Claim 14
Independent Claim
238 words
A method of multiplying and adding within an electronic multiplying and adding apparatus for multiplying an M-bit multiplicand by an N-bit multiplier and adding an (M+N)-bit accumulate value, said method comprising the steps of: (i) generating a sequence of partial summands representing multiplication of said M-bit multiplicand and said N-bit multiplier: initialising a carry-save partial result as an initialising carry-save cycle; (iii) performing a plurality of carry-save cycles, each carry-save cycle adding a respective one of the partial summands to an input carry-save partial result generated in an immediately preceding carry-save cycle to yield an output carry-save partial result for that carry-save cycle, wherein for each carry-save cycle said input carry-save partial result has active carry bits that correspond to carry bits in said output carry-save partial result that are dependent upon said partial summand for that carry-save cycle and active save bits that correspond to save bits in said output carry-save partial result that are dependent upon said partial summand for that carry-save cycle, a most significant bit of said active save bits having a bit position Z and a least significant bit of said active save bits having a bit position Y; and (iv) adding X bits of said (M+N)-bit accumulate value to said input carry-save partial result on each carry-save cycle at bit positions above bit position Z, wherein said performing step is such that Z and Y both increase by X between carry-save cycles.
Claim 15
Dependent Claim
13 words
A method of multiplying and adding as claimed in claim 12, wherein X=2.
Claim 16
Dependent Claim
109 words
A method of multiplying and adding as claimed in claim 12, wherein said step of adding comprises: extending said output carry-save partial result on a carry-save cycle with extension save bits at bit positions Z+1 and Z+2 and an extension carry bit at bit position Z+2, said extension save bits being given by the sum of: the Z+1 th bit of said (M+N)-bit accumulate value; the complement of the Z th bit of said active carry bits; and the complement of the Z+1 th bit of said partial summand, and said extension carry bit being given by the complement of the Z+2 th bit of said (M+N)-bit accumulate value.
Claim 17
Dependent Claim
42 words
A method of multiplying and adding as claimed in claim 12 wherein said step of initialising initialises said carry value and said save value to a respective one of: a least part of said (N+M)-bit accumulate value; and a first partial summand.
Claim 18
Dependent Claim
142 words
An electronic multiplying and adding apparatus for multiplying an M-bit multiplicand by an N-bit multiplier and adding an (N+M)-bit accumulate value, said apparatus comprising: (i) means for generating a sequence of partial summands representing multiplication of said M-bit multiplicand and said N-bit multiplier; (ii) means for initialising as an initialising carry-save cycle a carry value and a save value to a respective one of: at least part of said (N+M)-bit accumulate value; and a first partial summand; and (iii) means for performing a plurality of carry -save cycles, each carry-save cycle adding one of the partial summands to an input carry-save partial result generated in an immediately preceding carry-save cycle to yield an output carry-save partial result for that carry-save cycle, wherein said input carry-save partial result and said output carry-save partial result each comprises said carry value and said save value.
Claim 19
Dependent Claim
142 words
An electronic multiplying and adding apparatus for multiplying an M-bit multiplicand by an N-bit multiplier and adding an (N+M)-bit accumulate value, said apparatus comprising: (i) means for generating a sequence of partial summands representing multiplication of said M-bit multiplicand and said N-bit multiplier; (ii) means for initialising as an initialising carry-save cycle a carry value and a save value to a respective one of: at least part of said (N+M)-bit accumulate value; and a first partial summand; and (iii) means for performing a plurality of carry -save cycles, each carry-save cycle adding one of the partial summands to an input carry-save partial result generated in an immediately preceding carry-save cycle to yield an output carry-save partial result for that carry-save cycle, wherein said input carry-save partial result and said output carry-save partial result each comprises said carry value and said save value.
Claim 20
Dependent Claim
33 words
An electronic multiplying and adding apparatus as claimed in claim 16, wherein said means for generating comprises a modified Booth encoder, said sequence of partial summands being a sequence of modified Booth summands.
Claim 21
Dependent Claim
58 words
An electronic multiplying and adding apparatus as claimed in claim 17, wherein, said modified Booth encoder is operable such that when said N-bit multiplier is unsigned, respective bits R[a] of an internal multiplier representing said N-bit multiplier are given by: R[(N-1) to 0] are equal to corresponding bits of said N-bit multiplier, and R[N] is equal to zero.
Claim 22
Dependent Claim
58 words
An electronic multiplying and adding apparatus as claimed in claim 17, wherein, said modified Booth encoder is operable such that when said N-bit multiplier is signed, respective bits R[a] of an internal multiplier representing said N-bit multiplier are given by: R[(N-1) to 0] are equal to corresponding bits of said N-bit multiplier, and R[N] is equal to R[(N-1)].
Claim 23
Dependent Claim
35 words
An electronic multiplying and adding apparatus as claimed in claim 19, wherein, said modified Booth encoder is operable such that if R[0] is equal to zero, then said first partial summand is initialised to zero.
Claim 24
Dependent Claim
47 words
An electronic multiplying and adding apparatus as claimed in claim 19, wherein, said modified Booth encoder is operable such that if R[0] is equal to one, then said first partial summand is initialised to a bitwise inverse of said M-bit multiplicand with a one being added later.
Claim 25
Dependent Claim
35 words
An electronic multiplying and adding apparatus as claimed in claim 21, comprising a final adder for adding said carry value and said save value, a carry-in bit for said final adder being set to R[0].
Claim 26
Independent Claim
147 words
A method of multiplying and adding within an electronic multiplying and adding apparatus for multiplying an M-bit multiplicand by an N-bit multiplier and adding an (M+N)-bit accumulate value, said method comprising the steps of: (i) generating a sequence of partial summands representing multiplication of said M-bit multiplicand and said N-bit multiplier; (ii) initialising as an initialising carry-save cycle a carry value and a said save value to a respective one of: at least part of said (N+M)-bit accumulate value; and a partial summand; and (iii) performing a plurality of carry-save cycles, each carry-save cycle adding a respective one of the partial summands to an input carry-save partial result generated in an immediately preceding carry-save cycle to yield an output carry-save partial result for that carry-save cycle, wherein said input carry-save partial result and said output carry-save partial result each comprising said carry value and said save value.
Claim 27
Independent Claim
147 words
A method of multiplying and adding within an electronic multiplying and adding apparatus for multiplying an M-bit multiplicand by an N-bit multiplier and adding an (M+N)-bit accumulate value, said method comprising the steps of: (i) generating a sequence of partial summands representing multiplication of said M-bit multiplicand and said N-bit multiplier; (ii) initialising as an initialising carry-save cycle a carry value and a said save value to a respective one of: at least part of said (N+M)-bit accumulate value; and a partial summand; and (iii) performing a plurality of carry-save cycles, each carry-save cycle adding a respective one of the partial summands to an input carry-save partial result generated in an immediately preceding carry-save cycle to yield an output carry-save partial result for that carry-save cycle, wherein said input carry-save partial result and said output carry-save partial result each comprising said carry value and said save value.
References Cited (Backward Citations)
WO1985005705A1
Cited
WO1986002181A1
Cited
US5262976A
Cited
WO1992008189A1
Cited
US5325320A
Cited
US5426599A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-06-18 | 1999-12-18 | 2000-06-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-06-18 | 2003-12-18 | 2004-06-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-06-18 | 2007-12-18 | 2008-06-18 | $7700.00 | Window Closed / Lapsed |