Cellular multiplier comprising a tree of the overturned stairs type, and method of implementation

An overturned stairs type cellular structure adder tree for processing a given integer number of N greater than 23 operands and including a plurality of interconnected carry-save adders, said carry-save adders being connected together in a plurality of Q degrees of given horizontal rank q, with 1.ltoreq.q.ltoreq.Q and given depth, each of said carry-save adders having a sum output, a carry output and three inputs, said carry-save adders receiving one of said N operands as an input for each of said three inputs not receiving an input from another carry-save adder of said adder tree, wherein said cellular structure adder tree of order p and depth n', where p designates a parameter order of summing processing time of the form N.sup.1/(p+1) of said multiple operands and n' designates the maximum number of carry-save adders passed through by each operand for complete processing, at least comprises:

• a multiplier root R constituted by a carry-save adder, and
• a first multiplier body CO(p,n), of order p, depth n, with n=n'-1, and rank q=1, connected to said multiplier root R, said first multiplier body including:
• a five-input connector operator C(n,q) of rank q=1 and including first and second carry-save adders connected in cascade, the carry output of said first carry-save adder being connected to one of the inputs of said second carry-save adder, said five-input connector operator C(n,q) further including three outputs constituted by the sum output of the first carry-save adder, and the sum and the carry outputs of the second carry-save adder, and being connected to said multiplier root R, and
• a tree of order p-1, depth n-2 and rank q=1 comprising a plurality of interconnected carry-save adders including a final carry-save adder constituting a tree root r, the sum and the carry outputs of said tree root being connected to respective inputs of the first carry-save adder of said five-input connector operator of rank q=1,
• at least four successive sub-multiplier bodies of order p and of decremented depth determined by successively decrementing the depth n=n'-1 by one and incremented rank determined by successively incrementing the rank q by one, with 2.ltoreq.q.ltoreq.Q-1, each of said sub-multiplier bodies comprising:
• a single five-input connector operator of corresponding incremented rank and corresponding decremented depth and including first and second carry-save adders connected in cascade and connected to the five-input connector operator of the sub-multiplier body of immediately preceding rank,
• a tree of order p-1 and successively decremented in depth by 1 with respect to said tree of the sub-multiplier body of immediately preceding rank, said tree being connected to said single five-input connector operator of corresponding rank;
• the successive sub-multiplier body of rank q=Q-1 thus consisting of a single five-input connector operator of corresponding rank,
• the five-input connector operator of said sub-multiplier bodies of rank 2 being connected to the five-input connector operator of the first multiplier body,
• said adder tree further including, forming said degree of rank Q, a carry-save adder of rank q=Q and depth n=1 having carry and sum outputs connected to the first carry-save adder of the five-input connector operator of the submultiplier of the immediately preceding rank Q-1.