Comparison of heuristic algorithms for variable partitioning in circuit implementation

Functional decomposition is a process of splitting a complex circuit into smaller sub-circuits. This paper deals with the problem of determining the set of best free and bound variables (variable partitioning problem) for disjoint (disjoint serial) decomposition, such that the decomposed circuits are smaller in size and its truth table representation have maximal don´t cares. A novel pruned breadth first search (PBFS/IPBFS) approach is proposed to determine the set of good variable partitions with minimal time and computational complexity. The heuristics proposed minimize the size of the sub functions. The proposed approach has been successfully implemented and test with MCNC and Espresso benchmarks.