Boolean logic layout generator
AssigneeXerox Corporation
InventorBertrand P. Serlet
Life of this patent
Estimating the term…
Abstract
To reduce the size of binary decision tree-type integrated circuit representations of boolean expressions, any boolean expression or sub-expression which is fully defined by one of its partial expressions is represented by only that one partial expression. If gate branching of the decision tree is a default case which is invoked only when both partial expressions are needed to define an expression or sub-expression. These reduced size expression trees readily map into CMOS cascade logic, thereby producing low power, reasonably compact, integrated circuit representations of boolean expressions.
Claims6
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.multidot.F.sub.1 +.about.x.multidot.F.sub.0
- where:
- F=any given term of the decomposed expression,
- x=the input introduced by said given term, and
- F.sub.1 and F.sub.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 = .about.F.sub.0 = 1 or 0 F = x or F = .about.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 + .about.x ORNOT F.sub.1 = 0 F = .about.x F.sub.0 ANDNOT F.sub.1 = F.sub.0 F = F.sub.1 NoDependence F.sub.1 = .about.F.sub.0 F = x F.sub.1 + .about.x .about.F.sub.1 XORNOT ELSE F = x F.sub.1 + .about.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.
Dependencies are inferred from the claim text.