Preview

Информатика

Расширенный поиск

Аппаратная реализация булевых функций на основе автоматной модели

https://doi.org/10.37661/1816-0301-2023-20-1-91-101

Полный текст:

Аннотация

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

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

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

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

Об авторе

А. А. Бутов
Белорусский государственный университет информатики и радиоэлектроники
Беларусь

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

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



Список литературы

1. Белов, А. В. Программирование микроконтроллеров для начинающих и не только / А. В. Белов. – СПб. : Наука и техника, 2016. – 352 с.

2. Кузьмин, В. А. Реализация функций алгебры логики автоматами, нормальными алгоритмами и машинами Тьюринга / В. А. Кузьмин // Проблемы кибернетики. – 1965. – Вып. 13. – С. 75–96.

3. Хопкрофт, Д. Введение в теорию автоматов, языков и вычислений / Д. Хопкрофт, Р. Мотвани, Дж. Ульман. – 2-е изд., пер. с англ. – М. : Изд. дом «Вильямс», 2008. – 528 с.

4. Шалыто, А. А. Логическое управление. Методы аппаратной и программной реализации алгоритмов / А. А. Шалыто. – СПб. : Наука, 2000. – 780 с.

5. Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.

6. Andersen, H. R. An Introduction to Binary Decision Diagrams. Lecture Notes / H. R. Andersen. – Copenhagen : IT University of Copenhagen, 1999. – 35 p.

7. Akers, S. B. Binary decision diagrams / S. B. Akers // IEEE Transactions on Computers. – 1978. – Vol. C-27, no. 6. – P. 509–516.

8. 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.

9. 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.

10. Бибило, П. Н. Применение диаграмм двоичного выбора при синтезе логических схем / П. Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.

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

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

13. Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. – М. : Наука, 1981. – 416 c.

14. 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.


Дополнительные файлы

Рецензия

Для цитирования:


Бутов А.А. Аппаратная реализация булевых функций на основе автоматной модели. Информатика. 2023;20(1):91-101. https://doi.org/10.37661/1816-0301-2023-20-1-91-101

For citation:


Butov A.A. Hardware implementation of Boolean functions based on the automaton model. Informatics. 2023;20(1):91-101. (In Russ.) https://doi.org/10.37661/1816-0301-2023-20-1-91-101

Просмотров: 158


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)