Что такое цифровой автомат
Перейти к содержимому

Что такое цифровой автомат

  • автор:

Синтез цифровых автоматов Текст научной статьи по специальности «Компьютерные и информационные науки»

ЦИФРОВОЙ АВТОМАТ / DIGITAL AUTOMATIC MACHINE / ОПЕРАЦИОННЫЙ АВТОМАТ / OPERATING MACHINE / УПРАВЛЯЮЩИЙ АВТОМАТ / МИКРООПЕРАЦИИ / МОДЕЛИРОВАНИЕ СЕТИ ПЕТРИ / PETRI NETS / CONTROL AUTOMATON / MICROOPERATIONS / MODELING

Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Сахно Виталий Викторович, Ганжур Марина Александровна

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Сахно Виталий Викторович, Ганжур Марина Александровна

Синтез цифровых автоматов
Методы синтеза автоматов управления на больших интегральных схемах
Диагностирование HDL-моделей микропрограммных автоматов
Методические рекомендации по совершенствованию обучения сотрудников полиции
Конструктивные методы синтеза автоматов управления на больших интегральных схемах
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

THE SYNTHESIS OF DIGITAL MACHINES

The present work is devoted to the analysis of the digital automaton model of Viktor Mikhailovich Glushkov. A digital automaton is a discrete, finite information converter capable of receiving various states, passing under the influence of input signals, or commands of a program for solving a problem, from one state to another and outputting output signals.

Текст научной работы на тему «Синтез цифровых автоматов»

6. Bond B.M. How Education Impacts Police Performance. PUBLIC SAFETY: Relevant insights by the experts from American Military University https://inpublicsafety.com/2014/07/how-education-impacts-police-performance/ (accessed date 19.03.2018)

7. Carlan P.E., Lewis J.A. Dissecting police professionalism: A comparison of predictors within five professionalism subsets // Police Quarterlyro. 2009. Vol. 12. № 4. Рp. 370-387.

8. Code of Conduct for Law Enforcement Officials: UN Resolution A/RES/34/169 — 17 декабря 1979 https://documents-dds-ny.un.org/doc/RES0LUTI0N/GEN/NR0/377/96/IMG/NR037796.pdf70penElement (accessed date 19.03.2018)

9. Contemporary Fighting Arts (CFA) http://www.sammyfranco.com/

10. Declaration on the Police: Council of Europe Resolution 690-1979 http://www.assembly.coe.int/nw/xml/XRef/Xref-XML2HTML-en.asp?fileid=16101&lang=en (accessed date 19.03.2018)

11. Dogutas C., Dolu O., Gul S. A Comparative Study of the Police Training in the United Kingdom, the United States and Turkey // Turkish Journal of Police Studies. Polis Bilimleri Dergisi. 2007. № 9. Рp. 1-20.

12. Federal Law «On Police» of 07.02.2011 N 3-FZ of the Russian Federation http://www.consultant.ru/document/cons_doc_LAW_110165/ (accessed date 19.03.2018)

13. Frej W. U.S. Police: Education levels and the use of force. Newsletters: MSNBC. 12/09/14 http://www.msnbc.com/ronan-farrow-daily/us-police-education-levels-and-the-use-force (accessed date 19.03.2018)

14. Gardiner C. College Cops: A study of education and policing in California // Policing: An International Journal of Policing Strategies and Management. 2015. № 38(4). Рp.1-17.

15. Gardiner C. Policing around the Nation: Education, Philosophy, and Practice. Fullerton: California State University, The Center for Public Policy. 2017. 73 p. https://www.policefoundation.org/wp-content/uploads/2017/10/PF-Report-Policing-Around-the-Nation_10-2017_Final.pdf (accessed date 19.03.2018)

16. Johnsen B.H., Espevik R., Saus E.R., Sanden S., Olsen O.K., Hystad S.W. Hardiness as a Moderator and Motivation for Operational Duties as Mediator: the Relation Between Operational Self-Efficacy, Performance Satisfaction, and Perceived Strain in a Simulated Police Training Scenario // Journal of Police and Criminal Psychology. 2017. Vol. 32. № 4. Рp. 331-339. https://link.springer.com/article/10.1007/s11896-017-9225-1 (accessed date 19.03.2018)

17. Mawby R.I. Policing Across the World: Issues for the Twenty-first Century. London: Routledge, 2013. 256 p.

18. Police Self-Defense Training: Contemporary Fighting Arts (CFA) http://www.sammyfranco.com/police-self-defense.html (accessed date 19.03.2018)

19. Smith S.M., Aamodt M.G. The relationship between education, experience, and police performance // Journal of Police and Criminal Psychology. 1997. Vol. 12. № 2. Рp. 7-14 https://link.springer.com/article/10.1007/BF02806696 (accessed date 19.03.2018).

студент 2-го курса кафедры «Вычислительные системы и информационная безопасность» Сахно Виталий Викторович

Донской государственный технический университет (г. Ростов-на-Дону); старший преподаватель «Вычислительные системы и информационная безопасность» Ганжур Марина Александровна

Донской государственный технический университет (г. Ростов-на-Дону)

СИНТЕЗ ЦИФРОВЫХ АВТОМАТОВ

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

Ключевые слова: Цифровой автомат, операционный автомат, управляющий автомат, микрооперации, моделирование сети Петри.

Annotation. The present work is devoted to the analysis of the digital automaton model of Viktor Mikhailovich Glushkov. A digital automaton is a discrete, finite information converter capable of receiving various states, passing under the influence of input signals, or commands of a program for solving a problem, from one state to another and outputting output signals.

Keywords .Digital automatic machine, operating machine, control automaton, microoperations, modeling, Petri

Введение. Виктор Михайлович Глушков — советский математик, кибернетик. Глушков был инициатором и главным идеологом разработки и создания Общегосударственной автоматизированной системы учёта и обработки информации (ОГАС), предназначенной для автоматизированного управления всей экономикой СССР в целом. Для этого им была разработана система алгоритмических алгебр и теория для управления распределёнными базами данных [1].

Одна из его работ «Синтез цифровых автоматов» потрясла весь мир. Так как одним из значительных достижений науки и техники середины 20 века стало создание электронных цифровых машин с программным управлением, стал вопрос о рациональном конструировании (синтезе) схем.

По модели В.М. Глушкова ЦА как устройство для автоматической обработки цифровой информации по заданным алгоритмам выглядит как совокупность операционного автомата (ОА) и управляющего автомата (УА) рисунок 1 [3].

Рисунок 5. Модель цифрового автомата

ОА предназначен для выполнения набора требуемых операций алгоритма, а второй для задачи последовательности действий по алгоритму в зависимости от условий.

Работа автомата разбивается на определенные интервалы времени. Каждая элементарная, атомарная операция, которая может выполняться в ОА за один интервал времени, называется микрооперацией [5].

УА служит для выдачи управляющих сигналов в каждом интервале работы ЦА, инициирующих выполнение определенных микроопераций в ОА в соответствии с выполняемым алгоритмом и в зависимости от поступающих на входы УА условий. Если УА «знает, что и когда» делать, то ОА «знает, как» делать. При этом для УА «что делать» — этот коды команд, про их содержание он не знает [9].

Любая команда, операция или процедура, выполняемая в операционном блоке, описывается некоторой микропрограммой и реализуется за несколько тактов, в каждом из которых выполняется шаг микропрограммы в одну или несколько микроопераций.

Интервал времени, отводимый на выполнение микрооперации, называется рабочим тактом или просто тактом устройства или системы обработки цифровой информации.

Для реализации команды, операции или процедуры (микропрограммы) необходимо на соответствующие управляющие входы операционного блока подать определённым образом распределённую во времени последовательность управляющих сигналов. Часть устройства или системы обработки цифровой информации, предназначенная для выработки последовательностей управляющих сигналов, называется управляющим блоком (или управляющим автоматом). Генерируемая управляющим автоматом последовательность управляющих сигналов задаётся поступающими на входы этого автомата кодом операции (КОП) Ъ, сигналами из операционного блока и, несущими информацию об особенностях операндов, промежуточных и конечного результата, а также синхросигналами, задающими границы тактов [10].

Синтез цифрового автомата разделяют на четыре этапов, условно их называют:

а) этап блочного синтеза автомата — на этом этапе происходит разбор на отдельные блоки;

б) этап абстрактного синтеза — определяется объем затрачиваемой памяти для данного блока;

в) этап структурного синтеза — происходит выбор логических и запоминающих элементов для построения блока;

г) этап надежности синтеза — производится преобразование и дополнение построенных схем с целью обеспечение надежности [2].

Существуют два принципиально различных подхода в проектировании микропрограммного автомата (УА): использование принципа схемной логики или принципа программируемой логики.

В первом случае, т.е. при использовании принципа схемной логики, в процессе проектирования подбирается некоторый набор цифровых микросхем (обычно малой и средней степени интеграции) и определяется такая схема соединения их выводов, которая обеспечивает требуемое.

Устройства, построенные по такому принципу, способны обеспечивать наивысшее быстродействие при заданном типе технологии элементов. Недостаток этого принципа построения процессорных устройств состоит в трудности использования последних достижений микроэлектроники — большой интегральных микросхем и сверхбольшой степени интеграции (БИС и СБИС).

Для разных процессорных устройств потребуются различные БИС. Такие БИС окажутся узкоспециализированными. Число типов БИС будет большим, а потребность в каждом типе БИС окажется низкой, что приведет к экономической нецелесообразности выпуска их промышленностью. Эти обстоятельства заставляют обратиться к другому подходу в проектировании цифровых устройств, основанному на использовании принципа программируемой логики. Данный подход предполагает построение с использованием одной или нескольких БИС некоторого универсального устройства, требуемое функционирование (т.е. специализация) которого обеспечивается заключением в память устройства определенной программы (или микропрограммы). В зависимости от введенной программы такое универсальное устройство способно выполнить самые разнообразные функции. Число типов БИС в этом случае оказывается небольшим, а потребность в БИС каждого типа — высокой. Это обеспечивает целесообразность их выпуска промышленностью. Набор типов БИС, обеспечивающих построение таких универсальных устройств, образует микропроцессорный комплект (МКТ). Устройства, реализуемые на МПК, — микропроцессорные устройства (МПУ).

Микропроцессорные устройства обеспечили широкое использование цифровых методов в различных технических направлениях. Бурное внедрение этих новых методов рассматривается как революция в технике [7].

Формулировка цели статьи. Важность появление данной модели обусловлено тем, что с развитием технологии стало нерационально использовать цифровые автоматы без учета внешних факторов (ЦА, который делает невзирая ни на что), ведь невозможно просчитать все критические ситуации. Когда многие предприятия переходят на автоматизированные системы, не целесообразно не брать в расчёт внешние условия В данной работе расписан синтез цифрового автомата по методу синтеза ЦА по модели Глушково В.М. с использованием УА.

Изложение основного материала статьи. Типовые примеры можно легко увидеть в армейских структурах, системах государственной власти, на различных флотах (морской, воздушный), в коммерческих организациях и т.д. Рассмотрим контрольно-пропускное устройство (КПУ) на входе предприятия. Не рассматривая механику работы данного устройства, перейдем к алгоритму программы.

Устройства может находиться в нескольких состояний:

1) С1 — КПУ в открытом состоянии;

2) С2 — КПУ в закрытом состоянии;

3)С3 — КПУ в открытом состоянии после предъявления пропуска/ ключа;

4)С4 — КПУ заблокировано.

Сигналы, подаваемые на устройство: сигнал о предъявлении пропуска/ключа (а1), сигнал о несоответствии пропуска/ключа (а0), сигнал о использовании пропуска/ключа (а2), сигнал о аварийной ситуации (а3), сигнал о нарушении безопасности (а4), сигнал о возврате в прежние состояние (а5). Начальное состояние — это состояние С2, при предоставлении соответствующего пропуска, система отреагирует и подаст сигнал а1, состояние изменится на С3, так же после использование соответствующего пропуска/ключа система должна перейти в прежнее состояние с помощью сигнала а2, при не соответствии пропуска сигнал а0 не изменит состояние. Данное устройство связанно с общей системой предприятия и в случаи аварийной ситуации должно перейти в пропускной режим открытого типа, для свободного покидания помещение сотрудников во время эвакуации. Для этого на устройство должен подаваться сигнал а3, следовательно, состояние С2 заменится состоянием С1. Для обеспеченье информационную защиту предприятия, в случаи несанкционированного проникновение, должен пойти сигнал а4, который переведет из состояния С2 в С4. А также, у охраны предприятие присутствует сигнал а5, а6, который изменит состояние С1/С4 на С2. Для наглядности рассмотрим в виде графов, где точки «С» — это состояние системы, дуги «а» — переходы из этих состояний. Рассмотрим принцип работы на основе автомата Мили. В таблице переходов АА Мили на пересечении столбца аМ и строки СЫ записывается состояние а8. Для наглядности рассмотрим таблицу переходов Таблица 1.

а1 а2 а3 а4 а5 а6 а0

С1 С1 С1 С1 С1 С2 С1 С1

С2 С3 С2 С1 С4 С2 С2 С2

С3 С3 С2 С3 С3 С3 С3 С3

С4 С4 С4 С4 С4 С4 С2 С4

Граф ЦА (ГА) — ориентированный граф, у которого в качестве вершин используются состояния, а в качестве дуг — переходы. Так же можно представить в виде графов, где точки «С» -это состояние системы, дуги «а» — переходы из этих состояний Рисунок 2.

Рисунок 2. Граф состояний

При создании ГА Мили следует не забывать об условия корректности:

1) при выходе из данного состояния должны использоваться разные входные сигналы;

2) при заходе в данные состояния допускаются одинаковые входные сигналы;

3) при заходе в данное состояние разрешаются одинаковые выходные сигналы.

Табличный и графический способы задания автоматов эквивалентны, поэтому граф автомата содержит всю необходимую информацию о функциях выходов и функциях переходов. На граф цифрового автомата следует нанести все необходимые данные по функциям возбуждения триггеров заданного типа. Однако дальнейшее использование информации, заданной в виде разметки графа цифрового автомата, выполняется с использованием табличного или аналитического представления. Таким образом, синтез цифрового автомата только по графу обычно не делается и этот метод синтеза цифрового автомата является гораздо менее распространённым, чем синтез цифрового автомата с использованием таблиц [8].

Продемонстрируем работу данной системы с помощью классической сети Петри. Сети Петри — это инструмент для математического моделирования и исследования сложных систем. Цель представления системы в виде сети Петри и последующего анализа этой сети состоит в получении важной информации о структуре и динамическом поведении моделируемой системы [4].

Ф Petri ,NET mulator 2,0.1700.0- DEBUG — l:\1.pnd — □ X

File Edit View Help

DE5U \4i ► II ■ M | \ E = & V ч a-

Toolbox □ * x | Ä моделирование Й 1 1 0 x

О PetriNet Editor 1 Descriptio n 15 Respons

tgi input Operation (§> Resource © Control

Ц Transitio □ Label n S I Г1—

Lsj Sub syst e (31 In es» Out (jj) Resourc m block

-operation 1 • | ■ _ 1 •• J

____ pi fill ЯШ!

Toolbox | Doc um en: Exp. 1

1 (PetriNetDocument) v i* I— _ ——- V

PetriNetType Timelnva riant I * J-^ V Pi J

Синтез цифровых автоматов Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Сахно Виталий Викторович, Ганжур Марина Александровна

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Сахно Виталий Викторович, Ганжур Марина Александровна

Структурная организация самоконтролируемых автоматов для систем реального времени
Методы синтеза надежных автоматов для систем реального времени
Оптимизация схемы микропрограммного автомата Мили на FPGA
Метод построения контролируемых цифровых автоматов

Информационная технология проектирования систем автоматизированного управления технологическими процессами

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

SYNTHESIS OF DIGITAL AUTOMATA

The present work is devoted to the analysis of the digital automata model of Viktor Mikhailovich Glushkov. A digital automata is a discrete, finite information converter capable of receiving various states, change under the influence of input signals or commands of a problem solving program from one state to another and produce output signals.

Текст научной работы на тему «Синтез цифровых автоматов»

СИНТЕЗ ЦИФРОВЫХ АВТОМАТОВ

SYNTHESIS OF DIGITAL AUTOMATA

Сахно В. В., Ганжур М. А.

Донской государственный технический

университет, Ростов-на-Дону, Российская

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

Ключевые слова: цифровой автомат, операционный автомат, управляющий автомат, микрооперации.

Sakhno V. V., Ganzhur M. A.

Don State Technical University, Rostov-on-Don, Russian Federation

The present work is devoted to the analysis of the digital automata model of Viktor Mikhailovich Glushkov. A digital automata is a discrete, finite information converter capable of receiving various states, change under the influence of input signals or commands of a problem solving program from one state to another and produce output signals.

Keywords: digital automata, operating machine, control automaton, microoperations.

Введение. Виктор Михайлович Глушков — советский математик и кибернетик. Он был инициатором и главным идеологом разработки и создания Общегосударственной автоматизированной системы учёта и обработки информации (ОГАС), предназначенной для автоматизированного управления всей экономикой СССР в целом. Для этого им была разработана система алгоритмических алгебр и теория для управления распределёнными базами данных.

Одна из его работ «Синтез цифровых автоматов» потрясла весь мир. Так как одним из значительных достижений науки и техники середины 20 века стало создание электронных цифровых машин с программным управлением, стал вопрос о рациональном конструировании (синтезе) схем [1].

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

Основная часть. По модели В. М. Глушкова цифровой автомат (ЦА), как устройство для автоматической обработки цифровой информации по заданным алгоритмам, выглядит как совокупность операционного автомата (ОА) и управляющего автомата (УА) рис. 1.

Рис. 1. Модель цифрового автомата

ОА предназначен для выполнения набора требуемых операций алгоритма, а второй — для задачи последовательных действий по алгоритму в зависимости от условий.

Работа автомата разбивается на определенные интервалы времени. Каждая элементарная, атомарная операция, которая может выполняться в ОА за один интервал времени, называется микрооперацией.

УА служит для выдачи управляющих сигналов в каждом интервале работы ЦА, инициирующих выполнение определенных микроопераций в ОА в соответствии с выполняемым алгоритмом и в зависимости от поступающих на входы УА условий. Если УА «знает», что и когда делать, то ОА «знает», как делать. При этом для УА «что делать» — это код команд, про содержание которых он не «знает».

Синтез цифрового автомата разделяют на четыре этапа. Условно их называют:

а) этап блочного синтеза автомата — происходит разбор на отдельные блоки;

б) этап абстрактного синтеза — определяется объем затрачиваемой памяти для данного

в) этап структурного синтеза, когда происходит выбор логических и запоминающих элементов для построения блока;

г) этап надежности синтеза — производится преобразование и дополнение построенных схем с целью обеспечения надежности [2].

Современные устройства работают на методе синтеза Глушкова. Рассмотрим контрольно-пропускное устройство (КПУ) на входе предприятия. Не рассматривая механику работы данного устройства, перейдем к алгоритму программы.

Устройство может находиться в нескольких состояниях:

1) С1 — КПУ в открытом состоянии;

2) С2 — КПУ в закрытом состоянии;

3) С3 — КПУ в открытом состоянии после предъявления пропуска/ключа;

4) С4 — КПУ заблокировано.

Сигналы, подаваемые на устройство: сигнал о предъявлении пропуска/ключа (а1), сигнал о несоответствии пропуска/ключа (а0), сигнал об использовании пропуска/ключа (а2), сигнал об аварийной ситуации (а3), сигнал о нарушении безопасности (а4), сигнал о возврате в прежние состояние (а5).

Начальное состояние — это состояние С2. При предоставлении соответствующего пропуска, система отреагирует и подаст сигнал а1, состояние изменится на С3. После

использования соответствующего пропуска/ключа система должна перейти в прежнее состояние с помощью сигнала а2. При несоответствии пропуска сигнал а0 не изменит состояние.

Данное устройство связанно с общей системой предприятия и, в случае аварийной ситуации, должно перейти в пропускной режим открытого типа для свободного покидания помещения сотрудниками во время эвакуации. Для этого на устройство должен подаваться сигнал а3, следовательно, состояние С2 заменится состоянием С1. Для обеспечения информационной защиты предприятия, в случае несанкционированного проникновения, должен пойти сигнал а4. Он переведет систему из состояния С2 в С4. У охраны предприятия будет сигнал а5, который изменит состояние С1/С4 на С2. Для наглядности рассмотрим описанные примеры в виде графов, в которых точки «С» — это состояние системы, дуги «а» — переходы из этих состояний (рис. 2).

Рис. 2. Граф состояний

Задача синтеза автомата возникает, когда нет готовой стандартной интегральной схемы, подходящей для данного случая, и когда алгоритм работы интегрируемого автомата не слишком сложен. Если алгоритм сложный, то устройство разбивают на несколько отдельных автоматов или используют микроконтроллер. Автомат можно построить из отдельных типовых интегральных схемах или на базе программируемой логической интегральной схемы.

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

1. Глушков, В. М. Синтез цифровых автоматов / В. М. Глушков. — Москва : Государственное издательство физико-математической литературы. — 1962. — 476 с.

Описание цифровых автоматов на VHDL

Цифровой автомат (ЦА) — это устройство, которое осуществляет прием, хранение и преобразование дискретной информации по некоторому алгоритму и может находиться в одном из нескольких устойчивых состояний [7].

Рисунок 1 — Граф цифрового автомата

Если выходной сигнал цифрового автомата зависит лишь от текущего состояния, то такой автомат называется автоматом Мура, если же выходной сигнал зависит от текущего состояния и входных сигналов, то такой цифровой автомат носит название автомата Мили.

Цифровой автомат может быть описан с помощью таких представлений:

— в виде ориентированного графа,
— с помощью переходов и выходов.

Представление цифрового автомата в виде ориентированного графа показано на рис. 1. Здесь в кругах — вершинах графа — показаны состояния цифрового автомата, переходы между состояниями показаны дугами между вершинами, а переход в то же самое состояние — петлей.

Возле дуг и петель показаны значения входных сигналов, при которых происходит этот переход. Например, (a OR b) обозначает, что этот переход произойдет при a = 1 или b = 1.

Выходные сигналы для автомата Мура показаны около вершин графа, а для цифрового автомата Мили — на дугах возле входных сигналов. Т.о. на рис. 1 показан цифровой автомат Мура.

Представление цифрового автомата с помощью таблиц предполагает наличие двух таблиц: таблицы переходов и таблицы выходов. Таблица переходов связывает между собой текущее состояние, входные сигналы и будущее состояние цифрового автомата. Таблица переходов ЦА, описанного графом на рис. 1, показана в табл. 1.

Таблица 1 — Таблица переходов цифрового автомата

Текущее состояние Следующее состояние Условие перехода
S0 S0 a=0 ИЛИ c=0
S0 S1 a=1
S1 S1 a=1 ИЛИ b=1
S1 S0 a=0 И b=0
S0 S2 c=1
S2 S2 c=1 ИЛИ b=1
S2 S0 c=0 И b=0

Таблица выходов — показывает соответствие текущего состояния цифрового автомата и его выходных сигналов (табл. 2).

Таблица 2 — Таблица выходов цифрового автомата>

Текущее состояние Выход
S0 00
S1 01
S2 10

При реализации цифрового автомата мы будем придерживаться принципа разделения на комбинационную и последовательностную части схемы. При такой интерпретации цифровой автомат будет представлен тремя блоками (рисунок 2):

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

Рисунок 2 — Схематическое изображение цифрового автомата с асинхронными выходами

Схема логики переходов на свой вход получает код текущего состояния цифрового автомата (present_st) и внешние сигналы (input_signal). Выходом этого блока будет код следующего состояния (next_st).

В регистр состояний входит три сигнала: тактовый (clk), сброса (reset) и код следующего состояния (next_st). Тактовый сигнал и сигнал сброса предназначены для управления триггерами, которые хранят состояние цифрового автомата. По переднему фронту тактового сигнала производится запись следующего состояния (next_st) в триггеры. Результаты записи в триггеры появляется на выходе регистра состояния в виде сигнала текущего состояния ЦА (present_st).

Блок формирования выходных сигналов в зависимости от состояния ЦА (и входных сигналов для автомата Мили) формирует асинхронные выходные сигналы. Для получения синхронных выходных сигналов в этот блок дополнительно встраивают регистр.

Использование VHDL для описания цифровых автоматов

Для описания состояний цифрового автомата необходимо использовать перечислимый тип. Для этого описывается тип (state_type), значениями которого являются состояния цифрового автомата. Потом описывается сигнал (state) этого перечислимого типа, в котором и будет храниться текущее состояние автомата.

TYPE state_type IS (init, state1, state2, . ); SIGNAL state: state_type; 

При реализации будет получена схема из нескольких триггеров. В зависимости от метода кодирования состояний количество триггеров может изменяться, что влияет на быстродействие и размер схемы. Более подробно о методах кодирования мы поговорим чуть позже.

Для описания работы цифрового автомата и создания комбинационных схем логики переходов и выходов необходимо использовать соответствующие таблицы и помощью оператора case проанализировать значения сигнала present_st.

Процесс, который описывает комбинационную часть для вычисления логики переходов цифрового автомата, может быть описан с помощью такого шаблона:

PROCESS (present_st, input_signal) BEGIN CASE present_st IS WHEN state1 => IF input_signal = '1' THEN next_st IF input_signal = '1' THEN next_st  

Для описания логики выходных сигналов возможно использование оператора процесса или оператора параллельного условного присваивания.

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

PROCESS (present_st) BEGIN CASE present_st IS WHEN state1 => output output  

Здесь в списке инициализации процесса используется только текущее состояние цифрового автомата present_st, значения которого анализируются с помощью оператора case.

Для автомата Мили этот же процесс будет выглядеть таким образом:

PROCESS (present_st, input_signal) BEGIN CASE present_st IS WHEN state1 => IF input_signal = '1' THEN output IF input_signal = '1' THEN output  

Этот процесс для инициализации использует текущее состояние ЦА (present_st) и входной сигнал (input_signal) так как изменения любого из этих сигналов должно запускать выполнение процесса.

Для получения синхронных выходных сигналов необходимо использовать процесс, у которого в списке инициализации находится только тактовый сигнал clk. Анализ текущего состояния так же как и в предыдущем случае производится с помощью оператора case.

PROCESS (clk) BEGIN IF (rising_edge(clk)) THEN CASE present_st IS WHEN state1 => output output  

Формирование выходных сигналов с помощью параллельного условного присваивания не требует оператора процесса. В этом случае можно использовать такую конструкцию:

output  

При описании последовательностной части цифрового автомата в списке инициализаторов процесса должны содержатся сигналы clk и reset. При поступлении сигнала сброса reset цифровой автомат переходит в начальное состояние init, из которого начинается работа всего автомата. Передний фронт сигнала clk приводит к записи в триггеры ЦА его нового текущего состояния, т.е. сигнал next_st переписывается в сигнал present_st.

Фактически последовательностная часть представляет собой регистр со сбросом:

PROCESS (clk, reset) BEGIN IF reset = '1' THEN present_st  

Сигнал сброса может быть синхронным или асинхронным. Выше в листинге описан вариант асинхронного сброса.

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

Использование синхронного сигнала сброса не позволяет определить в каком состоянии окажется автомат при включении питания. Возможно, что он > в одном из неописанных состояний. Т.о. при описании цифрового автомата необходимо описать все2^n комбинаций состояний триггеров вне зависимости от того являются они рабочими состояниями цифрового автомата или нет. Здесь n — количество триггеров, применяемых для кодирования цифрового автомата. Это, в свою очередь приведет, к увеличению схемы логики переходов.

Для того, чтобы избежать > ЦА в неописанных состояниях необходимо явно прописывать действия в таких ситуациях с помощью конструкции when… others. Например, возможно использование такого процесса для описания синхронного сброса и действий в неиспользуемых состояниях.

PROCESS (clk) BEGIN IF (rising_edge(clk)) THEN IF reset = '1' THEN state IF input_signal = '1' THEN state IF input_signal = '1' THEN state state  
Три, два, один

Цифровой автомат можно описать с помощью одного, двух или трех операторов процесса. Эти варианты рассмотрим на примере цифрового автомата управления светофором.

Этот цифровой автомат имеет пять состояний: начальное (Init), красный ( R ), зеленый (G) и два желтых — один для перехода из красного к зеленому (RG), а второй — из зеленого к красному (GR). В том случае, когда вход cnt равняется нулю, никаких переходов не происходит, когда вход cnt равняется единице — происходит переход в следующее состояние. Граф цифрового автомата изображен на рис. 3.

Рисунок 3 — Граф цифрового автомата светофора

Этот же автомат может быть представлен с помощью таблицы переходов и таблицы выходов. Выходной сигнал представлен трехбитным вектором, в котором старший бит отвечает за красный, второй – за желтый и младший – за зеленый.

Таблица 3 — Таблица переходов

present_ st next_st Условие перехода
Init Init cnt = 0
Init R cnt = 1
R R cnt = 0
R RG cnt = 1
RG RG cnt = 0
RG G cnt = 1
G G cnt = 0
G GR cnt = 1
GR GR cnt = 0
GR R cnt = 1

Таблица 4 — Таблица выходов

present_st output
Init 000
R 100
RG 010
G 001
GR 010

Для описания состояний ЦА необходимо описать перечислимый тип, в котором будут перечислены все состояния. В приведенном примере вводится тип state_type, который содержит пять значений: Init, R, RG, G, GR. Для работы конкретного экземпляра цифрового автомата нужно описать сигналы этого типа. В примере это сигналы next_st, present_st для хранения последующего и текущего состояний автомата соответственно. При выполнении процессов этот сигнал будет принимать значение текущего состояния цифрового автомата.

Теперь рассмотрим описание этого цифрового автомата с помощью трех процессов (рисунок 4), каждый из которых описывает отдельную часть цифрового автомата:

— комбинационная часть для логики переходов;

— комбинационная часть для выходных сигналов;

— последовательностная часть только для записи состояний цифрового автомата.

Рисунок 4 — Цифровой автомат с тремя процессами

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

Сама программа представляет собой комбинацию трех процессов, описанных выше.

Описание цифрового автомата с помощью трех процессов

LIBRARY ieee; USE ieee.std_logic_1164.ALL; ENTITY traffic IS PORT(clk : IN std_logic; cnt : IN std_logic; reset : IN std_logic; output : OUT std_logic_vector(2 downto 0) ); END ENTITY; ARCHITECTURE rtl OF traffic IS TYPE state_type IS (Init, R, RG, G, GR); SIGNAL next_st, present_st: state_type; BEGIN state_proc: PROCESS (present_st, cnt) BEGIN CASE present_st IS WHEN Init => IF cnt = '1' THEN next_st if cnt = '1' THEN next_st IF cnt = '1' THEN next_st IF cnt = '1' THEN NEXT_st IF CNT = '1' THEN next_st next_st output output output output output  

Результирующий граф ЦА, полученный при компиляции в пакете Quartus II показан на рисунке 5 (меню Tools — Netlist Viewers — State Machine Viewer).

Рисунок 5 — Цифровой автомат с тремя процессами. Результат компиляции

Результат синтеза программы, приведенной в листинге выше, показан на рис. 6 (меню Tools — Netlist Viewers — Technology Map Viewer). Для облегчения понимания на рисунке элементы ввода-вывода обозначены как IO, триггеры как FF, а логические элементы — LE. Как видно в результате синтеза получится схема из 5 триггеров для хранения состояний цифрового автомата (в случае метода кодирования One Hot) и двух логических элементов для реализации схемы переходов и формирования выходных сигналов.

Рисунок 6 — Цифровой автомат с тремя процессами. Technology Map Viewer

Описание с помощью двух процессов (рис. 6) предполагает, что блок логики переходов и регистр состояний объединяются в один процесс, в котором с помощью оператора case производится выбор будущего значения состояния цифрового автомата. Поскольку нет необходимости разделять сигналы текущего и будущего состояний, то эти два сигнала заменены на один, state, в котором и хранится состояние цифрового автомата.

В листинге ниже показан пример описания ЦА с асинхронным сбросом. В результате компиляции будет получен такой же результат как и в предыдущем случае — рис.7.

Рисунок 7 — Цифровой автомат с двумя процессами

Описание ЦА с помощью двух процессов. Асинхронный сброс

LIBRARY ieee; USE ieee.std_logic_1164.ALL; ENTITY traffic IS PORT(clk : IN std_logic; cnt : IN std_logic; reset : IN std_logic; output : OUT std_logic_vector(2 downto 0) ); END ENTITY; ARCHITECTURE rtl OF traffic IS TYPE state_type IS (Init, R, RG, G, GR); SIGNAL state: state_type; BEGIN state_proc: PROCESS (clk, reset) BEGIN IF reset = '1' THEN state IF cnt = '1' THEN state IF cnt = '1' THEN state IF cnt = '1' THEN state IF cnt = '1' THEN state IF cnt = '1' THEN state output output output output output  

Цифровой автомат с синхронным сбросом, описанный двумя процессами показан ниже. Результаты синтеза из Technology Map Viewer показаны на рис. 8, из которого видно, что размер комбинационной части значительно автомата увеличился по сравнению с автоматом с асинхронным сбросом.

Описание ЦА с помощью двух процессов. Синхронный сброс

LIBRARY ieee; USE ieee.std_logic_1164.ALL; ENTITY traffic IS PORT(clk : IN std_logic; cnt : IN std_logic; reset : IN std_logic; output : OUT std_logic_vector(2 downto 0) ); END ENTITY; ARCHITECTURE rtl OF traffic IS TYPE state_type IS (Init, R, RG, G, GR); SIGNAL state: state_type; BEGIN state_proc: PROCESS (clk) BEGIN IF (rising_edge(clk)) THEN IF reset = '1' THEN state IF cnt = '1' THEN state IF cnt = '1' THEN state IF cnt = '1' THEN state IF cnt = '1' THEN state IF CNT = '1' THEN state output output output output output  

Рисунок 8 — Результат синтеза цифрового автомата с синхронным сбросом

Описание цифрового автомата с помощью одного процесса предполагает, что вся логика находится в одном процессе. Некоторые авторы [5] считают, что использование одного процесса для описания цифрового автомата является более простым и позволяет более просто описывать и отлаживать цифровой автомат. Данное утверждение справедливо для небольших цифровых автоматов. При увеличении количества состояний и использовании одного процесса ухудшается читабельность кода. Потому как еще древние римляне при описании цифровых автоматов пользовались правилом «Разделяй и властвуй».

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

И все же, для завершения образа, приведем пример описания цифрового автомата с асинхронным сбросом с помощью одного процесса.

Описание ЦА одним процессом

LIBRARY IEEE; USE ieee.std_logic_1164.ALL; ENTITY traffic IS PORT(clk : IN std_logic; cnt : IN std_logic; reset : IN std_logic; output : OUT std_logic_vector(2 downto 0) ); END ENTITY; ARCHITECTURE rtl OF traffic IS TYPE state_type IS (Init, R, RG, G, GR); SIGNAL state: state_type; BEGIN PROCESS (clk, reset) BEGIN IF reset = '1' THEN state IF cnt = '1' THEN state IF cnt = '1' THEN state IF cnt = '1' THEN state IF cnt = '1' THEN state IF cnt = '1' THEN state  

Результат компиляции программы показан на рисунке \ref. Очевидно, что результат оказался таким же как и при описании с помощью двух процессов с единственным отличием – добавились триггеры для выходного регистра.

Рисунок 9 — Цифровой автомат с одним процессом

Подведем небольшие итоги наших изысканий.

Первое, и самое важное. Цифровой автомат существует! Мы его видели на картинке 5.
Второе. Описания с помощью двух и трех процессов дают одинаковый результат и выбор метода описания зависит от предпочтений разработчика.
Третье. Нужно очень внимательно относиться к начальному сбросу автомата и описанию неиспользуемых состояний.
Четвертое. Описание с помощью одного процесса приводит к появлению регистров для выходных сигналов цифрового автомата.

1. Altera. Quartus II Handbook Version 10.0 Volume 1: Design and Synthesis Vol. 1, 2010 — 1820 p.
2. B. Cohen. VHDL Coding style and Metodologies. Kluwer Academic Publishers.2002 — 454 p.
3. D. L. Perry. VHDL programming by example. New York: McGraw-Hill, 2002.- 476 p.
4. D. J. Smith. HDL chip design: a practical guide for designing, synthesizing, and simulating ASICs and FPGAs using VHDL or Verilog. Madison, AL: Doone Publications, 1996. — 448 p.
5. A. Taylor. How to Implement State Machines in Your FPGA. Xcell, 81(4), p. 52–57.
6. Xilinx. VHDL Reference Guide. XST User Guide.
7. К. Г. Самофалов. Прикладная теория цифровых автоматов. М. 1987. 375 с.

P.S. PDF-вариант лежит тут.

Оптимизация цифрового автомата (FSM)

Данный материал представляет краткое описание проблемы в теории цифровых автоматов и объясняет один из способов решения данной проблемы, который был найден при попытке автоматизации процесса построения цифрововых автоматов.

Введение

Автомат – система механизмов, устройств, в которой полностью автоматизированы процессы получения, преобразования, передачи энергии, материалов, информации.

Термин > в основном используется в двух аспектах:

  • техническом;
  • математическом.

При математическом подходе под автоматом понимается математическая модель, у которой должны быть входы, внутренние состояния и выходы. Детали структуры устройства не учитываюся и не рассматриваются.

В техническом подходе под автоматом понимается вполне реальное устройство, например, телефонный автомат, торговый автомат и т. д. В данном случае, естественно, известными являются детали внутреннего строения устройства.

С точки зрения сигналов цифровой автомат (ЦА) – система, которая может принимать входные сигналы, под их воздействием переходить из одного состояния в другое, сохранять его до прихода следующего входного сигнала, выдавать выходные сигналы.

В данной работе рассматриваются цифровые сигналы и двоичная логика на базе логических элементов.

Структурно-функциональная схема цифрового конечного автомата

Применение

Теория автоматов лежит в основе всех цифровых технологий и программного обеспечения. Часть математического аппарата теории автоматов напрямую применяется при разработке лексических и синтаксических анализаторов для формальных языков, в том числе языков программирования, а также при построении компиляторов и разработке самих языков программирования, описания аппаратуры, а также разметки.

Другое важнейшее применение теории автоматов — математически строгое нахождение разрешимости и сложности задач.

Автоматы Мура и Мили широко применяются при проектировании цифровых устройств на основе программируемых логических интегральных схем (ПЛИС). Наличие минимальной выходной задержки, связанной с переключением выходного регистра, отсутствие нестабильности переходного процесса на выходе автомата, отсутствие сквозного распространения сигнала через комбинационную схему от входа до выхода автомата, простота описания на языках описания аппаратуры делает автомат Мура практически незаменимым. Также автоматы Мура и взаимодействующие автоматы Мили используются в генетическом программировании.

Описание проблемы

Построение цифрового автомата -- довольно трудоёмкий процесс. Можно выделить следующие этапы разработки ЦА:

1) Очень часто разработка ЦА начинается с реализации графа, который отражает закладываемую логику в простом и понятном для человека виде.

2) Оптимизация графа -- с этой задачей человек может справиться довольно быстро.

3) Определение разрядности памяти. Минимальное число триггеров можно вычислить по формуле:

где, S -- это число состояний, ceil -- функция приведения значения до ближайшего целого числа, которое не меньше исходного.

4) Присвоение состояниям кодов. Алгоритма для правильного задания кодов для состояний нет. Именно от этого зависит сложность уравнений, которые мы получим для входов триггеров и количество элементов необходимых для сборки схемы.

5) Составление таблицы состояний-переходов.

6) Составление булевых арифметических уравнений для входов триггеров. Карты Карно составляются по таблице состояний-переходов, уравнения минимизируются.

7) Преобразование уравнений для согласования с элементной базой.

8) Разработка электрической схемы.

Основная проблема -- отсутствие алгоритма для задания кодов состояниям автомата таким образом, чтобы уравнения для входов триггеров были как можно проще.

Решение

Была разработана программа для построения цифровых автоматов. На вход программа принимает граф. В программе граф представляется в наборе вершин и рёбер(вершина, входной сигнал, вершина для перехода). Итерируясь по рёбрам составляются таблицы истинности для каждого разряда в СКНФ и СДНФ. Методом Куайна-Мак-Класки минимизируются обе формы уравнений. Для каждого разряда выбирается выражение с минимальным количеством логических операций >, >. Общее количество этих операций является критерием качества данной кодировки.

Количество возможных вариантов задания состояний можно рассчитать зная разрядность памяти(M) и количество состояний(S).

Количество вариантов выборки(V) нужного количества состояний(S) из всего количества кодов(C), формула из комбинаторики:

Количество возможных вариантов задания состояний(A) равно:

Если перебирать все варианты и потом отобрать лучший, то в зависимости от графа программа может исполняться слишком долго. Такой вариант подойдёт для автоматов с небольшим числом вариантов задания кодов состояний.

Для автоматов с большим числом возможных вариантов задания состояний был разработан генетический алгоритм перебора вариантов состояний.

Схема генетического алгоритма

Результаты

Для исследования был спроектирован автомат с числом возможных вариантов задания состояний равным 6720. Для каждого варианта было рассчитано количество необходимых элементов для реализации.

Данный ЦА описывает поведение пчелы (для простоты восприятия), входной сигнал представляет 0(всё спокойно) или 1(пчела видит шершня).

Граф цифрового автомата, описывающий поведение пчелы

  • Количество состояний: 5
  • Разрядность памяти: ceil(log2(5)) = 3
  • Разрядность входного сигнала: 1

Пример расчёта числа всех возможных вариантов построения автомата:

Анализ показал, что наибольшая вероятность встретить автомат с наилучшим исходом -- если количество 0 и 1 в кодах состояний будет равнозначным.

Для сложных автоматов, где перебор занимает много времени, эффективным решением будет применить генетический алгоритм, он не обязательно найдёт наилучший исход, но позволит быстро найти решение близкое к нему.

  • fsm
  • конечный автомат
  • цифровой автомат
  • минимизация
  • автомат мили
  • автомат мура
  • цифровая
  • цифровая схемотехника
  • генетический алгоритм
  • генетичесие алгоритмы

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *