Boolean logic layout generator

Claim 1

A method for reducing the size of binary decision tree representations of boolean expressions on integrated circuits having ordered inputs, said method comprising the steps of: decomposing each boolean expression into its sub-expressions based on the ordering of said inputs, such that each term of said decomposed expression introduces a respective one of said inputs; factoring the input introduced by each term of said decomposed expression and the complement of that input from said term, whereby each term is converted into a pair of partial functions such that F=x·F.sub.1 +˜x·F.sub.0 where: F=any given term of the decomposed expression, x=the input introduced by said given term, and F 1 and F 0 =the partial expressions of said given term; testing the partial functions of each term of said decomposed expression to determine which of the following conditions is true: ______________________________________ Test Conclusion if True Operator Indicated ______________________________________ F.sub.1 = F.sub.0 = 1 or 0 F = 1 or F = 0 Constant F.sub.1 = ˜F.sub.0 = 1 or 0 F = x or F = ˜x Identity F.sub.1 = 1 F = x + F.sub.0 OR F.sub.0 = 0 F = x F.sub.1 AND F.sub.0 = 1 F = F.sub.1 + ˜x ORNOT F.sub.1 = 0 F = ˜x F.sub.0 ANDNOT F.sub.1 = F.sub.0 F = F.sub.1 NoDependence F.sub.1 = ˜F.sub.0 F = x F.sub.1 + ˜x ˜F.sub.1 XORNOT ELSE F = x F.sub.1 + ˜x F.sub.0 IF ______________________________________ selecting the operator required for each term of said decomposed expression based on the condition found to be true; and laying out said integrated circuit to provide the operator required for each term of said decomposed expression.

Claim 2

A method for reducing the size of binary decision tree representations of boolean expressions on integrated circuits having ordered inputs, said method comprising the steps of: decomposing each boolean expression into its sub-expressions based on the ordering of said inputs, such that each term of said decomposed expression introduces a respective one of said inputs; factoring the input introduced by each term of said decomposed expression and the complement of that input from said term, whereby each term is converted into a pair of partial functions such that F=x·F.sub.1 +˜x·F.sub.0 where: F=any given term of the decomposed expression, x=the input introduced by said given term, and F 1 and F 0 =the partial expressions of said given term; testing the partial functions of each term of said decomposed expression to determine which of the following conditions is true: ______________________________________ Test Conclusion if True Operator Indicated ______________________________________ F.sub.1 = F.sub.0 = 1 or 0 F = 1 or F = 0 Constant F.sub.1 = ˜F.sub.0 = 1 or 0 F = x or F = ˜x Identity F.sub.1 = 1 F = x + F.sub.0 OR F.sub.0 = 0 F = x F.sub.1 AND F.sub.0 = 1 F = F.sub.1 + ˜x ORNOT F.sub.1 = 0 F = ˜x F.sub.0 ANDNOT F.sub.1 = F.sub.0 F = F.sub.1 NoDependence F.sub.1 = ˜F.sub.0 F = x F.sub.1 + ˜x ˜F.sub.1 XORNOT ELSE F = x F.sub.1 + ˜x F.sub.0 IF ______________________________________ selecting the operator required for each term of said decomposed expression based on the condition found to be true; and laying out said integrated circuit to provide the operator required for each term of said decomposed expression.