Empirical Comparison of Multi-Output Boolean Function Minimization Algorithms using Ternary-Indexed Prime Implicants

Abstract

Prime implicant computation is a fundamental step in minimizing the two-level sum-of-products representation of Boolean function – the form used in programmable logic arrays and throughout classical digital system design. Ternary indexing offers an elegant algebraic framework for representing the prime implicants of binary Boolean functions and can, in principle, improve the efficiency of the computation. It has received little empirical attention to date. This paper resents the first systematic experimental comparison of three algorithms for prime implicant computation of multi-output Boolean functions: a ternary-indexed iterative algorithm, a ternary-indexed recursive algorithm, and the classical Quine-McCluskey Phase 1 method, which serves here as a correctness reference. No prior empirical evaluation of the two ternary-indexed approaches has appeared in the literature. All three algorithms are verified correct on a suite of 16 benchmark circuits using a three-check functional coverage protocol. The experiment quantifies the memory-time trade-off between the two ternary approaches: the recursive algorithm reduces memory consumption by a factor of 704 relative to the iterative algorithm at every tested input size, at the cost of higher runtime. It also strictly larger produces a cross-group prime implicants that per-output-group methods cannot reach. These results provide the first experimental foundation for the theoretical claims of both ternary approaches and clarify the conditions under which each is most advantageous.