US5883824A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parallel adding and averaging circuit and method
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1993-11-29
•
Granted: 1999-03-16
•
Expires: 2013-11-29
Abstract
Abstract An apparatus that can also be used for generating the average of two integers. The apparatus can be divided into a plurality of sub-adders that operate on sub-words of the input integers in parallel. Hence, the adder can be used for adding or subtracting one set of two integers wherein each integer is of some predetermined length or a plurality of sets of two integers provided the sum of the lengths of the integers is less than or equal to this predetermined length. The apparatus can also generate the sum, or difference, of each of the sub-words divided by two. The parallel operations can be carried out in response to a single instruction. The results of the division by two are rounded in a manner that eliminates biasing of the results.
Inventors
- 👤 Ruby Bei-Loh Lee
- 👤 John Paul Beck
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 12:57
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/38; G06F7/48; G06F7/50; G06F7/505; G06F7/506; G06F7/508; G06F7/544; G06F7/57; G06F7/575; G06F2207/00; G06F2207/38; G06F2207/3804; G06F2207/3808; G06F2207/3812; G06F2207/382; G06F2207/3828; G06F7/499; G06F7/49942; G06F7/49947; G06F7/49963
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
168 words
An apparatus for operating on the contents of an X word having bits X i and a Y word having bits Y i to generate a result word having bits Z i , where i=0 to N-1, where Z 0 is the least significant bit of one of said sub-words and Z N-1 is the most significant bit of one of said sub-words, said apparatus comprising: means for partitioning said X, Y and result words into a plurality of sub-words, there being one sub-word of said Y and result words corresponding to each sub-word of said X word; means, responsive to a first instruction, for generating the sum of each X sub-word and the corresponding Y sub-word, the result thereof determining said corresponding sub-word of said result word; and means, responsive to a second instruction, for generating the sum divided by two of each sub-word in said X word and the corresponding sub-word in said Y word, the result thereof determining said corresponding sub-word of said result word.
Claim 2
Independent Claim
168 words
An apparatus for operating on the contents of an X word having bits X i and a Y word having bits Y i to generate a result word having bits Z i , where i=0 to N-1, where Z 0 is the least significant bit of one of said sub-words and Z N-1 is the most significant bit of one of said sub-words, said apparatus comprising: means for partitioning said X, Y and result words into a plurality of sub-words, there being one sub-word of said Y and result words corresponding to each sub-word of said X word; means, responsive to a first instruction, for generating the sum of each X sub-word and the corresponding Y sub-word, the result thereof determining said corresponding sub-word of said result word; and means, responsive to a second instruction, for generating the sum divided by two of each sub-word in said X word and the corresponding sub-word in said Y word, the result thereof determining said corresponding sub-word of said result word.
Claim 3
Dependent Claim
88 words
The apparatus of claim 1 wherein said apparatus comprises means for operating on one or more bits from said X word and corresponding bits derived from said Y word, and means for generating a generate bit and a propagate bit corresponding to each said bit of said X word, and wherein said partitioning means comprises means for forcing said generate bit and said propagate bit to values determined by the operation being performed if said bit of said X word is the most significant bit of a sub-word.
Claim 4
Dependent Claim
90 words
The apparatus of claim 2 wherein said operating means generates N result bits, S i , for i=0 to N-1, S i being derived from operations on X i , and wherein said apparatus further comprises N multiplexing means, each said multiplexing means generating a signal indicative of one of said result bits, there being one said multiplexing means for each said result bit Z p , for p=0 to N-1, said multiplexing means corresponding to Z p connecting S p to Z p in response to said first instruction.
Claim 5
Dependent Claim
111 words
The apparatus of claim 3 further comprising means for generating a carry bit, C p , corresponding to each bit X p that is a most significant bit of a sub-word and wherein said multiplexing means corresponding to Z p connects Z p to S p+1 in response to said second instruction if Z p is interior to one of said sub-words and to C p if Z p is the most significant bit of one of said result sub-words, wherein C p is said carry bit generated by said adding stage operating on the most significant bit of said X sub-word corresponding to said result sub-word containing Z p .
Claim 6
Dependent Claim
42 words
The apparatus of claim 4 wherein said multiplexing means corresponding to Z p further comprises means to connect Z p to (S p+1 OR S p ) if Z p is the least most significant bit of one of said result sub-words.
Claim 7
Dependent Claim
80 words
The apparatus of claim 3 further comprising means for generating a carry bit, C p , corresponding to each bit X p that is a most significant bit of a sub-word and wherein said multiplexing means corresponding to Z p connects Z p to S p+1 in response to said second instruction if Z p is interior to one of said sub-words and to S p if Z p is the most significant bit of one of said result sub-words.
Claim 8
Dependent Claim
98 words
The apparatus of claim 1 wherein said apparatus comprises a plurality of adding stages connected in series, each said adding stage comprising means for operating on one or more bits from said X word and corresponding bits derived from said Y word, and means for propagating a carry bit from said adding stage to the next said adding stage in said series connection, and wherein said partitioning means comprises means for forcing said carry bit to a value determined by the operation being performed if said adding stages operate on bits of different sub-words in said X word.
Claim 9
Dependent Claim
90 words
The apparatus of claim 7 wherein said adding stages generate N result bits, S i , for i=0 to N-1, S i being derived from operations on X i , and wherein said apparatus further comprises N multiplexing means, each said multiplexing means generating a signal indicative of one of said result bits, there being one said multiplexing means for each said result bit Z p , for p=0 to N-1, said multiplexing means corresponding to Z p connecting S p to Z p in response to said first instruction.
Claim 10
Dependent Claim
84 words
The apparatus of claim 8 wherein said multiplexing means corresponding to Z p connects Z p to S p+1 in response to said second instruction if Z p is interior to one of said sub-words and to C p if Z p is the most significant bit of one of said result sub-words, wherein C p is said carry bit generated by said adding stage operating on the most significant bit of said X sub-word corresponding to said result sub-word containing Z p .
Claim 11
Dependent Claim
42 words
The apparatus of claim 9 wherein said multiplexing means corresponding to Z p further comprises means to connect Z p to (S p+1 OR S p ) if Z p is the least most significant bit of one of said result sub-words.
Claim 12
Independent Claim
192 words
An apparatus for operating on the contents of an X word having bits X i and a Y word having bits Y i to generate a result word having bits Z i , where i=0 to N-1, where Z 0 is the least significant bit of one of said sub-words and Z N-1 is the most significant bit of one of said sub-words, said apparatus comprising: means for partitioning said X, Y and result words into a plurality of sub-words, there being one sub-word of said Y and result words corresponding to each sub-word of said X word; means, responsive to a first instruction, for generating the sum of each X sub-word and the corresponding Y sub-word, the result thereof determining said corresponding sub-word of said result word; and means, responsive to a second instruction, for generating the sum divided by two of each sub-word in said X word and the corresponding sub-word in said Y word, the result thereof determining said corresponding sub-word of said result word, wherein each of said results is rounded to the next highest odd integer if said division by two resulted in a round off error.
Claim 13
Independent Claim
192 words
An apparatus for operating on the contents of an X word having bits X i and a Y word having bits Y i to generate a result word having bits Z i , where i=0 to N-1, where Z 0 is the least significant bit of one of said sub-words and Z N-1 is the most significant bit of one of said sub-words, said apparatus comprising: means for partitioning said X, Y and result words into a plurality of sub-words, there being one sub-word of said Y and result words corresponding to each sub-word of said X word; means, responsive to a first instruction, for generating the sum of each X sub-word and the corresponding Y sub-word, the result thereof determining said corresponding sub-word of said result word; and means, responsive to a second instruction, for generating the sum divided by two of each sub-word in said X word and the corresponding sub-word in said Y word, the result thereof determining said corresponding sub-word of said result word, wherein each of said results is rounded to the next highest odd integer if said division by two resulted in a round off error.
Claim 14
Independent Claim
205 words
An apparatus for operating on the contents of an X word having bits X i and a Y word having bits Y i to generate a result word having bits Z i , where i=0 to N-1, where Z 0 is the least significant bit of one of said sub-words and Z N-1 is the most significant bit of one of said sub-words, said apparatus comprising: means for partitioning said X, Y and result words into a plurality of sub-words, there being one sub-word of said Y and result words corresponding to each sub-word of said X word; means, responsive to a first instruction, for generating the sum of each X sub-word and the corresponding Y sub-word, the result thereof determining said corresponding sub-word of said result word; and means, responsive to a second instruction, for generating the difference of each sub-word in said X word and the corresponding sub-word in said Y word, the result thereof determining said corresponding sub-word of said result word; and means, responsive to a third instruction, for generating the difference divided by two of each sub-word in said X word and the corresponding sub-word in said Y word, the result thereof determining said corresponding sub-word of said result word.
Claim 15
Independent Claim
205 words
An apparatus for operating on the contents of an X word having bits X i and a Y word having bits Y i to generate a result word having bits Z i , where i=0 to N-1, where Z 0 is the least significant bit of one of said sub-words and Z N-1 is the most significant bit of one of said sub-words, said apparatus comprising: means for partitioning said X, Y and result words into a plurality of sub-words, there being one sub-word of said Y and result words corresponding to each sub-word of said X word; means, responsive to a first instruction, for generating the sum of each X sub-word and the corresponding Y sub-word, the result thereof determining said corresponding sub-word of said result word; and means, responsive to a second instruction, for generating the difference of each sub-word in said X word and the corresponding sub-word in said Y word, the result thereof determining said corresponding sub-word of said result word; and means, responsive to a third instruction, for generating the difference divided by two of each sub-word in said X word and the corresponding sub-word in said Y word, the result thereof determining said corresponding sub-word of said result word.
Claim 16
Independent Claim
83 words
An apparatus for operating on the contents of an X word having bits X i and a Y word having bits Y i to generate a result word having bits Z i , where i=0 to N-1, where Z 0 is the least significant bit and Z N-1 is the most significant bit, said apparatus comprising: means, responsive to an average instruction, for generating the sum of said X and Y words; and means for shifting said sum to generate said Z word.
Claim 17
Independent Claim
83 words
An apparatus for operating on the contents of an X word having bits X i and a Y word having bits Y i to generate a result word having bits Z i , where i=0 to N-1, where Z 0 is the least significant bit and Z N-1 is the most significant bit, said apparatus comprising: means, responsive to an average instruction, for generating the sum of said X and Y words; and means for shifting said sum to generate said Z word.
Claim 18
Dependent Claim
137 words
The apparatus of claim 13 wherein said apparatus comprises a plurality of adding stages connected in series, each said adding stage comprising means for operating on adding one or more bits from said X word to corresponding bits derived from said Y word, and wherein said adding stages generate N result bits, S i , for i=0 to N-1, S i being derived from operations on X i , and a carry out bit C N-1 , and wherein said apparatus further comprises N multiplexing means, each said multiplexing means generating a signal indicative of one of said result bits, there being one said multiplexing means for each said result bit Z p , for p=0 to N-1, said multiplexing means corresponding to Z p connecting S p to Z p in response to said average instruction.
Claim 19
Dependent Claim
35 words
The apparatus of claim 14 wherein said multiplexing means corresponding to Z p connects Z p to S p+1 in response to said average instruction for p=0 to N-2 and to C N-1 if p=N-1.
Claim 20
Dependent Claim
29 words
The apparatus of claim 15 wherein said multiplexing means corresponding to Z p further comprises means to connect Z p to (S p+1 OR S p ) if p=0.
Claim 21
Dependent Claim
35 words
The apparatus of claim 13 further comprising means, responsive to a difference instruction, for generating the difference divided by two of said X word and said Y word, the result thereof determining said result word.
Claim 22
Independent Claim
104 words
An apparatus for operating on the contents of an X word having bits X i and a Y word having bits Y i to generate a result word having bits Z i , where i=0 to N-1, where Z 0 is the least significant bit and Z N-1 is the most significant bit, said apparatus comprising: means, responsive to an average instruction, for generating the sum of said X and Y words; and means for shifting said sum to generate said Z word, wherein said Z word is rounded to the next highest odd integer if said shift resulted in a round off error.
Claim 23
Independent Claim
104 words
An apparatus for operating on the contents of an X word having bits X i and a Y word having bits Y i to generate a result word having bits Z i , where i=0 to N-1, where Z 0 is the least significant bit and Z N-1 is the most significant bit, said apparatus comprising: means, responsive to an average instruction, for generating the sum of said X and Y words; and means for shifting said sum to generate said Z word, wherein said Z word is rounded to the next highest odd integer if said shift resulted in a round off error.
References Cited (Backward Citations)
US3987291A
Cited
US4137568A
Cited
US4707800A
Cited
US4789953A
Cited
US4768160A
Cited
US4914617A
Cited
US5047975A
Cited
US5189636A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-03-15 | 2002-09-14 | 2003-03-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-03-15 | 2006-09-14 | 2007-03-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-03-15 | 2010-09-14 | 2011-03-16 | $7700.00 | Window Closed / Lapsed |