On removing redundancies from synchronous sequential circuits with synchronizing sequences
- 1 January 1996
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 45 (1) , 20-32
- https://doi.org/10.1109/12.481483
Abstract
We consider the removal of redundant logic from synchronous sequential circuits that have synchronizing sequences. The logic to be removed is identified by determining line stuck-at faults that do not affect the operation of the circuit. Such signal lines and some of the logic surrounding them can be removed without affecting the operation of the circuit. We show that circuits that have synchronizing sequences have certain 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 redundant faults that can always be removed, we show that there are two types of partially detectable faults in circuits that have synchronizing sequences. In the presence of the first type of faults, the circuit becomes unsynchronizable. Signal lines carrying such faults cannot be removed. The other type of partially detectable faults leave the circuit synchronizable. 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 synchronized. We also define weakly synchronizable circuits and derive similar results regarding the removal of redundant logic in them. The class 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 detectable faults that correspond to signal lines that can be removed in benchmark circuits.Keywords
This publication has 14 references indexed in Scilit:
- Sequential Redundancy Identification Using Verification TechniquesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Design and synthesis for testability of synchronous sequential circuits based on strong-connectivityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Sequential logic optimization by redundancy addition and removalPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On identifying undetectable and redundant faults in synchronous sequential circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On achieving complete testability of synchronous sequential circuits with synchronizing sequencesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An ATPG-based approach to sequential logic optimizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The multiple observation time test strategyIEEE Transactions on Computers, 1992
- A theory and implementation of sequential hardware equivalenceIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992
- On removing redundancy in sequential circuitsPublished by Association for Computing Machinery (ACM) ,1991
- Redundancies and don't cares in sequential logic synthesisJournal of Electronic Testing, 1990