Patent EA-002183-B1 (EA)
Title: Apparatus for multiprecision integer arithmetic
Inventor: SABIN MICHAEL
IPC: G06F7/52
Filed: 1998-11-04
Abstract: 1. An apparatus for multiprecision integer arithmetic, for processing a first data signal, y, with a second data signal, x, comprising: a plurality of large integer units (LIU's), LIU{0}, LIU{1}, LIU{2}, ..., LIU{n-1}, where "n" is a total number of large integer units in the plurality of large integer units, with each large integer unit having: a multiplier with a first multiplier input, a second multiplier input, a high part-product output and a low part-product output; an adder with a first adder input, a second adder input, a third adder input, a fourth adder input, and an adder output, said third adder input connected to the multiplier for receiving the low part-product output; and an LIU register with an LIU register input and an LIU register output, said LIU register input connected to the adder to receive the adder output, said LIU register latching a value of the adder output prior to a clock pulse and transferring the value to said LIU register output after the clock pulse, said LIU register output partitioned into an LIU-register-high output and an LIU-register-low output, said LIU-register-high output containing two upper bits of said LIU register output, said LIU-register-low output containing all bits of said LIU register output except those in said LIU-register-high output, said LIU-register-high output connected to the fourth adder input, said LIU register also having an LIU-register-clear input for clearing said LIU register output to zero when said LIU-register-clear input is activated; a first logical OR gate, connected to the LIU register, for receiving the LIU register output and a carry-in signal, ci, said first logical OR gate for generating a carry-out signal, co, said carry-out signal, co, being activated responsive to one of any bit of the LIU register output being active and said carry-in signal, ci, being active; a second logical OR gate, connected to the LIU register, for receiving the LIU-register-high output and for generating an auxiliary-carry-out signal, ca, said auxiliary-carry-out signal, ca, being activated when either bit of the LIU-register-high output is active; the first data signal, y, being applied to the first multiplier input of each large integer unit of said plurality of large integer units; the second data signal, x, having a plurality of elements x{0}, x{1}, x{2}, ..., x{n-1}, with each element respectively connected to the second multiplier input of each large integer unit of said plurality of large integer units; each i th large integer unit LIU{i} of said plurality of large integer units, for i greater than zero, having the first adder input connected to the high part-product output of an {i-1}th large integer unit, LIU{i-1}; each i th large integer unit LIU{i}, for i greater than zero, having the LIU-register-low output connected to the second adder input of an {i-1}th large integer unit, LIU{i-1}; a first complementing gate, connected to the first adder input of a first large integer unit, LIU{0}, for complementing a third data signal, z, when a subtract signal is active; a second complementing gate, connected to the LIU-register-low output of the first large integer unit, LIU{0}, for complementing said LIU-register-low output when said subtract signal is active, said second complementing gate generating a fourth data signal, a; a latching register with a latching register input and a latching register output, said latching register input connected to the high part-product output of said nth large integer unit, LIU{n-1}, and said latching register output connected to the second adder input of said nth large integer unit, LIU{n-1}, for latching a value of an n th high part-product prior to a clock pulse and for feeding the value of the nth high part-product to the second adder input of said nth large integer unit after the clock pulse; said first large integer unit LIU{0} having a ci input connected to a logical 0 value; said second large integer unit LIU{1} having a ci input connected to a ca output of the first large integer unit LIU{0}; each i th large integer unit LIU{i} of said plurality of large integer units, for i greater than one, having a ci input connected to a co output of an {i-1}th large integer unit, LIU{i-1}, a co output of the n th large integer unit LIU{n-1} being a fifth data signal, the carry flow signal, cy; said latching register having a latching-register-clear signal and each LIU having an LIU-register-clear input, a plurality of LIU-register-clear inputs and said latching-register-clear signal being connected together to form a data signal, clr; and said latching register having a clock input and each LIU having a clock input, a plurality of clock inputs being connected together to form a clock signal, clk. 2. An apparatus for multiprecision integer arithmetic, for processing a first data signal, y, with a second data signal x, comprising: a plurality of large integer units (LIU's), LIU{0}, LIU{1}, LIU{2}, ..., LIU{n-1}, where "n" is a total number of large integer units in the plurality of large integer units, with each large integer unit having: a multiplier with a first multiplier input, a second multiplier input, a high part-product output and a low part-product output; an adder with a first adder input and a second adder input, said adder connected to the multiplier for receiving the low part-product output; and  an LIU register having a sum signal output, said LIU register connected to said adder; the first data signal, y, being applied to the first multiplier input of each large integer unit of said plurality of large integer units; the second data signal x, having a plurality of elements x{0}, x{1}, x{2}, ..., x{n-1}, with each element respectively connected to a second multiplier input of each large integer unit of said plurality of large integer units; each i th large integer unit LIU{i} of said plurality of large integer units, for i greater than zero, having the first adder input connected to the high part-product output of an {i-1} th large integer unit, LIU{i-1}; each i th large integer unit, LIU{i}, for i greater than zero, having the sum signal output connected to the second adder input of an {i-1}th large integer unit, LIU{i-1}; a complementing gate, connected to the first adder input of a first large integer unit, LIU{0}, for complementing a third data signal, z, when a subtract signal is active; and a latching register, connected to the high part-product output of said n th large integer unit, LIU{n-1}, and to the second adder input of said n th large integer unit, LIU{n-1}, for latching a value of the n th high part-product prior to a clock pulse and for feeding the value of the n th high part-product to the second adder input of said n th large integer unit after the clock pulse. 3. An apparatus for multiprecision integer arithmetic, for processing a first data signal, y, with a second data signal x, comprising: a large integer unit (LIU) having: a multiplier with a first multiplier input, a second multiplier input, a high part-product output and a low part-product output; an adder with a first adder input and a second adder input, said adder connected to the multiplier for receiving the low part-product output, said adder for outputting a first sum signal; and an LIU register connected to said adder for receiving the first sum signal and for outputting a second sum signal; the first data signal, y, being applied to the first multiplier input of said large integer unit; the second data signal x, being applied to the second multiplier input of said large integer unit; a complementing gate, connected to the first adder input of said large integer unit, for complementing a third data signal, z, when a subtract signal is active; and a latching register, connected to the high part-product output of said large integer unit, and to the second adder input of said large integer unit, for latching a value of the high part-product prior to a clock pulse and for feeding the value of the high part-product to the second adder input of said large integer unit after the clock pulse. 4. The apparatus as set forth in claim 3, said large integer unit further comprising: an OR gate, coupled to an output of said LIU register, for receiving upper bits of the second sum signal from said LIU register as a carry signal, said second OR gate outputting a logical OR of the carry signal as a carry flow signal. 5. The apparatus as set forth in claim 3 or 4, further comprising: a plurality of large integer units, LIU{0}, LIU{1}, LIU{2}, ..., LIU{n-1}, where "n" is a total number of large integer units in the plurality of large integer units; each i th large integer unit LIU{i} of said plurality of large integer units, for i greater than zero, having the first adder input connected to the high part-product output of an {i-1}th large integer unit, LIU{i-1}; and each i th large integer unit, LIU{i}, for i greater than zero, having the sum signal output connected to the second adder input of an {i-1}th large integer unit, LIU{i-1}. 6. An apparatus for multiprecision integer arithmetic, for processing a first data signal, x, with a second data signal, y, comprising: a plurality of large integer units (LIU's), with each large integer unit having: a first multiplier input, a second multiplier input, a high part-product output; a first adder input, a second adder input, and a sum signal output; the first data signal, y, being applied to the first multiplier input of each large integer unit of said plurality of large integer units; the second data signal, x, having a plurality of elements, with each element respectively connected to the second multiplier input of each large integer unit of said plurality of large integer units; each i th large integer unit, LIU{i}, of said plurality of large integer units, for i other than an initial large integer unit, having: the first adder input connected to the high part-product output of an {i-1}th large integer