D. V. Demidov

Read the full article 


 This paper deals with a method of relational theory adaptation for integrated circuits CAD systems. A new algorithm is worked out for optimal search of implicit Don’t Care values for combinational multiple-level digital circuits. The algorithm is described in terms of the adapted relational theory that gives the possibility for a very simple algorithm description for both intuitive understanding and formal analysis. The proposed method makes it possible to apply progressive experience of relational databases in efficient implementation of relational algebra operations (including distributed ones).  Comparative analysis of the proposed algorithm and a classic one for optimal search of implicit Don’t Cares is carried out. The analysis has proved formal correctness of the proposed algorithm and its considerably less worst-case complexity.  The search of implicit Don’t Care values in the integrated circuits design makes it easier to optimize such characteristics of IC as chip area, power, verifiability and reliability. However, the classic algorithm for optimal search of implicit Don’t Care values is not used in practice due to its very high computational complexity. Application of algorithms for sub-optimal search doesn’t give the possibility to realize the potential of IC optimization to the full. Implementation of the proposed algorithm in IC CAD (a.k.a., EDA) systems is adequate due to much lower computational complexity, and potentially makes it possible to improve the quality-development time ratio of IC (chip area, power, verifiability and reliability). Developed method gives the possibility for creation of distributed EDA system with higher computational power and, consequently, for design automation of more complex IC.

Keywords:  CAD, EDA, VLSI, optimization of combinational schemes, Boolean networks, partially defined Boolean functions, implicit Don’t Cares, ODC, relational theory, relational algebra, natural join


 1. De Micheli G. Synchronous logic synthesis: algorithms for cycle-time minimization // IEEE Transactions

on Computer-Aided Design of Integrated Circuits and Systems. 1991. V. 10. N 1. P. 63–73.
2. Hachtel G.D., Rho J.K., Somenzi F., Jacoby R. Exact and heuristic algorithms for the minimization of incompletely
specified state machines // Proc. of European Conference on Design Automation. Amsterdam,
Netherlands, 1992. P. 184–191.
3. Bogatyrev V.A., Bogatyrev S.V., Golubev I.Yu. Optimization and the process of task distribution between
computer system clusters // Automatic Control and Computer Sciences. 2012. V. 46. N 3. P. 103–111.
4. Sentovich E.M., Singh K.J., Lavagno L., Moon C., Murgai R., Saldanha A., Savoj H., Stephan P.R.,
Brayton R.K., Sangiovanni-Vincentelli A.L. SIS: A System for Sequential Circuit Synthesis. Technical Report
UCB/ERL M92/41, Electronics Research Lab, Univ. of California, Berkeley, 1992.
5. Pederson D.O. The VIS Group. VIS: Verification Interacting with Synthesis, 1995 [Электронный ресурс].
Режим доступа:, свободный. Яз. англ. (дата об-
ращения 04.12.2013).
6. Bartlett K.A., Brayton R.K., Hachtel G.D., Jacoby R.M., Morrison C.R., Rudell R.L., Sangiovanni-
Vincentelli A., Wang A. Multi-level logic minimization using implicit don’t cares // IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems. 1988. V. 7. N 6. P. 723–740.
7. Fujiwara H. Logic Testing and Design for Testability. Cambridge: MIT Press, 1985. 304 p.
8. Chang A.C.L., Reed I.S., Beans A.V. Path sensitization, partial boolean difference and automated fault diagnosis
// IEEE Transactions on Computers. 1972. V. C-21. N 2. P. 189–195.
9. Bogatyrev V.A. Exchange of duplicated computing complexes in fault-tolerant systems // Automatic Control
and Computer Sciences. 2011. V. 45. N 5. P. 268–276.
10. Bogatyrev V.A. Fault tolerance of clusters configurations with direct connection of storage devices // Automatic
Control and Computer Sciences. 2011. V. 45. N 6. P. 330–337.
11. Богатырев В.А., Богатырев С.В. Критерии оптимальности многоуровневых отказоустойчивых ком-
пьютерных систем // Научно-технический вестник СПбГУ ИТМО. 2009. № 5 (63). С. 92–97.
12. Богатырев В.А., Богатырев А.В. Функциональная надежность систем реального времени // Научно-
технический вестник информационных технологий, механики и оптики. 2013. № 4 (86). С. 150–151.
13. Muroga S., Kambayashi Y., Lai H.C., Culliney J.N. Transduction method – design of logic networks based
on permissible functions // IEEE Transactions of Computers. 1989. V. 38. N 10. P. 1404–1424.
14. Lin B., Touati H.J., Newton A.R. Don’t care minimization of multi-level sequential logic networks // Proc.
IEEE International Conference on Computer-Aided Design. 1990. P. 414–417.
15. Brayton R.K., Hachtel G., McMullen C., Sangiovanni-Vincentelli A. Logic Minimization Algorithms for
VLSI Synthesis. Kluwer Academic Publishers, 1985. 206 p.
16. Theobald M., Nowick S.M., Wu T. Espresso-HF: a heuristic hazard-free minimizer for two-level logic //
Proceedings - Design Automation Conference. Las Vegas, USA, 1996. P. 71–76.
17. Codd E.F. A relational model of data for large shared data banks // M.D. Computing. 1998. V. 15. N 3.
P. 162–166.
18. Abiteboul S., Hull R., Vianu V. Foundations of Databases. Addison-Wesley, 1995. 685 p.
19. Date C.J., Darwen H. Foundation for Future Database Systems: The Third Manifesto. 2nd ed. Addison-
Wesley, 2000. 608 p.
Copyright 2001-2017 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.