# US 8,788,563 B2 · Method of addition with multiple operands, corresponding adder and computer program product

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,788,563 B2
- Document ID: US8788563B2
- Status: Granted
- Kind: B2
- Application number: 12/936,337
- Filed: 2009-04-02
- Published: 2011-05-05
- Granted: 2014-07-22
- Earliest claimed: 2008-04-02
- Assignees: S.A.R.L. Daniel Torno
- Applicants: Daniel Torno
- Inventors: Daniel Torno
- Web page: https://patentgrep.com/patent/US8788563B2

## CPC

- G06F 7/509: for multiple operands, e.g. digital integrators
- G06F 7/5095: {word-serial, i.e. with an accumulator-register}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method is provided for adding binary numbers, each of N bits, based on an accumulation mechanism which, for each iteration of index i+1 with I>0, generates an estimation signal Ui+1 on N bits and a correction signal Ri+1 on N bits, on the basis of a binary input number c, an estimation signal Ui and a correction signal Ri on N bits emanating from a previous iteration i. The estimation signal Ui and the correction signal Ri represent a sum of a least two binary numbers in redundant form. The estimation signal Ui+1 and the correction signal Ri+1 represent, in redundant form, the sum of the at least two binary numbers in redundant form and the binary number c. In other words, such a method makes it possible to sum a further binary number with a result represented in a redundant binary form of the type “U/R”, this result resulting from an initialization or a previous summation, and then to generate a result also in a redundant binary form of the type “U/R”. More precisely, method makes it possible to carry out this summation as many times as there are binary numbers to be added.

## Claims

### Claim 1

An addition device for adding a plurality of input binary numbers each represented by a digital signal of N bits, wherein the device comprises:
inputs configured to receive the digital signals representing the plurality of input binary numbers;
at least one accumulation device configured to carry out, each time that it is activated, one iteration, of index i+1 with i≧0, of an accumulation mechanism, each accumulation device comprising estimation means selected from the group consisting of:
first estimation means for generating an estimation signal Ui+1 on N bits, and first correction means for generating a first correction signal Ri+1 on N bits, said first estimation means and said first correction means comprising means for implementing the following first set of equations:
{
U
n
i
+
1
=
U
n
i
⊕
R
n
i
⊕
U
n
-
1
i
⊕
c
n
R
n
+
1
i
+
1
=
(
U
n
i
⊕
R
n
i
⊕
U
n
-
1
i
)
·
(
U
n
i
⊕
c
n
)
and second estimation means for generating an estimation signal Ui+1 on N bits, and second correction means for generating a second correction signal Hi+1 on N bits, said second estimation means and said second correction means comprising means for implementing the following second set of equations:
{
U
n
i
+
1
=
U
n
i
⊕
H
n
i
⊕
c
n
H
n
+
1
i
+
1
=
(
U
n
i
⊕
H
n
i
)
·
(
U
n
i
⊕
c
n
_
)
⊕
c
n
with:
Ui+1n: value of the bit of rank n of said estimation signal Ui+1, with 0≦n≦N−1, obtained during said iteration of index i+1;
Uin: a value of the bit of rank n of an estimation signal Ui, obtained during a preceding iteration of index i if i>0, or a determined initialization value U0n of the bit of rank n of an estimation signal Ui if i=0;
Uin−1: a value of the bit of rank n−1 of said estimation signal Ui, obtained during a preceding iteration of index i if n>0 and if i>0,
or a determined initialization value U0n−1 of the bit of rank n−1 of said estimation signal Ui if n>0 and if i=0;
or a predetermined initialization value of an fictive bit of rank n−1 of said estimation signal Ui if n=0;
Rin: a value of the bit of rank n of a first correction signal Ri, obtained during a preceding iteration of index i if n>0,
or a predetermined initialization value of the bit of rank n of said first correction signal Ri if n=0;
Ri+1n+1: a value of the bit of rank n+1 of said first correction signal Ri+1, obtained during said iteration of index i+1;
Hin: a value of the bit of rank n of a second correction signal Hi, obtained during a preceding iteration of index i;
Hi+1n+1: a value of the bit of rank n+1 of said second correction signal Hi+1, obtained during said iteration of index i+1;
Cn: a value of the bit of rank n of an input binary number C included in said plurality of input binary numbers and taken into account in said addition during said iteration of index i+1,
the estimation signal Ui and the first correction signal Ri or the second correction signal Hi representing a sum of at least two binary numbers of the plurality of input binary numbers in redundant form, the estimation signal Ui+1 and the first correction signal Ri+1 or the second correction signal Hi+1, representing the sum of said at least two binary numbers in redundant form and of the binary number c, wherein the last iteration of Un is the sum Sn of the bit of rank n.

### Claim 2 (depends on 1)

The addition device of claim 1, wherein said accumulation device comprises, for each bit n, an accumulation sub-unit comprising:
a first XOR logic gate receiving said value Uin−1 of the bit of rank n and of index i and said value Rin of the bit of rank n and of index i, and generating a first intermediate signal;
a second XOR logic gate receiving said first intermediate signal and said value Uin of the bit of rank n and of index i, and generating a second intermediate signal;
a third XOR logic gate receiving said second intermediate signal and said value of the bit of rank n of an input binary number C, and generating said value Ui+1n of the bit of rank n of said estimation signal Ui+1 for the iteration of index i+1;
a fourth XOR logic gate receiving said value Uin of the bit of rank n and of index i and said value cn of the bit of rank n of an input binary number C, and generating a third intermediate signal; and
an AND logic gate receiving said third intermediate signal and said second intermediate signal, and generating said value Ri+1n+1 of the bit of rank n+1 of said first correction signal Ri+1 for the iteration of index i+1.

### Claim 3 (depends on 1)

The addition device of claim 1, wherein said accumulation device comprises, for each bit n, an accumulation sub-unit comprising:
a first XOR logic gate receiving said value Uin−1 of the bit of rank n−1 and of index i and said value Hin of the bit of rank n and of index i, and generating a first intermediate signal;
a second XOR logic gate receiving said first intermediate signal and said value cn of the bit of rank n of an input binary number C, and generating said value Ui+1n of the bit of rank n of said estimation signal Ui+1 for the iteration of index i+1;
an XNOR logic gate receiving said value Uin−1 of the bit of rank n−1 and of index i and said value cn of the bit of rank n of an input binary number C and generating a second intermediate signal;
an AND logic gate receiving said first intermediate signal and said second intermediate signal and generating a third intermediate signal; and
a third XOR logic gate receiving said third intermediate signal and said value cn of the bit of rank n of an input binary number C and generating said value Hi+1n+1 of the bit of rank n+1 of said second correction signal Hi+1 for the iteration of index i+1.

### Claim 4 (depends on 1)

The addition device of claim 1, wherein the addition device includes an initialization unit comprising estimation means selected from the group consisting of:
third estimation means for generating an estimation signal U1 on N bits, and third correction means for generating a third correction signal R1 on N bits, said third estimation means and said third correction means comprising means for implementing the following third set of equations, with 0≦n≦N−1:
{
U
n
1
=
a
n
⊕
b
n
⊕
c
n
_
R
n
+
1
1
=
(
a
n
⊕
b
n
_
)
⁢
(
b
n
⊕
c
n
_
)
and fourth estimation means for generating an estimation signal U1 on N bits, and fourth correction means for generating a fourth correction signal H1 on N bits, said fourth estimation means and said fourth correction means comprising means for implementing the following fourth set of equations, with 0≦n≦N−1:
{
U
n
1
=
a
n
⊕
b
n
⊕
c
n
_
R
n
+
1
1
=
(
a
n
⊕
b
n
_
)
⁢
(
b
n
⊕
c
n
)
⊕
c
n
with:
an: a value of the bit of rank n of an input binary number A included in said plurality of input binary numbers and taken into account by said initialization unit;
bn: a value of the bit of rank n of an input binary number B included in said plurality of input binary numbers and taken into account by said initialization unit;
cn: a value of the bit of rank n of an input binary number C included in said plurality of input binary numbers and taken into account by said initialization unit;
and wherein said initialization unit replaces the accumulation unit, enabling the iteration of index 1 to be carried out.

### Claim 5 (depends on 4)

The addition device of claim 4, wherein said initialization unit comprises, for each bit n, an initialization sub-unit comprising:
a first XNOR logic gate receiving said value an of the bit of rank n of an input binary number A and of the said bn value of the bit of rank n of an input binary number B and generating a first intermediate signal;
an XOR logic gate receiving said first intermediate signal and said value said value cn of the bit of rank n of an input binary number C and generating said value U1n of the bit of rank n of said estimation signal U1 for the iteration of index 1;
a second XNOR logic gate receiving said value bn of the bit of rank n of an input binary number B and said value cn of the bit of rank n of an input binary number C and generating said intermediate signal; and
an AND logic gate receiving said first and second intermediate signals and generating said value R1n+1 of the bit of rank n+1 of said correction signal R1 for the iteration of index 1.

### Claim 6 (depends on 4)

The addition device of claim 4, wherein said initialization unit comprises, for each bit n, an initialization sub-unit comprising:
an XNOR logic gate receiving said value an of the bit of rank n of an input binary number A and of the said bn value of the bit of rank n of an input binary number B and generating a first intermediate signal;
a first XOR logic gate receiving said first intermediate signal and said value said value cn of the bit of rank n of an input binary number C and generating said value U1n of the bit of rank n of said estimation signal U1 for the iteration of index 1;
a second XOR logic gate receiving said value bn of the bit of rank n of an input binary number B and said value cn of the bit of rank n of an input binary number C and generating a second intermediate signal;
an AND logic gate receiving said first and second intermediate signals and generating a third intermediate signal; and
a third XOR logic gate receiving said third intermediate signal and said value cn of the bit of rank n of an input binary number C and generating said value H1n+1 of the bit of rank n+1 of said second correction signal H1 for the iteration of index 1 .

### Claim 7 (depends on 1)

The addition device of claim 1, wherein the addition device comprises:
first selection means for selecting a first input binary number included in said plurality of input binary numbers;
means for obtaining predetermined initialization values for:
each of the N bits of an estimation signal U0,
each of the N bits of a correction signal R0,
a fictive bit of rank −1 of said estimation signal U0;
first activation means for activating said accumulation unit in order for the accumulation unit to carry out the iteration of index 1 of said accumulation mechanism with, as input signals, said first input binary number and said predetermined initialization values, enabling an estimation signal U1 to be generated on N bits and a first R1 correction signal to be generated on N bits;
second activation means for activating the following, as long as said plurality of input binary numbers have not been taken into account in said addition:
second selection means for selecting a new input binary number included in said plurality of input binary numbers and not already selected;
said accumulation unit in order for same to carry out an iteration of index i+1, with i>0, of said accumulation mechanism with, as input signals, said new input binary number, the signals U1 and Ri generated during the iteration of index i of said accumulation mechanism, a predetermined initialization value Ui−1 of a fictive bit of rank −1 of said estimation signal Ui, and a predetermined initialization value Ri0 of the bit of rank 0 of said first correction signal Ri.

### Claim 8 (depends on 1)

The addition device of claim 1, wherein the addition device comprises:
first selection means for selecting a first input binary number included in said plurality of input binary numbers;
means for obtaining predetermined initialization values for:
each of the N bits of an estimation signal U0,
each of the N bits of a correction signal H0,
first activation means for activating said accumulation unit in order for the accumulation unit to carry out the iteration of index 1 of said accumulation mechanism with, as input signals, said first input binary number and said predetermined initialization values, enabling an estimation signal U1 to be generated on N bits and a second H1 correction signal to be generated on N bits;
second activation means for activating the following means, as long as said plurality of input binary numbers have not been taken into account in said addition:
second selection means for selecting a new input binary number included in said plurality of input binary numbers and not already selected;
said accumulation unit in order for same to carry out an iteration of index i+1, with i>0, of said accumulation mechanism with, as input signals, said new input binary number, the signals U1 and Hi generated during the iteration of index i of said accumulation mechanism, a predetermined initialization value Ri0 of the bit of rank 0 of said first correction signal Ri.

### Claim 9 (depends on 1)

The adding device of claim 1, wherein the digital processing device is implemented by a combination of hardware and software, which are configured to perform the functions of the first estimation means and the first correction means or the functions of the second estimation means and the second correction means.

### Claim 10 (depends on 1)

The adding device of claim 1, wherein each accumulation device is implemented in a digital logic circuit configured to perform the functions of the first estimation means and the first correction means or the functions of the second estimation means and the second correction means.

### Claim 11 (depends on 1)

The adding device of claim 1, wherein each accumulation device is implemented by a combination of hardware and software, which are configured to perform the functions of the first estimation means and the first correction means or the functions of the second estimation means and the second correction means.

### Claim 12

A non-transitory computer-readable storage medium, storing a set of instructions that may be run by a computer in order to implement a method for adding a plurality of input binary numbers each of N bits, wherein the method comprises, when said set of instructions is executed, configuring the computer by the set of instructions to perform digital signal processing, including:
receiving the plurality of input binary numbers, each represented by a digital signal having N bits; and
at least one iteration, of index i+1 with i≧0, of an accumulation step that generates an estimation signal Ui+1 on N bits and generates a first Ri+1 or second Hi+1 correction signal on N bits, according to a set of equations selected from the group consisting of:
a first set of equations:
{
U
n
i
+
1
=
U
n
i
⊕
R
n
i
⊕
U
n
-
1
i
⊕
c
n
R
n
+
1
i
+
1
=
(
U
n
i
⊕
R
n
i
⊕
U
n
-
1
i
)
·
(
U
n
i
⊕
c
n
)
and a second set of equations:
{
U
n
i
+
1
=
U
n
i
⊕
H
n
i
⊕
c
n
H
n
+
1
i
+
1
=
(
U
n
i
⊕
H
n
i
)
·
(
U
n
i
⊕
c
n
_
)
⊕
c
n
with:
Ui+1n: a value of the bit of rank n of said estimation signal Ui+1, with 0≦n≦N−1, obtained during said iteration of index i+1;
Uin: a value of the bit of rank n of an estimation signal Ui, obtained during a preceding iteration of index i if i>0, or a determined initialization value U0n of the bit of rank n of an estimation signal Ui if i=0;
Uin−1: a value of the bit of rank n−1 of said estimation signal obtained during a preceding iteration of index i if n>0 and if i>0,
or a determined initialization value U0n−1 of the bit of rank n−1 of said estimation signal Ui if n>0 and i=0,
or a predetermined initialization value of a fictive bit of rank n−1 of said estimation signal Ui if n=0;
Rin: a value of the bit of rank n of a first correction signal Ri, obtained during a preceding iteration of index i if n>0,
or a predetermined initialization value of the bit of rank n of said first correction signal Ri if n=0;
Ri+1n+1: a value of the bit of rank n+1 of said first correction signal Ri+1, obtained during said iteration of index i+1;
Hin: a value of the bit of rank n of a second correction signal Hi, obtained during a preceding iteration of index i;
Hi+1n+1: a value of the bit of rank n+1 of said correction signal Hi+1, obtained during said iteration of index i+1;
Cn: a value of the bit of rank n of an input binary number C included in said plurality of input binary numbers and taken into account in said addition during said iteration of index i+1 of said accumulation step,
the estimation signal Ui and the first correction signal Ri or the second correction signal Hi representing a sum of at least two of the input binary numbers in redundant form, the estimation signal Hi+1 and the first correction signal Ri+1 or the second correction signal Hi+1 representing the sum of said at least two binary numbers in redundant form and of the binary number c, wherein the last iteration of Un is the sum Sn of the bit of rank n.