Multi-Node Static Logic Implications for Redundancy Identification

This paper presents a method for redundancy identification (RID) using multi-node logic implications. The algorithm discovers a large number of direct and indirect implications by extending single node implications to multiple nodes. The large number of implications found by multi-node implication method introduces a new redundancy identification technique. Our approach uses an effective node-pair selection method which is O(n) in the number of nodes to reduce execution time, and it can be used as an efficient preprocessing phase for test generation. Application of these multi-node static logic implications uncovered more redundancies in ISCAS85 combinational circuits than previous single-node methods without excessive computational effort.