Theorems and extensions of single wire replacement

In this paper, we discuss the theorems and extensions of single alternative wire that attempts to replace one wire by another wire without changing th e logic functionality. The wire replacement technique has been successfully applied to achieve logic optimization and routability improvement. However , there still exist several fundamental problems that have not been address ed such as whether the algorithm can find all single alternative wires. Fir st, we present some cases of alternative wires, which the previous work (Ch ang et al., 1997) cannot obtain. Then, several theorems of tight necessary conditions and dominating conditions for a wire to be an alternative wire a re proposed. With these theorems, we are able to derive an efficient proced ure to find all possible alternative wires. The experimental results are ve ry encouraging.