Redundancy identification and removal in combinational logic circuits

In many logic circuit designs, redundancy is introduced unintentionally because of sub-optimal logic synthesis. Since such redundancy can cause larger area, longer delay, and worse testability, redundancy identification (RI) and removal (RR) have received constant attention in the area of logic synthesis. Previous works, mostly using automatic test pattern generation (ATPG) algorithms for RI, do not make full use of the functional specification from which the circuit is derived. This prevents one from identifying some redundancies whose removal does not violate the functional specification. Furthermore because removal of a redundancy may make other redundancies detectable, RI is usually performed again after each RR. But actually in a multi-output circuit, some of the remaining redundancies may be removable simultaneously with the first one if their removal is not invalidated by the first one. In this paper, we present an efficient RI and RR method for combinational logic circuits, called RIDAR, which can perform RI by taking advantage of the functional specification and can remove simultaneously more than one redundancy during one RR iteration. Experimental results show that significant savings in literal-count can be obtained for synthesized circuits in small amounts of CPU time. Surprisingly, we found that a significant reduction in literal-count can be obtained in many cases for combinational circuits even when conventional ATPG declares the circuit to be irredundant.