Abstract
The scan design is the most widely used technique used to ensure the testability of sequential circuits. In this article it is shown that testability is still guaranteed, even if only a small part of the flipflops is integrated into a scan path. An algorithm is presented for selecting a minimal number of flipflops, which must be directly accessible. The direct accessibility ensures that, for each fault, the necessary test sequence is bounded linearly in the circuit size. Since the underlying problem is NP-complete, efficient heuristics are implemented to compute suboptimal solutions. Moreover, a new algorithm is presented to map a sequential circuit into a minimal combinational one, such that test pattern generation for both circuit representations is equivalent and the fast combinational ATPG methods can be applied. For all benchmark circuits investigated, this approach results in a significant reduction of the hardware overhead, and additionally a complete fault coverage is still obtained. Amazingly the overall test application time decreases in comparison with a complete scan path, since the width of the shifted patterns is shorter, and the number of patterns increase only to a small extent.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
V.D. Agrawal, K. Cheng, D.D. Johnson, and T. Lin, “A complete solution to the partial scan problem,” Proc. IEEE Intern. Test Conf., pp. 44–51, September 1987.
V.D. Agrawal, K.-T. Cheng, D.D. Johnson, and T. Lin, “Designing circuits with partial scan, IEEE Design & Test Comput. 6 (2): 8–15, 1988.
M.J.Y. Williams and J.B. Angell, “Enhancing testability of large scale integrated circuits via test points and additional logic,” IEEE Trans. Comput. C-22 (1), 1973.
R.G. Bennetts, Design of Testable Logic Circuits, Addison-Wesley, London, 1984.
J.J. LeBlanc, “LOCST: A built-in self-test technique” IEEE Design & Test Comput. 1 (4): 45–52, 1984.
K. Cheng and V.D. Agrawal, “An economical scan design for sequential logic test generation,” Proc. 19th Intern. Symp. Fault-Tolerant Comput., pp. 28–35, June 1989.
N. Christofides and S. Korman, “A computational survey of methods for the set covering problem, Management Science 21 (5): 591–599, 1975.
A. Ehrenfeucht, L. Fosdick, and L. Osterweil, “An algorithm for finding the elementary circuits of a directed graph,” Tech. Rep. CU-CS-024–23, Dept. of Computer Science, University of Colorado, Boulder, 1973.
E.B. Eichelberger and T.W. Williams, “A logic design structure for LSI testability,” Proc. 14th ACM/IEEE Design Autom. Conf., pp. 462–468, 1977.
A.D. Friedman and P.R. Menon, Theory and Design of Switching Circuits, Computer Science Press, Rockville, MD, 1975.
H. Fujiwara and T. Shimono, “On the acceleration of test generation algorithms,” Proc. 13th Intern. Symp. Fault-Tolerant Comput., pp. 98–105, 1983.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman, San Francisco, 1979.
R. Gupta, R. Gupta, and M.A. Breuer, “BALLAST: A methodology for partial scan design,” Proc. 19th Intern. Symp. Fault-Tolerant Comput., pp. 118–125, 1989.
P. Goel, “An implicit enumeration algorithm to generate tests for combinational logic circuits,” IEEE Trans. Comput. C-30 (3): 215–222, 1981.
L.H. Goldstein, “Controllability/observability analysis of digital circuits,” IEEE Trans. Circuits and Systems CAS-26 (9): 685–693, 1979.
P. Gutberlet, “Entwurf eines schnellen Matrizen-Multiplizierers,” Studienarbeit Fakultät Informatik, Universität Karlsruhe, 1988.
O. Haberl, “Entwurf und Implementierung eines PROLOG-Preprozessors als Standardzellen-Chip mit dem Entwurfssystem VENUS,” Diplomarbeit an der Fakultät Informatik, Universität Karlsruhe, 1986.
J. Hartmanis, “Loop-free structure of sequential machines,” Information and Control (5): 25–43, 1962.
D.B. Johnson, “Finding all the elementary circuits of a directed graph,” SIAM J. Comput. 4(1): 77–84, 1975.
R.M. Karp, “Reducibility among combinatorial problems,” In R.E. Miller and J.W. Thatcher (eds.), Complexity of Computer, Computations, Plenum Press, New York, pp. 85–103, 1972.
A. Kunzmann, Verbesserung der Testbarkeit von Schaltwerken durch die Integration eines unvollständigen Prüfpfades,” Interner Bericht 25/87, Universität Karlsruhe, Fakultät für Informatik, Oktober 1987.
A. Kunzmann, “Produktionstest mit deterministisch bestimmten Testmustern: der Testmustergenerator SPROUT,” Interner Bericht 26/87, Universität Karlsruhe, Fakultät für Informatik, Oktober 1987.
A. Kunzmann, Produktionstest synchroner Schaltwerke auf der Basis von Pipeline-Stukturen, GI-Jahrestagung, Hamburg, 1988.
A. Kunzmann, “Test synchroner Schaltwerke auf des Basis partieller Prüfpfade,” VDI-Verlag, Fortschritt-Berichte 10 (117), Düsseldorf, 1989.
A. Kunzmann and H.-J. Wunderlich, “Design automation of random testable circuits,” 11th European Solid State Circuits Conf. (ESSCIRC), pp. 277–285, 1985.
ETA LASAR Users Guide, Vers. 4.7, November 1985.
H.T. Ma et al., “An incomplete scan design approach to test generation for sequential machines,” Proc. Intern. Test Conf., pp. 730–734, 1988.
P. Muth, “A nine-valued circuit model for test generation,” IEEE Trans. Comp. C-25 (6): 630–636, 1976.
J.P. Roth, “Sequential test generation,” Technical Disclosure Bull., IBM, January 1978.
M.H. Schulz and E. Auth, “SOCRATES: Advanced automatic test pattern generation and redundancy identification techniques,” Proc. 18th Intern. Symp. Fault-tolerant Comput., pp. 30–35, Tokyo, 1988.
M.H. Schulz, E. Trischler, and T.M. Sarfert, “SOCRATES: A highly efficient automatic test pattern generation system,” Proc. Intern. Test Conf., 1987.
R. Tarjan, “Enumeration of the elementary circuits of a directed graph,” SIAM J. Comput. 2 (3): 211–216, 1973.
J.C. Tiernan, “An efficient search algorithm to find the elementary circuits of a graph,” Comm. ACM, 13, pp. 722–726, 1970.
E. Trischler, “Testability analysis and incomplete scan path,” Proc. Intern. Conf. Computer-Aided Design S, pp. 38–39, 1983.
E. Trischler, “Incomplete scan path with an automatic test generation methodology,” Proc. Intern. Test Conf., pp. 153–162, 1984.
H. Weinblatt, “A new search algorithm for finding the simple cycles of a finite directed graph,” J. Assoc. Comput. Mach., 19: 43–56, 1972.
H.-J. Wunderlich, “PROTEST: A tool for probabilistic testability analysis,” Proc. 22th Design Autom. Conf., pp. 204–211, 1985.
H.-J. Wunderlich, “On computing optimized input probabilities for random tests,” Proc. 24th Design Autom. Conf., pp. 382–389, 1987.
H.-J. Wunderlich, “The design of random-testable sequential circuits,” Proc. 19th Intern. Symp. Fault-Tolerant Comput., pp. 110–111, 1989.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kunzmann, A., Wunderlich, HJ. An analytical approach to the partial scan problem. J Electron Test 1, 163–174 (1990). https://doi.org/10.1007/BF00137392
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00137392