ON REMOVING REDUNDANCIES FROM SYNCHRONOUS SEQUENTIAL-CIRCUITS WITH SYNCHRONIZING SEQUENCES

We consider the removal of redundant logic from synchronous sequential circuits that have synchronizing sequences. The logic to be removed i s identified by determining line stuck-at faults that do not affect th e operation of the circuit. Such signal lines and some of the logic su rrounding them can be removed without affecting the operation of the c ircuit. We show that circuits that have synchronizing sequences have c ertain properties that help in identifying logic that can be removed. Specifically, their state diagrams have a strongly connected component that contains all the synchronization states, This strongly connected component, called the main strongly-connected component, is reachable from all other strongly connected components. In addition to redundan t faults that can always be removed, we show that there are two types of partially detectable faults in circuits that have synchronizing seq uences. In the presence of the first type of faults, the circuit becom es unsynchronizable. Signal lines carrying such faults cannot be remov ed. The other type of partially detectable faults leave the circuit sy nchronizable. We show that such faults do not affect the main strongly connected component, and hence the corresponding signal lines can be removed without affecting the operation of the circuit after it is syn chronized. We also define weakly synchronizable circuits and derive si milar results regarding the removal of redundant logic in them. The cl ass of removable lines is thus extended beyond those corresponding to redundant faults to include some partially detectable faults as well. We present experimental evidence to the existence of partially detecta ble faults that correspond to signal lines that can be removed in benc hmark circuits.