Addition circuits
AssigneeSTMicroelectronics S.r.l.
InventorSimon Knowles
Life of this patent
Estimating the term…
Abstract
A method of designing an addition circuit, and an addition circuit designed according to the method are described. The design technique is optimised to facilitate design of an addition circuit of minimum depth. The design technique takes into account the number of logical stages of the addition circuit and the manner in which those stages are connected by spanning paths to create fan-out nodes. The number of fan-out nodes per level can be optimized. For bit lengths n, the number (m+2) of logical stages is n=2m+1 and for bit lengths n not of a binary order, the number (m+2) of logical stages is nbo=2m+1, where nbo is the next largest binary order after n.
Claims18
An addition circuit for adding together two binary numbers each having a length of n bits, comprising:
- an array of logical nodes that are arranged so that each set of logical nodes extending widthwise of the circuit form a logical stage and each set of nodes extending depthwise of the circuits forms an addition path, with each pair of adjacent addition paths forming a column;
- spanning paths arranged to interconnect selected logical nodes so that adjacent logical stages are connected via an interconnection level, each spanning path extending from a node in one stage across at least one column being connected to a number f of fan-out nodes in a subsequent stage, the circuit having the following configuration parameters:
- i) for each interconnection level the number f of fan-out nodes lies in the range 1 to 2j, where j is the interconnection level index lying between 0 and m, 2j is the maximum fan-out number for that level, and there are m+2 logical stages;
- ii) the fan-out f of nodes at each level is always no greater than the number f of fan-out nodes at a subsequent level;
- iii) the number of columns across which a spanning path extends within an interconnection level is 2j;
- and
- at least one level has a fan-out number f<2j and at least one level has a fan-out number f>1.
A method of designing an addition circuit for adding together two binary numbers each of bit length n, the method comprising:
- determining the number (m+2) of logical stages in the addition circuit according to the following:
- for bit length n of a binary order, n=2m+1
- and for bit lengths which are not binary orders nbo=2m+1 where nbo is the next largest binary order after n;
- for each of said logical stages allocating a set of virtual nodes, said virtual nodes forming potential addition paths depthwise of the circuit and adjacent addition paths forming a column;
- determining for each logical stage its expected input capacitance;
- and
- defining spanning paths wherein the spanning paths constitute an interconnection level between adjacent logical stages, wherein definition of the spanning paths is carried out in accordance with the following configuration parameters and depending on the expected input capacitance of each stage:
- i) for each interconnection level the number f of fan-out nodes in a subsequent stage to which a node of a preceding stage is connected lies in the range 1 to 2j, where j is the interconnection level index lying between 0 and m and 2j is the maximum fan-out number for that level,
- ii) the fan-out f of nodes at each level is always no greater than the fan-out f of nodes at a subsequent level,
- iii) the number of columns across which a spanning path extends within an interconnection level is 2j, and
- at least one level has a fan-out number f<2j and at least one level has a fan-out number f>1.
An addition circuit for an integrated circuit, comprising:
- a plurality of nodes, the nodes arranged in rows and columns, each row forming a logical stage, and each column forming an addition path;
- a plurality of spanning paths connecting nodes in one column with nodes in one or more adjacent columns and in one or more subsequent stages;
- and
- the number (m+2) of logical stages comprises:
- for bit lengths n of a binary order, n=2m+1.
A method for designing an addition circuit, comprising:
- determining the bit-length n of the operands to be added;
- determining the number (m+2) of logical stages in the addition circuits, comprising:
- for bit length n of a binary order, n=2m+1;
- determining the addition path for each operand bit to form one or more columns;
- determining the expected input capacitance for each logical stage;
- and
- defining a plurality of spanning paths connecting nodes in one column with one or more nodes in adjacent columns and in subsequent stages in accordance with the following configuration parameters:
- i) for each interconnection level the number f of fan-out nodes in a subsequent stage to which a node of a preceding stage is connected lies in the range 1 to 2j, where j is the interconnection level index lying between 0 and m and 2j is the maximum fan-out number for that level,
- ii) the fan-out f of nodes at each level is always no greater than the fan-out f of nodes at a subsequent level,
- iii) the number of columns across which a spanning path extends within an interconnection level is 2j, and at least one level has a fan-out number f<2j and at least one level has a fan-out number f>1.
Dependencies are inferred from the claim text.