Binary tree calculations on monolithic integrated circuits

Claim 3

An apparatus as in claim 1 wherein a first portion of the binary tree means within each cell of the plurality of cells comprises: a tree input means for accepting intermediate binary tree values from a prior cell; and, a tree output means, coupled to the tree input means, for utilizing the intermediate binary tree values to produce resulting intermediate binary tree values for use by a next succeeding cell.

Claim 4

An apparatus as in claim 2 wherein the driving means comprises: a function input means for accepting a digit from an operand; and, a function output means coupled to the function input means and the tree input means for combining the intermediate binary tree values with the digit of the operand to produce a digit of a resultant.

Claim 5

An apparatus as in claim 3 wherein the arithmetic function is incrementation.

Claim 6

An apparatus as in claim 3 wherein: the arithmetic function is addition; the function input means accepts one digit from each of two operands; the first portion of the tree output means combines the intermediate binary tree values with the digits from each of the two operands; the function output means combines the intermediate binary tree values with the digits from each of the two operands; and the resultant is a sum.

Claim 7

An arithmetic circuit on an integrated circuit comprising a plurality of logic cells, the logic cells being coupled serially, and each logic cell having substantially the same number of components as every other logic cell, the components in each logic cell being arranged so that each logic cell comprises: a function input means for accepting a digit from an operand; a binary tree input means for accepting intermediate binary tree values from a prior cell; a binary tree output means, coupled to the function input means and the tree input means, for combining the intermediate binary tree values with the digit of the operand to produce intermediate binary tree values for use by a next succeeding cell, wherein when the binary tree is full the total number of layers of logic for all binary tree output means in every cell of the plurality of cells is essentially proportional to the base two logarithm of the number of cells in the plurality of cells; a function output means coupled to the function input means and the tree input means for combining the intermediate binary tree values with the digit of the operand to produce a digit of a resultant.

Claim 8

An arithmetic circuit on an integrated circuit comprising a plurality of logic cells, the logic cells being coupled serially, and each logic cell having substantially the same number of components as every other logic cell, the components in each logic cell being arranged so that each logic cell comprises: a function input means for accepting a digit from an operand; a binary tree input means for accepting intermediate binary tree values from a prior cell; a binary tree output means, coupled to the function input means and the tree input means, for combining the intermediate binary tree values with the digit of the operand to produce intermediate binary tree values for use by a next succeeding cell, wherein when the binary tree is full the total number of layers of logic for all binary tree output means in every cell of the plurality of cells is essentially proportional to the base two logarithm of the number of cells in the plurality of cells; a function output means coupled to the function input means and the tree input means for combining the intermediate binary tree values with the digit of the operand to produce a digit of a resultant.

Claim 9

An arithmetic circuit as in claim 6 wherein each logic cell performs incrementation.

Claim 10

An arithmetic circuit as in claim 7 wherein: the binary tree input means includes a first plurality of wires; the function input means includes a first wire; the binary tree output means includes a second plurality of wires, the second plurality of wires coupled to the first plurality of wires and the first wire, and a gate means for performing a Boolean "AND" between data from two wires, the two wires being from the first plurality of wires and the first wire; and,

Claim 11

the function output means includes a second gate means for performing a Boolean "AND" between data from each wire in the plurality of wires and a third gate means for performing a Boolean "XOR" between data from an output of the second gate means and data from the input wire.

Claim 12

the function output means includes a second gate means for performing a Boolean "AND" between data from each wire in the plurality of wires and a third gate means for performing a Boolean "XOR" between data from an output of the second gate means and data from the input wire.

Claim 13

An arithmetic circuit as in claim 6 wherein: each logic cell performs addition; the function input means accepts one digit from each of two operands; the binary tree output means combines the intermediate binary tree values with the digits from each of the two operands; the function output means combines the intermediate binary tree values with the digits from each of the two operands; and the resultant is a sum.

Claim 14

An arithmetic circuit as in claim 9 wherein: the binary tree input means includes a first plurality of generate wires and a first plurality of propagate wires; the function input means includes a first wire accepting a first digit from a first of the two operands and a second wire accepting a second digit from a second of the two operands; the binary tree output means includes a second plurality of generate wires and a second plurality of propagate wires, the second plurality of generate wires being coupled to the first plurality of generate wires and the second plurality of propagate wires being coupled to the first plurality of propagate wires and a gating means for performing logic functions on data from a plurality of inputs, the inputs including the first wire, the second wire, a first generate wire from the first plurality of generate wires, and a first propagate wire from the first plurality of propagate wires, a first resultant of the logic functions being coupled to the second plurality of generate wires and a second resultant of the logic functions being coupled to the second plurality of propagate wires; and, the function output means includes a series of Boolean logic gates.