Fast heuristic and exact algorithms for two-level hazard-free logic minimization

None of the available minimizers for two-level hazard-free logic minimizati on can synthesize very large circuits. This limitation has forced researche rs to resort to manual and automated circutt partitioning techniques. This paper introduces two new two-level hazard-free logic minimizers: ESPRE SSO-HF, a heuristic method loosely based on ESPRESSO-II, and IMPYMIN, an ex act method based on implicit data structures. Both minimizers can solve all currently available examples, which range up to 32 inputs and 33 outputs, These include examples that have never been solved before. For the more dif ficult examples that can be solved by other minimizers, our methods are sev eral orders of magnitude faster. As by-products of these algorithms, we also present two additional results. First, we propose a fast nem method to check if a hazard-free covering pro blem can feasibly be solved. Second, we introduce a novel reformulation of the two-level hazard-free logic minimization problem by capturing hazard-fr eedom constraints within a synchronous function through the addition of new variables.