Abstract
This paper discusses a new design methodology for concurrent error detection in synchronous sequential circuits based on the use of monitoring machines. In this approach, an auxiliary sequential circuit, called the monitoring machine, operates in lock-step with the main machine, such that any fault in either of the two machines is immediately detected. This methodology is independent of the fault model. It can be applied to FSMs with pre-encoded states and can also be used for ones being synthesised. It also provides a systematic framework for the combined optimisation of the main and monitoring machines, and for exploring tradeoffs in their implementation.
The design of monitored sequential circuits is a two-fold problem; namely one of designing an optimal monitoring machine given the main machine, and the other of encoding the main machine states so that the resulting monitoring machine is minimal. This paper formally discusses the design of both the main and monitoring machines and techniques for their combined optimisation. Tradeoffs in their implementation based on selective fault detection are also examined.
Through experimental results, it is shown that the proposed synthesis technique is eminently suitable for the design of low-cost sequential circuits with concurrent error detection. The monitoring machine is less costly than the main machine. It is also not identical to it. As a result, a monitored sequential circuit has significantly lower hardware cost and improved fault coverage than previous implementations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
V.D. Agrawal and S.C. Seth,Test Generation for VLSI Chips, IEEE Computer Society Press, Los Alamitos, CA, 1988.
M. Goessel and S. Graf,Error Detection Circuits, McGraw Hill Book Co., Berkshire, England, 1993.
G.L. Craig, C.R. Kime, and K.K. Saluja, “Test Scheduling and Control for VLSI Built-in Self-Test,”IEEE Trans. on Computers, Vol. 37, No. 9, pp. 1099–1109, September 1988.
T.W. Williams and K.A. Parker, “Design for Testability—A Survey,”IEEE Trans. on Computers, Vol. 31, No. 1, pp. 2–14, January 1982.
A. Mahmood and E.J. McCluskey, “Concurrent Error Detection Using Watchdog Processors—A Survey,”IEEE Trans. on Computers, Vol. 37, No. 2, pp. 160–174, February 1988.
R. Leveugle and G. Saucier, “Optimised Synthesis of Concurrently Checked Controllers,”IEEE Trans. on Computers, Vol. 39, No. 4, pp. 419–425, April 1990.
S.H. Robinson and J.P. Shen, “Direct Methods for Synthesis of Self-Monitoring State Machines,”Proc. 22nd IEEE Fault Tolerant Computing Symp., 1992, pp. 306–315.
V.S. Iyengar and L.L. Kinney, “Concurrent Fault Detection in Microprogrammed Control Units,”IEEE Trans. on Computers, Vol. 34, No. 9, pp. 810–821, September 1985.
L.P. Holmquist and L.L. Kinney, “Error Detection with Latency in Sequential Circuits,”Proc. Intl. Test Conf., 1988, pp. 926–933.
S. Devadas, H-K.T. Ma, A.R. Newton, and A. S-Vincentelli, “Synthesis and Optimisation Procedures for Fully and Easily Testable Sequential Machines,”Proc. IEEE Intl. Test Conf., 1988, pp. 621–630.
S. Devadas, “Delay Test Generation for Synchronous Sequential Circuits,”Proc. IEEE Intl. Test Conf., 1989, pp. 144–152.
V.D. Agrawal and K-T. Cheng, “Finite State Machine Synthesis with Embedded Test Function,”Journal of Electronic Testing: Theory and Applications, Vol. 1, pp. 221–228, 1990.
B. Eschermann, “Enhancing On-Line Testability During Synthesis,”Journal of Electronic Testing: Theory and Applications, Kluwer Academic Publ., Vol. 4, pp. 105–116, 1993.
R. Leveugle, R. Rochet, and G. Saucier, “Alternative Approaches to Fault Detection in FSMs,”Proc. IEEE Intl. Workshop on Defect and Fault Tolerance in VLSI Systems, October 1994, IEEE Computer Society Press, Los Alamitos, California, 1994.
J. Wakerly,Error Detecting Codes, Self-Checking Circuits and Applications, Elsevier North Holland, Inc., New York, 1978.
T. Nanya and T. Kawamura, “A Note on Strongly Fault-Secure Sequential Circuits,”IEEE Trans. on Computers, Vol. 36, No. 9, pp. 1121–1123, September 1987.
R. Amann and U.G. Baitinger, “Optimal State Chains and State Codes in Finite State Machines,”IEEE Trans. on CAD, Vol. 8, No. 2, pp. 153–170, February 1989.
R.A. Parekhji, G. Venkatesh, and S.D. Sherlekar, “A Methodology for Designing Optimal Self-checking Sequential Circuits,”Proc. IEEE Intl. Test Conf., 1991, pp. 283–291.
Z. Kohavi,Switching and Finite Automata Theory, McGraw-Hill, Inc., New York, 1978.
R.A. Parekhji,Design of Monitored Self-checking Sequential Circuits, Ph.D. Thesis, Dept. of Computer Science & Engg., Indian Institute of Technology, Bombay, India, 1994.
T. Villa and A.S- Vincentelli, “NOVA: State Assignment of Finite State Machines for Optimal Two-Level Logic Implementation,”IEEE Trans. on CAD, Vol. 9, No. 9, pp. 905–924, September 1990.
S. Devadas, H-K. Ma, A.R. Newton, and A.S- Vincentelli, “MUSTANG: State Assignment of Finite State Machines Targeting Multilevel Logic Implementations,”IEEE Trans. CAD, Vol. 7, No. 12, pp. 1290–1300, December 1988.
G.D. Micheli, R.K. Brayton, and A. S- Vincentelli, “Optimal State Assignment for Finite State Machines,”IEEE Trans. on CAD, Vol. 4, No. 3, pp. 269–285, July 1985.
G. Saucier, M.C. de Paulet, and P. Sicard, “ASYL: A Rule-Based System for Controller Synthesis,”IEEE Trans. on Computers, Vol. 36, No. 11, pp. 1088–1097, November 1987.
B. Lin and A.R. Newton, “Synthesis of Multiple Level Logic from Symbolic High-Level Description Languages,”Proc. IFIP Intl. Conf. on VLSI, 1989, in G. Musgrave and U. Lauther, (Eds.),VLSI 89, Elsevier Science Publ., North Holland, New York, 1990.
X. Du, G. Hachtel, B. Lin, and A.R. Newton, “MUSE: A MUltilevel Symbolic Encoding Algorithm for State Assignment,”IEEE Trans. on CAD, Vol. 10, No. 1, pp. 28–38, January 1991.
R.A. Parekhji, G. Venkatesh, and S.D. Sherlekar, “Concurrent Error Detection Using Monitoring Machines,”IEEE Design & Test of Computers, Vol. 12, No. 3, pp. 24–32, September 1995.
Logic Synthesis and Optimization Benchmarks, MCNC Intl. Workshop on Logic Synthesis, Microelectronics Center of North Carolina, USA, 1991.
R.K. Brayton, R. Rudell, A.S- Vincentelli, and A.R. Wang, “MIS: A Multiple-Level Logic Optimization System,”IEEE Trans. on CAD, Vol. 6, No. 6, pp. 1062–1081, November 1987.
Author information
Authors and Affiliations
Additional information
Presently at Texas Instruments (India) Ltd., Bangalore, India.
Rights and permissions
About this article
Cite this article
Parekhji, R.A., Venkatesh, G. & Sherlekar, S.D. Monitoring machine based synthesis technique for concurrent error detection in finite state machines. J Electron Test 8, 179–201 (1996). https://doi.org/10.1007/BF02341823
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02341823