Boolean resubstitution with permissible functions and binary decision diagrams

Abstract

In this paper, we present a new Boolean resubstitution technique with permissible functions and ordered binary decision diagrams, abbreviated as OBDD[8]. Boolean resubstitution is one technique for multi-level logic optimization. Permissible functions are special don't care sets. We represent the data structure of permissible functions and logic functions at each node in Boolean networks in terms of OBDD. Therefore, logic functions can be flexibly manipulated and rapidly executed. We have previously reported a multi-level logic optimization technique called transduction methods[1] using OBDD in ICCAD'89[7]. We have improved the OBDD operation techniques, so that now OBDD operations can be executed faster than we reported before. We also applied Boolean resubstitution to our multi-level logic synthesis. We present results of experiments employing the improved OBDD operation techniques and applying Boolean resubstitution to our multi-level logic synthesis.