US4722067A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for implementing modulo arithmetic calculations
Assignee: NXP USA Inc
•
Filing: 1985-03-25
•
Granted: 1988-01-26
•
Expires: 2005-03-25
Abstract
Abstract A modulo arithmetic unit and method for providing a sum of first and second numbers is provided. In one form, a first adder calculates a first sum which is equal to the arithmetic sum of the first and second numbers. A second adder is provided for adding the first number to an offset value equal to (2 X -M), where X defines the number of bits of the number system used, M is a predetermined modulus and X and M are integers. A third adder operates in parallel with the first adder to calculate the sum of the output value of the second adder and the second operand to provide a second output sum and a carry output bit. In another form, only two adders are utilized wherein the first adder calculates a first output sum of the first and second numbers, and the second adder calculates the sum of the first output sum and the offset value. Both illustrated forms utilize a multiplexer which outputs one of the two calculated output sums depending upon whether a wraparound of an upper modulus boundary occurred.
Inventors
- 👤 Tim A. Williams
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 07:21
CPC Classifications
G; G06; G06F; G06F5/00; G06F5/06; G06F5/10; G06F7/00; G06F7/60; G06F7/72; G06F9/00; G06F9/06; G06F9/30; G06F9/34; G06F9/355; G06F9/3552; G06F2205/00; G06F2205/10; G06F2205/106
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
183 words
A modulo M arithmetic unit for providing a sum of first and second numbers, said numbers being integers of a number system having X bits and being within a predetermined range having an upper boundary and a lower boundary of zero relative to M, where M is a selected one of a plurality of predetermined modulae and M and X are integers, comprising: first adder means for selectively receiving and adding the first and second numbers to provide a first output sum; second adder means for selectively receiving and adding the first number and an offset value, said offset value being equal to (2 X -M), and for providing an intermediate modulo value; third adder means for selectively receiving and adding the intermediate modulo value and the second number to provide a second output sum and an output carry bit; and logic means for providing, in response to a logic state of the output carry bit, a selected one of the first and second output sums as a sum of the first and second numbers which has a value within the predetermined range.
Claim 2
Dependent Claim
183 words
A modulo M arithmetic unit for providing a sum of first and second numbers, said numbers being integers of a number system having X bits and being within a predetermined range having an upper boundary and a lower boundary of zero relative to M, where M is a selected one of a plurality of predetermined modulae and M and X are integers, comprising: first adder means for selectively receiving and adding the first and second numbers to provide a first output sum; second adder means for selectively receiving and adding the first number and an offset value, said offset value being equal to (2 X -M), and for providing an intermediate modulo value; third adder means for selectively receiving and adding the intermediate modulo value and the second number to provide a second output sum and an output carry bit; and logic means for providing, in response to a logic state of the output carry bit, a selected one of the first and second output sums as a sum of the first and second numbers which has a value within the predetermined range.
Claim 3
Dependent Claim
55 words
The modulo M arithmetic unit of claim 1 further comprising: first storage means coupled to the second adder means, for storing the first number; second storage means coupled to the second adder means, for storing the offset value; and third storage means coupled to the first and third adder means, for storing the second number.
Claim 4
Dependent Claim
16 words
The modulo M arithmetic unit of claim 1 wherein the logic means is a multiplexer circuit.
Claim 5
Dependent Claim
174 words
In combination in a system for adding first and second numbers in a predetermined modulus, said numbers being integers of a number system having X bits and being within a predetermined range having an upper boundary and a lower boundary of zero relative to M, where M is a selected one of a plurality of predetermined modulae, M and X being integers, a method comprising the steps of: providing first means for selectively adding the first and second numbers to provide a first output sum; providing second means for selectively adding the first number to an offset value, the offset value being equal to (2 X -M), to provide an intermediate modulo value; providing third means for selectively adding the intermediate value and the second number to provide a second output sum and an output carry signal; and providing fourth means for selecting, in response to the output carry signal, one of the first or second output sums as a sum of the first and second numbers having a value within the predetermined range.
Claim 6
Dependent Claim
174 words
In combination in a system for adding first and second numbers in a predetermined modulus, said numbers being integers of a number system having X bits and being within a predetermined range having an upper boundary and a lower boundary of zero relative to M, where M is a selected one of a plurality of predetermined modulae, M and X being integers, a method comprising the steps of: providing first means for selectively adding the first and second numbers to provide a first output sum; providing second means for selectively adding the first number to an offset value, the offset value being equal to (2 X -M), to provide an intermediate modulo value; providing third means for selectively adding the intermediate value and the second number to provide a second output sum and an output carry signal; and providing fourth means for selecting, in response to the output carry signal, one of the first or second output sums as a sum of the first and second numbers having a value within the predetermined range.
Claim 7
Dependent Claim
165 words
A modulo M arithmetic unit for providing a sum of first and second numbers, said numbers being integers of a number system having X bits and being within a predetermined range having an upper boundary and a lower boundary of zero relative to M, where M is a selected one of a plurality of predetermined modulae and M and X are integers, comprising: first adder means for selectively receiving and adding the first and second numbers to provide a first output sum; second adder means for selectively receiving and adding the first output sum and an offset value, said offset value being equal to (2 X -M), and providing a second output sum and an output carry signal; and logic means coupled to the first and second adder means, for providing, in response to the output carry signal, a selected one of the first and second output sums as a sum of the first and second numbers which has a value within the predetermined range.
Claim 8
Dependent Claim
165 words
A modulo M arithmetic unit for providing a sum of first and second numbers, said numbers being integers of a number system having X bits and being within a predetermined range having an upper boundary and a lower boundary of zero relative to M, where M is a selected one of a plurality of predetermined modulae and M and X are integers, comprising: first adder means for selectively receiving and adding the first and second numbers to provide a first output sum; second adder means for selectively receiving and adding the first output sum and an offset value, said offset value being equal to (2 X -M), and providing a second output sum and an output carry signal; and logic means coupled to the first and second adder means, for providing, in response to the output carry signal, a selected one of the first and second output sums as a sum of the first and second numbers which has a value within the predetermined range.
Claim 9
Dependent Claim
53 words
The modulo M arithmetic unit of claim 5 further comprising: first storage means coupled to the first adder means, for storing the first number; second storage means coupled to the first adder means, for storing the second number; and third storage means coupled to the second adder means, for storing the offset value.
Claim 10
Dependent Claim
15 words
The modulo arithmetic unit of claim 5 wherein the logic means is a multiplexer circuit.
Claim 11
Dependent Claim
163 words
In combination in a system for adding first and second numbers in a predetermined modulus, said numbers being integers of a number system having X bits and being within a predetermined range having an upper boundary and a lower boundary of zero relative to M, where M is a selected one of a plurality of predetermined modulae, M and X being integers, a method comprising the steps of: providing first means for selectively adding the first number and an offset value equal to (2 X -M) to provide a first output sum; providing second means for selectively adding the first output sum to an offset value, the offset value being equal to (2 X -M, to provide a second output sum and an output carry signal; and providing third means which, in response to the output carry signal, select one of the first and second output sums as a sum of the first and second numbers having a value within the predetermined range.
Claim 12
Dependent Claim
163 words
In combination in a system for adding first and second numbers in a predetermined modulus, said numbers being integers of a number system having X bits and being within a predetermined range having an upper boundary and a lower boundary of zero relative to M, where M is a selected one of a plurality of predetermined modulae, M and X being integers, a method comprising the steps of: providing first means for selectively adding the first number and an offset value equal to (2 X -M) to provide a first output sum; providing second means for selectively adding the first output sum to an offset value, the offset value being equal to (2 X -M, to provide a second output sum and an output carry signal; and providing third means which, in response to the output carry signal, select one of the first and second output sums as a sum of the first and second numbers having a value within the predetermined range.
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) | 1991-01-25 | 1991-07-27 | 1992-01-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1995-01-25 | 1995-07-27 | 1996-01-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1999-01-25 | 1999-07-27 | 2000-01-26 | $7700.00 | Window Closed / Lapsed |