Adder circuitry utilizing redundant signed digit operands

Claim 2

In an arithmetic processor which performs arithmetic operations on radix 2 signed-digit numbers each having N digits denoted by an order index which assumes integer values from 1 to N, said arithmetic processor having a plurality of adder cells each of which performs addition operations on an i-th digit x i of a signed-digit augend x and an i-th digit y i of a signed-digit addend y for a different value of the order index i by first determining an intermediate carry digit c i and an intermediate sum digit s i , and then determining the final sum digit z i by adding the intermediate sum s i to an intermediate carry c i-1 obtained from the adder cell operating on the next lower order digits, wherein each of said digits of said augend and addend are represented by two one-bit signals respectively representing the sign and magnitude of said digit, said adder cells each comprising: (a) first circuit means to which are supplied signals representative of said digits x i and y i , said first circuit means determining therefrom and providing as output a 1-bit signal p i whose value depends upon the binary states of said digits x i and y i ; (b) second circuit means to which are supplied at least two signals representative of said digits x i and y i , and a 1-bit signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as output a 1-bit signal u i representing the difference p i-1 -s i ; (c) third circuit means to which are supplied at least two signals representative of said digits x i and y i and said signal p i-1 , said third circuit means determining therefrom and providing as output a 1-bit signal v i representing the sum p i +c i ; and (d) fourth circuit means to which are supplied as input said signal u i and a signal v i-1 obtained from the third circuit means of the adder cell which operates on the next lower digits, said fourth circuit means determining therefrom and prodiving as output a 2-bit signal representing the sign and magnitude of the i-th digit of the sum of x and y expressed as a radix 2 signed-digit number.

Claim 3

The arithmetic processor in accordance with claim 1, wherein said first circuit means is supplied with a 1-bit signal x i s and a 1 -bit signal y i s which represent the sign of digits x i and y i respectively and determines therefrom a 1-bit signal p i whose value depends upon whether digits x i and y i are both non-negative, or whether at least one of said digits x i and y i is negative.

Claim 4

The arithmetic processor according to claim 2 wherein said second circuit means is supplied with two 1-bit signals x i a and y i a representing the magnitude of said digits x i and y i respectively and a 1-bit signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as an output a 1-bit signal u i representing the difference p i-1 -s i .

Claim 5

The arithmetic processor in accordance with claim 1, wherein said first circuit means is supplied with a 1-bit signal x i s and a 1-bit signal y i s which represent the sign of digits x i and y i respectively and determines therefrom a 1-bit signal p i whose value depends upon whether digits x i and y i are both non-positive or whether at least one of said digits x i and y i is positive.

Claim 6

The arithmetic processor according to claim 4 wherein said second circuit means is supplied with two 1-bit signals x i a and y i a representing the magnitude of said digits x i and y i respectively and a 1-bit signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as an output a 1-bit signal u i representing the difference p i-1 -s i .

Claim 7

The arithmetic processor in accordance with claim 1, wherein said first circuit means is supplied with a 1-bit signal x i s and a 1-bit signal y i s which represent the sign of digits x i and y i respectively and determines therefrom a 1-bit signal p i whose value depends upon whether the sum of the digits x i and y i is greater than or equal to zero or whether the sum of the digits x i and y i is less than zero.

Claim 8

The arithmetic processor according to claim 6 wherein said second circuit means is supplied with two 1-bit signals x i a and y i a representing the magnitude of said digits x i and y i respectively and a 1-bit signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as an output a 1-bit signal u i representing the difference p i-1 -s i .

Claim 9

The arithmetic processor according to claim 1 wherein said second circuit means is supplied with two 1-bit signals x i a and y i a representing the magnitude of said digits x i and y i respectively and a 1-bit signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as an output a 1-bit signal u i representing the difference p i-1 -s i .

Claim 10

In an arithmetic processor which performs arithmetic operations on radix 2 signed-digit numbers each having N digits denoted by an order index which assumes integer values from 1 to N, said arithmetic processor having a plurality of adder cells each of which performs addition operations on an i-th digit x i of a signed-digit augend x and an i-th digit y i of a signed-digit addend y for a different value of the order index i by first determining an intermediate carry digit c i and an intermediate sum digit s i , and then determining the final sum digit z i by adding the intermediate sum s i to an intermediate carry c i-1 obtained from the adder cell operating on the next lower order digits, wherein each of said digits of said augend and addend are represented by two one-bit signals respectively representing the sign and magnitude of said digit, said adder cells each comprising: (a) first circuit means to which are supplied as inputs a 1-bit signal x i s and a 1-bit signal y i s which represent the sign of digits x i and y i respectively, said first circuit means determining therefrom and providing as output a 1-bit signal p i whose value depends upon whether both x i and y i are non-negative, or whether at least one of said digits x i and y i is negative; (b) second circuit means to which are supplied as input a 1-bit signal x i a and a 1-bit signal y i a which represent the magnitude of said digits x i and y i respectively and a signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as output a 1-bit signal u i representing the difference p i-1 -s i ; (c) third circuit means to which are supplied input signals representing the digits x i and y i respectively and said signal p i-1 , said third circuit means determining therefrom and providing as output a 1-bit signal v i representing the sum p i +c i ; and (d) fourth circuit means to which are supplied as input said 1-bit signal u i and a 1-bit signal v i-1 obtained from the third circuit means of the adder cell which operates on the next lower order digits, said fourth circuit means determining therefrom and providing as output a 2-bit signal representing the sign and magnitude of the i-th ordere digit of the sum of x and y expressed as a radix 2 signed-digit number.

Claim 11

In an arithmetic processor which performs arithmetic operations on radix 2 signed-digit numbers each having N digits denoted by an order index which assumes integer values from 1 to N, said arithmetic processor having a plurality of adder cells each of which performs addition operations on an i-th digit x i of a signed-digit augend x and an i-th digit y i of a signed-digit addend y for a different value of the order index i by first determining an intermediate carry digit c i and an intermediate sum digit s i , and then determining the final sum digit z i by adding the intermediate sum s i to an intermediate carry c i-1 obtained from the adder cell operating on the next lower order digits, wherein each of said digits of said augend and addend are represented by two one-bit signals respectively representing the sign and magnitude of said digit, said adder cells each comprising: (a) first circuit means to which are supplied as inputs a 1-bit signal x i s and a 1-bit signal y i s which represent the sign of digits x i and y i respectively, said first circuit means determining therefrom and providing as output a 1-bit signal p i whose value depends upon whether both x i and y i are non-negative, or whether at least one of said digits x i and y i is negative; (b) second circuit means to which are supplied as input a 1-bit signal x i a and a 1-bit signal y i a which represent the magnitude of said digits x i and y i respectively and a signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as output a 1-bit signal u i representing the difference p i-1 -s i ; (c) third circuit means to which are supplied input signals representing the digits x i and y i respectively and said signal p i-1 , said third circuit means determining therefrom and providing as output a 1-bit signal v i representing the sum p i +c i ; and (d) fourth circuit means to which are supplied as input said 1-bit signal u i and a 1-bit signal v i-1 obtained from the third circuit means of the adder cell which operates on the next lower order digits, said fourth circuit means determining therefrom and providing as output a 2-bit signal representing the sign and magnitude of the i-th ordere digit of the sum of x and y expressed as a radix 2 signed-digit number.

Claim 12

In an arithmetic processor which performs arithmetic operations on radix 2 signed-digit numbers each having N digits denoted by an order index which assumed integer values from 1 to N, said arithmetic processor having a plurality of adder cells each of which performs addition operations on an i-th digit x i of a signed-digit augend x and an i-th digit y i of a signed-digit addend y for a different value of the order index i by first determining an intermediate carry digit c i and an intermediate sum digit s i , and then determining the final sum digit z i by adding the intermediate sum s i to an intermediate carry c i-1 obtained from the adder cell operating on the next lower order digits, wherein each of said digits of said augend and addend are represented by two one-bit signals respectively representing the sign and magnitude of said digit, said adder cells each comprising: (a) first circuit means to which are supplied signals representative of said digits x i and y i , said first circuit means determining therefrom and providing as output a 1-bit signal p i whose value depends upon the binary states of said digits x i and y i ; (b) second circuit means to which are supplied at least two signals representative of said digits x i and y i , and a 1-bit signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as output a 1-bit signal u i representing the sum p i-1 +s i ; (c) third circuit means to which are supplied at least two signals representative of said digits x i and y i , and said signal p i-1 , said third circuit means determining therefrom and providing as output a 1-bit signal v i representing the difference p i -c i ; and (d) fourth circuit means to which are supplied as input said signal u i and a signal v i-1 obtained from the third circuit means of the adder cell which operates on the next lower digits, said fourth circuit means determining therefrom and providing as output a 2-bit signal representing the sign and magnitude of the i-th digit of the sum of x and y expressed as a radix 2 signed-digit number.

Claim 13

In an arithmetic processor which performs arithmetic operations on radix 2 signed-digit numbers each having N digits denoted by an order index which assumed integer values from 1 to N, said arithmetic processor having a plurality of adder cells each of which performs addition operations on an i-th digit x i of a signed-digit augend x and an i-th digit y i of a signed-digit addend y for a different value of the order index i by first determining an intermediate carry digit c i and an intermediate sum digit s i , and then determining the final sum digit z i by adding the intermediate sum s i to an intermediate carry c i-1 obtained from the adder cell operating on the next lower order digits, wherein each of said digits of said augend and addend are represented by two one-bit signals respectively representing the sign and magnitude of said digit, said adder cells each comprising: (a) first circuit means to which are supplied signals representative of said digits x i and y i , said first circuit means determining therefrom and providing as output a 1-bit signal p i whose value depends upon the binary states of said digits x i and y i ; (b) second circuit means to which are supplied at least two signals representative of said digits x i and y i , and a 1-bit signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as output a 1-bit signal u i representing the sum p i-1 +s i ; (c) third circuit means to which are supplied at least two signals representative of said digits x i and y i , and said signal p i-1 , said third circuit means determining therefrom and providing as output a 1-bit signal v i representing the difference p i -c i ; and (d) fourth circuit means to which are supplied as input said signal u i and a signal v i-1 obtained from the third circuit means of the adder cell which operates on the next lower digits, said fourth circuit means determining therefrom and providing as output a 2-bit signal representing the sign and magnitude of the i-th digit of the sum of x and y expressed as a radix 2 signed-digit number.

Claim 14

The arithmetic processor in accordance with claim 10, wherein said first circuit means is supplied with a 1-bit signal x i s and a 1-bit signal y i ys which represent the sign of digits x i and y i respectively and determines therefrom a 1-bit signal p i whose value depends upon whether digits x i and y i are both non-negative, or whether at least one of said digits x i and y i is negative.

Claim 15

The arithmetic processor according to claim 11 wherein said second circuit means is supplied with two 1-bit signals x i a and y i a representing the magnitude of said digits x i and y i respectively and a 1-bit signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as an output a 1-bit signal u i representing the sum p i-1 +s i .

Claim 16

The arithmetic processor in accordance with claim 10, wherein said first circuit means is supplied with a 1-bit signal x i s and a 1-bit signal y i s which represent the sign of digits x i and y i respectively and determines therefrom a 1-bit signal p i whose value depends upon whether digits x i and y i are both non-positive or whether at least one of said digits x i and y i is positive.

Claim 17

The arithmetic processor according to claim 13 wherein said second circuit means is supplied with two 1-bit signals x i a and y i a representing the magnitude of said digits x i and y i respectively and a 1-bit signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as an output a 1-bit signal u i representing the sum p i-1 +s i .

Claim 18

The arithmetic processor in accordance with claim 10, wherein said first circuit means is supplied with a 1-bit signal x i s and a 1-bit signal y i s which represent the sign of digits x i and y i respectively and determines therefrom a 1-bit signal p i whose value depends upon whether the sum of the digits x i and y i is greater than or equal to zero or whether the sum of the digits x i and y i is less than zero.

Claim 19

The arithmetic processor according to claim 15 wherein said second circuit means is supplied with two 1-bit signals x i a and y i a representing the magnitude of said digits x i and y i respectively and a 1-bit signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as an output a 1-bit signal u i representing the sum p i-1 +s i .

Claim 20

The arithmetic processor according to claim 10 wherein said second circuit means is supplied with two 1-bit signals x i a and y i a representing the magnitude of said digits x i and y i respectively and a 1-bit signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as an output a 1-bit signal u i representing the sum p i-1 +s i .

Claim 21

In an arithmetic processor which performs arithmetic operations on radix 2 signed-digit numbers each having N digits denoted by an order index which assumed integer values from 1 to N, said arithmetic processor having a plurality of adder cells each of which performs addition operations on an i-th digit x i of a signed-digit augend x and an i-th digit y i of a signed-digit addend y for a different value of the order index i by first determining an intermediate carry digit c i and an intermediate sum digit s i , and then determining the final sum digit z i by adding the intermediate sum s i to an intermediate carry c i-1 obtained from the adder cell operating on the next lower order digits, wherein each of said digits of said augend and addend are represented by two one-bit signals respectively representing the sign and magnitude of said digit, said adder cells each comprising: (a) first circuit means to which are supplied as inputs a 1-bit signal x i s and a 1-bit signal y i s which represent the sign of digits x i and y i respectively, said first circuit means determining therefrom and providing as output therefrom a 1-bit signal p i whose value depends upon whether both x i and y i are non-negative, or whether at least one of said digits x i and y i is negative; (b) second circuit means to which are supplied as input a 1-bit signal x i a and a 1-bit signal y i a which represent the magnitude of said digits x i and y i respectively and a signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as output a 1-bit signal u i representing the sum p i-1 +p i ; (c) third circuit means to which are supplied input signals representing the digits x i and y i respectively and said signal p i-1 , said third circuit means determining therefrom and providing as output a 1-bit signal v i representing the difference p i -c i ; and (d) fourth circuit means to which are supplied as input said 1-bit signal u i and a 1-bit signal v i-1 obtained from the third circuit means of the adder cell which operates on the next lower digits, said fourth circuit means determining therefrom and providing as output a 2-bit signal representing the sign and magnitude of the i-th order digit of the sum of x and y expressed as a radix 2 signed-digit number.

Claim 22

In an arithmetic processor which performs arithmetic operations on radix 2 signed-digit numbers each having N digits denoted by an order index which assumed integer values from 1 to N, said arithmetic processor having a plurality of adder cells each of which performs addition operations on an i-th digit x i of a signed-digit augend x and an i-th digit y i of a signed-digit addend y for a different value of the order index i by first determining an intermediate carry digit c i and an intermediate sum digit s i , and then determining the final sum digit z i by adding the intermediate sum s i to an intermediate carry c i-1 obtained from the adder cell operating on the next lower order digits, wherein each of said digits of said augend and addend are represented by two one-bit signals respectively representing the sign and magnitude of said digit, said adder cells each comprising: (a) first circuit means to which are supplied as inputs a 1-bit signal x i s and a 1-bit signal y i s which represent the sign of digits x i and y i respectively, said first circuit means determining therefrom and providing as output therefrom a 1-bit signal p i whose value depends upon whether both x i and y i are non-negative, or whether at least one of said digits x i and y i is negative; (b) second circuit means to which are supplied as input a 1-bit signal x i a and a 1-bit signal y i a which represent the magnitude of said digits x i and y i respectively and a signal p i-1 obtained from the first circuit means of the adder cell which operates on the next lower order digits, said second circuit means determining therefrom and providing as output a 1-bit signal u i representing the sum p i-1 +p i ; (c) third circuit means to which are supplied input signals representing the digits x i and y i respectively and said signal p i-1 , said third circuit means determining therefrom and providing as output a 1-bit signal v i representing the difference p i -c i ; and (d) fourth circuit means to which are supplied as input said 1-bit signal u i and a 1-bit signal v i-1 obtained from the third circuit means of the adder cell which operates on the next lower digits, said fourth circuit means determining therefrom and providing as output a 2-bit signal representing the sign and magnitude of the i-th order digit of the sum of x and y expressed as a radix 2 signed-digit number.

Claim 23

In an arithmetic processor which performs arithmetic operations on radix 2 signed-digit numbers each having N digits denoted by an order index which assumes integer values from 1 to N, said arithmetic processor having a plurality of adder cells each of which performs addition operations on an i-th digit x i of a signed-digit augend x and an i-th digit y i of an ordinary binary addend y for a different value of the order index i by first determining an intermediate carry digit c i and an intermediate sum digit s i , and then determining the final sum digit z i by adding the intermediate sum s i to an intermediate carry c i-1 obtained from the adder cell operating on the next lower order digits, wherein each of said digits of said augend are represented by two one-bit signals x i s and x i a respectively representing the sign and magnitude of said digit and each of said digits of said addend are represented by a 1-bit signal y i , said adder cells each comprising: (a) first circuit means to which are supplied signals representative of said digits x i and y i , said first circuit means determining therefrom and providing as output a 1-bit signal u i representing said intermediate sum digit s i ; (b) second circuit means to which are supplied at the signals representative of said digits x i and y i , said second circuit means determining therefrom and providing as an output a 1-bit signal v i representing said intermediate carry c i ; and (c) third circuit means to which are supplied as inputs said 1-bit signal u i and a 1-bit signal v i-1 obtained from the second circuit means of the adder cell which operates on the next lower digits, said third circuit means determining therefrom and providing as output a 2-bit signal representing the sign and magnitude of the i-th digit of the sum of x and y expressed as a radix 2 signed-digit number.

Claim 24

In an arithmetic processor which performs arithmetic operations on radix 2 signed-digit numbers each having N digits denoted by an order index which assumes integer values from 1 to N, said arithmetic processor having a plurality of adder cells each of which performs addition operations on an i-th digit x i of a signed-digit augend x and an i-th digit y i of an ordinary binary addend y for a different value of the order index i by first determining an intermediate carry digit c i and an intermediate sum digit s i , and then determining the final sum digit z i by adding the intermediate sum s i to an intermediate carry c i-1 obtained from the adder cell operating on the next lower order digits, wherein each of said digits of said augend are represented by two one-bit signals x i s and x i a respectively representing the sign and magnitude of said digit and each of said digits of said addend are represented by a 1-bit signal y i , said adder cells each comprising: (a) first circuit means to which are supplied signals representative of said digits x i and y i , said first circuit means determining therefrom and providing as output a 1-bit signal u i representing said intermediate sum digit s i ; (b) second circuit means to which are supplied at the signals representative of said digits x i and y i , said second circuit means determining therefrom and providing as an output a 1-bit signal v i representing said intermediate carry c i ; and (c) third circuit means to which are supplied as inputs said 1-bit signal u i and a 1-bit signal v i-1 obtained from the second circuit means of the adder cell which operates on the next lower digits, said third circuit means determining therefrom and providing as output a 2-bit signal representing the sign and magnitude of the i-th digit of the sum of x and y expressed as a radix 2 signed-digit number.

Claim 25

The arithmetic processor in accordance with claim 19, wherein said first circuit means is supplied with a 1-bit signal x i a which represents the magnitude of said signed-digit x i and a 1-bit signal which represents the ordinary binary digit y i , said first circuit means determining therefrom and providing as output a 1-bit signal u i which represents said intermediate sum digit s i .