Residue addition overflow detection processor
AssigneeThe Boeing Company
InventorTheodore L. Houk
Life of this patent
Estimating the term…
Abstract
A residue addition overflow detection processor detects overflow resulting from the addition of two residue numbers by extending the base of the two numbers, adding the two extended numbers to each other, and converting the resultant sum into mixed base representation. The digits of the mixed base representation are processed to produce signals indicating whether overflow has occurred. Delay circuits maintain the synchronism of the processing. The detection processor can be used in conjunction with optical information processing systems.
Claims33
A residue addition overflow detection processor which adds a first non-redundant residue input number and a second non-redundant residue input number, said overflow detection processor comprising:
- a first base extension circuit which receives said first non-redundant residue input number and which generates a first redundant residue digit;
- a second base extension circuit, in parallel to said first base extension circuit, which receives said second non-redundant residue input number and which generates a second redundant residue digit;
- a first adder which receives said first non-redundant residue input number and said first redundant residue digit as a first operand, and receives said second non-redundant residue input number and said second redundant residue digit as a second operand, said first adder adding said first operand to said second operand using modular addition to produce a first sum in residue representation;
- a residue to mixed base converter which receives said first sum, converts said first sum into mixed base representation, and generates at least one mixed base digit corresponding to said mixed base representation;
- and
- a validity determination circuit which receives said at least one mixed base digit and transmits at least one signal indicating whether overflow has occurred in addition of said first non-redundant residue input number to said second non-redundant residue input number.
A residue addition overflow detection processor which adds a first redundant residue input number and a second redundant residue input number, said overflow detection processor comprising:
- an adder which receives said first redundant residue input number as a first operand and said second redundant residue input number as a second operand, said adder adding said first operand to said second operand using modular addition to produce a sum in residue representation;
- a residue to mixed base converter which receives said sum, converts said sum into mixed base representation, and transmits a value of a mixed base digit corresponding to said mixed base representation;
- a validity determination circuit which receives said value of said mixed base digit and transmits at least one signal, indicating that overflow has occurred in addition of said first redundant residue input number to said second redundant residue input number, when said value of said mixed base digit is either equal to zero or equal to the value of a highest order modulus minus one.
A method of detecting overflow resulting from adding a first non-redundant residue input number to a second non-redundant residue input number, comprising the steps of:
- receiving said first non-redundant residue input number;
- receiving said second non-redundant residue input number;
- generating a first redundant residue digit corresponding to said first non-redundant residue input number;
- delaying said first non-redundant residue input number to produce a delayed first non-redundant residue input number;
- generating a second redundant residue digit corresponding to said second non-redundant residue input number;
- delaying said second non-redundant residue input number to produce a delayed second non-redundant residue input number;
- adding said delayed first non-redundant residue input number and said first redundant residue digit as a first operand to said delayed second non-redundant residue input number and said second redundant residue digit as a second operand to produce a sum;
- converting said sum into mixed base representation in a form of at least one mixed base digit;
- generating at least one signal based on at least one value of said at least one mixed base digit, said at least one signal indicating whether overflow resulted from addition of said first non-redundant residue input number to said second non-redundant residue input number;
- and
- delaying a transmission of said sum in order to transmit said sum simultaneously with transmission of said at least one signal.
A method of detecting overflow resulting from adding a first redundant residue input number to a second redundant residue input number, comprising the steps of:
- receiving said first redundant residue input number;
- receiving said second redundant residue input number;
- adding said first redundant residue input number to said second redundant residue input number to produce a sum;
- converting said sum into mixed base representation in a form of at least one mixed base digit;
- generating at least one signal based on at least one value of said at least one mixed base digit, said at least one signal indicating whether overflow resulted from addition of said first redundant residue input number to said second redundant residue input number;
- and
- delaying a transmission of said sum in order to transmit said sum simultaneously with a transmission of said at least one signal.
A residue addition overflow detection processor which adds a first non-redundant residue input number and a second redundant residue input number, said overflow detection processor comprising:
- a first base extension circuit which receives said first non-redundant residue input number and which generates a first redundant residue digit;
- a first adder which receives said first non-redundant residue input number and said first redundant residue digit as a first operand, and receives said second redundant residue input number as a second operand, said first adder adding said first operand to said second operand using modular addition to produce a first sum in residue representation;
- a residue to mixed base converter which receives said first sum, converts said first sum into mixed base representation, and generates at least one mixed base digit corresponding to said mixed base representation;
- and
- a validity determination circuit which receives said at least one mixed base digit and transmits at least one signal indicating whether overflow has occurred in addition of said first non-redundant residue input number to said second redundant residue input number.
A method of detecting overflow resulting from adding a first non-redundant residue input number to a second redundant residue input number, comprising the steps of:
- receiving said first non-redundant residue input number;
- receiving said second redundant residue input number;
- generating a first redundant residue digit corresponding to said first non-redundant residue input number;
- delaying said first non-redundant residue input number to produce a delayed first non-redundant residue input number;
- delaying said second redundant residue input member to produce a delayed second redundant residue input number;
- adding said delayed first non-redundant residue input number and said first redundant residue digit as a first operand to said delayed second redundant residue input number as a second operand to produce a sum;
- converting said sum into mixed base representation in a form of at least one mixed base digit;
- generating at least one signal based on at least one value of said at least one mixed base digit, said at least one signal indicating whether overflow resulted from addition of said first non-redundant residue input number to said second redundant residue input number;
- and
- delaying a transmission of said sum in order to transmit said sum simultaneously with transmission of said at least one signal.
Dependencies are inferred from the claim text.