Theory of wire addition and removal in combinational Boolean networks

Let wt be a wire in a combinational Boolean network. There may exist a wire wa such that when wa is added and wt is removed, the overall circuit functionality is unchanged. Redundancy-addition-and-removal (RAR) is an efficient technique to find such a wa. The idea is to add a redundant alternative wire wa to make the target wire wt redundant. However, as long as the addition of wa together with the removal of wt does not change the overall functionality of the circuit, wires that are added and removed do not necessarily need to be redundant. This raises a question about the existence of alternative wires. Why can one wire replace another wire in a combinational Boolean network? In this paper, we analyze theoretically the existence of alternative wires and model it as an error-cancellation problem. The two existing rewiring techniques, the redundancy-addition-and-removal and the global flow optimization, are unified under the proposed generalized model.