ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 9. Vol. 30. 2024

DOI: 10.17587/it.30.450-461

P. N. Bibilo, Dr. Sci. (Eng.), Professor,
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk, 220012, Republic of Belarus

Synthesis of Two-Block Logic Circuits, Implementing the Functions of k-Valued Logic

The problem of the schematic implementation of k-valued logic functions defined by tabular representations is considered. The proposed approach is based on technologically independent optimization of the representation of the k-valued logic function in the form of a multi-valued Decision Diagram (MDD), after which the values of the arguments and values of the function are encoded by sets of Boolean variables. As a result of encoding, the k-valued function is replaced by a system of not fully defined Boolean functions. The system of Boolean functions is minimized in the BDD class of representations (Binary Decision Diagram (BDD) — binary decision diagram). It is proposed to carry out intermediate encoding of the values of a k-valued function using special encoding of neighboring leaf vertices BDD, which can lead to a reduction in the area of a two-block logic circuit implementing a k-valued logic function.
Keywords: functions of k-valued logic, Multi-valued Decision Diagram (MDD), Boolean functions, Binary Decision Diagram (BDD), Shannon expansion, digital logic synthesis, VHDL, VLSI

P. 450-461

References

1. Akushskij I. Ya., Yudickij D. I. Machine arithmetic in residual classes, Moscow, Sovetskoe radio, 1968, 440 p. (in Russian).
2. Chervyakov N. I., Sakhnyuk P. A., Shaposhnikov A. V., Ryadnov S. A. Modular parallel computing structures of neuro-processor systems, Moscow, Fizmatlit, 2003, 288 p. (in Russian).
3. Stempkovskiy A. L., Kornilov A. I., Semenov M. Yu. Features of the implementation of devices with digital signal processing in the integrated design using modular arithmetic, Informatsionnye Tekhnologii, 2004, no. 2, pp. 2—9 (in Russian).
4. Bibilo P. N., Avdeev N. A., Romanov V. I. Functional verification of VHDL descriptions of synchronous digital devices, Moscow, LENAND, 2020, 328 p. (in Russian).
5. Ashenden P. J., Lewis J. VHDL-2008. Just the New Stuff, Burlington, MA, USA, Morgan Kaufman Publishers, 2008, 909 p.
6. Tarasov I. E. XILINX FPGA. Hardware Description Languages VHDL and Verilog, CAD, Design Techniques, Mos­cow, Goryachaya liniya — Telekom, 2020, 538 ð . (in Russian).
7. Solovyov V. V. XILINX FPGA Architectures: FPGA and CPLD 7-Series, Moscow, Goryachaya liniya — Telekom, 2016, 392 ð. (in Russian).
8. Bibilo P. N. Integrated Circuit Design Systems Based on the VHDL Language. StateCAD, ModelSim, LeonardoSpectrum, Moscow, SOLON-Press Publ., 2005, 384 p. (in Russian).
9. Zakrevskij A. D. Parallel logic control algorithms, Minsk, Inttekhnicheskoj kibernetiki AN Belarusi, 1999, 202 p. (in Russian).
10. Bibilo P. N. Application of Binary Decision Diagrams in the Synthesis of Logic Circuits, Minsk, Belaruskaja navuka, 2014, 231 p. (in Russian).
11. 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., available at: https://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/ERL-96-75.pdf
12. Bryant R. E., Meinel C. Ordered Binary Decision Diagrams, Logic synthesis and verification (ed. by S. Hassoun, T. Sasao, R. K. Brayton), Kluwer Academic Publishers, 2002, pp. 285—307.
13. Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD — Foundations and Applications, Berlin, Heidelberg, Springer-Verlag, 1998, 267 p.
14. Knut D. E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. CH. 1, Moscow, Vil'yams, 2013, 960 p. (in Russian).
15. Bibilo P. N. Application of decision diagrams of incompletely specified of k-valued logic functions in the synthesis of logical circuits, Informatika, 2023, vol. 20, no. 2, pp. 39—64 (in Russian).
16. Zakrevskij A. D. Algorithms of energy-saving coding of an automaton states, Informatika, 2011, no. 1, pp. 66—78 (in Russian).
17. 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.
18. Bibilo P. N., Lankevich Yu. Yu., Romanov V. I. Logical minimization of multilevel representations of boolean function systems, Informatsionnye Tehnologii, 2023, vol. 29, no. 2, pp. 59—71 (in Russian).
19. De Micheli G. Symbolic design of combinational and sequen­tial logic circuits implemented by two-level logic macros, IEEE Trans. Computer-Aided Design, 1986, vol. CAD-5, no. 4, pp. 597—616.

To the contents