Arithmetic processor using redundant signed digit arithmetic

Claim 2

An arithmetic processor which performs addition or subtraction of two redundant signed-digit numbers X and Y of radix r having N digits denoted by single digits x i and y i , where i is an index which assumes integer values ranging from 1 to N to denote digits in descending order, said arithmetic processor for each order comprising: (a) means for receiving a control signal and a single digit, and in response to the value of said control signal, producing an output operand by either inverting the sign of said single digit, leaving said single digit unchanged, or replacing said single digit operand with 0; (b) a first arithmetic means for receiving said output operand and for receiving a second single digit, and determining therefrom, in the case of addition an intermediate sum and an intermediate carry, or, in the case of subtraction, determining therefrom an intermediate difference and an intermediate borrow, said intermediate carry or borrow being output by said first arithmetic means for utilization in the processing of the next higher order digits; and (c) a second arithmetic means for determining the final sum by combining an intermediate carry obtained from processing the digits of the next lower order and said intermediate sum, or in the case of subtraction, determining the final difference by combining an intermediate borrow obtained from processing the digits of the next lower order and said intermediate difference; whereby said arithmetic processor performs addition or subtraction of said two redundant signed-digit numbers X and Y in a manner which eliminates carry-propagation.

Claim 3

An arithmetic processor which performs addition or subtraction of two redundant signed-digit numbers X and Y of radix r having N digits denoted by single digits x i and y i , where i is an index which assumes integer values ranging from 1 to N to denote digits in descending order, said arithmetic processor for each order comprising: (a) first means for receiving a control signal and a single digit, and in response to the value of said control signal, producing an output operand by either inverting the sign of said single digit, leaving said single digit unchanged, or replacing said single digit with 0; (b) second means for receiving said output operand from said first means and for receiving a second single-digit and in the case of addition, determining therefrom, an intermediate carry or, in the case of subtraction, determining therefrom an intermediate borrow, said intermediate carry or borrow being output by said second means for utilization in the processing of the next higher order digits; and (c) third means for receiving said output operand from said first means and for receiving said second single digit, determining therefrom an intermediate sum, or in the case of subtraction, an intermediate difference, and combining the intermediate carry, or in the case of subtraction, the intermediate borrow obtained from the processing of digits of the next lower order with said intermediate sum or difference respectively to determine a final sum or difference; whereby said arithmetic processor performs addition or subtraction of said two redundant signed-digit numbers X and Y in a manner which eliminates carry-propagation.

Claim 4

An arithmetic processor which performs addition or subtraction of two redundant signed-digit numbers X and Y of radix r having N digits denoted by single digits x i and y i , where i is an index which assumes integer values ranging from 1 to N to denote digits in descending order, said arithmetic processor for each order comprising: (a) first means for receiving a control signal and a single digit, and in response to the value of said control signal, producing an output operand by either inverting the sign of said single digit, leaving said single digit unchanged, or replacing said single digit with 0; (b) second means for receiving said output operand from said first means and for receiving a second single-digit and in the case of addition, determining therefrom, an intermediate carry or, in the case of subtraction, determining therefrom an intermediate borrow, said intermediate carry or borrow being output by said second means for utilization in the processing of the next higher order digits; and (c) third means for receiving said output operand from said first means and for receiving said second single digit, determining therefrom an intermediate sum, or in the case of subtraction, an intermediate difference, and combining the intermediate carry, or in the case of subtraction, the intermediate borrow obtained from the processing of digits of the next lower order with said intermediate sum or difference respectively to determine a final sum or difference; whereby said arithmetic processor performs addition or subtraction of said two redundant signed-digit numbers X and Y in a manner which eliminates carry-propagation.

Claim 5

An arithmetic processor in accordance with claim 2 wherein said first, second and third means are incorporated into each of a plurality of redundant arithmetic cells connected in an array, said array performing addition or subtraction operations on said single digits of said redundant signed-digit numbers X and Y to obtain a sum or difference.

Claim 6

An arithmetic processor which performs addition or subtraction of two redundant signed-digit numbers X and Y of radix r having N digits denoted by single digits x i and y i , where i is an index which assumes integer values ranging from 1 to N to denote digits in descending order, said arithmetic processor for each order comprising: (a) means for receiving a control signal and a single digit, and in response to the value of said control signal, producing a first output operand by either inverting the sign of said single digit or leaving said single digit unchanged; (b) second means for receiving a control signal and a second single digit, and in response to the value of said control signal, producing a second output operand by either leaving said second single digit unchanged, or replacing said second single digit with 0; (c) third means for receiving said first and second output operands, and in the case of addition, determining therefrom an intermediate carry, or in the case of subtraction, determining therefrom an intermediate borrow, said intermediate carry or intermediate borrow being output by said third means for utilization in the processing of the next higher order digits; (d) fourth means for receiving said first and second output operands, and, in the case of addition determining therefrom an intermediate sum, or in the case of subtraction determining therefrom an intermediate difference; and (e) fifth means for receiving the intermediate sum or difference from said fourth means and an intermediate carry or borrow from the processing of the next lower order digits and respectively determining therefrom a final sum or difference in the form of a signed-digit number of radix r.

Claim 7

An arithmetic processor which performs addition or subtraction of two redundant signed-digit numbers X and Y of radix r having N digits denoted by single digits x i and y i , where i is an index which assumes integer values ranging from 1 to N to denote digits in descending order, said arithmetic processor for each order comprising: (a) means for receiving a control signal and a single digit, and in response to the value of said control signal, producing a first output operand by either inverting the sign of said single digit or leaving said single digit unchanged; (b) second means for receiving a control signal and a second single digit, and in response to the value of said control signal, producing a second output operand by either leaving said second single digit unchanged, or replacing said second single digit with 0; (c) third means for receiving said first and second output operands, and in the case of addition, determining therefrom an intermediate carry, or in the case of subtraction, determining therefrom an intermediate borrow, said intermediate carry or intermediate borrow being output by said third means for utilization in the processing of the next higher order digits; (d) fourth means for receiving said first and second output operands, and, in the case of addition determining therefrom an intermediate sum, or in the case of subtraction determining therefrom an intermediate difference; and (e) fifth means for receiving the intermediate sum or difference from said fourth means and an intermediate carry or borrow from the processing of the next lower order digits and respectively determining therefrom a final sum or difference in the form of a signed-digit number of radix r.

Claim 8

An arithmetic processor in accordance with claim 4 wherein said first, second, third, fourth and fifth means are incorporated into each of a plurality of redundant arithmetic cells connecting in an array, said array performing addition or subtraction operations on said single digits of said redundant signed digit numbers X and Y to obtain a sum or difference.

Claim 9

An arithmetic processor for performing internal addition or subtraction operations using signed-digit radix r arithmetic on an r-radix signed-digit number and an ordinary r-radix number, said arithmetic processor comprising: (a) first means for receiving a control signal and a digit of said ordinary r-radix number, and in response to the value of said control signal producing an output digit by either leaving said digit unchanged, replacing said digit with 0, or obtaining the logical inversion of said digit; (b) second means for receiving said output digit and for receiving a digit of the said redundant signed-digit number, and in the case of addition, determining therefrom an intermediate carry, or in the case of subtraction, determining therefrom an intermediate borrow, said intermediate carry or borrow being output by said second means for utilization in the processing of the next higher order digits; (c) third means for receiving said output digit and for receiving a digit of said redundant signed-digit number, and determining therefrom in the case of addition, an intermediate sum digit, or in the case of subtraction, determining therefrom an intermediate difference digit; and (d) fourth means for receiving said intermediate sum or difference digit and an intermediate carry or borrow from the processing of the next lower order digits, and combining said intermediate sum and carry digits, or in the case of subtraction, combining said intermediate difference and borrow digits to determine therefrom a final sum or difference digit in the form of a signed-digit of radix r.

Claim 10

An arithmetic processor for performing internal addition or subtraction operations using signed-digit radix r arithmetic on an r-radix signed-digit number and an ordinary r-radix number, said arithmetic processor comprising: (a) first means for receiving a control signal and a digit of said ordinary r-radix number, and in response to the value of said control signal producing an output digit by either leaving said digit unchanged, replacing said digit with 0, or obtaining the logical inversion of said digit; (b) second means for receiving said output digit and for receiving a digit of the said redundant signed-digit number, and in the case of addition, determining therefrom an intermediate carry, or in the case of subtraction, determining therefrom an intermediate borrow, said intermediate carry or borrow being output by said second means for utilization in the processing of the next higher order digits; (c) third means for receiving said output digit and for receiving a digit of said redundant signed-digit number, and determining therefrom in the case of addition, an intermediate sum digit, or in the case of subtraction, determining therefrom an intermediate difference digit; and (d) fourth means for receiving said intermediate sum or difference digit and an intermediate carry or borrow from the processing of the next lower order digits, and combining said intermediate sum and carry digits, or in the case of subtraction, combining said intermediate difference and borrow digits to determine therefrom a final sum or difference digit in the form of a signed-digit of radix r.

Claim 11

An arithmetic processor in accordance with claim 6 wherein the radix r=2.

Claim 12

An arithmetic processor in accordance with claim 6, wherein said first, second, third and fourth means are incorporated into each of a plurality of redundant arithmetic cells connecting in an array, said array performing addition or subtraction operations on said single digits of said r-radix signed-digit number and said ordinary r-radix number.

Claim 13

An arithmetic processor in accordance with claim 8, wherein the radix r=2.

Claim 14

An arithmetic processor in which a divider performs division in a plurality of stages, said divider having a quotient determining means for determining each digit of a quotient and partial remainder determining means for determining a partial remainder corresponding to each digit of the quotient, said partial remainder determining means for each digit comprising: (a) first means for receiving a digit of said quotient from said quotient determining means for use as a control signal, and for receiving a digit of an r-radix divisor, and determining therefrom an output digit, depending upon the value of said control signal; (b) second means for receiving a digit of the partial remainder expressed as a signed-digit number of radix r derived from a higher stage operation and said output digit, and determining therefrom an intermediate carry; (c) third means for receiving a digit of the partial remainder expressed as a signed-digit number of radix r derived from a higher stage operation and said output digit, and determining therefrom an intermediate sum; and (d) fourth means which combines said intermediate sum with an intermediate carry from a lower order arithmetic operation to determine therefrom one digit of said partial remainder as a signed-digit number of radix r.

Claim 15

An arithmetic processor in which a divider performs division in a plurality of stages, said divider having a quotient determining means for determining each digit of a quotient and partial remainder determining means for determining a partial remainder corresponding to each digit of the quotient, said partial remainder determining means for each digit comprising: (a) first means for receiving a digit of said quotient from said quotient determining means for use as a control signal, and for receiving a digit of an r-radix divisor, and determining therefrom an output digit, depending upon the value of said control signal; (b) second means for receiving a digit of the partial remainder expressed as a signed-digit number of radix r derived from a higher stage operation and said output digit, and determining therefrom an intermediate carry; (c) third means for receiving a digit of the partial remainder expressed as a signed-digit number of radix r derived from a higher stage operation and said output digit, and determining therefrom an intermediate sum; and (d) fourth means which combines said intermediate sum with an intermediate carry from a lower order arithmetic operation to determine therefrom one digit of said partial remainder as a signed-digit number of radix r.

Claim 16

An arithmetic processor in accordance with claim 10, wherein the radix r=2.

Claim 17

An arithmetic processor in accordance with claim 10 wherein said quotient determining means and said partial remainder determining means are incorporated into each of a plurality of arithmetic cells connected in an array, said array performing division.

Claim 18

An arithmetic processor which performs addition or subtraction operations utilizing radix r signed-digit arithmetic on a signed-digit number of radix r and an ordinary number of radix r comprising: (a) first means for receiving a control signal and a digit of said signed-digit number of radix r, and in response to the value said control signal, producing a first output digit by either inverting the sign of said single digit or leaving said single digit unchanged; (b) second means for receiving a control signal and a digit of said ordinary number of radix r, and in response to the value said control signal, producing a second output digit by either leaving said digit of said ordinary number unchanged, or replacing said digit of said ordinary number with 0; (c) third means for receiving said first and second output digits, and for the case of addition determining therefrom an intermediate carry or for the case of subtraction determining therefrom an intermediate borrow, said intermediate carry or borrow being output by said third means for utilization in the processing of the next higher order digits; (d) fourth means for receiving said first and second output digits, and in the case of addition determining therefrom an intermediate sum, or in the case of subtraction determining therefrom an intermediate difference; and (e) fifth means for receiving the intermediate sum or difference from said fourth means and an intermediate carry or borrow from the processing of the next lower order digits and respectively determining therefrom a final sum or difference in the form of a signed-digit of radix r.

Claim 19

An arithmetic processor which performs addition or subtraction operations utilizing radix r signed-digit arithmetic on a signed-digit number of radix r and an ordinary number of radix r comprising: (a) first means for receiving a control signal and a digit of said signed-digit number of radix r, and in response to the value said control signal, producing a first output digit by either inverting the sign of said single digit or leaving said single digit unchanged; (b) second means for receiving a control signal and a digit of said ordinary number of radix r, and in response to the value said control signal, producing a second output digit by either leaving said digit of said ordinary number unchanged, or replacing said digit of said ordinary number with 0; (c) third means for receiving said first and second output digits, and for the case of addition determining therefrom an intermediate carry or for the case of subtraction determining therefrom an intermediate borrow, said intermediate carry or borrow being output by said third means for utilization in the processing of the next higher order digits; (d) fourth means for receiving said first and second output digits, and in the case of addition determining therefrom an intermediate sum, or in the case of subtraction determining therefrom an intermediate difference; and (e) fifth means for receiving the intermediate sum or difference from said fourth means and an intermediate carry or borrow from the processing of the next lower order digits and respectively determining therefrom a final sum or difference in the form of a signed-digit of radix r.

Claim 20

An arithmetic processor in accordance with claim 13, wherein said first, second, third, fourth and fifth means are incorporated into each of a plurality of redundant arithmetic cells connecting in an array, said array performing addition or subtraction operations on said single digits of said redundant signed-digit number of radix r and said ordinary number of radix r.

Claim 21

An arithmetic processor in accordance with claim 14, wherein said radix r is radix 2.

Claim 22

An arithmetic processor of claim 13 in which a divider performs division in a plurality of stages, said divider having a quotient determining means for determining each digit of a quotient and partial remainder determining means for determining a partial remainder corresponding to each digit of the quotient, wherein said partial remainder determining means for each digit comprises: (a) first means for receiving a digit of said quotient from said quotient determining means for use as said control signal, and a digit of the partial remainder determined in the previous higher stage operation expressed as a signed-digit of radix r and determining therefrom an output digit, depending upon the value of the control signal, (b) second means for receiving a digit of said quotient from said quotient determining means for use as a control signal, and a digit of a divisor expressed as an ordinary number of radix r, producing therefrom a second output digit of radix r; (c) third means for receiving said first and second output digits and determining therefrom an intermediate carry or borrow; (d) fourth means for receiving said first and second output digits and determining therefrom an intermediate sum or difference; and (e) fifth means for combining said intermediate carry or borrow with said intermediate sum or difference respectively to form a digit of a partial remainder expressed as a signed- digit of radix r.

Claim 23

An arithmetic processor in accordance with claim 16, wherein said radix r is radix 2.

Claim 24

An arithmetic processor in accordance with claim 16, wherein said first, second, third, fourth and fifth means are incorporated in each of a plurality of partial remainder determining cells connected in an array, said array, in combination with said quotient determining means performing division operations.

Claim 25

An arithmetic processor in accordance with claim 16, wherein said quotient determining means includes said first means.

Claim 26

An arithmetic processor in accordance with claim 13, wherein said radix r is radix 2.