Tallinn Technical University
DEPARTMENT OF COMPUTER ENGINEERING
Chair for Computer Hardware and Diagnostics

Research Results


 



Head of the Chair: Prof. Raimund Ubar

The main research results obtained in the recent years by the staff and students at the chair belong to the following fields of Digital Design and Test:


1. Decision Diagrams in Test Synthesis and Diagnosis of Digital Systems
A new approach based on decision diagrams (DD) to create algorithms and tools for automated test design and fault diagnosis for digital systems was developed.
DDs were proposed the first time for test generation under the name of alternative graphs (AG) in [8].
Unlike the traditional binary decision diagrams (BDD), a special class of structurally synthesized BDDs (SSBDD) support test design for gate-level structural faults (whereas BDDs can help only getting functional tests with uncertain quality for the given implementation).
DDs serve as a mathematical basis for solving a wide spectrum of test design tasks, resulting in a uniform model and a restricted set of standardized procedures (horizontal universality). They also allow a uniform approach to test design at different system levels (vertical universality).
DD-approach made it possible to describe a wide class of digital circuits and systems on mixed logical and functional levels. This class contains random logic, traditionally treated at the gate level, as well as digital systems like microprocessors, controllers etc., traditionally described at the procedural or RTL levels.
On the basis of the proposed DD-description, a general fault model for digital systems was developed. The proposed model covers in a uniform way a wide class of faults at different system representation levels (stuck-at faults, opens, shorts, functionality faults, different functional faults introduced specially for microprocessors, or for VHDL designs). The model defined on DDs can be regarded as a generalization of the classical gate-level stuck-at fault model.

References:

  1. R. Ubar. Multi-Valued Simulation of Digital Circuits with Structurally Synthesized Binary Decision Diagrams. OPA (Overseas Publishers Assotiation) N.V. Gordon and Breach Publishers, Multiple Valued Logic, Vol.4  pp. 141-157, 1998.
  2. R.Leveugle, R.Ubar. Synthesis of Decision Diagrams from Clock-Driven Multi-Process VHDL Descriptions for Test Generation. Proc. of the 5th International Conference on Mixed Design of Integrated Circuits and Systems. Lodz (Poland), June 18-20, 1998, pp. 353-358. Best Paper Award.
  3. R. Ubar. Test Synthesis with Alternative Graphs. IEEE Design & Test of Computers, 1996 Spring, pp. 48-57.
  4. Fehler in Automaten. By  D.Bochmann and R.Ubar. VEB Verlag Technik, Berlin,1989, 216 S.
  5. R. Ubar. Test Generation for Digital Systems on the Vector Alternative Graph Model. Proc. of the 13th Annual Int. Symp. on Fault Tolerant Computing, Milano, Italy, 1983, pp.374-377.
  6. M.Plakk, R.Ubar. Digital Circuit Test Design using the Alternative Graph Model. Automation and Remote Control, Vol.41, No 5, part 2,  Nov. 1980, Plenum Publishing Corporation, USA, pp. 714-722.
  7. R. Ubar. Beschreibung Digitaler Einrichtungen mit Alternativen Graphen für die Fehlerdiagnose. Nachrichtentechnik/Elektronik, (30) 1980, H.3, pp.96-102.
  8. R. Ubar.Test generation for digital circuits using alternative graphs. Proc. of Tallinn Technical University, Estonia, No.409, 1976, pp.75-81 (in Russian).
2. New Test Generation Methods

2.1. Hierarchical Test Synthesis for Digital Systems.
On the basis of generalization of DDs, new test generation methods for complex multi-level systems have been developed.
Differently from known methods both, higher and lower design abstraction levels, and both, control and data paths are handled by uniform fault models and procedures. Joint formal basis for gate- and higher level descriptions allowed to adopt and generalize gate-level methods to higher level ones, and to increase the test generation efficiency.
A novel conception of mixed level combining of deterministic and random techniques in test generation is introduced. On the RT-level, deterministic path activating is combined with random techniques used in constraints solving. The gate-level local test patterns for components are randomly generated driven by high-level constraints and partial path activation solutions. The technique of mixing deterministic and random approaches allows more efficiently handle high-level constraints while deriving local test patterns for components.
Top-down and bottom-up approaches are combined in the same framework which allows to increase the efficiency of the test generation for a broader class of digital systems.
The new hierarchical test generator shows the highest speed compared to the known generators for a given set of internationally recognized benchmark circuits [7].
The dramatic increase in the speed of test generation was reached by simplifying the fault propagation procedure, which in some cases may lead to a lower fault coverage. For the given bechmark circuits, however, the loss in fault coverage was minimal.

References:

  1. J.Raik, R. Ubar. Sequential Circuit Test Generation Using Decision Diagram Models. IEEE Proc. of  Design Automation and Test in Europe. Munich, March  9-12, 1999.
  2. R. Ubar. Combining Functional and Structural Approaches in Test Generation for Digital Systems. Journal of Microelectronics and Reliability, Elsevier Science Ltd. Vol. 38:3, pp.317-329, 1998.
  3. M.Brik, G.Jervan, A.Markus, J.Raik, R.Ubar. Hierarchical Test Generation for Digital Systems. In "Mixed Design of Integrated Circuits and Systems". Kluwer Academic Publishers, pp.131-136, 1998.
  4. G.Jervan, A.Markus, J.Raik, R.Ubar. Mixed-Level Deterministic-Random Test Generation for Digital Systems. Proc. of the 5th International Conference on Mixed Design of Integrated Circuits and Systems. Lodz (Poland), June 18-20, 1998, pp. 335-340.
  5. J.Raik, R.Ubar. Hierarchical Test Generation for Digital Systems Based on Combining Bottom-Up and Top-Down Approaches. World Multiconference on Systemics, Cybernetics and Informatics. Orlando, Florida, July 12-16, 1998, Vol.1, pp. 374-381.
  6. G. Jervan, A.Markus, J. Raik, R. Ubar. Assembling Low-Level Tests to High-Level  Symbolic Test Frames. IEEE 15th NORCHIP Conference, Tallinn, November 10-11, 1997, pp. 275-280.
  7. R. Ubar. Test Synthesis with Alternative Graphs. IEEE Design and Test of Computers. Spring, 1996, pp.48-59.
2.2. Test Generation for Finite State Machines
A new multi-level solution of automated test pattern generation (ATPG) and fault diagnosis in finite state machines based on DDs was developed. For the description of functions, structure and faults in FSM, three levels are used: functional level (state transition diagrams), logical or signal-path level and gate level. For all these levels, uniform description language, uniform fault model and uniform procedures for ATPG and test analysis were developed. This uniformity allows easily to move and carry partial results from level to level when solving the tasks mentioned.
The ATPG approach proposed allows to solve the inconsistencies of signals by backtracking at the level where signals were assigned without crossing level borders. This helps to reduce search area, and the complexity of test generation for sequential circuits is reduced nearly to the complexity of the combinational circuits.

References:

  1. R.Ubar, M.Brik. Multi-Level Test Generation and Fault Diagnosis for Finite State Machines. Lecture Notes in Computer Science No 1150. Dependable Computing - EDCC-2. Springer-Verlag, 1996, pp.264-281.
  2. R. Ubar. Fault Diagnosis in Digital Devices. Proceedings of the Estonian Academy of Sciences, Engineering, 1995, No. 1/1, pp.51-67.
2.3. Functional Test Generation for Microprocessors
High level approach is used, which makes the solution independent of internal circuit details. This independence is important to designers of microprocessor-based systems, where main sources of information are user manuals. The task of input data preparation can be distributed between different experts with different skills: a designer produces the description of the system, a test programmer prepares subroutine templates for the test equipment, and a test expert should create local test data for testing functions (if the gate-level implementation of these functions is known, the local test data can be generated automatically).
The methods developed are uniform for different levels of hierarchy, for example, for behavioral (instruction sets or procedural descriptions), functional (macrocomponent netlists),  or for logical (gate netlists) levels.
The the following advantages were obtained: independency of tests from the given tester, reduced memory cost because of concisely structured tests, and reduced time cost for loading test data which allows to increase the throughput of tester.

References:

  1. R.Ubar, A.Markus, G.Jervan, J.Raik. Fault Model and Test Synthesis for RISC Processors. Baltic Electronics Conference. Proceedings. Tallinn, October 7-11, 1996, pp. 229-232.
  2. R. Ubar. Test Generation for Digital Systems Based on Alternative Graphs Theory. Lecture Notes in Computer Science No 852. Dependable Computing - EDCC-1. Springer-Verlag, 1994, pp.151-164.
  3. R.Ubar, J.Dushina, H.Krupnova, S.Storozhev, V.Zaugarov. Functional Test Program Generation for Digital Systems. Proc. of the 6. Workshop "Testmethoden und Zuverlässigkeit von Schaltungen und Systemen", Vaals (Niederlande), March 6-8, pp. 14-18, 1994.
  4. R.Ubar, K.Kuchcinski, Z.Peng. Test generation of digital systems at functional level. The 2nd European Test Conference, Munich, Germany, April 10-12, 1991.
  5. T.Lohuaru, R.Ubar. A set of tools for diagnosis of digital devices. PC World, Information Computer Enterprise, Moscow, No1, 1991, pp.122-125.
  6. R. Ubar. Test Generation for Digital Systems on the Vector Alternative Graph Model. Proc. of the 13th Annual Int. Symp. on Fault Tolerant Computing, Milano, Italy, 1983, pp.374-377.
2.4. Gate-Level Test Generation
A novel low.level test generation approach was developed based on structurally synthesized BDDs (SSBDD) which provide a compact representation of gate-level circuits, unlike traditional BDDs they support directly gate-level faults.
Traditional PODEM test generation algorithm was implemented on SSBDDs, which showed higher speed than earlier gate-level PODEM implementations.

References:

  1. R. Ubar. Combining Functional and Structural Approaches in Test Generation for Digital Systems. Journal of Microelectronics and Reliability, Elsevier Science Ltd. Vol. 38:3, pp.317-329, 1998.
  2. J.Raik, R.Ubar. Feasibility of Structurally Synthesized BDD Models for Test Generation. Proc. of the IEEE European Test Workshop, Barcelona, May 27-29, 1998, pp.145-146.
  3. J.Raik, R.Ubar. Test Generation with Structurally Synthesized BDD Models. Proceedings of the 5th Electronic Devices and Systems Conference, Brno, June 11-12, 1998, pp.66-68.
  4. E.Ivask, J.Raik, R.Ubar. Comparison of Genetic and Random Techniques for Test Pattern Generation. Proc. of the 6th Baltic Electronics Conference, Oct. 7-9, 1998, Tallinn, pp. 163-166.
  5. A.Markus, J.Raik, R.Ubar. Test Set Minimization Using Bipartite Graphs. Proc. of the 6th Baltic Electronics Conference, Oct. 7-9, 1998, Tallinn, pp. 175-178.


3. New Approaches to Fault Simulation

3.1. High Level Fault Simulation
A new conceptual approach based on high-level decision diagrams for simulation of digital systems was developed. DDs allow to uniformly describe a wide class of digital systems on mixed logical and functional levels. This class contains random logic, traditionally treated at the gate level, as well as complex digital circuits like microprocessors, controllers etc., traditionally described at the procedural or RTL levels. Unlike the HDL-based descriptions, DDs give an excellent formal basis for diagnostic analysis of digital systems, and allow to create more efficient CAD tools than event-driven HDL-based simulators for functional simulation as well as for fault analysis and testing purposes. Due to the fact that only a part of DDs should be traced during simulation and due to neglecting the time specific information inherent in HDL descriptions, the speed of simulation on DDs can be drastically increased in comparison to traditional event-driven simulators.
The research has been carried out in a close cooperation with Laboratories CSI and TIMA in Grenoble, France.

References:

  1. R.Leveugle, R. Ubar. Modeling VHDL Clock-Driven Multi-Processes by Decision Diagrams. In "Mixed Design of Integrated Circuits and Systems". Kluwer Academic Publishers, 1999.
  2. R.Ubar, A.Moraviec, J.Raik. Cycle-based Simulation with Decision Diagrams. IEEE Proc. of Design Automation and Test in Europe. Munich, March  9-12, 1999.
  3. R. Ubar. Behavioral Level Modeling of Digital Systems for Testing Purposes. 42nd International Conference, Ilmenau, September 22-25, 1997.
3.2. Fault Simulation at the Gate Level
A new method was developed for fault analysis based on combining the parallel backward critical path tracing inside fanout free regions (FFR) with parallel forward critical path tracing between FFRs for FFR stem fault analysis. The detectability of all given faults is calculated by one simulation pass simultaneously for N test patterns, where N is the length of the computer word. Because of reducing the complexity of the network model to be analysed and because of the fault collapsing on FFR paths to only two representative faults, the efficiency of the simulation rises and the capacity of the memory needed reduces, compared to the known gate- or macro-level approaches.

References:

  1. R. Ubar. Behavioral Level Modeling of Digital Systems for Testing Purposes. 42nd Int. Conference, Ilmenau, Sept. 22-25, 1997.
  2. R. Ubar. Parallel Critical Path Tracing Fault Simulation. Proc. of the 39th Int. Conference. Ilmenau, Sept. 27-30, 1994. Band 1, pp. 399-404.
  3. R. Ubar. Analysis of Diagnostic Tests for Combinational Circuits by Method of Backtracking of Faults. Automation and Remote Control, Vol.40, No.11, part 2, Nov. 1978. Plenum Publishing Corporation, USA, pp. 1254-1260.
3.3. Dynamic Simulation Methods
A new efficient multi-valued simulation approach for combinational or scan-path circuits for delay fault analysis, hazard detection or dynamic test analysis was developed. Its basic idea is substituting the traditional gate-level waveform calculation by nested Boolean differential calculus on structurally synthesized BDDs. Introducing SSBDDs allows to reduce the complexity of the model by replacing low-level two-input-gate networks with higher macro-level representations. It is not needed to create for each new macro-block a separate dedicated multi-valued model. Instead, from the gate-level description automatically a SSBDD-representation will be created, where a single general procedure for all types of macros will be used. Experimental results showed the efficiency of the new approach, compared to the traditional gate-level simulation. The efficiency of simulation is increasing with increasing the number of levels in the gate-level circuit.

References:

  1. R. Ubar. Multi-Valued Simulation of Digital Circuits with Structurally Synthesized Binary Decision Diagrams. OPA (Overseas Publishers Assotiation) N.V. Gordon and Breach Publishers, Multiple Valued Logic, Vol.4  pp. 141-157, 1998.
  2. R. Ubar. Dynamic Analysis of Digital Circuits with 5-valued Simulation. In "Mixed Design of Integrated Circuits and Systems". Kluwer Academic Publishers, pp.187-192, 1998.
  3. R. Ubar. Dynamic Analysis of Digital Circuits with Multi-Valued Simulation. Microelectronics Journal, Elsevier Science Ltd., Vol. 29, No. 11, Nov. 1998, pp.821-826.


4. New Methods for Estimating Fault-Tolerance of Systems

A new technique was developed to select malicious faults for dependability validation of fault-tolerant systems. A high-level fault analysis method based on decision diagrams is applied. Thanks to the generality of DDs, the present approach is independent from the fault model. This independence allows easy introduction of hierarchy and multilevel fault handling.
The main idea of the approach is to carry out fault analysis and malicious fault list generation at a higher behavioral level where the complexity of the model is low. The high-level reduced fault list will be translated then into a lower-level fault list. In such a way, low-level fault analysis in low-level circuit descriptions can be avoided.
Differently from the known method based on using data flow diagrams where only data fault analysis is possible, the new method is more general, and allows explicit handling in a uniform way of both data and control faults.
Instead of expanding the full explicit data flow whose size can explode, fault tracing is carried out on the compressed high-level DD-model to build up a fault tree.
A new result is also integration of different methods for fault collapsing. On a simple high-level example it was shown that the new method allowed to reduce the malicious fault candidate list more than 4 times for control faults and more than twice for data faults.
The research has been carried out in a close cooperation with the research group of prof. Prinetto at Politechnico di Torino, Italy.

References:

  1. A. Benso, P.Prinetto, M.Rebaudengo, M.Sonza, R.Ubar. A New Approach to Build a Low-Level Malicious Fault List Starting from High-Level Description and Alternative Graphs. Proc. IEEE European Design & Test Conference, Paris, March 17-20, 1997.
  2. A.Benso, P.Prinetto, M.Rebaudengo, M.Sonza Reorda, J.Raik, R.Ubar. Exploiting High-Level Descriptions for Circuits Fault Tolerance Assessments.  1997 IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems. Paris, October 20-22, 1997, pp. 212-216.
5. Verification and Design Error Diagnosis

A new approach is presented to automatically diagnose single gate design errors in combinational circuits. The main original feature of the method is the idea of mapping stuck-at fault diagnosis results into the final localization of the design error. This allows to use the test patterns and fault tables generated by traditional stuck-at fault test generators to produce design error diagnosis.
The other important features of the approach are: hierarchical approach, based on using structurally synthesized BDDs, and the use of very powerful error detection and fault localization procedures based on SSBDDs.
The future research in this field is directed to the case of multiple design errors and to the case of complex gates. The use of word level DDs seems to be very efficient in design error diagnosis at higher functional levels like RTL or behavioral ones.
The research is carried out in a close cooperation with the research group of prof. Borrione at the TIMA Laboratory in Grenoble, France.

References:

  1. R.Ubar, D.Borrione. Generation of Tests for the Localization of Single-Gate Design Errors in Combinational Circuits Using the Stuck-at Fault Model. Proc. of the 11th IEEE Brasilian Symposium on Integrated Circuit Design. Rio de Janeiro, Brazil, Sept. 30 – Oct. 3, 1998, pp.51-54
  2. R.Ubar, D.Borrione. Localization of Single-Gate Design Errors in Combinational Circuits by Diagnostic Information about Stuck-at Faults. Proc. of the 2nd International Workshop on Design and Diagnostics of Electronic Circuits and Systems. Szczyrk, Poland, Sept. 2-4, 1998, pp.73-79.
  3. R.Ubar, D.Borrione. Single Gate Design Error Diagnosis in Combinational Circuits. Proceedings of the Estonian Acad. of Sci. Engng, 1999, Vol. 5 , No 1, pp.3-21.


6. Design for Testability

A new technique for calculating the testability measures of combinational circuits represented by structurally synthesized BDDs is presented. The following advantages of the technique can be outlined: 1) instead of gate-level, higher macro-level is considered which reduces the complexity of the model; 2) no libraries of controllability and observability models for macros are needed; 3) a generic procedure developed for SSBDDs can be used for different testability measures defined either in probabilistic or heuristic ways; 4) the proposed method has overcome the problem of reconvergent fanouts at the subcircuit (macro) level, which allows to calculate exact probabilities by a simple cumulative procedure.
The new technique to testability analysis is applicable for sequential and combinational circuits specified at higher functional levels. The primary use of the developed testability measures will be in the evaluation of various designs in the early de-sign phase. Since the measures are defined at the higher level compared to the gate level, they can be used early in the design process, before the final implementation is available. The new technique developed is based on DDs which allow a uniform representation of both combinational and sequential circuits. Known methods for testability calculation are based on different models for these types of circuits, in particular, BDDs for combinational circuits and state tables for sequential circuits, and therefore they require different techniques and algorithms for calculation. Another advantage of new algorithms is the generality in regard to different testability measures.
This research is currently carried on in a close cooperation with prof. Zebo Peng at Linköping University, Sweden.

References:

  1. R.Ubar, J.Heinlaid, J.Raik, L.Raun. Calculation of Testability Measures on Structurally Synthesized Binary Decision Diagrams. Proc. of the 6th Baltic Electronics Conference, Oct. 7-9, 1998, Tallinn, pp. 179-182.
  2. R.Ubar, K.Kuchcinski. Functional Level Testability Analysis for Digital Circuits. Proc. of European Test Conference ETC'93, Rotterdam, April 19-22, 1993, pp.545-546.
  3. R.Ubar, K.Kuchcinski, Z.Peng. Test generation of digital systems at functional level. The 2nd European Test Conference, Munich, Germany, April 10-12, 1991.
7. Development of CAD Software for Automatization of Test Design

On the mathematical basis of structurally synthesized BDDs a set of new algorithms and CAD tools for solving test design tasks on the logical level representation of digital circuits has been developed and implemented in a software system Turbo-Tester.
The software package consists of the following tools: test pattern generation for circuits with scan-path (deterministic, random and genetic approaches), test quality analysis for stuck-at and delay faults (fault simulation and parallel critical path tracing method), multivalued simulation (for hazard analysis and dynamic testing), fault grading (for estimating the quality of random testing and Built-In Self-Test architectures – BILBO, Circular Self Test Path). The package has been introduced into the university teaching, it has been used in teaching in Estonia, Finland and Sweden.

References:

  1. R. Ubar. Teaching Dependability Issues in System Engineering at the Technical University of Tallinn. Global J. of Engineering Education, Vol.2, No 2, 1998 UICEE, Printed in Australia, pp. 215-218.
  2. G.Jervan, A.Markus, P.Paomets, J.Raik, R.Ubar. Turbo Tester: A CAD System for Teaching Digital Test. In "Microelectronics Education". Kluwer Academic Publishers, pp.287-290, 1998.
  3. R.Ubar, P.Paomets, J.Raik. Low-Cost CAD System for Teaching Digital Test. Microelectronics Education. World Scientific Publishing Co. Pte. Ltd. 1996, p.185-188.
  4. R. Ubar, A. Buldas, P. Paomets, J.Raik, V. Tulit. A PC-based CAD System for Training Digital Test. 5th  EUROCHIP Workshop on VLSI Design Training. Dresden, October 17-19, 1994, pp.152-157.


8. Development activities in microelectronics design

8.1.  CC – a cryptographical module for digital communications.
8.2.  Digital Encryption Standard Macroblock – a design for an ASIC (contract with Fincitec OY Finland).

References:

  1. J.Põldre, K.Tammemäe, M.Mandre. Modular Exponent Realization on FPGAs Lecture Notes in Computer Science 1482. Field-Programmable Logic and Applications. Springer-Verlag, 1998, pp.336-347.
  2. A.Buldas, J.Põldre. A VLSI Implementation of RSA and IDEA encryption engine IEEE 15th NORCHIP Conference, Tallinn, November 10-11, 1997,  pp. 281-288.
9.  Software Developed in the Laboratory

a) Tools for test generation and fault analysis dor digital circuits and systems

b) Converters c) Libraries d) Scripts for synthesis