Application of decision diagrams of incompletely specified of k-valued logic functions in the synthesis of logical circuits

Objectives. The problem of circuit implementation of incompletely specified (partial) k-valued logic functions given by tabular representations is considered. The stage of technologically independent optimization is studied to obtain minimized representations of systems of completely specified Boolean functions from tabular representations of partial functions of k-valued logic. According to these representations of Boolean functions, technological mapping is performed at the second stage of the synthesis of logic circuits.
Methods. Using additional definitions of Multi-valued Decision Diagrams (MDD) representing partial functions of k-valued logic, and Binary Decision Diagrams (BDD) representing partial systems of Boolean functions at the stage of technologically independent optimization is proposed. The task of additional definition of MDD is oriented to reducing the number of vertices of the MDD graph that correspond to the cofactors of the Shannon expansion of a multi-valued function.
Results. The MDD minimization problem is reduced to solving the problems of coloring undirected graphs of incompatibility of cofactors by minimum number of colors. Encoding of multi-valued values of arguments and values of functions of k-valued logic by binary codes leads to systems of partial Boolean functions, which are also further defined in order to minimize their multi-level BDD representations.
Conclusion. The proposed approach makes it possible to define partial multi-valued functions to fully defined Boolean functions in two stages. At the second stage, well-known and effective methods are used to redefine BDD representing systems of partial Boolean functions. As a result of this two-step approach, minimized BDD representations of systems of completely defined functions are obtained. According to completely defined Boolean functions, a technological mapping into a given library of logical elements is performed, i.e. the optimized descriptions of Boolean function systems are covered with descriptions of logical elements

1. Chervyakov N.I., Sakhnyuk P.A., Shaposhnikov A.V., Ryadnov S.A. Modulyarnye parallel'nye vychislitel'nye struktury neyroprotsessornykh system [Modular parallel computing structures of neuroprocessor systems]. M.: Fizmatlit, 2003, 288 p. (in Russ.).

2. Solov'ev R.A., Tel'puhov D.V., Balaka E.S., Ruhlov V.S., Mihmel' A.S. Osobennosti proektirovaniya modulyarnyh umnozhitelej s pomoshch'yu sovremennyh SAPR [Design features of modular multipliers using modern CAD]. // Problemy razrabotki perspektivnyh mikro- inanoelektronnyh sistem (MES). 2016, no. 1, pp. 249–254.

3. Amerbaev V.M., Solov'ev R.A., Tel'puhov D.V. Realizaciya biblioteki modul'nyh arifmeticheskih operacij na osnove algoritmov minimizacii logicheskih funkcij [Implementation of a library of modular arithmetic operations based on algorithms for minimizing logical functions]. // Izvestiya YUFU. Tekhnicheskienauki, Taganrog. 2013, no. 7, pp.221–225. (In Russ.).

4. Kam T., Villa T., Brayton R. K., Sangiovanni-Vincentelli A. L. Multi-Valued Decision Diagrams for Logic Synthesis and Verification // Memorandum No. UCB/ERL M96/75, 1996. 39 p.

5. http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/ERL-96-75.pdf

6. Bryant R. E. Graph-based algorithms for Boolean function manipulation // IEEE Transactions on Computers. – 1986. – Vol. 35, no. 8. – P. 677–691.

7. Drechsler R. Binary Decision Diagrams: Theory and Implementation. Springer, 1998. – 210 p.

8. Ebendt R., Fey G, Drechsler R. Advanced BDD Optimization. Springer, 2005. – 222 p.

9. Bryant R. E., C. Meinel Ordered binary decision diagrams // Logic Synthesis and Verification / eds.: S. Hassoun, T. Sasao, R. K. Brayton. – Kluwer Academic Publishers, 2002. – P. 285–307.

10. Meinel C.,Theobald T. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications. – Berlin, Heidelberg: Springer-Verlag, 1998. – 267 p.

11. Knut D. E. Iskusstvo programmirovaniya. T. 4, A. Kombinatornye algoritmy. [The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1.] CH. 1 : per. s angl.M.: Vil'yams, 2013, 960 p. (In Russ.).

12. Bibilo P. N. Primenenie diagram dvoichnogo vybora pri sinteze logicheskih shem. [Application of Binary Decision Diagrams in the Synthesis of Logic Circuits]. Minsk, Belaruskajanavuka, 2014, 231 p. (In Russ.).

13. Brayton K. R., Hachtel G. D., McMullen C., Sangiovanni-Vincentelli A. L.Logic Minimization Algorithm for VLSI Synthesis. – Boston, Kluwer Academic Publishers, 1984, 193 p.

14. Toropov N. R. Minimization of systems of Boolean functions in the class DNF. Logicheskoe proektirovanie [Logical Design]. Minsk, Institut tehnicheskoj kibernetik iNacional'noj akademii nauk Belarusi, 1999, iss. 4, рр. 4–19 (In Russ.).

15. Brayton R. K., Hachtel G. D., Sangiovanni-Vincentelli A. L. Synthesis of multi-level combinational logic circuits. Trudy Institute inzhenerov po jelektronike i radiotehnike [Proceedings of the Institute of Electronics and Radio Engineering], 1990, vol. 78, no. 2, рр. 38–83 (In Russ.).

16. Bibilo P.N., Kirienko N.A. Ocenka energopotrebleniya logicheskih KMOP-skhem po ih pereklyuchatel'noj aktivnosti [Estimating Energy Consumption in Logical CMOS Circuits Based on Their Switching Activity] // Mikroelektronika, 2012, no. 1, pp. 65 – 77 (In Russ.).

17. Bibilo P. N. Cistemy proektirovaniya integral'nyh skhem na osnove yazyka VHDL. StateCAD, ModelSim,LeonardoSpectrum. [Integrated Circuit Design Systems Based on the VHDL Language. StateCAD, ModelSim, LeonardoSpectrum]. Moscow, SOLON-Press, 2005, 384 р. (In Russ.).

18. Zakrevskij A. D. Logicheskij sintez kaskadnyh skhem. [Logical Synthesis of Cascading Circuit]. Moscow, Nauka, 1981, 416 р. (In Russ.).

19. Bibilo P. N., Lankevich Yu. Yu. Ispol'zovanie polinomov ZHegalkina pri minimizacii mnogourovnevyh predstavlenij sistem bulevyh funkcij na osnove razlozheniya SHennona [The use of Zhegalkin polynomials in minimizing multilevel representations of systems of Boolean functions based on the Shannon expansion]. Programmnayainzheneriya [Software Engineering], 2017, no. 8,рр. 369–384 (In Russ.).

20. Bibilo P. N. Minimizaciya BDDI-predstavlenij sistem ne polnost'yu opredelennyh bulevyh funkcij [Minimization of Binary Decision Diagrams for Systemsof Incompletely Defined Boolean Functions using inverse cofactors] // Programmnaya inzheneriya [Software Engineering], 2020, vol. 11, no. 3, pp. 152–168 (In Russ.).

21. Ashenden P. J., Lewis J. VHDL-2008. Just the New Stuff. – Burlington, MA, USA. – Morgan Kaufman Publishers, 2008. 909 p.