Структурная схема конечного автомата с описанием его функционирования и выделением особенностей автоматов Мили и Мура
КУРСОВАЯ РАБОТА.
по дисциплине:
“ Теория дискретных устройств. ”
на тему:
“Синтез цифрового автомата с памятью. ”
Выполнил студент группы ТСТ-211 Ляшенко Кирилл Юрьевич
Принял преподаватель Архипов Евгений Васильевич
Москва 2013.
Содержание.
1) Задача синтеза цифрового автомата………………………………………………………3
2)Структурная схема конечного автомата с описанием его функционирования и выделением особенностей автоматов Мили и Мура…………………………………………4
3)Таблица переходов и выходов конечного автомата……………………….........................6
4. Граф автомата…………………………………………………………….............................7
5. Определение количества элементов памяти, определение количества триггеров........................................................................................................................................8
6. Выбор элементов памяти типа триггер. Условное обозначение для триггеров. Таблицы переходов и характеристические таблицы триггеров…………………………………………….9
7.Кодирование внутренних состояний триггеров в соответствии с заданием………………………………………………………………………… …………….12
8.Кодирование наборов входных переменных……………………………… ……………..12
9. Разработка схемы управления JK-триггерами в соответствии с таблицей переходов, а также таблицами кодирования состояний и наборов входных переменных…………………………………………………………………………………….13
10. Временная диаграмма для блока 1(схемы управления) и блока 2(блока элементов памяти) конечного автомата, выполненного на JK-триггерах...........................................17
11. Разработка схемы управления D-триггерами в соответствии с таблицей переходов, а также таблицами кодирования состояний и наборов входных переменных…………………………………………………………………………………….18
12. Временная диаграмма для блока 1(схемы управления) и блока 2(блока элементов памяти) конечного автомата, выполненного на D-триггерах……………………………….20
13. Разработка схемы , реализующей наборы выходных сигналов конечного автомата………………………………………………………………………......................21
14. Временная диаграмма для 3 блока, т.е.для схемы , реализующей наборы выходных сигналов конечного автомата………………………………………………………………25
15. Таблица функционирования конечного автомата………………………......................25
16. Минимизация функций аналитическим способом……………………………………...27
17. Литература………………………………………………………………………………32
18.Приложения (принципиальные схемы конечных автоматов)…………………………….33
Задача синтеза цифрового автомата.
Синтез автомата осуществляется в три этапа:
1 этап – задается словесное описание алгоритма работы автомата.
2 этап – на основании словесного описания алгоритма работы автомата разрабатывают формализованное задание алгоритма работы автомата. Применяют две формы задания алгоритма работы автомата:
а) В виде таблицы переходов и выходов.
б) В виде графа работы автомата.
3 этап – на основе формализованного задания алгоритма работы автомата, с помощью методов изучаемых в курсе ТДУ, осуществляют построение принципиальной схемы автомата. На основе методов ТДУ представляется возможным разработать жесткий алгоритм проектирования принципиальной схемы автомата. Этот алгоритм позволяет разработать специальное программное обеспечение и создать систему автоматического проектирования цифрового автомата.
В курсовом проекте будет осуществляться разработка принципиальной схемы работы автомата, включая все этапы синтеза, после того как будет заданно формализованное представление работы автомата.
Структурная схема конечного автомата с описанием его функционирования и выделением особенностей автоматов Мили и Мура.
Цифровой автомат с памятью состоит из 3-х блоков:
1 блок автомата представляет собой комбинационное устройство или комбинационную схему, с помощью которой будут формироваться управляющие сигналы на входах элементов памяти. Эти сигналы должны обеспечивать переключение триггеров в соответствии с таблицей переходов и выходов (в соответствии с графом работы автомата). Проектируемый автомат имеет 3 набора входных сигналов:Х1, Х2, Х3. И один запрещённый набор X0.Чтобы задать эти 4 набора необходимо иметь 2 входные двоичные переменные: х1, х2.(M=22=4). Переключение автомата, переход в новое состояние зависит от того, какие сигналы поступают на вход автомата (х1, х2) и какое внутреннее состояние имеет автомат в данный момент времени, т.е. какие значения имеют Q3, Q2, Q1 . Входными переменными для блока 1 будут х1, х2 , х1, х2 ,а также выходы элементов памяти Q3, Q2, Q1, Q3, Q2, Q1. Выходными – функции возбуждения триггеров.
2 блок представляет собой блок элементов памяти. Элемент памяти имеет 2 состояния. Одно из них условно называют “0”, а другое “1”. В качестве элементов памяти обычно используют триггеры. Управляющие входы триггеров предназначены для переключения триггера в соответствии с требуемым алгоритмом. Выходы триггера Q и Q. Если на Q = 0, то триггер находится в состоянии 0, при этом на инверсном выходе Q = 1. Переключение триггера из одного состояния в другое происходит в момент подачи импульса синхронизации на вход синхронизации. В этот момент триггер переключается в состояние “0” или в состояние “1” в зависимости от того, какие сигналы действуют на управляющих входах. В проектируемом автомате в соответствии с таблицей переходов и выходов содержится 8 внутренних состояний(a0 -a7).Чтобы задать 8 внутренних состояний, необходимо иметь 3 триггера: К=23=8.
3 блок автомата представляет собой комбинационную схему, с помощью которой формируются выходные сигналы. Проектируемый автомат имеет 3 набора входных сигналов (Х1 -Х3). И один запрещённый набор X0. А также 3 триггера. В соответствии с таблицей переходов и выходов мы определяем, что выходных сигналов будет 3 (Y1 – Y3). Для представления этих выходных наборов достаточно иметь 2 переменные: y1, y2. Выходные сигналы формируются в зависимости от внутреннего состояния автомата и от того, какие сигналы поступают на вход автомата.
Различают 2 типа конечного автомата , автомат Мили и автомат Мура.
Особенностью автомата Мили является то, что функции выходов зависят и от внутреннего состояния автомата и от входных сигналов. Также автомат Мили - это автомат с импульсным выходом. Зависимость выходного сигнала только от внутреннего состояния представлена в автоматах типа Мура. В автомате Мура функция выходов определяет значение выходных символов только по одному типу аргументов — состоянию автомата. Автомат Мура - это автомат с потенциальным выходом. В данном курсовом проекте в соответствии с заданием будет использован автомат Мили.
В автомате Мура связей, отмеченных (*) не будет.
Таблица переходов и выходов конечного автомата.
4. Граф автомата.