System for evaluating boolean expressions using total differential generating tree structured processing elements controlled by partial subfunction differentials

An apparatus for processing an arbitrary, complex Boolean function comprised of a plurality of subfunctions, said Boolean subfunctions being functions of corresponding input variables at each level of an actual or virtual logic tree, said logic tree comprising a plurality of levels with one or more actual or virtual nodes at each level, said plurality of Boolean subfunctions being related to each other in a hierarchic order corresponding to said levels within said logic tree, each of said Boolean subfunctions being a function of two variables, a lowest level of said hierarchic order of Boolean functions having independent variables, each higher level of said hierarchic order of Boolean functions at a next higher level within said logic tree having as its corresponding variables two total differential signals of the next lower order Boolean subfunctions at the next lower level within said logic tree until said complex Boolean is obtained, said apparatus comprising:

• means for receiving and storing a plurality of inputs corresponding to said independent variables at said lowest level within said logic tree;
• means for generating and storing a plurality of partial differential signals corresponding to partial derivatives of each of said Boolean subfunctions at each node and at each level with said logic tree;
• means for generating and storing a plurality of total differential signals corresponding to total derivatives of each of said subfunctions at each node at each level within said logic tree according to a predetermined rule;
• means for logically combining said plurality of signals corresponding to said total derivatives at each node at each level within said logic tree, partial derivatives and inputs combined to generate a total derivative of said Boolean subfunctions at each node at each level within said logic tree, said means for logically combining being coupled to and communicating with said means for receiving and storing a plurality of inputs, to said means for generating and storing a plurality of partial differential signals, and to said means for generating and storing a plurality of total differential signals;
• and
• means for generating a signal corresponding to that value of said Boolean function at said corresponding plurality of inputs corresponding to said independent variables from a zero initial value signal and said total differential signal at the highest level of said logic tree,
• whereby said complex Boolean function is evaluated at high speed and minimal use of memory.

A method of processing a Boolean function comprised of a plurality of Boolean subfunctions of corresponding variables in a memory and processing circuit, said plurality of Boolean subfunctions being related to each other in a hierarchic order, at least one of said Boolean subfunctions being a function of at least two independent variables, said plurality of Boolean subfunctions being related to each other in a hierarchic order having a plurality of levels, each of said Boolean subfunctions being a function of two variables, a lowest level of said hierarchic order of Boolean functions having independent variables, each higher level of said hierarchic order of Boolean functions having as its corresponding variables two of the next lower order Boolean subfunctions until said complex Boolean is obtained, comprising the steps of:

• initializing said memory and processing circuit by:
• generating in said processing circuit an initial value signal, F(0), corresponding to an initialized value of said Boolean function when all independent variables are set to 0;
• generating in said processing circuit a partial differential signal for each said subfunction of said Boolean function at each level;
• and
• storing in said memory said initial value signal, F(0), corresponding to said initialized value of said Boolean function and partial derivatives corresponding to each said level, and
• generating a plurality of total differential signals in said processing circuit corresponding to a total derivative of each subfunction at each said level, by:
• generating one of said plurality of total differential signals for each said subfunctions at each node at said level according to a predetermined method of operating said processing circuit, each subfunction being related to other ones of said subfunctions at a next lower level in said hierarchic order and to said Boolean function according to a sequence of related levels in a logic tree;
• and
• generating in said processing circuit said Boolean function from said logic tree by steps modeled by the equation
• F(v)=F(0)+dF(v)
• where F is the Boolean function, v a vector having said plurality of independent variables as elements, and dF the total derivative of said Boolean function at the highest level of said logic tree.