Synthesis for Logical Initializability of Synchronous Finite State Machines
Authors: 
M. Singh, S. M. NowickAuthors Info & Claims
Abstract
We present a new method for the synthesis for logical initializability of synchronous state machines. The goal is to produce a gate-level implementation that is initializable when simulated by a 3-valued (0,1,X) simulator. We build on the approach of Cheng and Agrawal (1989,92) who constrain state assignment to translate functional initializability into logic initializability. We propose an alternative method which is guaranteed safe and not as conservative. In addition, we propose necessary and sufficient conditions on 2-level and multi-level logic synthesis to insure 3-valued simulation succeeds.
References
[1]
V.D. Agrawal, K.T. Cheng, and P. Agrawal, "A directed search method for test generation using a concurrent fault simulator," IEEE Trans. CAD, vol. CAD-8, pp. 131-138, Feb 1989.
[2]
S. Mallela and S. Wu, "A sequential circuit test generation system," in Proc. of ITC, Philadelphia, PA. 1985, pp. 57-61.
[3]
J.A. Wehbeh and D.G. Saab, "On the initialization of sequential circuits," in Proc. of ITC, pp. 233-239, 1994.
[4]
K. Cheng and V. Agrawal, "State assignment for initializable synthesis," in Proc. ICCAD, pp. 212-215, 1989.
[5]
K. Cheng and V. Agrawal, "Initializability consideration in sequential machine synthesis," IEEE Trans. Comput., vol 41, pp. 374-379, Mar. 1992.
[6]
J.-K. Rho, F. Somenzi, and C. Pixley, "Minimum length synchronizing sequences of finite state machines," Proc. DAC, pp. 463-468, 1993.
[7]
S.T. Chakradhar, S. Banerjee, R.K. Roy, and D.K. Pradhan, "Synthesis of initializable asynchronous circuits," in Proc. 7th Int. Conf. on VLSI Design, pp. 383-388, Jan. 1994.
[8]
S. Banerjee, R.K. Roy, S.T. Chakradhar, and D. K. Pradhan, "Initialization Issues in the Synthesis of Asynchronous Circuits," in Proc. ICCD-1994.
[9]
S.H. Unger. Asynchronous Sequential Switching Circuits. New York: Wiley-Interscience, 1969.
[10]
G.D. Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill (1994).
[11]
E.B. Eichelberger, "Hazard detection in combinational and sequential switching circuits," IBM J. Res. Develop., vol 9, no. 2, pp. 90-99, 1965.
[12]
S.M. Nowick and D.L. Dill, "Exact Two-level Minimization of Hazard-free Logic with Multiple-Input Changes," IEEE Trans. CAD, vol. CAD-14, pp. 986-997, Aug. 1995.
[13]
D.S. Kung, "Hazard-Non-Increasing Gate-Level Optimization Algorithms," in Proc. ICCAD, pp. 631, 1992.
[14]
B. Lin and S. Devadas, "Synthesis of Hazard-Free Multilevel Logic Under Multi-Input Changes from Binary Decision Diagrams," IEEE Trans. CAD, vol. 14, pp. 974-985, Aug. 1995.
[15]
M. Singh and S.M. Nowick, "Synthesis-for-initializability of asynchronous sequential machines," in Proc. of ITC, 1996.
[16]
M. Singh and S.M. Nowick. Logic Synthesis for Initializability of Synchronous Finite State Machines. TR-CUCS-036-96, Dept. of Computer Science, Columbia University (to appear).
Recommendations
Synthesis for logical initializability of synchronous finite-state machines
Special issue on the 11th international symposium on system-level synthesis and design (ISSS'98)Logical initializability is the property of a gate-level circuit whereby it can be driven to a unique start state when simulated by a three-valued (0, 1, X) simulator. In practice, commercial logic and fault simulators often require initialization under ...
Initializability Consideration in Sequential Machine Synthesis
It is shown that a finite-state machine, whose state encoding is obtained only to reduce the amount of logic in the final implementation, may not be initializable by a logic simulator or a test generator even when the circuit is functionally ...
Multi-level logic optimization of FSM networks
ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided designAbstract: Current approaches to compute and exploit the flexibility of a component in an FSM network are all at the symbolic level. Conventionally, exploitation of this flexibility relies on state minimizers for incompletely specified FSMs (ISFSMs) or ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 1997
ISBN:0818677554
Copyright © Copyright (c) 1997 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.
Publisher
IEEE Computer Society
United States
Publication History
Published: 04 January 1997
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Dec 2024