Removing multiple redundancies in combinational circuits

Redundancy removal is an important step in combinational logic optimisation. After a redundant wire is removed, other originally redundant wires may become irredundant, and some originally irredundant wires may become redundant. When multiple redundancies exist in a circuit, this creates a problem, where we need to decide which redundancy to remove first. The authors present both a theoretical analysis and a very efficient heuristic to deal with multiple redundancies. Each redundant wire is associated with a Boolean function that describes how the wire can remain redundant after removing other wires. When multiple redundancies exist, this set of Boolean functions characterises the global relationship among redundancies. The proposed heuristic for dealing with the multiple-redundancy problem is very efficient and the experimental results are very promising