An Offline Tree-Based Breadth-First Search Two-Level Minimization Approach for Reducing the Number of Boolean Operators in Boolean Functions
摘要
Designing logic circuits involves optimizing Boolean functions to reduce the number of digital gates, integrated circuits, power requirements, and logic delays. Various graphical and non-graphical techniques have been proposed to achieve this goal. This paper presents a novel two-level minimization approach for reducing the number of Boolean operators, combining the benefits of graphical and non-graphical methods while addressing their limitations. Our proposed approach is based on a tree-based breadth-first search iterative algorithm. In the first iteration, the root of the tree is connected to all variables and their complement leaves. During each iteration, the tree leaves are examined to determine whether they cover all or part of the minterms of the input Boolean function. If a leaf satisfies this condition, it is labeled as part of the output, and no further expansion is performed from that leaf or its complement. This process continues until the labeled tree nodes cover all minterms of the input Boolean function. Our proposed algorithm yields the final solution in a single iterative phase, resulting in an acceptable memory complexity. Our proposed method was evaluated using the ESPRESSO and MCNC benchmarks in comparison to the BOOM, ESPRESSO, evolutionary, machine-learning (ML)-based, and Reinforcement Learning (RL)-based techniques. It outperformed other methods by minimizing the number of required Boolean operators. Moreover, as the complexity of the input Boolean function increases, our approach achieves even greater reduction rate, surpassing the optimization powers of BOOM, ESPRESSO, and other methods by up to 50%.