US4538237A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for calculating the residue of a binary number
Assignee: Bull HN Information Systems Inc
•
Filing: 1983-01-18
•
Granted: 1985-08-27
•
Expires: 2003-01-18
Abstract
Abstract Method and apparatus for calculating the residue of a binary number of "n" bits with respect to a given check base m where m=2 b -1. The binary number is partitioned into segments, each of b bits starting with the least significant bit. If n is not an even multiple of b, higher order bit positions of the segment containing the most significant bit of the number are filled with logical zeros. The segments are applied to levels of carry save adders to reduce the segments of the binary number to a single sum segment of b bits and a single rotated carry segment of b bits where a rotated carry segment is a carry segment produced by a carry save adder, the most significant bit of which is rotated so that it becomes the least significant bit of the rotated carry segment. Carry segments produced by carry save adders of one level are converted to rotated carry segments before being applied to a carry save adder of a lower level carry save adder. The single sum segment and single rotated carry segment produced by the lowest level carry save adder are applied to a 1's complement full adder. The b bit output of the 1's complement full adder is the residue of the binary number with respect to the check base (2 b -1).
Inventors
- 👤 Joseph C. Circello
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 22:32
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/727
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
142 words
Apparatus for calculating the residue of a binary number with respect to a check base, said binary number being partitioned into a plurality of equal sized segments, with each segment including b contiguous bits where b is an integer greater than one, comprising: carry save adder means for adding the segments of the binary number and for reducing said segments to a single sum segment and a single rotated carry segment the single rotated carry segment being a carry segment wherein each bit position of the carry segment is increased in its bit significance by one, and further wherein the most significant bit is rotated to the least significant bit position; and one's complement full adder means for adding said single sum segment and single rotated carry segment to produce the residue of said binary number with respect to said check base.
Claim 2
Dependent Claim
142 words
Apparatus for calculating the residue of a binary number with respect to a check base, said binary number being partitioned into a plurality of equal sized segments, with each segment including b contiguous bits where b is an integer greater than one, comprising: carry save adder means for adding the segments of the binary number and for reducing said segments to a single sum segment and a single rotated carry segment the single rotated carry segment being a carry segment wherein each bit position of the carry segment is increased in its bit significance by one, and further wherein the most significant bit is rotated to the least significant bit position; and one's complement full adder means for adding said single sum segment and single rotated carry segment to produce the residue of said binary number with respect to said check base.
Claim 3
Dependent Claim
17 words
Apparatus as defined in claim 1 in which the check base equals the quantity 2 b -1.
Claim 4
Dependent Claim
9 words
Apparatus as defined in claim 2 in which b=5.
Claim 5
Dependent Claim
21 words
Apparatus as defined in claim 3 in which the number of bits in the binary number is a multiple of 9.
Claim 6
Dependent Claim
234 words
Apparatus for calculating the residue of a binary number of "n" bits with respect to a check base "m", said binary number being partitioned into a segment of "b" contiguous bits beginning with the least significant of the binary number, higher order bit positions of the segment containing the most significant bit of the binary number, being filled by logical 0's, where m=2 b -1 and m, n and b are integers greater than 1, comprising: levels of carry save adders for adding the bits of the segments of the binary number and for producing a sum segment and a carry segment, the lowest level of the carry save adders consisting of a single carry save adder, means for rotating the bits of each carry segment produced by each carry save adder so that the most significant bit of each carry segment becomes the least significant bit of its corresponding rotated carry segment; circuit means for applying the segments of the binary number and the sum and the rotated carry segments to carry save adders to reduce them to a single sum segment and a single rotated carry segment produced by the lowest carry save adder; a one's complement full adder for producing the residue of b bits of the binary number; and circuit means for applying the sum and rotated carry segments of the lowest level carry save adder to the full adder.
Claim 7
Dependent Claim
234 words
Apparatus for calculating the residue of a binary number of "n" bits with respect to a check base "m", said binary number being partitioned into a segment of "b" contiguous bits beginning with the least significant of the binary number, higher order bit positions of the segment containing the most significant bit of the binary number, being filled by logical 0's, where m=2 b -1 and m, n and b are integers greater than 1, comprising: levels of carry save adders for adding the bits of the segments of the binary number and for producing a sum segment and a carry segment, the lowest level of the carry save adders consisting of a single carry save adder, means for rotating the bits of each carry segment produced by each carry save adder so that the most significant bit of each carry segment becomes the least significant bit of its corresponding rotated carry segment; circuit means for applying the segments of the binary number and the sum and the rotated carry segments to carry save adders to reduce them to a single sum segment and a single rotated carry segment produced by the lowest carry save adder; a one's complement full adder for producing the residue of b bits of the binary number; and circuit means for applying the sum and rotated carry segments of the lowest level carry save adder to the full adder.
Claim 8
Dependent Claim
8 words
The apparatus of claim 5 in which b=5.
Claim 9
Dependent Claim
13 words
The apparatus of claim 6 in which n equals a multiple of 9.
Claim 10
Dependent Claim
59 words
The apparatus of claim 7 in which the means for rotating the bits of each carry segment includes a bus having conductors for each bit of each carry segment and in which the conductor of the most significant bit of the carry segment is adapted to be connected to the least significant input terminal of a lower level adder.
Claim 11
Independent Claim
214 words
The method of calculating the residue of a binary number with respect to a given check base, comprising the steps of: partitioning the binary number into segments, each segment consisting of a plurality of contiguous bits beginning with the least significant bit of the binary number; filling higher order bit positions of the segment containing the most significant bit of the binary number with logical zeroes; applying the segments into which the binary number is partitioned to a plurality of carry save adders each carry save adder producing a sum segment and a carry segment; rotating the bits of the carry segments to form rotated carry segments in which the most significant bit of each carry segment becomes the least significant bit of the corresponding rotated carry segment; applying any segments into which the binary number is partitioned not previously applied to a carry save adder, sum segments and rotated carry segments to additional carry save adders until all the segments into which the binary number is partitioned and all rotated carry and sum segments are reduced to a single sum segment and a single rotated carry segment; and adding the single sum segment and the single rotated carry segment in a one's complement full adder to produce the residue of said binary number.
Claim 12
Independent Claim
214 words
The method of calculating the residue of a binary number with respect to a given check base, comprising the steps of: partitioning the binary number into segments, each segment consisting of a plurality of contiguous bits beginning with the least significant bit of the binary number; filling higher order bit positions of the segment containing the most significant bit of the binary number with logical zeroes; applying the segments into which the binary number is partitioned to a plurality of carry save adders each carry save adder producing a sum segment and a carry segment; rotating the bits of the carry segments to form rotated carry segments in which the most significant bit of each carry segment becomes the least significant bit of the corresponding rotated carry segment; applying any segments into which the binary number is partitioned not previously applied to a carry save adder, sum segments and rotated carry segments to additional carry save adders until all the segments into which the binary number is partitioned and all rotated carry and sum segments are reduced to a single sum segment and a single rotated carry segment; and adding the single sum segment and the single rotated carry segment in a one's complement full adder to produce the residue of said binary number.
Claim 13
Dependent Claim
14 words
The method of claim 9 in which b is an integer greater than 2.
Claim 14
Independent Claim
15 words
The method ofclaim 10 in which the check base equals the quantity 2 b -1.
Claim 15
Dependent Claim
10 words
The method of claim 11 in which b equals 5.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1988-08-26 | 1989-02-25 | 1989-08-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1992-08-26 | 1993-02-25 | 1993-08-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1996-08-26 | 1997-02-25 | 1997-08-27 | $7700.00 | Window Closed / Lapsed |