Method and apparatus for pipelined detection of overflow in residue arithmetic multiplication

An overflow detection processor which detects whether or not multiplicative overflow has occurred during multiplication of a first operand and a second operand, said first and second operands being in a non-redundant residue number system representation, said overflow detection processor comprising:

• a first mixed base converter connected for receiving said first operand and for converting said first operand into a first set of mixed base digits and generating a first redundant residue digit corresponding to said first operand;
• a second mixed base converter connected for receiving said second operand and converting said second operand into a second set of mixed base digits and generating a second redundant residue digit corresponding to said second operand;
• a multiplier connected to receive said first and second operands and said first and second redundant residue digits and multiplying said first operand and said first redundant residue digit by said second operand and said second redundant residue digit to produce a product;
• a most significant digits detector connected for receiving said first and second sets of mixed base digits and calculating a first magnitude measure of said first set of mixed base digits and a second magnitude measure of said second set of mixed base digits and generating first signals indicative of a relationship between said first magnitude measure and said second magnitude measure;
• a third mixed base converter connected to said multiplier for receiving said product and converting said product into a third set of mixed base digits, said third mixed base converter operating independently of results of said most significant digits detector;
• and
• a logic circuit connected for receiving said first signals and second signals based on said third set of mixed base digits and generating a validity signal indicative of whether or not multiplicative overflow has occurred.

A method of generating a validity optical signal, comprising the steps of:

• (a) receiving first optical signals form a first plurality of optical transmission paths, said optical first signals representing a first operand in residue representation;
• (b) receiving second optical signals from a second plurality of optical transmission paths, said second optical signals representing a second operand in residue representation;
• (c) converting said first optical signals representing said first operand in residue representation into third optical signals representative of said first operand in mixed base representation;
• (d) converting said second optical signals representing said second operand in residue representation into fourth optical signals representative of said second operand in mixed base representation;
• (e) multiplying said first optical signals and said second optical signals to produce product optical signals;
• (f) generating a most significant digits optical signal indicative of whether or not a first magnitude measure associated with said third optical signals is greater than a second magnitude measure associated with said fourth optical signals;
• (g) generating fifth optical signals independently of results of step (f), said fifth optical signals corresponding to a mixed base representation of said product optical signals;
• (h) time delaying at least one of said most significant digits optical signal and said fifth optical signals such that said most significant digits optical signal and said fifth optical signals arrive at an optical logic circuit at the same time;
• and
• (i) subsequent to steps (a) through (h), transmitting, from said optical logic circuit, a validity optical signal indicating whether or not multiplicative overflow has occurred based on said most significant digits optical signal and said fifth optical signals.

A method of generating a validity optical signal, comprising the steps of:

• (a) receiving first optical signals from a first plurality of optical transmission paths, said first optical signals representing a first operand in residue representation;
• (b) receiving second optical signals from a second plurality of optical transmission paths, said second optical signals representing a second operand in residue representation;
• (c) converting said first optical signals representing said first operand in residue representation into third optical signals representative of said first operand in mixed base representation and generating first redundant residue digit optical signals corresponding to a redundant residue digit associated with said first operand;
• (d) converting said second optical signals representing said second operand in residue representation into fourth optical signals representative of said second operand in mixed base representation and generating second redundant residue digit optical signals corresponding to a redundant residue digit associated with said second operand;
• (e) multiplying said first optical signals and said first redundant residue digit optical signals and said second optical signals and said second redundant residue digit optical signals to produce product optical signals;
• (f) generating a most significant digits optical signal indicative of whether or not a first magnitude measure associated with said third optical signals is greater than a second magnitude measure associated with said fourth optical signals;
• (g) generating fifth optical signals independently of results of step (f), said fifth optical signals corresponding to a mixed base representation of said product optical signals;
• time delaying at least one of said most significant digits optical signal and said fifth optical signals such that said most significant digits optical signal and said fifth optical signals arrive at an optical logic circuit at the same time;
• and
• (i) subsequent to steps (a) through (h), transmitting, from said optical logic circuit, a validity optical signal indicating whether or not multiplicative overflow has occurred based on said most significant digits optical signal and said fifth optical signals.