# Patent

## Title
Method of addition with multiple operands, corresponding adder and computer program product

## 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.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This Application is a Section 371 National Stage Application of International Application No. PCT/EP2009/053976, filed Apr. 2, 2009 and published as WO 2009/121943 on Oct. 8, 2009, not in English.
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
None.
THE NAMES OF PARTIES TO A JOINT RESEARCH AGREEMENT
None.
FIELD OF THE DISCLOSURE
The field of the disclosure is that of digital information processing circuits and systems and, more particularly, digital signal processing computers performing the addition of binary numbers.
The disclosure has numerous applications, e.g., such as in microprocessors, digital signal processors (DSPs), application specific integrated circuits (ASICs), or very large scale integration (VLSI), or else optical or quantum computers within neural networks.
More precisely, the disclosure relates to an addition technique using multiple operands enabling a result to be provided in a redundant binary form.
The disclosure applies, in particular, but not exclusively, to digital signal processing for summing and/or accumulating results within the framework of digital filter production, for example.
Since binary addition is the most widely used of arithmetic operations, the disclosure can be applied more generally to any circuit, system or device requiring summation of several operands.
BACKGROUND OF THE DISCLOSURE
Adders are extremely common and indispensable operators not only in the arithmetic units of digital signal processing microprocessors and processors but likewise in all logic circuits.
However, adders often prove to be the critical operators of a digital processing system, in particular during certain implementations, both from the viewpoint of the speed of execution thereof and the viewpoint of the design and testability of same.
As a matter of fact, nowadays, the creation of algorithms of increasing complexity within computers makes the architecture of the operators increasingly difficult to implement and, in particular, compactness problems arise. A choice must therefore generally be made between complexity and speed of execution.
The technical problem of the computing speed with respect to binary number addition operations is a problem known to those skilled in the art, and several techniques have already been proposed for addressing it.
In a first standard technique, by cascading several 1-bit full adders, the binary adder, more commonly named a Ripple Carry Adder (RCA), enables the carry digit to be propagated from adder to adder.
The disadvantage of this first standard technique is the slowness of the computations that it implements. As a matter of fact, the computing time depends directly on the time required to propagate the carry digit from adder module to adder module. Thus, this method can only be chosen for addition operations which do not exceed a few bits.
Taking account of the fact that computation of the carry digits must be accelerated, a second known technique is a carry look-ahead computation carried out with a so-called Carry Look-Ahead Adder (CLA). Such an adder facilitates, in particular, computation of the carry digits by means of an outside circuit.
However, this type of standard adder has the disadvantage of providing a propagation time that is still too long, in particular for applications including complex algorithms and requiring fast computation.
In order to prevent propagation of the carry digits and to thereby improve the execution time of the computations, another conventionally used technique consists of an addition of binary numbers in redundant form, using an adder structure also known as a carry save adder. These standard adders use redundant expressions which enable additions to be performed in parallel, and therefore without propagating carry digits.
To illustrate, the American patent documents U.S. Pat. No. 6,578,063 B1 (IBM) and U.S. Pat. No. 6,567,835 B1 (INTRINSITY) propose two binary number adder architectures of the “carry save” type. These two architectures enable five binary numbers to be added and to furnish the result thereof in the form of a sum and a carry digit. The conventional method cited in these documents consists in using, in particular, a redundant representation of each of the added binary numbers.
However, the standard “carry save” layout described requires a significant number of logic gates and intermediate digital processing stages. Since the architecture and layout of the logic devices is not optimised, this method involves a still significant propagation time.
One known technique, as described in the international application WO2007122319 (TORNO), consists in making several estimates of bit values of the sum of two binary numbers, by means of a “U/R” type redundant binary representation of the intermediate computation results, and in successively correcting these estimates using a correction signal. The number of logic gates and intermediate digital processing stages of this type of adder is thereby reduced.
This method, which is based on a “U/R” type representation, is today unfortunately applicable only for adding two binary numbers. Accordingly, if it is desired to add more than two binary numbers, this method must be applied to two numbers, and then (as many times as necessary) to the result of a preceding addition and a new binary number. This solution is not optimal.
SUMMARY
In one particular embodiment of the invention, an addition method is proposed for adding a plurality of input binary numbers each of N bits, the method comprising at least one iteration, of index i+1 with i≧0, of an accumulation step enabling an estimation signal Ui+1 to be generated on N bits and a first Ri+1 or second Hi+1 correction signal to be generated on N bits,

    
    
        according to the following 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
                  
                
                )
              
            
          
        
      
    
  




    
    
        or according to the following 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 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 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+1+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 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.



The general principle in an embodiment of the invention therefore consists in summing an additional binary number with a result represented in a “U/R” type redundant binary form (this result being the result of an initialization or preceding summation), and in then generating a result likewise in a “U/R” type redundant binary form.
More precisely, such a method enables this summation to be carried out as many times as there are binary numbers to be added. Reference is then made to steps of accumulating intermediate results of computation.
More precisely, at each accumulation step, an estimation signal U and a correction signal R are generated on N bits in the form of a redundant binary representation.
In this way, such a method enables an additional standard binary number to be summed while preventing the carry digits from propagating.
The iteration of index 1 of said accumulation step is advantageously replaced by an initialization step enabling an estimation signal U1 to be generated on N bits and first R1 or second H1 correction signal to be generated on N bits,

    
    
        according to the following 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
                    
                  
                  _
                
                )
              
            
          
        
      
    
  




    
    
        or according to the following equations, with 0≦n≦N−1:
    
    






   
  
    {
    
      
        
          
            
              U
              n
              1
            
            =
            
              
                
                  a
                  n
                
                ⊕
                
                  b
                  n
                
                ⊕
                
                  c
                  n
                
              
              _
            
          
        
      
      
        
          
            
              H
              
                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 in said addition during said initialization step;
    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 in said addition during said initialization step;
    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 initialization step.


In this way, it is possible to initially add three binary numbers and to generate an estimation signal U and a correction signal R of first iteration.
The addition method preferably comprises the following steps:

    
    
        selecting a first input binary number included in said plurality of input binary numbers;
        obtaining specific 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;
        
        
        iterating index 1 of said accumulation step 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;
        as long as said plurality of input binary numbers have not been taken into account in said addition:
        
            selecting a new input binary number included in said plurality of input binary numbers and not already selected;
            iterating index i+1, with i>0, of said accumulation step with, as input signals, said new input binary number, the signals Ui and Ri generated during the iteration of index i of said accumulations step, 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.
        
        
    
    


In this way, an embodiment of the invention enables a set of binary numbers to be summed sequentially, as is the case, for example, for digital filters.
According to another alternative embodiment, the addition method comprises the following steps:

    
    
        selecting a first input binary number included in said plurality of input binary numbers;
        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,
        
        
        iterating index 1 of said accumulation step 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;
        as long as said plurality of input binary numbers have not been taken into account in said addition:
        
            selecting a new input binary number included in said plurality of input binary numbers and not already selected;
            iterating index i+1, with i>0, of said accumulation step with, as input signals, said new input binary number, the signals Ui and Hi generated during the iteration of index i of said accumulations step, a predetermined initialization value Ri0 of the bit of rank 0 of said first correction signal Ri.
        
        
    
    


In another advantageous embodiment of the invention, an addition device is proposed for adding a plurality of input binary numbers each of N bits. Such a device comprises at least one accumulation unit enabling, each time that it is activated, to carry out one iteration, of index i+1 with i≧0, of an accumulation mechanism, each accumulation unit comprising:

    
    
        first estimation means, enabling an estimation signal Ui+1 to be generated on N bits, and first correction means, enabling a first correction signal Ri+1 to be generated on N bits, said first estimation means and said first correction means comprising means for implementing the following 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
                  
                
                )
              
            
          
        
      
    
  




    
    
        or second estimation means, enabling an estimation signal Ui+1 to be generated on N bits, and second correction means, enabling a second correction signal Hi+1 to be generated on N bits, said second estimation means and said second correction means comprising means for implementing the following 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 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.



In this way, the adder can receive an additional binary number at each accumulation unit, in addition to the estimation and correction signals derived from the accumulation unit situated upstream.
For each bit n, the accumulation unit advantageously comprises an accumulation sub-unit itself 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.
    
    


The architecture of the accumulation unit thus enables a shorter propagation time and facilitates testability.
According to an alternative, for each bit n, the accumulation unit comprises an accumulation sub-unit itself 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.
    
    


The addition device advantageously an initialization unit comprising:

    
    
        third estimation means, enabling an estimation signal U1 to be generated on N bits, and third correction means R1 on N bits, said third estimation means and said third correction means comprising means for implementing the following 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
                    
                  
                  _
                
                )
              
            
          
        
      
    
  




    
    
        or fourth estimation means, enabling an estimation signal U1 to be generated on N bits, and fourth correction means, enabling a fourth correction signal H1 to be generated on N bits, said fourth estimation means and said fourth correction means comprising means for implementing the following equations, with 0≦n≦N−1:
    
    






   
  
    {
    
      
        
          
            
              U
              n
              1
            
            =
            
              
                
                  a
                  n
                
                ⊕
                
                  b
                  n
                
                ⊕
                
                  c
                  n
                
              
              _
            
          
        
      
      
        
          
            
              H
              
                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 in that said initialization unit replaces the accumulation unit, enabling the iteration of index 1 to be carried out.



In this way, the initialization unit enables three input binary numbers to be added directly.
For each bit n, the initialization unit preferably comprises an initialization sub-unit itself 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.
    
    


According to an alternative, for each bit n, the initialization unit comprises an initialization sub-unit itself 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.
    
    


According to one advantageous characteristic, the device comprises:

    
    
        first means for selection, enabling selection of 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 enabling said accumulation unit to be activated in order for it 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 enabling the following means to be activated, as long as said plurality of input binary numbers have not been taken into account in said addition:
        
            second means for selection, enabling selection of 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 R1 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.
        
        
    
    


A single accumulation unit is thus sufficient.
According to an alternative embodiment, the addition device comprises:


    
    
        first means for selection enabling selection of 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 enabling said accumulation unit to be activated in order for it 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 enabling the following means to be activated, as long as said plurality of input binary numbers have not been taken into account in said addition:
        
            second means of selection, enabling selection of 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.
        
        
    
    


In another embodiment, the invention relates to a computer program product downloadable from a communication network and/or recorded on a computer-readable medium and/or executable by a processor, including program code instructions for implementing the decoding method as described above.



BRIEF DESCRIPTION OF THE DRAWINGS
Other characteristics and advantages of embodiments of the invention will become apparent upon reading the following description, given for illustrative and non-limiting purposes (all of the embodiments of the invention are not limited to the characteristics and advantages of the embodiments described hereinbelow), and from the appended drawings, in which:
FIG. 1 shows a logic architecture for an accumulation module in U/R form, according to one particular embodiment of the invention;
FIG. 2 shows a logic architecture for an initialization module in U/R form, according to a first embodiment of the invention;
FIG. 3 shows a logic architecture for an initialization module in U/R form, according to a second embodiment of the invention;
FIG. 4 shows an example of an initialization device in U/R form on 16 bits, according to a particular embodiment of the method of the invention, including 16 initialization modules as shown in FIG. 2 or 3;
FIG. 5 shows an example of an accumulation device in U/R form on 16 bits, according to a particular embodiment of the invention, including 16 accumulation modules as shown in FIG. 1;
FIG. 6 shows an alternative embodiment, in U/H form, of the accumulation module in U/R form shown in FIG. 1 according to an embodiment of the invention;
FIG. 7 shows a logic architecture for an initialization module in U/H form, according to a first embodiment of the invention;
FIG. 8 shows a logic architecture for an initialization module in U/H form according to a second embodiment of the invention;
FIG. 9 shows a block diagram of a parallel multi-operand adder according to a particular embodiment of the method according to the invention;
FIG. 10 shows a block diagram of a sequential multi-operand adder according to a particular embodiment of the method according to the invention;
FIG. 11 shows an example of digital computation of a seven-operand summation carried out by the adder of FIG. 9.



DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS
In all of the figures of this document, identical elements and steps are designated by a single numerical reference.
A logic architecture will now be introduced in connection with FIG. 1, for an accumulation module in U/R form, according to a particular embodiment of the invention, which implements the accumulation step of the method according to an embodiment of the invention.
More particularly, for a given bit of rank n, the accumulation module 100 makes it possible to add a result expressed in a redundant binary form “Ui/Ri” derived from an iteration of index i (i≧0) and a standard binary number, referenced as C, and to once again provide a binary result thereof in redundant form “Ui+1/Ri+1” obtained for an iteration of index i+1. The accumulation mechanism put into place by the module 100 enables the binary values Ui+1n and Ri+1n+1, to be generated, which correspond to the value of the bit of rank n of the estimation signal U1+1 and to the value of the bit of rank n+1 of the correction signal Ri+1n respectively, with 0≦n≦N−1.
In this particular embodiment, the accumulation module 100 consists of a first logic gate of the “OR Exclusive” type, likewise called the “XOR” gate, which is capable of receiving as input a value Uin−1 known as the value of the bit of rank n−1 of the estimation signal Ui, obtained during a preceding iteration of index i, and a value Rin, known as the value of the bit of rank n of a correction signal Ri, obtained during a preceding iteration of index i. This first “XOR” gate generates as output an intermediate digital signal 101.
A second “XOR” gate in turn receives the intermediate digital signal 101 and a value Uin, known as the value of the bit of rank n of an estimation signal Ui, obtained during a preceding iteration of index i, and generates as output another intermediate digital signal 102. A third “XOR” gate receives the intermediate digital signal 102 and cn a value of the bit of rank n of an additional input binary number C to be added, and delivers as output a value Ui+1n known as the value of the bit of rank n of said estimation signal Ui+1, obtained during an iteration of index i+1.
A third “XOR” gate likewise enables the value and the value of the bit of the additional binary number C to be received as input, and delivers as output an intermediate digital signal 103. An “AND” type logic gate, liked called an “AND” gate, receives the two intermediate signals 102 and 103, and delivers as output a value Ri+1n+1, known as the value of the bit of rank n+1 of the correction signal Ri+1, obtained during an iteration of index i+1.
In this way, the value Ri+1n+1 of the bit of rank n+1 of the correction signal Ri+1 of index i+1 is determined from the last estimate of the bit Uin of rank n, of the last correction bit Rin of rank n, from the last estimate of the bit Uin−1 of rank n−1 and from the bit value cn of rank n of the additional binary number C.
It is important to note that, in the case where the bit in question corresponds to the bit of rank n=0, the bit Uin−1 is considered to be a fictive bit of the estimation signal Ui, and the bit Rin is a predetermined initialization bit of the correction signal bit Ri. Furthermore, if the accumulation step corresponds to an iteration of index 0, then the bit U0n−1 likewise corresponds to a specific initialization value (with n>0) and the bit U0n to a specific initialization value of the estimation signal Ui.
Consequently, the estimation signals Ui+1 on N bits and correction signals Ri+1 on N bits are determined from the following generic equations (1), with 0≦n≦N−1:




  
    
      
        {
        
          
            
              
                
                  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
                      
                    
                    )
                  
                
              
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




    with:
    Ui+1n: a value of the bit of rank n of the estimation signal Ui+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 specific initialization value U0n of the n-position bit of an estimation signal Ui if i=0;
    Uin−1: a value of the bit of rank n−1 of the estimation signal Ui, obtained during a preceding iteration of index i if n>0 and if i>0,
    
        or a specific initialization value U0n−1 of the bit of rank n−1 of the estimation signal Ui if n>0 and if i=0,
        or a predetermined initialization value of an n−1 position fictive bit of the estimation signal Ui if n=0;
    
    
    Rin: a value of the n 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 the correction signal Ri, if n=0;
    
    
    Ri+1n+1: a value of the bit of rank n+1 of the correction signal Ri+1, obtained during the 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 the iteration of index i+1 of the accumulation step.


It is clear that other logic architectures (different from that of FIG. 1) can easily be anticipated by a person skilled in the art, in order to implement the generic equations (1), while at the same time remaining within the scope of an embodiment of this invention.
A logic architecture will now be presented in connection with FIG. 2, for an initialization module in U/R form, according to a first embodiment of the invention.
More precisely, the initialization module 200 implements the initialization step of the method according to an embodiment of the invention. As a matter of fact, it enables three standard binary numbers A, B and C to be added and to generate an estimation signal Ui on N bits and a correction signal R1 on N bits, corresponding to an iteration of rank 1. These three binary numbers are likewise conventionally expressed on N bits and defined as follows:




  
    
      
        {
        
          
            
              
                A
                =
                
                  
                    
                      a
                      
                        N
                        -
                        1
                      
                    
                    ·
                    
                      2
                      
                        N
                        -
                        1
                      
                    
                  
                  +
                  ...
                  +
                  
                    
                      a
                      n
                    
                    ·
                    
                      2
                      n
                    
                  
                  +
                  ...
                  +
                  
                    
                      a
                      1
                    
                    ·
                    
                      2
                      1
                    
                  
                  +
                  
                    
                      a
                      0
                    
                    ·
                    
                      2
                      0
                    
                  
                
              
            
          
          
            
              
                B
                =
                
                  
                    
                      b
                      
                        N
                        -
                        1
                      
                    
                    ·
                    
                      2
                      
                        N
                        -
                        1
                      
                    
                  
                  +
                  ...
                  +
                  
                    
                      b
                      n
                    
                    ·
                    
                      2
                      n
                    
                  
                  +
                  ...
                  +
                  
                    
                      b
                      1
                    
                    ·
                    
                      2
                      1
                    
                  
                  +
                  
                    
                      b
                      0
                    
                    ·
                    
                      2
                      0
                    
                  
                
              
            
          
          
            
              
                C
                =
                
                  
                    
                      c
                      
                        N
                        -
                        1
                      
                    
                    ·
                    
                      2
                      
                        N
                        -
                        1
                      
                    
                  
                  +
                  ...
                  +
                  
                    
                      c
                      n
                    
                    ·
                    
                      2
                      n
                    
                  
                  +
                  ...
                  +
                  
                    
                      c
                      1
                    
                    ·
                    
                      2
                      1
                    
                  
                  +
                  
                    
                      c
                      0
                    
                    ·
                    
                      2
                      0
                    
                  
                
              
            
          
        
      
    
    
      
        (
        2
        )
      
    
  




with:

an, bn and cn the bit values of rank n of the input binary numbers A, B and C, taken into account in the initialization step, with n varying from 0 to N−1.
The module includes a first sub-module 201, called a pre-computation module, and a second sub-module 202, called an initial accumulation module. More precisely, the pre-computation module 201, as described in the international patent document WO2007122319 (TORNO), introduces a first logic gate of the “Exclusive NOT-OR” type, also called an “XNOR” gate, which is capable of receiving the input bit values an−1, bn, and generating as output an initial correction value R0n of the bit of rank n. Two “Inverter” type logic gates, referenced as “INV”, which are input with the bit value an−1 and bn, furnish as output an initial estimation value U0n−1 of the bit of rank n−1 and an initial estimation value U0n of the bit of rank n.
In this particular embodiment, the pre-computation module 201 is situated upstream from the initial accumulation module. The latter, as described in connection with FIG. 1, enables the value of the bit of rank n of an additional binary number (cn) to be added to the values Uin−1, Rin and Uin. In this specific case, since the iteration is of index 0, the input values of module 202 are therefore U0n−1, R0n and U0n. Since the principle and architecture of module 202 are identical to the accumulation module 100 of FIG. 1, the values obtained as output from the initialization module are therefore incremented by an index having a value of 1.
In the end, the initialization module 200 generates the bit estimation U1n and correction R1n+1 values of rank n and n+1, respectively, as defined by the following equations (3):




  
    
      
         
        
          {
          
            
              
                
                  
                    U
                    n
                    1
                  
                  =
                  
                    
                      
                        a
                        n
                      
                      ⊕
                      
                        b
                        n
                      
                      ⊕
                      
                        c
                        n
                      
                    
                    _
                  
                
              
            
            
              
                
                  
                    R
                    
                      n
                      +
                      1
                    
                    1
                  
                  =
                  
                    
                      (
                      
                        
                          
                            a
                            n
                          
                          ⊕
                          
                            b
                            n
                          
                        
                        _
                      
                      )
                    
                    ⁢
                    
                      (
                      
                        
                          
                            b
                            n
                          
                          ⊕
                          
                            c
                            n
                          
                        
                        _
                      
                      )
                    
                  
                
              
            
          
        
      
    
    
      
        (
        3
        )
      
    
  




with 0≦n≦N−1.

Furthermore, the pre-computation sub-module enables the following equalities to be implemented:



  
    
      
        U
        n
        0
      
      =
      
        
          a
          n
        
        _
      
    
    ;
  




  
    
      
        U
        
          n
          -
          1
        
        0
      
      =
      
        
          a
          
            n
            -
            1
          
        
        _
      
    
    ;
  




  
    
      R
      n
      0
    
    =
    
      
        
          
            a
            
              n
              -
              1
            
          
          ⊕
          
            b
            n
          
        
        _
      
      .
    
  



By substituting the bit values obtained by the pre-computation sub-module in the generic equations (1) in connection with FIG. 1, the following equations are obtained:




   
  
    {
    
      
        
          
            
              U
              n
              1
            
            =
            
              
                
                  a
                  n
                
                _
              
              ⊕
              
                (
                
                  
                    
                      a
                      
                        n
                        -
                        1
                      
                    
                    ⊕
                    
                      b
                      n
                    
                  
                  _
                
                )
              
              ⊕
              
                
                  a
                  
                    n
                    -
                    1
                  
                
                _
              
              ⊕
              
                c
                n
              
            
          
        
      
      
        
          
            
              R
              
                n
                +
                1
              
              1
            
            =
            
              
                (
                
                  
                    
                      a
                      n
                    
                    _
                  
                  ⊕
                  
                    (
                    
                      
                        
                          a
                          
                            n
                            -
                            1
                          
                        
                        ⊕
                        
                          b
                          n
                        
                      
                      _
                    
                    )
                  
                  ⊕
                  
                    
                      a
                      
                        n
                        -
                        1
                      
                    
                    _
                  
                
                )
              
              ·
              
                (
                
                  
                    
                      a
                      n
                    
                    _
                  
                  ⊕
                  
                    c
                    n
                  
                
                )
              
            
          
        
      
    
  




Then, by establishing the equality

( an⊕bn)·( an⊕cn)=( an⊕bn)·( bn⊕cn),

the aforesaid equalities are simplified, namely:





   
  
    {
    
      
        
          
            
              U
              n
              1
            
            =
            
              
                
                  a
                  n
                
                _
              
              ⊕
              
                b
                n
              
              ⊕
              
                c
                n
              
            
          
        
      
      
        
          
            
              R
              
                n
                +
                1
              
              1
            
            =
            
              
                (
                
                  
                    
                      a
                      n
                    
                    _
                  
                  ⊕
                  
                    b
                    n
                  
                
                )
              
              ·
              
                (
                
                  
                    
                      a
                      n
                    
                    _
                  
                  ⊕
                  
                    c
                    n
                  
                
                )
              
            
          
        
      
    
  




It is thus noted that the bit value an−1 is no longer part of the aforesaid equation. Consequently, after simplifications, the equations (3) established previously in connection with FIG. 2 are obtained:




  
    
      
         
        
          {
          
            
              
                
                  
                    U
                    n
                    1
                  
                  =
                  
                    
                      
                        a
                        n
                      
                      ⊕
                      
                        b
                        n
                      
                      ⊕
                      
                        c
                        n
                      
                    
                    _
                  
                
              
            
            
              
                
                  
                    R
                    
                      n
                      +
                      1
                    
                    1
                  
                  =
                  
                    
                      (
                      
                        
                          
                            a
                            n
                          
                          ⊕
                          
                            b
                            n
                          
                        
                        _
                      
                      )
                    
                    ⁢
                    
                      (
                      
                        
                          
                            b
                            n
                          
                          ⊕
                          
                            c
                            n
                          
                        
                        _
                      
                      )
                    
                  
                
              
            
          
        
      
    
    
      
        (
        3
        )
      
    
  




U1−1 the bit value of rank n−1 for n=0 of the estimation signal is arbitrarily considered equal to 1 because it is considered to be derived from the equation:

U1−1= a−1⊕b−1⊕c−1 with: a−1=0, b−10, c−1=0.

This case remains true irrespective of the iteration of the method.

In the same way, Ri0, the bit value of rank n for n=0 of the correction signal is arbitrarily considered equal to 1 because it is considered to be derived from the equation:

R01=( a−1⊕b−1)·( b−1⊕c−1)

with: a−1=0, b−1=0, c−1=0.

This case remains true irrespective of the iteration of the method.

An alternative embodiment of the initialization module, in connection with FIG. 3, will now be introduced, as shown in FIG. 2 according to an embodiment of the invention. This alternative, in particular, enables the initialization step of the method to be optimally implemented.
More particularly, the initialization module 300 shown in this figure performs an addition of three bit values an, bn and cn derived from any three input binary numbers A, B, C, and generates as output a value U1n, known as the value of the bit of rank n of the estimation signal U1 obtained during iteration 1, and a value R1n+1 known as the value of the n bit of rank n+1 of the correction signal R1 obtained during iteration 1.
A first logic gate of the “XNOR” type receives the bit of rank n values of the input binary numbers an and bn and generates as output an intermediate digital signal 301. A logic gate of the “Exclusive OR” type, likewise called “XOR”, receives the intermediate signal 301 as well as the bit value of rank n of the third binary number cn, and delivers the n-position value U1n.
A second logic gate of the “XNOR” type receives the bit values of rank n of the input binary numbers bn and cn, and generates as output a second intermediate digital signal 302. The “AND” gate receives the two intermediate digital signals 301 and 302, respectively, so as to furnish the value R1n+1 of rank n+1.
It is clear that this alternative likewise enables the initialization step to be implemented, likewise according to the aforesaid equations (3).
Furthermore, it is obvious that other logic architectures (different from that of FIG. 2 or FIG. 3) can easily be anticipated by a person skilled in the art in order to implement the equations (3), while at the same time remaining within the scope of an embodiment of this invention.
An explanation, in the form of equations, of the shift from the prior art to the initialization module in “U/R” form will be found in Appendix 1, and, in Appendix 2, an explanation will be found, in the form of equations, of the shift from the initialization module in “U/R” form to the accumulation module in “U/R” form.
An example of an initialization device 400 will now be shown in connection with FIG. 4, which enables three binary numbers expressed on 16 bits to be processed.
More precisely, this involves adding three standard binary numbers A, B and C each defined on 16 bits (N=16). To accomplish this, sixteen initialization modules 401 to 416, as described above in connection with FIG. 2 or FIG. 3, are assembled in parallel, so as to comprise a device 400 for executing the initialization step on 16 bits. For each bit of rank n, an initialization module 401 to 416 receives the bit values of rank n of each of the three binary numbers an, bn, cn, with n included between 0 and 15. It delivers as output the estimation U1n and correction R1n−1 values of bit of rank n and n+1, respectively, according to the equations (3) defined in FIG. 2, and expressed on 16 bits in this example.
In this particular embodiment, it bears noting that, for the bit of rank n=0, the predetermined initialization value corresponding to the correction signal R1 is initialized at 1 because it is not generated due to the fact that the modules do not generate a correction value for a rank n+1.
An example of an accumulation device 500, according to the embodiment shown in FIG. 1, will now be introduced in connection with FIG. 5, enabling binary numbers expressed on 16 bits to be processed, and more particularly enabling an additional binary number to be processed.
This involves adding an additional standard binary number C of 16 bits to the estimation Ui and correction Ri signals obtained previously for any iteration of index i, which are likewise expressed on 16 bits. To accomplish this, sixteen accumulation modules 501 to 516, as described above in connection with FIG. 1, are assembled in parallel so as to comprise the device 500 for executing the accumulation phase on 16 bits for a given iteration i. Each accumulation module 501 to 516 (i.e., for each rank n) receives as input the value of the bit cn of rank n, the value of the bit of rank n of the estimation signal Ui, the value of the bit of rank n of the correction signal Ri as well as the value of the value of the bit of preceding rank n−1 of the estimation signal Ui, n likewise being included between 0 and 15. Each accumulation module delivers as output the estimation Ui+1n and correction Ri+1n+1 values of bit of rank n and n+1, respectively, in accordance with the aforesaid equations (1) in connection with FIG. 1, and expressed on 16 bits in this drawing.
Reference is made to FIG. 6 now, which describes an alternative embodiment of the accumulation module shown in FIG. 1 according to the invention, and which likewise implements the accumulation method according to an embodiment of the invention.
As a matter of fact, instead of computing the estimation Ui+1n and correction Ri+1n+1 values, consideration can be given only to Ui+1n and an intermediate variable referenced as Hi+1n+1, defined such that:

Hin+1=R1n+1⊕U1n 

Starting with the equations (3) of FIG. 3, enabling the summation of three binary numbers A, B and C, namely:




  
    
      
        {
        
          
            
              
                
                  U
                  n
                  1
                
                =
                
                  
                    
                      a
                      n
                    
                    ⊕
                    
                      b
                      n
                    
                    ⊕
                    
                      c
                      n
                    
                  
                  _
                
              
            
          
          
            
              
                
                  R
                  
                    n
                    +
                    1
                  
                  1
                
                =
                
                  
                    (
                    
                      
                        
                          a
                          n
                        
                        ⊕
                        
                          b
                          n
                        
                      
                      _
                    
                    )
                  
                  ⁢
                  
                    (
                    
                      
                        
                          b
                          n
                        
                        ⊕
                        
                          c
                          n
                        
                      
                      _
                    
                    )
                  
                
              
            
          
        
      
    
    
      
        (
        3
        )
      
    
  




the following equations are obtained using the equality:




  
    
      H
      
        n
        +
        1
      
      1
    
    =
    
      
        R
        
          n
          +
          1
        
        1
      
      ⊕
      
        
          U
          n
          1
        
        ⁢
        
          :
        
      
    
  




  
    {
    
      
        
          
            
              
                U
                n
                1
              
              =
              
                
                  
                    a
                    n
                  
                  ⊕
                  
                    b
                    n
                  
                  ⊕
                  
                    c
                    n
                  
                
                _
              
            
          
        
        
          
            
              
                H
                
                  n
                  +
                  1
                
                1
              
              =
              
                
                  
                    (
                    
                      
                        
                          a
                          n
                        
                        ⊕
                        
                          b
                          n
                        
                      
                      _
                    
                    )
                  
                  ⁢
                  
                    (
                    
                      
                        
                          b
                          n
                        
                        ⊕
                        
                          c
                          n
                        
                      
                      _
                    
                    )
                  
                
                ⊕
                
                  
                    
                      a
                      n
                    
                    ⊕
                    
                      b
                      n
                    
                    ⊕
                    
                      c
                      n
                    
                  
                  _
                
              
            
          
        
      
      ,
    
  



and after simplification:





  {
  
    
      
        
          
            
              U
              n
              1
            
            =
            
              
                
                  a
                  n
                
                ⊕
                
                  b
                  n
                
                ⊕
                
                  c
                  n
                
              
              _
            
          
        
      
      
        
          
            
              H
              
                n
                +
                1
              
              1
            
            =
            
              
                
                  (
                  
                    
                      
                        a
                        n
                      
                      ⊕
                      
                        b
                        n
                      
                    
                    _
                  
                  )
                
                ⁢
                
                  (
                  
                    
                      b
                      n
                    
                    ⊕
                    
                      c
                      n
                    
                  
                  )
                
              
              ⊕
              
                c
                n
              
            
          
        
      
    
    .
  




The equations (1), for in iteration of index 1, for example, namely:





   
  
    {
    
      
        
          
            
              U
              n
              1
            
            =
            
              
                U
                n
                0
              
              ⊕
              
                R
                n
                0
              
              ⊕
              
                U
                
                  n
                  -
                  1
                
                0
              
              ⊕
              
                c
                n
              
            
          
        
      
      
        
          
            
              R
              
                n
                -
                1
              
              1
            
            =
            
              
                (
                
                  
                    U
                    n
                    0
                  
                  ⊕
                  
                    R
                    n
                    0
                  
                  ⊕
                  
                    U
                    
                      n
                      -
                      1
                    
                    0
                  
                
                )
              
              ·
              
                (
                
                  
                    U
                    n
                    0
                  
                  ⊕
                  
                    c
                    n
                  
                
                )
              
            
          
        
      
    
  




then become the following equations:





  
    
      
        {
        
          
            
              
                
                  U
                  n
                  1
                
                =
                
                  
                    U
                    n
                    0
                  
                  ⊕
                  
                    R
                    n
                    0
                  
                  ⊕
                  
                    U
                    
                      n
                      -
                      1
                    
                    0
                  
                  ⊕
                  
                    c
                    n
                  
                
              
            
          
          
            
              
                
                  H
                  
                    n
                    +
                    1
                  
                  1
                
                =
                
                  
                    
                      (
                      
                        
                          U
                          n
                          0
                        
                        ⊕
                        
                          R
                          n
                          0
                        
                        ⊕
                        
                          U
                          
                            n
                            -
                            1
                          
                          0
                        
                      
                      )
                    
                    ·
                    
                      (
                      
                        
                          U
                          n
                          0
                        
                        ⊕
                        
                          c
                          n
                        
                      
                      )
                    
                  
                  ⊕
                  
                    U
                    n
                    0
                  
                  ⊕
                  
                    R
                    n
                    0
                  
                  ⊕
                  
                    U
                    
                      n
                      -
                      1
                    
                    0
                  
                  ⊕
                  
                    c
                    n
                  
                
              
            
          
        
      
    
    
      
        (
        4
        )
      
    
  
  
    
      
        {
        
          
            
              
                
                  U
                  n
                  1
                
                =
                
                  
                    U
                    n
                    0
                  
                  ⊕
                  
                    R
                    n
                    0
                  
                  ⊕
                  
                    U
                    
                      n
                      -
                      1
                    
                    0
                  
                  ⊕
                  
                    c
                    n
                  
                
              
            
          
          
            
              
                
                  H
                  
                    n
                    +
                    1
                  
                  1
                
                =
                
                  
                    
                      (
                      
                        
                          U
                          n
                          0
                        
                        ⊕
                        
                          R
                          n
                          0
                        
                        ⊕
                        
                          U
                          
                            n
                            -
                            1
                          
                          0
                        
                      
                      )
                    
                    ·
                    
                      (
                      
                        
                          
                            U
                            n
                            0
                          
                          ⊕
                          
                            c
                            n
                          
                        
                        _
                      
                      )
                    
                  
                  ⊕
                  
                    c
                    n
                  
                
              
            
          
        
      
    
    
      
        
      
    
  




Thus, for any iteration of index i, the following generic equations (5) are obtained:





  
    
      
        {
        
          
            
              
                
                  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
                  
                
              
            
          
        
      
    
    
      
        (
        5
        )
      
    
  




Based on the same principle as for the accumulation module of FIG. 1, and for a given bit of rank n, this alternative accumulation module 600 enables a standard binary number C to be added to the estimation Ui and correction Hi signals derived from an iteration i and to once again provide a result in redundant binary form, namely an iteration of index i+1 estimation Ui+1 and correction Hi+1 signal.
According to this alternative accumulation module architecture, it is possible to generate as output from the module 600, a value of the bit of rank not the estimation signal Ui+1 and a value of the bit of rank n+1 of the correction signal Hi+1 from the following values obtained during a preceding iteration of index i of the accumulation step: Uin−1 a value of the bit of rank n−1 of an estimation signal Ui, Hin a value of the bit of rank n of the correction signal Hi and cn the value of the bit of rank n of a standard binary number C.
More precisely, the values Uin−1 and Hin derived from the preceding iteration i, are received by a first logic gate of the “Exclusive OR” type, also called an “XOR” gate, providing an intermediate digital signal 601. A second “XOR” gate in turn receives the intermediate digital signal 601 and the bit value cn of the additional binary number C, and generates as output the value Ui+1n, known as the value of the bit of rank n of the estimation signal Ui+1, obtained during an iteration of index i+1.
The values Uin−1 and cn are received as input by an “XNOR” gate and deliver as output an intermediate digital signal 602. An “AND” type logic gate next receives the two intermediate signals 601 and 602 and in order to deliver an intermediate digital signal 603. Finally, the third “XOR” gate receives the intermediate signal 603 and the value cn of the binary number C, and delivers the value Hi+1n+1, known as the value of the bit of rank n+1 of the correction signal Hi+1 obtained during said iteration of index i+1.
Consequently, the estimated bits Ui+1n and the corrected bits Hi+1n+1 obtained during an iteration of index i+1 are determined from the following generic equations (5):




  
    
      
        {
        
          
            
              
                
                  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
                  
                
              
            
          
        
      
    
    
      
        (
        5
        )
      
    
  




with:

    Ui+1n: a value of the n bit of rank n of the estimation signal Ui+1, with 0≦n≦N−1, obtained during an iteration of index i+1;
    Uin: a value of the bit of rank n of the estimation signal Ui, obtained during a preceding iteration of index i if i>0, or a specific 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 specific 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;
    
    
    Hin: a value of the bit of rank n of a second correction signal Hi, obtained during the 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 the 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 the addition, during the iteration of index i+1 of the accumulation step.


It is clear that other logic architectures (different from that of FIG. 6) can easily be anticipated by a person skilled in the art in order to implement the generic equations (5), while at the same time remaining within the scope of an embodiment of this invention.
An logic architecture 700 will now be introduced in connection with FIG. 7, for an initialization module which is capable of being implemented by the alternative embodiment of FIG. 6 of an initialization module according to a particular embodiment implementing the initialization step of the method according to an embodiment of the invention.
The initialization module 700 includes a first sub-module 701, called a pre-computation module, and a second sub-module 702, called an initial accumulation module. More precisely, the pre-computation module 701, unlike the initialization module 200 of FIG. 2, has a single logic gate of the “INV” type, which is capable of receiving the bit value of rank n of inputs an generating as output an initial bit value U0n of rank n. As a matter of fact, by returning to the equations (4) and by establishing the following equalities for the pre-computation module 701, namely:

Hn0=Rn0⊕Un−10 with Un−10= an−1 and Rn0= an−1⊕bn,

the equations for the pre-computation module can be simplified: Hn0=bn and Un0= an.

In this architecture, the pre-computation module 701 is situated upstream from the initial accumulation module 702. The latter, as described in FIG. 6, enables the bit value of rank n of an additional binary number referenced as cn to be added to the estimation Uin−1 and correction Hin bit values of rank n−1 and n, respectively. Since the iteration is of index 0, the input values of the module 702 are therefore U0n−1 and H0n.
Furthermore, since the principle and architecture of module 702 are identical to the accumulation module 600 of FIG. 6, the values obtained as output from initialization module are therefore incremented by an index having a value of 1. In this way, the estimation U1n, and correction Hin+1 values are obtained for the n and bit of rank n+1, respectively, as defined by the following equations:




  {
  
    
      
        
          
            
              U
              n
              1
            
            =
            
              
                U
                n
                0
              
              ⊕
              
                R
                n
                0
              
              ⊕
              
                U
                
                  n
                  -
                  1
                
                0
              
              ⊕
              
                c
                n
              
            
          
        
      
      
        
          
            
              H
              
                n
                +
                1
              
              1
            
            =
            
              
                
                  (
                  
                    
                      U
                      n
                      0
                    
                    ⊕
                    
                      R
                      n
                      0
                    
                    ⊕
                    
                      U
                      
                        n
                        -
                        1
                      
                      0
                    
                  
                  )
                
                ·
                
                  (
                  
                    
                      
                        U
                        n
                        0
                      
                      ⊕
                      
                        c
                        n
                      
                    
                    _
                  
                  )
                
              
              ⊕
              
                
                  c
                  n
                
                .
              
            
          
        
      
    
     
  




Accordingly, module 700 enables the following equations to be implemented:




  
    
      
        {
        
          
            
              
                
                  U
                  n
                  1
                
                =
                
                  
                    
                      a
                      n
                    
                    ⊕
                    
                      b
                      n
                    
                    ⊕
                    
                      c
                      n
                    
                  
                  _
                
              
            
          
          
            
              
                
                  H
                  
                    n
                    +
                    1
                  
                  1
                
                =
                
                  
                    
                      (
                      
                        
                          
                            a
                            n
                          
                          ⊕
                          
                            b
                            n
                          
                        
                        _
                      
                      )
                    
                    ⁢
                    
                      (
                      
                        
                          b
                          n
                        
                        ⊕
                        
                          c
                          n
                        
                      
                      )
                    
                  
                  ⊕
                  
                    c
                    n
                  
                
              
            
          
        
      
    
    
      
        (
        6
        )
      
    
  




It is clear that other logic architectures (different from that of FIG. 7) can easily be anticipated by a person skilled in the art, in order to implement the equations (6), while at the same time remaining with the scope of an embodiment of this invention.
Reference will now be made to FIG. 8, which describes an alternative embodiment of the initialization module shown in FIG. 7. This alternative is considered to enable optimal implementation of the initialization step of the method.
More particularly, the initialization module 800 shown in this figure adds three bit values an, bn and cn, derived from any three input binary numbers A, B, C. As output, it generates a value U1n known as the bit value of rank n of the estimation signal U1 obtained during iteration 1, and a value R1n+1 known as the bit value of rank n+1 of the correction signal R1, likewise obtained during iteration 1.
To accomplish this, a first logic gate of the “XNOR” type receives the bit values of rank n of the input binary numbers an and bn, and generates, as output, an intermediate digital signal 801. A logic gate of the “XOR” type receives the intermediate signal 801 as well as the bit value of rank n of the third binary number cn, and delivers the bit value U1n of rank n identically to the initialization module 300 of FIG. 3.
Furthermore, a second logic gate of the “XOR” type receives the bit values of rank n bn and cn and generates as output a second intermediate digital signal 802. The “AND” gate receives the two intermediate digital signals, 801 and 802, respectively, and generates a third intermediate signal 803. The latter is used with the value cn, by means of a third “XOR” gate so as to provide the value H1n+1 of rank n+1.
A block diagram of a parallel multi-operand adder according to a particular embodiment in accordance with the invention will now be presented in connection with FIG. 9. More precisely, this adder adds seven binary numbers, referenced as E1 to E7, each binary number being expressed on 16 bits.
In this particular embodiment, a first computation stage is introduced, which consists of the initialization device 400, as described above in connection with FIG. 3, which computes the sum of three binary numbers E1, E2 and E3, and enables the two estimation U10-15 and correction R11-15 signals, of iteration i=1, represented in a “U/R” type redundant form, to be provided as output.
A second computation stage consisting of the accumulation device 500, as described above in connection with FIG. 5, receives, as input, the estimation U10-15 and correction R11-15 signals derived from the preceding device 400 (i=1) and an additional binary number E4 on 16 bits. This second stage generates, as output, two estimation U20-15 and correction R21-15 signals, of index iteration 2, and likewise represented in a “U/R” type redundant form. In the same way, three other stages 500 are added so as to be capable of adding, at each computation stage (i.e., at each iteration of index i), one of the three remaining additional binary numbers, namely E5 (for the iteration of index 3), E6 (for the iteration if index 4) and E7 (for the iteration of index 5).
In the end, the last estimation U50-15 and correction R51-15 signals derived from last stage (iteration of index 5) are received by a “Carry-Look-Ahead” or “Ripple-Carry” type adder 901 customized so as to obtain the result S0-15 of the seven binary numbers added, in standard binary form, from the signals represented in a “U/R” type redundant binary form. The computation details concerning this final sum are described in the international patent WO2007122318 (TORNO).
It is to be noted that the values Ri0 and Ui−1 are the predetermined bit of rank n=0 of the correction signal and specific initialization values which, in this specific case, are equal to 1. As a matter of fact, since each module generates a correction signal Rin+1 of rank n+1 for an iteration of index i, the correction signal of rank n=0 and of iteration i is therefore nonexistent. The same is true for the fictive bit Ui−1.
Furthermore, it is to be noted that the bit values of rank 16, referenced as Ri16, are not used in this particular embodiment. As a matter of fact, the dynamics of expressing on 16 bits are sufficient for the accumulation of the seven binary numbers to be capable of being carried out without any overflow.
A block diagram of a sequential multi-operand adder according to a particular embodiment in accordance with the invention will now be introduced in connection with FIG. 10. More particularly, this adder adds seven binary numbers, referenced as E1 to E7, of 16 bits each. It can be used, in particular, within the framework, of digital filtering, for example.
In this particular embodiment, a single accumulation device 500 is required (as described in FIG. 5), and a register 1020 stores all of the intermediate accumulation results. The computation is done sequentially for i iterations, with i varying from 1 to 7.
In a first phase, the register 1030 containing signals U00-15 and the correction signals R01-15 is initialized so that each n bit value U00-15 and R01-16 has the value of 1, as well as U0−1, and R00.
In a second phase, the selection control for the multiplexer 1010 selects the input binary number E1 and a computation of index 1 (i+1 with i=0), which is then carried out. The accumulation device 500, consisting of 16 accumulation modules, adds the inputs U10-15, R11-16 on 16 bits and E1 in order to generate the values U10-15 and R11-16. The previously obtained values are then input into the 32-bit register and stored by the action of the clock. Then, the selection control of the multiplexer selects the next input E2.
It is to be noted that the values U1−1 and R10 are always equal to 1 irrespective of the accumulation computation step, in other words, irrespective of the iteration value i.
The actions of the preceding step are then repeated for i, ranging from 2 to 7, so as to be capable of adding all the inputs E2 to E7 to the intermediate results U10-15 and R11-16 to U60-15 and R61-16 to obtain the intermediate results U20-15 and R21-16 to U70.15 and R71-16.
Finally, a final computation is carried out by means of an adder. The intermediate result U70-15 and R71-15 corresponding to the last iteration (i=7) is input into an adder 901 of the “Carry-Look-Ahead” type or “Ripple-Carry” type, on 16 bits, which is adapted to receive as input a “U/R” redundant binary form, as described in the international patent WO2007122319 (TORNO). The bits U7−1 and R70 are initialized at 1. The adder 901 thus enables determination of the final result, in standard binary form, of the sum of the seven binary numbers E1 to E7.
It is to be noted that the bit values of rank 16, referenced as Ri16, are not likewise used in this particular embodiment. As a matter of fact, the expression dynamics on 16 bits is sufficient for the accumulation of the seven binary numbers to be capable of being carried out without any overflow.
FIG. 11 shows an example of digital computation of a summation of seven binary numbers, carried out by the multi-operand adder of FIG. 9. Each computation line is expressed on 16 bits of data and each estimation U and correction R signal is shown for each of the iterations of the method in accordance with an embodiment of the invention.
The final binary result S is likewise presented on 16 bits of data, the latter having been obtained in standard binary form.
It shall be noted that the invention is not limited to a purely hardware implementation, but that it can also be implemented in the form of a sequence of computer program instructions or any form combining a hardware portion and a software portion. In the case where the invention is partially or completely implemented in software form, the corresponding sequence of instructions may or may not be stored in a removable storage means (e.g., such as a diskette, a CD-ROM or a DVD-ROM), this storage means being partially or entirely readable by a computer or microprocessor.
At least one embodiment of the disclosure provides a technique for adding binary numbers using a “U/R” type redundant binary representation (thereby enabling the carry digits from being propagating onto intermediate computation results), which offers better performance levels than the aforesaid known technique described in the international application WO2007122319.
An embodiment likewise providing such a technique which enables more than two binary numbers to be summed.
An embodiment provides such a technique which enables the execution time for adding multiple binary numbers to be reduced. More precisely, one objective is to reduce the propagation time.
An embodiment provides such a technique enabling the number of logic gates required by the adder to be reduced so as to gain compactness and reduce the energy consumption thereof.
An embodiment provides such a technique which introduces improved testability, due, in particular, to a particular layout of “Exclusive OR” (EXOR) and “AND” gates.
An embodiment provides such a technique which facilitates the implementation of burn-in of the parity-check computations.
An embodiment provides such a technique which is simple to implement and inexpensive.
1. APPENDIX 1
Shift from the Prior Art to the Initialization Module in “U/R” Form
Given A, B and C as the three numbers that one wished to add, and which are expressed on N bits:




   
  
    {
    
      
        
          
            A
            =
            
              
                
                  a
                  
                    N
                    -
                    1
                  
                
                ·
                
                  2
                  
                    N
                    -
                    1
                  
                
              
              +
              ...
              +
              
                
                  a
                  n
                
                ·
                
                  2
                  n
                
              
              +
              ...
              +
              
                
                  a
                  1
                
                ·
                
                  2
                  1
                
              
              +
              
                
                  a
                  0
                
                ·
                
                  2
                  0
                
              
            
          
        
      
      
        
          
            B
            =
            
              
                
                  b
                  
                    N
                    -
                    1
                  
                
                ·
                
                  2
                  
                    N
                    -
                    1
                  
                
              
              +
              ...
              +
              
                
                  b
                  n
                
                ·
                
                  2
                  n
                
              
              +
              ...
              +
              
                
                  b
                  1
                
                ·
                
                  2
                  1
                
              
              +
              
                
                  b
                  0
                
                ·
                
                  2
                  0
                
              
            
          
        
      
      
        
          
            C
            =
            
              
                
                  c
                  
                    N
                    -
                    1
                  
                
                ·
                
                  2
                  
                    N
                    -
                    1
                  
                
              
              +
              ...
              +
              
                
                  c
                  n
                
                ·
                
                  2
                  n
                
              
              +
              ...
              +
              
                
                  c
                  1
                
                ·
                
                  2
                  1
                
              
              +
              
                
                  c
                  0
                
                ·
                
                  2
                  0
                
              
            
          
        
      
    
  




It is conventionally possible, in a first phase, to sum these three binary numbers and to obtain a result of the standard “Carry-Save” form by means of a network of “full-adder” type adders. This network of adders enables a partial sum and a partial carry-over to be generated as output, such that:




   
  
    {
    
      
        
          
            
              S
              n
            
            =
            
              
                a
                n
              
              ⊕
              
                b
                n
              
              ⊕
              
                c
                n
              
            
          
        
      
      
        
          
            
              Cy
              
                n
                +
                1
              
            
            =
            
              
                
                  a
                  n
                
                ·
                
                  b
                  n
                
              
              ⊕
              
                
                  c
                  n
                
                ·
                
                  (
                  
                    
                      a
                      n
                    
                    ⊕
                    
                      b
                      n
                    
                  
                  )
                
              
            
          
        
      
    
  




with:

Sn the partial sum in n, and

Cyn+1 the partial carry=−over in (n+1).

In order to obtain a representation in the “U/R” form non-obviously, the partial sum and the partial carry-over are considered to be 2 binary numbers to be added and the so-called initial estimation method described in the document WO2007122319 is described.
In this way, the following numbers U and R are obtained:




   
  
    {
    
      
        
          
            
              U
              n
            
            =
            
              
                S
                n
              
              _
            
          
        
      
      
        
          
            
              R
              
                n
                +
                1
              
            
            =
            
              
                
                  Cy
                  
                    n
                    +
                    1
                  
                
                ⊕
                
                  S
                  n
                
              
              _
            
          
        
      
    
  




By substituting the values for Sn and Cyn+1 with the expressions thereof as an, bn, cn, one obtains:




   
  
    {
    
      
        
          
            
              U
              n
            
            =
            
              
                
                  a
                  n
                
                ⊕
                
                  b
                  n
                
                ⊕
                
                  c
                  n
                
              
              _
            
          
        
      
      
        
          
            
              R
              
                n
                +
                1
              
            
            =
            
              
                
                  a
                  n
                
                ·
                
                  b
                  n
                
              
              ⊕
              
                
                  c
                  n
                
                ·
                
                  (
                  
                    
                      a
                      n
                    
                    ⊕
                    
                      b
                      n
                    
                  
                  )
                
              
              ⊕
              
                
                  
                    a
                    n
                  
                  ⊕
                  
                    b
                    n
                  
                  ⊕
                  
                    c
                    n
                  
                
                _
              
            
          
        
      
    
  




After expansion, the following two expressions are obtained:




   
  
    {
    
      
        
          
            
              U
              n
            
            =
            
              
                
                  a
                  n
                
                ⊕
                
                  b
                  n
                
                ⊕
                
                  c
                  n
                
              
              _
            
          
        
      
      
        
          
            
              R
              
                n
                +
                1
              
            
            =
            
              
                
                  (
                  
                    
                      a
                      n
                    
                    ⊕
                    
                      
                        b
                        n
                      
                      _
                    
                  
                  )
                
                ·
                
                  b
                  n
                
              
              ⊕
              
                
                  
                    c
                    n
                  
                  _
                
                ·
                
                  (
                  
                    
                      a
                      n
                    
                    ⊕
                    
                      b
                      n
                    
                  
                  )
                
              
              ⊕
              
                
                  c
                  n
                
                _
              
            
          
        
      
    
  




and after factorization, the following equations (3) implemented by the mechanism of this invention are obtained, namely:





  
    
      
        {
        
          
            
              
                
                  U
                  n
                
                =
                
                  
                    
                      a
                      n
                    
                    ⊕
                    
                      b
                      n
                    
                    ⊕
                    
                      c
                      n
                    
                  
                  _
                
              
            
          
          
            
              
                
                  R
                  
                    n
                    +
                    1
                  
                
                =
                
                  
                    (
                    
                      
                        
                          a
                          n
                        
                        ⊕
                        
                          b
                          n
                        
                      
                      _
                    
                    )
                  
                  ·
                  
                    (
                    
                      
                        
                          b
                          n
                        
                        ⊕
                        
                          c
                          n
                        
                      
                      _
                    
                    )
                  
                
              
            
          
        
      
    
    
      
        (
        3
        )
      
    
  




2. APPENDIX 2
Shift from the Initialization Module in “U/R” Form to the Accumulation Module in “U/R” Form
Starting with the same equations as previously, it is possible to construct an accumulation module enabling an estimation signal U, a correction signal R and a standard binary number c to be received as input. The computation details enabling determination of the result in “U/R” redundant form are set forth hereinbelow.
Starting with the aforesaid equations (3), it is possible, for example, to construct an initial form expressed in the following way from binary numbers A and B:




  {
  
    
      
        
          
            
              U
              n
              0
            
            =
            
              
                a
                n
              
              _
            
          
        
      
      
        
          
            
              R
              
                n
                +
                1
              
              0
            
            =
            
              
                
                  a
                  n
                
                ⊕
                
                  b
                  
                    n
                    +
                    1
                  
                
              
              _
            
          
        
      
    
    ⁢
    
      
    
    ⁢
    and
    ⁢
    
      
    
    ⁢
    
      {
      
        
          
            
              
                U
                
                  n
                  -
                  1
                
                0
              
              =
              
                
                  a
                  
                    n
                    -
                    1
                  
                
                _
              
            
          
        
        
          
            
              
                R
                n
                0
              
              =
              
                
                  
                    a
                    
                      n
                      -
                      1
                    
                  
                  ⊕
                  
                    b
                    n
                  
                
                _
              
            
          
        
      
    
  




The values an and bn can then be deduced, namely:




   
  
    {
    
      
        
          
            
              a
              n
            
            =
            
              
                U
                n
                0
              
              _
            
          
        
      
      
        
          
            
              b
              n
            
            =
            
              
                R
                n
                0
              
              ⊕
              
                U
                
                  n
                  -
                  1
                
                0
              
            
          
        
      
    
  




Then, by substituting the values of an and bn in the system of equations (1), the following expression is obtained:




   
  
    {
    
      
        
          
            
              U
              n
              1
            
            =
            
              
                
                  U
                  n
                  0
                
                _
              
              ⊕
              
                (
                
                  
                    R
                    n
                    0
                  
                  ⊕
                  
                    U
                    
                      n
                      -
                      1
                    
                    0
                  
                
                )
              
              ⊕
              
                
                  c
                  n
                
                _
              
            
          
        
      
      
        
          
            
              R
              
                n
                +
                1
              
              1
            
            =
            
              
                (
                
                  
                    
                      U
                      n
                      0
                    
                    _
                  
                  ⊕
                  
                    (
                    
                      
                        
                          R
                          n
                          0
                        
                        ⊕
                        
                          U
                          
                            n
                            -
                            1
                          
                          0
                        
                      
                      _
                    
                    )
                  
                
                )
              
              ·
              
                (
                
                  
                    (
                    
                      
                        R
                        n
                        0
                      
                      ⊕
                      
                        U
                        
                          n
                          -
                          1
                        
                        0
                      
                    
                    )
                  
                  ⊕
                  
                    
                      c
                      n
                    
                    _
                  
                
                )
              
            
          
        
      
    
  




After expansion and simplification, the two following expressions are obtained:




   
  
    {
    
      
        
          
            
              U
              n
              1
            
            =
            
              
                U
                n
                0
              
              ⊕
              
                R
                n
                0
              
              ⊕
              
                U
                
                  n
                  -
                  1
                
                0
              
              ⊕
              
                c
                n
              
            
          
        
      
      
        
          
            
              R
              
                n
                +
                1
              
              1
            
            =
            
              
                (
                
                  
                    U
                    n
                    0
                  
                  ⊕
                  
                    R
                    n
                    0
                  
                  ⊕
                  
                    U
                    
                      n
                      -
                      1
                    
                    0
                  
                
                )
              
              ·
              
                (
                
                  
                    U
                    n
                    0
                  
                  ⊕
                  
                    c
                    n
                  
                
                )
              
            
          
        
      
    
  




If the computation is no longer generalized at index 1 but rather at index i+1, then, accordingly, for any index i+1, the following generic equations (1) are obtained:




  
    
      
        {
        
          
            
              
                
                  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
                      
                    
                    )
                  
                
              
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




Although the present disclosure has been described with reference to one or more examples, workers skilled in the art will recognize that changes may be made in form and detail without departing from the scope of the disclosure and/or the appended claims.

## Claims

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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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 .

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

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.