informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2023-20-1-91-101inform-1233Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNАппаратная реализация булевых функций на основе автоматной моделиHardware implementation of Boolean functions based on the automaton modelБутовА. А.ButovA. A.

Бутов Алексей Александрович, кандидат технических наук, доцент

ул. П. Бровки, 6, Минск, 220013

Alexey A. Butov, Ph. D. (Eng.), Assoc. Prof.

st. P. Brovka, 6, Minsk, 220013

tmkrb9@gmail.comБелорусский государственный университет информатики и радиоэлектроникиBelarusian State University of Informatics and Radioelectronics20232903202320191101Copyright © Бутов А.А., 20232023Бутов А.А.Butov A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1233Цели

Цели. В настоящее время электронные устройства управления все шире внедряются в различные изделия бытового и производственного назначения. В качестве таких устройств широко применяются микроконтроллеры самой разной конфигурации. Можно предложить другой подход, где устройство управления со стандартной структурой синтезируется из типовых интегральных схем и реализует булеву функцию, описывающую требуемые управляющие воздействия. Целью работы является исследование возможности реализации булевых функций с помощью устройств со стандартной структурой, проектирование которых основано на использовании модели дискретного автомата.

Методы

Методы. Исходная булева функция, подлежащая реализации, задается в виде дизъюнктивной нормальной формы. Для нее строится бинарная диаграмма решений (англ. Binary Decision Diagram, BDD), оптимизированная по числу вершин, на основе которой формируется граф переходов синхронного автомата Мура с абстрактным состоянием. Далее после выполнения этапа кодирования состояний автомата на основе его таблицы переходов формируется входная информация для прошивки (программирования) матричной памяти постоянного запоминающего устройства (ПЗУ).

Результаты

Результаты. Устройство, реализующее булеву функцию на основе автоматной модели, синтезируется из типовых микросхем. Основным компонентом служит ПЗУ, которое в соответствии со стандартной структурой устройства дополняется сдвиговым регистром, регистром состояний, триггером и тремя селекторами начального и двух финальных состояний.

Заключение

Заключение. Процесс проектирования устройства со стандартной структурой, реализующего булеву функцию, в итоге сводится к программированию матричной памяти ПЗУ на основе автоматной таблицы переходов. Использование многократно программируемого ПЗУ позволяет изменять функциональность устройства при сохранении прежней схемной реализации. Недостатком такого устройства, так же как и устройств, реализованных на основе микроконтроллеров, является низкое быстродействие, достоинством – возможность использования в различных изделиях и приборах, прежде всего бытового назначения, которые не требуют высокоскоростной реакции на изменение входного сигнала.

Objectives

Objectives. Currently, electronic control devices are increasingly being introduced into various household and production products. Microcontrollers of a wide variety of configurations are widely used as such devices. Another approach can be proposed where a control device with a standard structure is synthesized from typical integrated circuits and implements a Boolean function describing the required control actions.

The purpose of the work is to investigate the possibility of implementing Boolean functions using devices with a standard structure, the design of which is based on the use of a discrete automaton model.

Methods

Methods. The original Boolean function to be implemented is given as a disjunctive normal form. A binary  decision diagram (BDD) is built for such function, optimized by the number of vertices, on the basis of which a graph of transitions of a synchronous Moore automaton with an abstract state is formed. Further, after performing the state encoding step of the machine, input information for flashing (programming) of the matrix memory of the read-only memory (ROM) is generated based on its transition table.

Results

Results. A device that implements a Boolean function based on an automaton model is synthesized from typical microcircuits. The main component is ROM, which, according to the standard structure of the device, is  supplemented by a shift register, a state register, a trigger and three selectors of the initial and two final states.

Conclusion

Conclusion. The process of designing a device with standard structure that implements the Boolean function, as a result, comes down to programming the ROM matrix memory based on an automaton transition table. The use of a reprogrammable ROM allows to change the functionality of the device while maintaining the previous circuit implementation. The disadvantage of such a device, as well as devices implemented on the basis of  microcontrollers, is the low speed, the advantage is the possibility of use it in various products and devices, primarily for household purposes, which do not require a high-speed response to the change of  input signal.

синтез комбинационных схембулева функциядискретный автоматбинарная диаграмма решенийпостоянное запоминающее устройствоsynthesis of combination circuitsBoolean functiondiscrete automatonbinary decision diagramread-only memoryReferencesБелов, А. В. Программирование микроконтроллеров для начинающих и не только / А. В. Белов. – СПб. : Наука и техника, 2016. – 352 с.Belov A. V. Programmirovanie mikrokontrollerov dlya nachinayushchih i ne tol'ko Microcontroller Programming for Beginners and Beyond Saint-Petersburg, Nauka i tekhnika, 2016, 352 p. (In Russ.).Кузьмин, В. А. Реализация функций алгебры логики автоматами, нормальными алгоритмами и машинами Тьюринга / В. А. Кузьмин // Проблемы кибернетики. – 1965. – Вып. 13. – С. 75–96.Kuz'min V. A. Realization of functions of the algebra of logic by automata, normal algorithms and Turing machines. Problemy kibernetiki [Cybernetics Issues], 1965, vol. 13, pp. 75–96 (In Russ.).Хопкрофт, Д. Введение в теорию автоматов, языков и вычислений / Д. Хопкрофт, Р. Мотвани, Дж. Ульман. – 2-е изд., пер. с англ. – М. : Изд. дом «Вильямс», 2008. – 528 с.Hopcroft J. E., Motwani R., Ullman J. D. Introduction to Automata, Theory, Languages and Computation, 2nd edition. Addison-Wesley, 2000, 521 р.Шалыто, А. А. Логическое управление. Методы аппаратной и программной реализации алгоритмов / А. А. Шалыто. – СПб. : Наука, 2000. – 780 с.Shalyto A. A. Logicheskoe upravlenie. Metody apparatnoj i programmnoj realizacii algoritmov. Logical Control. Methods of Hardware and Software Implementation of Algorithms. Saint-Petersburg, Nauka, 2000, 780 p. (In Russ.).Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.Zakrevskij A. D., Pottosin Yu. V., Cheremisinova L. D. Logicheskie osnovy proektirovanija diskretnyh ustrojstv. Logical Fundamentals of Discrete Devices Design. Moscow, Fizmatlit, 2007, 592 p. (In Russ.).Andersen, H. R. An Introduction to Binary Decision Diagrams. Lecture Notes / H. R. Andersen. – Copenhagen : IT University of Copenhagen, 1999. – 35 p.Andersen H. R. An Introduction to Binary Decision Diagrams. Lecture Notes. Copenhagen, IT University of Copenhagen, 1999, 35 p.Akers, S. B. Binary decision diagrams / S. B. Akers // IEEE Transactions on Computers. – 1978. – Vol. C-27, no. 6. – P. 509–516.Akers S. B. Binary decision diagrams. IEEE Transactions on Computers, 1978, vol. C-27, no. 6, pр. 509–516.Bryant, R. E. Ordered binary decision diagrams / R. E. Bryant, C. Meinel // Logic Synthesis and Verification / eds.: S. Hassoun, T. Sasao, R. K. Brayton. – Kluwer Academic Publishers, 2002. – P. 285–307.Bryant R. E., Meinel C. Ordered binary decision diagrams. Logic Synthesis and Verification. In S. Hassoun, T. Sasao, R. K. Brayton (eds.). Kluwer Academic Publishers, 2002, pp. 285–307.Yang, S. BDS: a BDD-based logic optimization system / S. Yang, M. Ciesielski // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – 2002. – Vol. 21, no. 7. – P. 866–876.Yang S., Ciesielski M. BDS: a BDD-based logic optimization system. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 2002, vol. 21, no. 7, pp. 866–876.Бибило, П. Н. Применение диаграмм двоичного выбора при синтезе логических схем / П. Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.Bibilo P. N. Primenenie diagram dvoichnogo vybora pri sinteze logicheskih shem. Application of Binary Selection Diagrams in the Synthesis of Logic Circuits. Minsk, Belaruskaja navuka, 2014, 231 p. (In Russ.).Meinel, C. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications / C. Meinel, T. Theobald. – Berlin, Heidelberg : Springer-Verlag, 1998. – 267 p.Meinel C., Theobald T. Algorithms and Data Structures in VLSI Design: OBDD – Foundations and Applications. Berlin, Heidelberg, Springer-Verlag, 1998, 267 p.Ebendt, R. Advanced BDD Optimization / R. Ebendt, G. Fey, R. Drechsler. – Springer, 2005. – 222 p.Ebendt R., Fey G., Drechsler R. Advanced BDD Optimization. Springer, 2005, 222 p.Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. – М. : Наука, 1981. – 416 c.Zakrevskij A. D. Logicheskij sintez kaskadnyh skhem. Logical Synthesis of Cascading Circuit. Moscow, Nauka, 1981, 416 р. (In Russ.).Vemuri, N. BDD-based logic synthesis for LUT-6-based FPGAs / N. Vemuri, P. Kalla, R. Tessier // ACM Transactions on Design Automation of Electronic Systems. – 2002. – Vol. 7, no. 4. – P. 501–525.Vemuri N., Kalla P., Tessier R. BDD-based logic synthesis for LUT-6-based FPGAs. ACM Transactions on Design Automation of Electronic Systems, 2002, vol. 7, no. 4, рр. 501–525.

The authors declare that there are no conflicts of interest present.