Very fast variable input multi-bit adder

A circuit to produce an output sum of M N-bit input numbers, where M and N are integers greater than two, each of said M N-bit input numbers represented as N input bit signal lines wherein a voltage level on each of the input bit signal lines represents a value of either zero or one, each of the M N-input bit signal lines organized in ascending order of magnitude, said circuit comprising:

• a plurality of first stage X-bit adder subcircuits for adding M input addends, the first stage adder subcircuits, Y in number, where Y is a positive integer of value equal to the quotient formed by dividing X into N for a predetermined integral value of X, and where X has a value at least as large as the base two logarithm of M, each of the first stage X-bit adder subcircuits coupled to X contiguous ordered input signal bit lines of each of the N bit numbers such that each of the first stage X-bit adder subcircuits adds X equal-ordered bit clusters of each of the M input numbers different in order from each of the other stage X-bit adder subcircuits, each of the first stage X-bit adder subcircuits outputting X first stage sum bit signals, and Z first stage carry bit signals, where Z is the smallest positive integer at least equal to the base two logarithm of M;
• a second stage K-bit adder subcircuit, for adding an addend and an augend, where K is a positive integer at least equal to {(N+Z)-X}, the K-bit adder having as input a K bit addend signal and a K bit augend signal, and having as output a K bit final sum signal such that the output signal represents the K most significant bits of the output sum of the M N-bit input numbers, the K-bit adder coupled to each X-bit adder of the plurality of X-bit adders, except the X-bit adder which adds the least significant equal-ordered bit cluster of the M N-bit input numbers, in a manner whereby the ((Y-1)X) least significant bits of the K bit addend signal are formed by the first stage sum bit signals, and ((Y-1)Z) bits of the K bit augend signal are formed by the first stage carry bit signals, each of the first stage carry bit signals input to the K bit augend signal in the bit position that corresponds to the order associated with the first stage carry bit signal;
• a plurality of sets of Z carry bit signal lines, where the number of sets of Z carry bit signal lines is Y in number, each set of the plurality of sets of Z carry bit signal lines coupling one of the first stage adder subcircuits to the second stage K-bit adder subcircuit, the carry bit signal lines disposed such that each of the sets of Z carry bit signal lines provides the first stage carry bit signals of an individual first stage adder to the K bit augend signal of the second stage K-bit adder;
• a plurality of sets of X first stage sum bit signal lines, where the number of sets of Z carry bit signal lines is D in number, where D is equal to one less than Y, each of the sets of the plurality of sets of X first stage sum bit signal lines coupling one of the D highest ordered first stage adder subcircuits to the second stage K-bit adder subcircuits, the first stage sum bit signal lines disposed such that each of the sets of X first stage sum bit signal lines provides the first stage sum bit signals of an individual first stage adder to the K bit augend signal of the second stage K-bit adder;
• such that the N+Z bit output sum of M N-bit input numbers comprises the X first stage sum bit signals of the X-bit adder which adds the least significant X bit cluster of the M N-bit input numbers, and the K bit final sum signal of the second stage K-bit adder subcircuit.

A method to produce an output sum of M N-bit input numbers, where M and N are integers greater than two, each of said M N-bit input numbers represented as N input bit signal lines wherein a voltage level on each of the input bit signal lines represents a value of either zero or one, each of the M N-input bit signal lines organized in ascending order of magnitude, said circuit comprising the steps of:

• dividing each of the N input bit signal lines of each of the M N-bit input numbers into Y distinct clusters of X contiguous ordered input signal bit lines, where X is a predetermined integral value having a value at least as large as the base two logarithm of M, and Y is the integral quotient formed by dividing X into N;
• providing one of the clusters of X of contiguous ordered input signal bit lines for each of the M N-bit numbers to one X-bit adder of a plurality of first stage X-bit adder subcircuits for adding M input addends, each of the first stage X-bit adder subcircuits, Y in number, coupled to X contiguous ordered input signal bit lines of each of the N bit input numbers, such that each of the first stage X-bit adder subcircuits adds X equal-ordered bit clusters of each of the M input numbers different in order from each of the other first stage X-bit adder subcircuits, each of the first stage X-bit adder subcircuits outputting X first stage sum bit signals, and Z first stage carry bit signals, where Z is the smallest positive integer at least equal to the base two logarithm of M;
• providing the first stage carry bit signals of the plurality of first stage X-bit adders, and the first stage sum bit signals of each of the X-bit adders of the plurality of X-bit adders, except the X-bit adder which adds the least significant equal-ordered bit cluster of the M N-bit input numbers, to a second stage K-bit adder subcircuit for adding an addend and an augend, where K is a positive integer at least equal to {(N+Z)-X}, the K-bit adder having as input a K bit addend signal and a K bit augend signal, and having as output a K bit final sum signal, such that the output signal represents the K most significant bits of the output sum of the M N-bit input numbers, the K-bit adder coupled to each X-bit adder of the plurality of X-bit adders, except the X-bit adder which adds the least significant equal-ordered bit cluster of the M N-bit input numbers, in a manner whereby the ((Y-1)X) least significant bits of the K bit addend signal are formed by the first stage sum bit signals, and ((Y-1)Z) bits of the K bit augend signal are formed by the first stage carry bit signals, each of the first stage carry bit signals input to the K bit augend signal in the bit position that corresponds to the order associated with the first stage carry bit signal;
• such that the N+Z bit output sum of M N-bit input numbers comprises the X first stage sum bit signals of the X-bit adder which adds the least significant X bit cluster of the M N-bit input numbers, and the K bit final sum signal of the second stage K-bit adder subcircuit.