FRAIGs: Functionally Reduced AND-INV Graphs

AND-INV graphs (AIGs) are Boolean networks composed of two-input AND-gates and inverters. They can be used to represent and manipulate large Boolean functions in several applications such as equivalence checking and technology mapping. For many practical circuits, AIGs are smaller and easier to construct than BDDs. However, the applicability of traditional AIGs is limited because they are not canonical. The paper presents a new way to compute functionally reduced AIGs (FRAIGs), a variation of AIGs, which are “semi-canonical ” in the sense that each AIG node has unique functionality among the nodes of the AIG. Previous methods perform functional reduction of traditional AIGs as a post-processing step. The new method performs functional reduction on-the-fly, as part of the AIG construction. This leads to significant savings in runtime by avoiding potentially large intermediate results. Preliminary experiments indicate an order-of-magnitude speed-up for typical applications.