Multiplier tree using nine-to-three adders

A nine-to-three bit adder for summing partial products resulting from a multiplication of two binary operands, comprising:

• first, second and third logic means each having three inputs for receiving and summing the partial products having weight 2.sup.n, where n is an integer, and two outputs, each first, second and third logic means producing first intermediate output bit of weight 2.sup.n, and a second intermediate output bit of weight 2.sup.n+1, such that the combined value of first and second intermediate output bits equals the combined value of the received partial products;
• a fourth logic means having inputs coupled to the outputs of first, second, and third logic means for receiving and summing first intermediate output bits, and having outputs, and producing a fourth intermediate output bit of weight 2.sup.n and a fifth intermediate output bit of weight 2.sup.n+1, such that the combined value of fourth and fifth intermediate output bits equals the combined value of first intermediate output bits;
• a fifth logic means having inputs coupled to the outputs of first, second, and third logic means for receiving and summing second intermediate output bits and having outputs, and producing another fifth intermediate output bit of weight 2.sup.n+1 and a carry-out bit of weight 2.sup.n+2 to be applied to a first bit adder in a multiplier tree, such that the combined value of the fifth intermediate output bit of the fifth logic means and the carry-out bit equals the combined value of second intermediate output bits;
• an inverting means having its input coupled to one output of the fourth logic means for receiving and inverting a fourth intermediate output bit, producing an inverted final output bit of weight 2.sup.n ;
• a sixth logic means having inputs coupled to the outputs of fifth and fourth logic means for receiving the fifth intermediate output bits, and coupled to a second bit adder in the multiplier tree for receiving a carry-in bit of weight 2.sup.n+1, summing the fifth intermediate output bits and the carry-in bit, and producing two final output bits of weight 2.sup.n+1 and 2.sup.n+2, such that the combined value of all final output bits and the carry-out bit equals the combined value of the nine partial products bits and the carry-in bit;
• and such that the production of the carry-out bit of weight 2.sup.n+2 from the fifth logic means is independent of the inputting of the carry-in bit into the sixth logic means.

A multiplier tree for summing a plurality of partial products resulting from a multiplication of two binary operands, accepting the plurality of partial products along an input bus, and producing first and second output sums along first and second output buses for summation in a bit adder, comprising:

• a plurality of tree slices each having inputs coupled to the input bus for receiving the plurality of partial products and each further coupled to adjacent tree slices for applying carry bits to the adjacent tree slices, where each tree slice receives partial products all having equal weight, for summing the partial products and the applied carry bits and producing first and second output sums;
• each tree slice containing a hierarchical arrangement of bit adders, at least one tree slice containing regular arrangements of nine-to-three bit adders having nine inputs for receiving partial products of equal weight and an input for receiving a carry-in bit of greater weight, and having an output and three carry-outputs, for summing the partial products and the carry-in bit to produce three carry-out bits to be applied to adjacent tree slices and an output bit to be applied to further bit adders within the tree slice for further summing, such that the combined value of the three carry-out bits and the output bit equals the combined value of the partial products and the carry-in bit;
• each tree slice further containing additional bit adders in the hierarchical arrangement, each additional bit adder having three inputs for receiving either an output bit from a nine-to-three bit adder or a carry-in bit from adjacent tree slices, for summing its inputs and producing an output bit within the tree slice and a carry bit to be applied to an adjacent tree slice, where the output bits from an additional bit adder form part of the first and second output sums where there are three or less bits input into the additional bit adder.

A bit adder for use in a multiplier tree for summing the partial products resulting from a multiplication of two binary operands, comprising:

• twenty-seven initial inputs for receiving twenty-seven partial products of weight 2.sup.n, where n is an integer;
• twn carry-inputs for receiving three first carry-inputs of weight 2.sup.n+1, three second carry-inputs of weight 2.sup.n, three third carry-inputs of weight 2.sup.n, and one fourth carry-input of weight 2.sup.n+1 from other adders in a multiplier tree;
• a plurality of logic elements, each logic element coupled to receive a separate subset of the initial inputs, and a separate subset of the carry inputs, such that all initial inputs and carry inputs are received, for sequentially summing the partial products and the carry-inputs as the carry-inputs are received and producing from the summed inputs three final output bits, comprising a first final output bit of weight 2.sup.n, a second final output of weight 2.sup.n+1, and a third final output bit of weight 2.sup.n+2 ;
• the logic elements of the bit adder further jointly producing ten carry-outputs comprising three first carry-outputs of weight 2.sup.n+2, three second carry-outputs of weight 2.sup.n+2, three third carry-outputs of weight 2.sup.n+1, and one fourth carry-output of weight 2.sup.n+2 ;
• such that the first, second, third, and fourth carry-outputs of the bit adder respectively become first, second, third, and fourth carry-inputs of other adders used in the multiplier tree, and the production of the each of the first, second, third, and fourth carry outputs is logically independent of the respective input of the first, second, third, and fourth carry-inputs, and such that the combined value of the twenty-seven initial inputs and the ten carry-inputs equals the combined value of the three final output bits and the ten carry-output bits.

A bit adder for use in a multiplier tree for summing partial products resulting from a multiplication of two binary numbers, where the bit adder is capable of being combined with other bit adders to form a bit adding array for summing the partial products, the bit adder comprising:

• three primary bit adders each having nine initial inputs, such that there are twenty seven initial inputs, for receiving nine partial products, and a carry input for receiving a first level carry-input bit from another bit adder in the multiplier tree, and having one intermediate output, and three carry outputs, and each primary bit adder summing its partial products and first level carry-input bit and producing three first level carry-output bits to be applied to another bit adder in the multiplier tree, and one intermediate output bit and;
• a fourth secondary bit adder having three inputs coupled to the intermediate outputs of the three primary bit adders for receiving the three intermediate output bits from the three primary bit adders, and having six inputs for receiving six second level carry-input bits from another bit adder, and a carry input for receiving a second level carry-input bit from another bit adder, summing these inputs to produce three final output bits and a final carry out bit, such that the combined value of the twenty-seven initial inputs and the three first level carry inputs and the second level carry inputs equals the combined value of the three final output bits, the final carry out bit, and the nine first level carry out bits.

A multiplier tree for summing M.sub.1 through M.sub.y subsets of partial products, each subset containing m partial products resulting from a multiplication of two binary operands, the multiplier tree comprising:

• T.sub.1 through T.sub.y tree slices, each T.sub.i tree slice for 1'i.ltoreq.(y-2) coupled to tree slices T.sub.i+1, T.sub.i+2, tree slice T.sub.y-1 coupled to tree slice T.sub.y, and tree slice T.sub.y coupled internally, and receiving the M.sub.i subset partial products of equal weight along an input bus, and including L.sub.1 through L.sub.z levels of bit adders, each L.sub.j level for 1.ltoreq.j.ltoreq.z for adding a m.sub.i,j subset of partial products comprising:
• pi,j counter blocks each having n inputs, where n is a positive integer, coupled to receive n partial products of the m.sub.i,j partial products and having x outputs, pi,j equal to the integer component of((m.sub.i,j +1)/n), for summing the n partial products producing x output bits as partial products, each p.sub.i,j counter block in each level L.sub.j in each tree slice T.sub.i for 1.ltoreq.i.ltoreq.(y-n+2) coupled to a p.sub.i+1,j counter block and a p.sub.i+2,j counter block to apply carry out bits;
• s.sub.i,j carry-save adders, s.sub.i,j equal the greater of either zero or the integer component of (((m.sub.i,j -p.sub.i,j *n)+1)/3), each carry-save adder coupled to receive as inputs three partial products of the m.sub.i,j partial products, for summing the three partial products and producing two output bits as partial products, the s.sub.i,j carry-save adders in each level L.sub.j in each tree slice T.sub.i coupled to a s.sub.i+1,j carry-save adder to apply carry out bits;
• w.sub.i,j wires, w.sub.i,j equal to the greater of either zero or (Mm.sub.i,j -p.sub.i,j *n-s.sub.i,j *3), each wire coupled to transmit one partial product of the m.sub.i,j partial products to a carry save adder in tree slice T.sub.i in level L.sub.j+1.