Floating point computation apparatus and method

A method comprises receiving a first N-bit unsigned number and a second N-bit unsigned number, receiving a control signal indicating a m-bit shifting operation and processing the first N-bit unsigned number, the second N-bit unsigned number and the control signal in an add-and-shift apparatus, wherein an addition/subtraction operation and the m-bit shifting operation are performed in parallel in the add-and-shift apparatus.

TECHNICAL FIELD

The present invention relates to central processing unit and digital signal processor designs, and, in particular embodiments, to a floating point addition and subtraction apparatus and method.

BACKGROUND

Floating-point arithmetic operations are widely used in digital applications such as Central Process Unit (CPU), Digital Signal Processor (DSP) and/or the like. A real number can be written in floating-point representation. For example, a real number ‘a’ can be expressed by the following equation:
a=(−1)S·Ma·bq(1)
where S is the sign of the real number ‘a’; Ma is the mantissa of the real number ‘a’; b is the base (2 or 10) of the real number and q is the exponent of the real number ‘a’.

Floating-point arithmetic operations such as an addition/subtraction process may be carried out by a variety of logic circuits. An addition/subtraction process may include computing the exponent difference of two real numbers, aligning these two real numbers based upon the exponent difference (e.g., shifting the real number with the smaller exponent to the right), adding/subtracting the aligned mantissas, normalizing the result by shifting the result to the left a number of positions equal to the number of the leading zeros and rounding the result in accordance with a specified rounding mode.

SUMMARY OF THE INVENTION

These and other problems are generally solved or circumvented, and technical advantages are generally achieved, by preferred embodiments of the present invention which provide an apparatus and method for computing two binary numbers such as an addition operation, a subtraction operation and/or the like.

In accordance with an embodiment, an apparatus comprises an input block configured to receive a first N-bit unsigned number and a second N-bit unsigned number, wherein the input block comprises N propagate and generate cells.

The apparatus further comprises a plurality of calculation cells arranged in rows and columns, wherein the number of the columns is equal to N and the number of the rows is equal to log2(N), wherein each row has N cells and has an index ri, and wherein a variable d is equal to 2ri, and wherein each calculation cell has three groups of inputs connected to three cells in a preceding row, and wherein a first group of inputs are connected to outputs of a first calculation cell in the preceding row and vertically aligned with the calculation cell, a second group of inputs are connected to outputs of a second calculation cell that is d cells away from the first calculation cell and a third group of inputs are connected to outputs of a third calculation cell that is 2d cells away from the first calculation cell and an output block comprising a plurality of XOR gates.

In accordance with another embodiment, a system comprises an input block configured to receive a first N-bit unsigned number, a second N-bit unsigned number and a control signal, wherein the input block comprises N propagate and generate cells, a plurality of calculation cells arranged in rows and columns and coupled to the input block, wherein the calculation cells are configured to perform an add operation and a shifting operation based upon the control signal, and the add operation and the shifting operation are applied in parallel to the first N-bit unsigned number and the second N-bit unsigned number and an output block comprising a plurality of XOR gates coupled to a last row of the plurality of calculation cells.

In accordance with yet another embodiment, a method comprises receiving a first N-bit unsigned number and a second N-bit unsigned number, receiving a control signal indicating a m-bit shifting operation and processing the first N-bit unsigned number, the second N-bit unsigned number and the control signal in an add-and-shift apparatus, wherein an addition or subtraction operation and the m-bit shifting operation are performed in parallel in the add-and-shift apparatus.

An advantage of a preferred embodiment of the present invention is to achieve fast computation of two binary numbers through an add-and-shift apparatus having (3·log2(N)+4) levels of 2-input NAND gates. Such an apparatus helps to reduce the logic gate delay, thereby improving the efficiency of floating-point arithmetic operations.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

The present invention will be described with respect to preferred embodiments in a specific context, namely an addition/subtraction apparatus in digital circuit applications. The invention may also be applied, however, to a variety of floating-point arithmetic operations in applications such as Central Processing Unit (CPU), Digital Signal Processing (DSP) and/or the like. Hereinafter, various embodiments will be explained in detail with reference to the accompanying drawings.

FIG. 1illustrates a block diagram an add-and-shift apparatus in accordance with various embodiments of the present disclosure. The add-and-shift apparatus100has four inputs and an output as shown inFIG. 1. The first input A is configured to receive a first unsigned number in binary format. In some embodiments, the first unsigned number has n bits ranging from bit0to bit (n−1). The binary representation of the first unsigned number is A[0:n−1]. The second input B is configured to receive a second unsigned number in binary format. The second unsigned number has n bits ranging from bit0to bit (n−1). The binary representation of the second unsigned number is B[0:n−1]. In some embodiments, the first unsigned number and the second unsigned number are aligned matissas to be added or subtracted.

The third input is configured to receive an initial carry cin indicating addition and subtraction operations. More particularly, cin is set to 0 in binary notation when an addition operation is performed on the first unsigned number and the second unsigned number. On the other hand, cin is set to 1 in binary notation when a subtraction operation is performed on the first unsigned number and the second unsigned number. The fourth input is configured to receive a control signal Sel.

The control signal Sel is employed to provide the shifting value in the addition/subtraction operations. In some embodiments, the shifting value is generated by a Leading Zero Anticipation/Leading Zero Detection (LZA/LZD) unit. The LZA/LZD unit may be part of a floating point (FP) arithmetic circuit including the add-and-shift apparatus100. The operation principles of the LZA/LZD unit are well known in the art, and hence are not discussed in further detail herein to avoid unnecessary repetition.

The control signal Sel has m bits ranging from bit0to bit (m-1). In some embodiments, m is given by the following equation:
m=log2(n)   (2)
where n is the number of bits of the first unsigned number.

The output of the add-and-shift apparatus100carries out the addition or subtraction of the two n-bit unsigned numbers. The output of the add-and-shift apparatus100generates a number in binary format. The output Out has (n+1) bits ranging from bit0to bit n. Based upon the control signal Sel, the output Out[0:n] has been normalized by shifting left to eliminate the leading zeros. The shifting operations and the addition/subtraction operations are performed in parallel in the add-and-shift apparatus100. The longest delay path of the add-and-shift apparatus100is equal to (3·m+4) levels of 2-input NAND gates.

The add-and-shift apparatus100comprises one row of Propagate (P) and Generate (G) modules and m rows of Propagate and Shift (PS) units and Generate and Shift (GS) units. The PS units and GS units are not only used to carry out the addition/subtraction operations, but also used to enable the shifting operations. More particularly, the shifting operations are performed in parallel with the addition/subtraction operations. The detailed operation principles and schematic diagrams of the add-and-shift apparatus100will be described below in detail with respect toFIGS. 2-13.

FIG. 2illustrates a block diagram an 8-bit add-and-shift apparatus in accordance with various embodiments of the present disclosure. The 8-bit add-and-shift apparatus200receives two unsigned 8-bit numbers (e.g., A and B shown inFIG. 2) and generates a 9-bit output number Out. The 8-bit add-and-shift apparatus200includes four rows, namely row201, row210, row211and row212. As shown inFIG. 2, these four rows include a plurality of cells. These cells are arranged in columns and rows. The index of the columns shown inFIG. 2ranges from 0 to 7.

Row201includes eight Propagate and Generate cells, each of which comprises two inputs coupled to two corresponding bits of the two unsigned 8-bit numbers. For example, the fourth cell of row201receives two input bits A(3) and B(3) respectively and generates G(0,3) and P(0,3). The detailed schematic diagram of the Propagate and Generate cells will be described below with respect toFIG. 3.

Row210includes eight cells, each of which is vertically aligned with a corresponding Propagate and Generate cell in row201. The corresponding Propagate and Generate cell in row201is referred to as the preceding cell because it is placed above the cell in row210and vertically aligned with the cell in row210. For example, the fourth cell of row201is the preceding cell of the fourth cell (cell GS(0,3) and PS(0,3)) of row210.

Each cell of row210includes a Propagate and Shift (PS) unit and a Generate and Shift (GS) unit. The schematic diagram of the PS units and GS units of row210will be described below in detail with respect toFIG. 5andFIG. 7respectively.

Each cell of row210has three inputs connected to the outputs of the cells of row201. A first input of a cell (e.g., cell including GS(0,7) and PS(0,7)) is connected to the output of the preceding cell (e.g., cell including G(0,7) and P(0,7)). The second input of the cell (e.g., cell including GS(0,7) and PS(0,7)) is connected to the output of a cell immediately next to the preceding cell. In other words, the second input of the cell is connected to the output of a cell (e.g., cell including G(0,6) and P(0,6)) that is one cell away from the preceding cell. The third input of the cell (e.g., cell including GS(0,7) and PS(0,7)) is connected to the output of a cell (e.g., cell including G(0,5) and P(0,5)) that is two cells away from the preceding cell.

In sum, each cell of row210is connected to its preceding cell in row201, a first cell in row201having d positions away from the preceding cell and a second cell in row201having 2d positions away from the preceding cell. In some embodiments, d is equal to 2ri, where ri is the row index of row210. Row210has a row index of 0. As a result, in row210, each cell has inputs connected to its preceding cell, a first cell having one cell away from the preceding cell and a second cell having two cells away from the preceding cell. According to this connection principle, some inputs of the first cell and second cell of row210are connected to cells that do not exist. These inputs of the first cell and second cell of row210are set to 0 as shown inFIG. 2.

Row211includes eight cells, each of which is vertically aligned with a corresponding cell in row210. The corresponding cell in row210is referred to as the preceding cell because it is placed above the cell in row211and vertically aligned with the cell in row211. Each cell of row211includes a PS unit and a GS unit. The schematic diagram of the PS units and GS units of row211will be described below in detail with respect toFIG. 4andFIG. 6respectively.

Row211has a row index of 1. As a result, d of row211is equal to 2. As shown inFIG. 2, each cell of row211has three inputs. A first input of a cell (e.g., cell including GS(1,7) and PS(1,7)) is connected to the output of the preceding cell (e.g., cell including GS(0,7) and PS(0,7)) in row210. The second input of the cell (e.g., cell including GS(1,7) and PS(1,7)) is connected to the output of a cell (e.g., cell including GS(0,5) and PS(0,5)) that is two cells (d=2) away from the preceding cell(e.g., cell including GS(0,7) and PS(0,7)). The third input of the cell (e.g., cell including GS(1,7) and PS(1,7)) is connected to the output of a cell (e.g., cell including GS(0,3) and PS(0,3)) that is four cells (2d=4) away from the preceding cell. Some inputs of the cells in row211are connected to cells that do not exist. These inputs are set to 0 as shown inFIG. 2.

Row212includes eight cells, each of which is vertically aligned with a corresponding cell in row211. The corresponding cell in row211is referred to as the preceding cell. Each cell of row212includes a GS unit. The schematic diagram of the GS units of row212will be described below in detail with respect toFIG. 6.

Row212has a row index of 2. As a result, d of row211is equal to 4. As shown inFIG. 2, each cell of row212has three inputs. A first input of a cell (e.g., cell including GS(2,7)) is connected to the output of the preceding cell (e.g., cell including GS(1,7) and PS(1,7)) in row211. The second input of the cell (e.g., cell including GS(2,7)) is connected to the output of a cell (e.g., cell including GS(1,3) and PS(1,3)) that is four cells (d=4) away from the preceding cell (e.g., cell including GS(1,7) and PS(1,7)). The third input of the cell (e.g., cell including GS(2,7)) is connected to the output of a cell that is eight cells (2d=8) away from the preceding cell. Since the cell connected to the third input does not exist, the third input of the cell including GS(2,7) is set to 0 as shown inFIG. 2. Likewise, some inputs of the other cells in row212are connected to cells that do not exist. These inputs in row212are set to 0 as shown inFIG. 2.

The 8-bit add-and-shift apparatus200further comprises an output block220. The output block220comprises nine exclusive OR (XOR) gates. As shown inFIG. 2, a first XOR gate has a first input connected to an output of a barrel shifter214and a second input connected to GS(2,−1). As shown inFIG. 2, GS(2,−1) is generated by a logic circuit comprising a plurality of logic gates. The logic gates receive an initial carry cin indicating addition and subtraction operations and 3 bits of the control signal Sel (e.g., Sel(0), Sel(1) and Sel(2)) indicating the shifting value in the addition/subtraction operations, and generate GS(0,−1), GS(1,−1) and GS(2,−1) as shown inFIG. 2.

The other XOR gates of the output block220have a first input connected to an output of a preceding cell in row212and a second input connected to a corresponding bit of the output of the barrel shifter214. The detailed schematic diagrams of the output block220and barrel shifter214will be described below with respect toFIGS. 12-13.

It should be noted thatFIG. 2illustrates only eight cells in each row that may include hundreds of such cells. The number of cells in each row illustrated herein is limited solely for the purpose of clearly illustrating the inventive aspects of the various embodiments. The various embodiment of the present application are not limited to any specific number of cells in each row.

Furthermore, the diagram shown inFIG. 2is merely an example, which should not unduly limit the scope of the claims. One of ordinary skill in the art would recognize many variations, alternatives, and modifications. For example, the 8-bit add-and-shift apparatus200illustrated inFIG. 2is simply one embodiment and that other configurations for an add-and-shift apparatus, including an arithmetic operation with a different number of bits, can be employed.

FIG. 3illustrates a schematic diagram of the Propagate and Generate cells shown inFIG. 2in accordance with various embodiments of the present disclosure. The Propagate and Generate cell300includes an AND gate302and a XOR gate304. The Propagate and Generate cell300has a first input connected to A(ci) where ci represents a bit of the first unsigned number A, and a second input connected to B(ci), which is a corresponding bit of the second unsigned number B. Both A(ci) and B(ci) are fed into the AND gate302. The output of the AND gate302is G(0,ci). Likewise, Both A(ci) and B(ci) are fed into the XOR gate304. The output of the XOR gate304is P(0,ci).

FIG. 4illustrates a schematic diagram of the PS units shown inFIG. 2in accordance with various embodiments of the present disclosure. The PS unit400a NOT gate402, a first AND gate404, a second AND gate406and an OR gate408.

The PS unit400has four inputs, namely Sel(ri), PS(ri−1,ci), PS(ri-1,ci-d) and PS(ri-1,ci-2d) where ri represents the index of the row where the PS unit is located; ci represents the index of the column where the PS unit is located; d is a variable. In some embodiments, d is given by the following equation:
d=2ri(3)

As shown inFIG. 4, the first AND gate404has three inputs. The first input of the first AND gate404is connected to Sel(ri) through the NOT gate402. The second input and third input of the first AND gate404are connected to PS(ri-1,ci) and PS(ri-1,ci-d) respectively. The second AND gate406has three inputs. The first input of the second AND gate406is connected to Sel(ri). The second input and third input of the second AND gate406are connected to PS(ri-1,ci-d) and PS(ri-1,ci-2d) respectively. The outputs of the first AND gate404and the second AND gate406are fed into the OR gate408. The output of the OR gate408generates PS(ri,ci).

FIG. 5illustrates a schematic diagram of the PS units in the first row of the 8-bit add-and-shift apparatus shown inFIG. 2in accordance with various embodiments of the present disclosure. The schematic diagram of the PS unit500is similar to that of the PS unit400shown inFIG. 4except that the inputs of PS unit500are connected to P(0,ci), P(0,ci-1) and P(0,ci-2) respectively. It should be noted that P(0,ci), P(0,ci-1) and P(0,ci-2) are generated by the Propagate and Generate cells shown inFIG. 3.

FIG. 6illustrates a schematic diagram of the GS units shown inFIG. 2in accordance with various embodiments of the present disclosure. The GS unit600includes a NOT gate602, AND gates612,614,616and618, NOR gates622and624, and a NAND gate632. The GS unit600has six inputs, namely Sel(ri), PS(ri-1,ci), GS(ri-1,ci-d), GS(ri-1,ci), PS(ri-1,ci-d) and GS(ri-1,ci-2d).

As shown inFIG. 6, the first AND gate612has three inputs. The first input of the first AND gate612is connected to Sel(ri) through the NOT gate602. The second input and third input of the first AND gate612are connected to PS(ri-1,ci) and GS(ri-1,ci-d) respectively. The second AND gate614has two inputs. The first input of the second AND gate614is connected to Sel(ri) through the NOT gate602. The second input of the second AND gate614is connected to GS (ri-1,ci).

The third AND gate616has three inputs. The first input of the third AND gate616is connected to Sel(ri). The second input and third input of the third AND gate616are connected to PS(ri-1,ci-d) and GS(ri-1,ci-2d) respectively. The fourth AND gate618has two inputs. The first input of the fourth AND gate618is connected to Sel(ri). The second input of the fourth AND gate618is connected to GS(ri-1,ci-d).

The outputs of the first AND gate612and the second AND gate614are fed into the first NOR gate622. The outputs of the third AND gate616and the fourth AND gate618are fed into the second NOR gate624. The NAND gate632has two inputs connected to the outputs of the first NOR gate622and the second NOR gate624respectively. The output of the NAND gate632is GS(ri,ci).

FIG. 7illustrates a schematic diagram of the GS units in the first row of the 8-bit add-and-shift apparatus shown inFIG. 2in accordance with various embodiments of the present disclosure. The schematic diagram of the GS unit700is similar to that of the GS unit600shown inFIG. 6except that the inputs of GS unit700are connected to P(0,ci), G(0,ci-1), G(0,ci), P(0,ci-1) and G(0,ci-2) respectively. It should be noted that P(0,ci), G(0,ci-1), G(0,ci), P(0,ci-1) and G(0,ci-2) are generated by the Propagate and Generate cells shown inFIG. 3.

FIG. 8illustrates a subtraction process of two aligned matissas in accordance with various embodiments of the present disclosure. Two aligned matissas are fed into an 8-bit add-and-shift apparatus800similar to that shown inFIG. 2. The aligned matissas are two unsigned numbers A and B, each of which has 8 bits ranging from bit0to bit7.

The shifting value of this subtraction process is provided by the control signal Sel. In some embodiments, Sel is generated by a LZA/LZD unit (not shown).

In the subtraction operation, a first number is equal to 01110001 in binary format. A second number is equal to 01101001 in binary format. The subtraction process can be implemented by inverting all bits of the second number to obtain the complement B, which is 10010110 in binary format. Then, A, the complement B and one are added together to obtain the difference of the first number and the second number.

In the example above, the complement is equal to 10010110 in binary format. The sum of A, the complement and 1 is equal to 000010000 in binary format. The LZA/LZD unit (not shown) provides the control signal Sel indicating the result should be shifted to left by five bits. As a result, the output of the 8-bit add-and-shift apparatus800is equal to 100000000 in binary format.

FIG. 9illustrates a schematic diagram of a first row of the 8-bit add-and-shift apparatus shown inFIG. 8in accordance with various embodiments of the present disclosure. Row201includes eight Propagate and Generate cells, each of which comprises two inputs coupled to two corresponding bits of the two unsigned 8-bit numbers A and B. The unsigned 8-bit numbers A and B are processed by the AND gate302and XOR gate304shown inFIG. 3. The output of Propagate cells is 11100111 in binary format as shown inFIG. 9. The output of Generate cells is 00010000 in binary format as shown inFIG. 9.

Row210comprises eight cells. Each cell includes a PS unit and a GS unit. Each cell has three groups of inputs. The row index of row210is equal to 0 as shown inFIG. 9. Referring back to Equation (3), the variable d of the row210is equal to 1. In other words, three groups of inputs are connected to a preceding cell in row201, a cell that is one cell away from the preceding cell and a cell that is two cells away from the preceding cell.

For example, the cell of GS(0,2) and PS(0,2) has three groups of inputs. These three groups of inputs are connected to the outputs of the cell of P(0,2) and G(0,2), the cell of P(0,1) and G(0,1), and the cell of P(0,0) and G(0,0) respectively. Furthermore, the cell of GS(0,0) and PS(0,0) has three groups of inputs. These three groups of inputs are connected to the outputs of the cell of P(0,0) and G(0,0), the cell of P(0,−1) and G(0,−1), and the cell of P(0,−2) and G(0,−2) respectively. As shown inFIG. 9, G(0,−1) is equal to Cin. P(0,−1), P(0,−2) and G(0,−2) are set to 0 as shown inFIG. 9.

The eight cells in the row210receive a first bit (bit0) of the control signal Sel, which is equal to 1 as shown inFIG. 9. The input signals of the eight cells in the row210are processed by the logic gates shown inFIGS. 5 and 7. The output of the PS units is 10001100 in binary format as shown inFIG. 9. The output of the GS units is 01100011 in binary format as shown inFIG. 9.

FIG. 10illustrates a schematic diagram of a second row of the 8-bit add-and-shift apparatus shown inFIG. 8in accordance with various embodiments of the present disclosure. Row211comprises eight cells. Each cell includes a PS unit and a GS unit. Each cell has three groups of inputs. The row index of row211is equal to 1. Referring back to Equation (3), the variable d of the row211is equal to 2 as shown inFIG. 10. In other words, three groups of inputs of each cell are connected to a preceding cell in row210, a cell that is two cells away from the preceding cell and a cell that is four cells away from the preceding cell. For example, the cell of GS(1,1) and PS(1,1) has three groups of inputs. These three groups of inputs are connected to the outputs of the cell of PS(0,1) and GS(0,1), the cell of PS(0,−1) and GS(0,−1), and the cell of PS(0,−3) and GS(0,−3) respectively. Referring back toFIG. 9, GS(0,−1) is generated from G(0,−1) and Sel(0). PS(0,−1), PS(0,−3) and GS(0,−3) are set to 0 as shown inFIG. 10.

The eight cells in the row211receive a second bit (bit 1) of the control signal Sel, which is equal to 0 as shown inFIG. 10. The input signals of the eight cells in the row211are processed by the logic gates shown inFIGS. 4 and 6. The output of the PS units is 00000000 in binary format as shown inFIG. 10. The output of the GS units is 11101111 in binary format as shown inFIG. 10.

FIG. 11illustrates a schematic diagram of a third row of the 8-bit add-and-shift apparatus shown inFIG. 8in accordance with various embodiments of the present disclosure. Row212comprises eight cells. Each cell includes a PS unit and a GS unit. Each cell has three groups of inputs. The row index of row212is equal to 2. Referring back to Equation (3), the variable d of the row212is equal to 4 as shown inFIG. 11. In other words, three groups of inputs of each cell are connected to a preceding cell in row211, a cell that is four cells away from the preceding cell and a cell that is eight cells away from the preceding cell. For example, the cell of GS(2,4) and PS(2,4) has three groups of inputs. These three groups of inputs are connected to the outputs of the cell of PS(1,4) and GS(1,4), the cell of PS(1,0) and GS(1,0), and the cell of PS(1,−4) and GS(1,−4) respectively. PS(1,−4) and GS(1,−4) are set to 0 as shown inFIG. 11.

The eight cells in the row212receive a third bit (bit2) of the control signal Sel, which is equal to 1 as shown inFIG. 11. The input signals of the eight cells in the row212are processed by the logic gates shown inFIGS. 4 and 6. The output of the PS units is 00000000 in binary format as shown inFIG. 11. The output of the GS units is 11110000 in binary format as shown inFIG. 11.

FIG. 12illustrates a block diagram of a barrel shifter of the 8-bit add-and-shift apparatus shown inFIG. 8in accordance with various embodiments of the present disclosure. The barrel shifter has eight inputs connected to 8 bits of the Propagate cells and an input configured to receive ‘0’ as shown inFIG. 12. The barrel shifter further receives the control signal Sel, which is equal to 101 in binary format. The control signal Sel indicates the input binary number of the barrel shifter should be shifted to left by five bits. As shown inFIG. 12, the output binary number is 011100000 after shifting the input binary number 011100111 to left by five bits.

FIG. 13illustrates a schematic diagram of an output block of the 8-bit add-and-shift apparatus shown inFIG. 8in accordance with various embodiments of the present disclosure. The output block comprises nine exclusive OR (XOR) gates. As shown inFIG. 13, a first XOR gate has a first input connected to a first output of the barrel shifter shown inFIG. 12and a second input connected to GS(2,−1). Referring back toFIG. 11, GS(2,−1) is generated by a logic circuit comprising a plurality of logic gates receiving input signals from GS(1,−1), G(0,−1) and Sel(2).

The other XOR gates of the output block have a first input connected to an output of a GS unit of a preceding cell in row212and a second input connected to a corresponding bit at the output of the barrel shifter. The output of the output block is 100000000 in binary format.

FIG. 14illustrates a flow chart of an arithmetic operation in accordance with various embodiments of the present disclosure. At step1402, receiving a first N-bit unsigned number and a second N-bit unsigned number. At step1404, receiving a control signal indicating a m-bit shifting operation. At step1406, processing the first N-bit unsigned number, the second N-bit unsigned number and the control signal in an add-and-shift apparatus, wherein an addition or subtraction operation and the m-bit shifting operation are performed in parallel in the add-and-shift apparatus. At step1408, generating a binary number at an output of the add-and-shift apparatus, wherein the binary number has (N+1) bits.

The add-and-shift apparatus comprises an input block configured to receive a first N-bit unsigned number and a second N-bit unsigned number, wherein the input block comprises N propagate and generate cells, a plurality of calculation cells arranged in rows and columns, wherein the number of the columns is equal to N and the number of the rows is equal to log2(N), wherein each row has N cells and has an index ri, and wherein a variable d is equal to 2ri, and wherein each calculation cell has three groups of inputs connected to three cells in a preceding row, and wherein a first group of inputs are connected to outputs of a first calculation cell in the preceding row and vertically aligned with the calculation cell, a second group of inputs are connected to outputs of a second calculation cell that is d cells away from the first calculation cell and a third group of inputs are connected to outputs of a third calculation cell that is 2d cells away from the first calculation cell and an output block comprising a plurality of XOR gates.