eesti teaduste
akadeemia kirjastus
Estonian Journal of Engineering

Canonical representations of high-level decision diagrams; pp. 39–55

Full article in PDF format | doi: 10.3176/eng.2010.1.06

Anton Karputkin, Raimund Ubar, Jaan Raik, Mati Tombak

In this paper we give a short overview of the decision diagrams, and define a special class of high-level decision diagrams (HLDD) for formal representation of digital systems. We show how the HLDDs can be used for high-level verification of digital systems. For this purpose, HLDDs are represented by characteristic polynomials as a canonical form of HLDDs. The polynomials can be used for proving the equivalence between two HLDDs, which have the same functionalities but may have different internal structures. Some possibilities are shown how to cope with the complexity of the verification problem.

  1. Kapuer, R. High Level ATPG is important and is on its way! In Proc. IEEE International Test Conference. Atlantic City, NJ, 1999, 1115–1116.

  2. Corno, F., Cumani, G., Sonza Reorda, M. and Squillero, G. Effective techniques for high-level ATPG. In Proc. IEEE Asian Test Symposium. Kyoto, Japan, 2001, 225–230.

  3. Fin, A. and Fummi, F. Genetic algorithms: the philosopher’s stone or an effective solution for high-level TPG? In Proc. IEEE High-Level Design Validation and Test Workshop. San Francisco, CA, 2003, 163–168.

  4. Ferrandi, F., Fummi, F. and Sciuto, D. Implicit test generation for behavioral VHDL models. In Proc. IEEE International Test Conference. Washington, D.C., 1998, 436–441.

  5. Xin, F., Ciesielski, M. and Harris, I. Design validation of behavioral VHDL descriptions for arbitrary fault models. In Proc. IEEE European Test Symposium. Tallinn, Estonia, 2005, 156–161.

  6. Ghosh, I. and Fujita, M. Automatic test pattern generation for functional register-transfer level circuits using assignment decision diagrams. IEEE Trans. Comput.-Aided Des. Integrated Circuits Systems, 2001, 20, 402–415.

  7. Zhang, L., Ghosh, I. and Hsiao, M. Efficient sequential ATPG for functional RTL circuits. In Proc. International Test Conference. Charlotte, NC, 2003, 290–298.

  8. Armstrong, J. A., Lam, F. S. and Ward, P. C. Test generation and fault simulation for behavioural models. In Performance and Fault Modelling with VHDL (Shoen, J. M., ed.). Prentice Hall, Englewood Cliffs, NY, 1992, 240–303.

  9. Cho, H. Ch. and Armstrong, J. A. B-algorithm – a behavioural test generation algorithm. In Proc. International Test Conference. Washington, D.C., 1994, 968–979.

10. Raik, J. and Ubar, R. Fast test pattern generation for sequential circuits using decision diagram representations. J. Electronic Testing: Theory and Applications, 2000, 16, 213–226.

11. Jervan, G., Ubar, R., Peng, Z. and Eles, P. Test generation: a hierarchical approach. In System-level Test and Validation of Hardware/Software Systems (Sonza Reorda, M., Peng, Z. and Violante, M., eds.), Springer, London, 2005, 63–77.

12. Chayakul, V., Gajski, D. D. and Ramachandran, L. High-level transformations for minimizing syntactic variances. In Proc. ACM/IEEE Design Automation Conference. Dallas, TX, 1993, 413–418.

13. Ubar, R. Test synthesis with alternative graphs. IEEE Des. Test Comput., 1996, 13, 48–57.

14. Ubar, R., Morawiec, A. and Raik, J. Back-tracing and event-driven techniques in high-level simulation with decision diagrams. In Proc. IEEE International Symposium on Circuits and Systems ’00. Geneva, 2000, 208–211.

15. Ubar, R., Raik, J., Jutman, A., Instenberg, M. and Wuttke, H.-D. Modeling microprocessor faults on high-level decision diagrams. In Proc. International Conference on Dependable Systems & Networks. Anchorage, AL, 2008, C-17–C-22.

16. Di Guglielmo, G., Fummi, F., Marconcini, C. and Pravadelli, G. Improving gate-level ATPG by traversing concurrent EFSMs. In Proc. IEEE VLSI Test Symposium. Berkeley, CA, 2006, 172–179.

17. Guglielmo, G., Fummi, F., Jenihhin, M., Pravadelli, G., Raik, J. and Ubar, R. On the combined use of HLDDs and EFSMs for functional ATPG. In Proc. 5th IEEE East-West Design and Test International Symposium. Jerevan, Armenia, 2007, 503–508.

18. Lee, C. Y. Representation of switching circuits by binary decision programs. Bell Syst. Techn. J., 1959, 38, 985–999.

19. Ubar, R. Test generation for digital circuits with alternative graphs. Proc. Tallinn Technical University, 1976, No. 409, 75–81 (in Russian).

20. Plakk, M. and Ubar, R. Digital circuit test design using the alternative graph model. In Automation and Remote Control. Plenum Publishing Corporation, New York, 1980, 41, 714–722.

21. Akers, S. B. Functional testing with binary decision diagrams. J. Design Automat. Fault-Tolerant Comput., 1978, 2, 311–331.

22. Bryant, R. E. Graph-based algorithms for Boolean function manipulation. IEEE Trans. Computers, 1986, C-35, 677–691.

23. Minato, S. Binary Decision Diagrams and Applications for VLSI CAD. Kluwer, Norwell, MA, 1996.

24. Sasao, T. and Fujita, M. (eds.). Representations of Discrete Functions. Kluwer, Norwell, MA, 1996.

25. Drechsler, R. and Becker, B. Binary Decision Diagrams. Kluwer, Boston, Dordrecht, London, 1998.

26. Ubar, R. Multi-valued simulation of digital circuits with structurally synthesized binary decision diagrams. In Multiple Valued Logic. Gordon and Breach Publishers, 1998, vol. 4, 141–157.

27. Jutman, A., Raik, J. and Ubar, R. SSBDDs: Advantageous model and efficient algorithms for digital circuit modeling, simulation & test. In Proc. 5th International Workshop on Boolean Problems. Freiberg, Germany, 2002, 157–166.

28. Ubar, R., Raik, J., Karputkin, A. and Tombak, M. Synthesis of high-level decision diagrams for functional test pattern generation. In Proc. 16th International Conference on Mixed Design of Integrated Circuits and Systems. Lodz, Poland, 2009, 519–524.

29. Ubar, R., Vassiljeva, T., Raik, J., Jutman, A., Tombak, M. and Peder, A. Optimization of structurally synthesized BDDs. In Proc. 4th IASTED International Conference on Modelling, Simulation and Optimization. Kauai, HI, 2004, 234–240.

30. Agrawal, V. D. and Lee, D. Characteristic polynomial method for verification and test of combinational circuits. In Proc. 9th International Conference on VLSI Design: VLSI in Mobile Communication. Bangalore, India, 1996, 341–342.

31. Jain, J., Bitner, J., Fussell, D. S. and Abraham, J. A. Probabilistic design verification. ICCAD-91. In Digest of Technical Papers., 1991 IEEE International Conference on Computer-Aided Design. Santa Clara, CA, 1991, 468–471.

32. Dubrova, E. and Sack, H. Probabilistic verification of multiple-valued functions. In Proc. 30th IEEE International Symposium on Multiple-Valued Logic. Portland, OR, 2000, 460–466.

33. Atkinson, K. A. An Introduction to Numerical Analysis, 2nd ed. J. Wiley, New York, 1989.

Back to Issue