On the existence of hazard-free multi-level logic

This paper introduces a new method which, given an arbitrary Boolean function and specified set of (function hazard-free) input transitions, determines if any hazard-free multi-level logic implementation exists. The algorithm is based on iterative decomposition, using disjunction and inversion. Earlier approaches by Nowick/Dill [7] and Theobald/Nowick [8] have been proposed to determine if a hazard-free two-level logic implementation exists. However it is,well-known that the effects of multi-level transformations are quite complex: since they can both decrease and increase logic hazards in a given circuit. In this paper a method is proposed to solve the hazard-free multi-level existence problem. The method is proven to be both sound and complete for a large class of multi-level implementations. A novel contribution is to show that, if any hazard-free multi-level solution exists, then a hazard-free solution always exists using only 3 logic levels, in a 3-level NAND or OR-AND-OR structure. Moreover in this case, it is shown there always exists a unique canonical hazard-free 3-level implementation.