Abstract
This paper reports a novel approach to design efficient BIST structures for sequential machines (FSMs) with reduced gate area. In a PRPG based BIST structure, an FSM shows limited testability due to three kinds of states, viz., the unreachable states, the hard-to-exit states, and the hard-to-reach states. A metric, referred to as degree-of-freedom (DOF) in FSM states has been introduced that quantifies the BIST quality of an FSM. Analysis of DOF enables efficient state encoding to ensure high BIST quality as well as low gate area of the resulting FSM. A genetic algorithm (GA) based graph embedding approach is adopted to solve the state encoding problem. Experimental results on benchmark circuits show that the proposed scheme improves the BIST quality significantly simultaneously reducing the gate area of the resultant machine.
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 K.-T. Cheng, ‘Finite State Machine Synthesis with Embedded Test Function,’ J. of Electronic Testing Theory and Applications, vol. 1, no. 3, pp. 221–228, 1990.
V.D. Agrawal, C.R. Kime, and K.K. Saluja, ‘A Tutorial on Built-in-Self-Test Part 1: Principles,’ IEEE Design and Test of Computers, 1993, pp. 73–82.
V.D. Agrawal, C.R. Kime, and K.K. Saluja, ‘A Tutorial on Built-in-Self-Test Part 2: Applications,’ IEEE Design and Test of Computers, 1993, pp. 69–77.
S.T. Chakradhar, S. Kanjilal, and V.D. Agrawal, ‘Finite State Machine Synthesis with Fault Tolerant Test Function,’ in Proc. of 29th ACM/IEEE Design Automation Conference, Anaheim, CA, 1992, pp. 562–567.
S. Devadas and K. Keutzer, ‘A Unified Approach to the Synthesis of Fully Testable Sequential Machines,’ IEEE Transactions on CAD, vol. 10, no. 1, pp. 39–50, 1991.
S. Devadas and A.R. Newton, ‘Decomposition and Factorization of Sequential Finite State Machines,’ IEEE Trans. on Computer-Aided Design, vol. 8, no. 11, pp. 1206–1217, 1989.
S. Devadas, M.A.R.H. Newton, and A. Sangiovanni-Vincentelli, ‘MUSTANG: State Assignment of Finite State Machines Targeting Multi Level Logic Implementations,’ IEEE Transactions on Computer-Aided Design, vol. 7, no. 12, pp. 1290–1300, 1988.
B. Eschermann and H.-J. Wunderlich, ‘A Unified Approach for the Synthesis of Self-Testable Finite State Machines,’ in Proc. of 28th ACM/IEEE Design Automation Conference, San Francisco, CA, 1991, pp. 372–377.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, New York: W.H. Freeman and Company, 1979.
D.E. Goldberg, Genetic Algorithms: Search, Optimization and Machine Learning, New York: Addison Wesley, 1989.
P. Kalla and M. Ceisielski, ‘A Comprehensive Approach to the Partial Scan Problem Using Implicit State Enumeration,’ IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 21, no. 7, pp. 810–826, 2002.
H.K. Lee and D.S. Ha, ‘HOPE: An Efficient Parallel Fault Simulator for Synchronous Sequential Circuits,’ IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 9, pp. 1048–1058, 1996.
B. Lin and A. Newton, ‘Synthesis of Multiple Level Logic from Symbolic High-level Description Languages,’ in Proc. of Int. Conf. on VLSI Design, 1989, pp. 187–196.
S. Liu, M. Pedram, and A.M. Despain, ‘A Fast State Assignment Procedure for Large FSMs,’ in Proc. of ACM/IEEE 32nd Design Automation Conf., 1995, pp. 327–332.
F. Muradali, T. Nishida, and T. Shimizu, ‘A Structure and Technique for Pseudo-Random-Based Testing of Sequential Circuits,’ Journal of Electronic Testing: Theory and Applications, pp. 107–115, 1995.
L. Nachman, K.K. Saluja, S. Upadhaya, and R. Reuse, ‘Random Pattern Testing for Sequential Circuits Revisited,’ in Proc. of 19th Fault-Tolerant Computing Symp., 1996, pp. 44-52.
P. Pal Chaudhuri, D.R. Chowdhury, S. Nandi, and S. Chatterjee, Additive Cellular Automata—Theory and Application, vol. 1, California, USA: IEEE Comp. Society Press, 1997.
I. Pomeranz and S.M. Reddy, ‘Built-in-Test Generation for Synchronous Sequential Circuits,’ in Proc. of Int. Conference on Computer-Aided Design, 1997, pp. 421–426.
I. Pomeranz and S.M. Reddy, ‘Improved Built-in Test Pattern Generators Based on Comparison Units for Synchronous Sequential Circuits,’ in Proc. of International Conference on Computer Design, 1998, pp. 26–31.
C.H.L. Quintero and M. Strum, ‘SINMEF—A Decomposition Based Synthesis Tool for Large FSMs,’ in Proc. of 9th VLSI Great Lakes Symposium, 1999, pp. 176–179.
S. Roy, B.K. Sikdar, M. Mukherjee, and D.K. Das, ‘Degree-of-Freedom Analysis for Sequential Machines Targeting BIST Quality and Gate Area,’ in Proc. of the 7th Asia and South Pacific Design Automation Conference and 15th Int. Conf. on VLSI Design (ASP-DAC/VLSID-2002), 2002, pp. 671–676.
B.K. Sikdar, S. Roy, and D.K. Das, ‘Enhancing BIST Quality of Sequential Machines Through Degree-of-Freedom Analysis,’ in Proc. of the Tenth Asian Test Conference, 2001, pp. 285–290.
SIS: A System for Sequential Circuit Synthesis, University of California, Berkeley, Rep. M92/41, 1992.
A.P. Storele and H. Wunderlich, ‘Hardware-Optimal Test Register Insertion,’ IEEE Transactions on Computer-Aided Design, vol. 17, no. 6, pp. 531–539, 1998.
H. Wunderlich, ‘The Design of Random Testable Sequential Circuits,’ in Proceedings of 19th Fault-Tolerant Computing Symposium, 1989, pp. 110–117.
H. Wunderlich and G. Kiefer, ‘BIT-Flipping BIST,’ in Proc. of International Conference on Computer-Aided Design, 1996, pp. 337–343.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sikdar, B.K., Roy, S. & Das, D.K. A Degree-of-Freedom Based Synthesis Scheme for Sequential Machines with Enhanced BIST Quality and Reduced Area. J Electron Test 21, 83–93 (2005). https://doi.org/10.1007/s10836-005-5289-4
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/s10836-005-5289-4