Patent ID: 8468193

Claim:
A method comprising: multiplying, using an array of adders, two binary numbers X and Y of N and M bits respectively, namely: { X = x N · 2 N + x N - 1 · 2 N - 1 + … + x n · 2 n + … + x 1 · 2 1 + x 0 · 2 0 Y = y M · 2 M + y M - 1 · 2 M - 1 + … + y n · 2 n + … + y 1 · 2 1 + y 0 · 2 0 defining an initial matrix [E n i =x n−i ·y i ], wherein the initial matrix [E n i =x n−i ·y i ] is transformed into a matrix [E n i =(x n−i ⊕y i )·(y i−1 ⊕y i )=(x n−i ⊕y i )·Y i ] with Y i =y i−1 ⊕y i or [E n i =e n i ·Y i ] with e n i =x n−i ⊕y i , wherein the step of multiplying comprises: forming a first approximation U n o and R n+1 0 of a sum and carry of the first two rows y 0 and y 1 of this matrix thus transformed over the entire length of said numbers, using this first approximation as an input for a following estimation step which is repeated for all the following rows, successively carrying out addition of the following y i+1 rows up to the last non-zero row, according to a first given series of propagation equations, carrying-out a propagation of the carries R n i−1 over the zero y i+1 rows according to a second given series of propagation equations, in order to obtain a final result of the product P P=p M+N+1 ·2 M+N+1 p M+N ·2 M+N + . . . +p N ·2 N + . . . +p 1 ·2 1 +p 0 ·2 0 .