A Constraint-Driven Gate-Level Test Generator

Jaan Raik, Raimund Ubar, Gert Jervan, Helena Krupnova

Electronics Competence Centre
Tallinn Technical University


In current paper, a constraint-driven gate-level test generator which operates as a low-level part of a hierarchical datapath test generation system is presented. The low-level test generator generates tests for gate-level structural faults taking into account the functional constraints, which have been previously extracted during high-level path activation. Both, the high-level and the low-level test generators operate on the design model of alternative graphs (AG). Experimental results have been included, showing the acceleration of fault simulation speed on structural AG model compared to the conventional gate-level netlist representation.

In recent times, a lot of effort has been made in the field of functional testing to solve the problem of testing complex digital devices. However, the functional test generation approaches are often ineffective due to the lack of information about the structural implementation on higher model abstraction levels. At present, more and more digital circuits are being created through designer's interaction with high-level synthesis (HLS) tools. The output of these tools is register-transfer (RT) level description, i.e. representation where design has been partitioned into control (a finite state machine) and datapath (network of functional units) parts.

A hierarchical test generation method for gate-level datapath faults will be presented. The method operates on two design abstraction levels: RT-level (referred to as higher level) and gate level (lower level). Hierarchical test generation approach is based on the 'divide and conquer' principle. In the approach device under test is considered at different abstraction levels and test generation is performed on these levels by utilizing an appropriate test generation tool. In hierarchical testing, top-down and bottom-up strategies are known. In the bottom-up approach, tests generated at the lower abstraction level will later be assembled at the higher level. Current paper describes a hierarchical system implementing the top-down approach, where constraints extracted at higher level are taken into account while deriving tests for the lower level.

  1. R. Ubar. Test Generation for Digital Circuits Using Alternative Graphs. Proc. of Tallinn Technical University, Estonia, No. 409, pp. 75-81 (in Russian), 1976.

  2. B. Akers. Binary Decision Diagrams. IEEE Trans. On Computers, Vol. 27, pp. 509-516, 1978.

  3. J. Lee, J. H. Patel. ARTEST: An Architectural Level Test Generator for Data Path Faults and Control Faults. Proc. Int. Test Conf., pp. 729-738, Oct. 1991.

  4. J. Lee, J. H. Patel. Hierarchical Test Generation under Intensive Global Functional Constraints. Proc. 29th ACM/IEEE Design Automation Conf., pp. 261-266, June 1992.

  5. H. Krupnova, R. Ubar. Constraints Analysis in Hierarchical Test Generation for Digital Systems. Proc. of the 4th Baltic Electronics Conference, Tallinn, pp. 313-318, Oct. 1994.

  6. R. Ubar. Test Synthesis with Alternative Graphs. IEEE Design and Test of Computers, Vol.13, No. 1, pp. 48-57. Spring 1996.

  7. K. Tilly. A Comparative Study of Automatic Test Pattern Generation and Constraint Satisfaction Methods. Ser. Electrical Engineering, Budapest, June, 1994.

  8. M.S. Abadir and M.A. Breuer. A Knowledge Based System for Designing Testable VLSI Chips. IEEE Design and Test, pp. 56-68, Aug. 1985.

  9. Freeman, Test Generation for Data Path Logic: The F-Path Method. IEEE Journal of Solid State Circuits, vol.23, pp. 421-427, Apr. 1988.