Optimizing depths of circuits for Boolean functions

摘要

Boolean circuits are designed with minimal depth by calculating the depth of an existing circuit. Those subtrees having a non-regular root cell (i.e., cells having other than one child or having a child of a type different from the cell) are balanced by constructing a new subtree. The cells are then iteratively transformed with parent and/or grandparent cells to reduce the depth of the circuit. The transformation may include balancing the subtree to make the parent cell the same type as the selected cell, or by creating a new cell as parent to the selected cell.