Моделирование дискретного автомата
Содержание
Введение
Абстрактный синтез дискретного
автомата
Структурный синтез дискретных
автоматов
Моделирование дискретного автомата
Заключение
Список использованных источников
Введение
Современные приборы и устройства сервиса
представляют собой сложные технические системы, реализованные на базе средств
вычислительной техники. Цифровые устройства и микропроцессоры являются
важнейшей составной частью различных объектов бытовой техники: радиоэлектронной
аппаратуры, стиральных и посудомоечных машин, холодильников и климат-систем,
изделий оргтехники и других устройств.
Такой широкий диапазон применения цифровых
устройств определяется их высокими техническими параметрами и
технико-экономическими показателями. В частности - это низкое
энергопотребление, высокое быстродействие, высокая надежность и
помехозащищенность, возможность реализации алгоритмов управления и обработки
сигналов любой сложности, малые габариты, технологичность и низкая стоимость
[1].
Управляющие автоматы реализуются в виде
"гибкой" или программируемой логики, на основе микропроцессоров, а
также в виде "жесткой логики" - на основе последовательностных
цифровых устройств. Математическими моделями, используемыми при анализе и
синтезе последовательностных устройств. В последнее время интерес к конечным
автоматам возрос, что связано с развитием интегральной программируемой
электроники и др. В основе синтеза таких устройств лежат методы абстрактного
(логического) и структурного синтеза конечных автоматов. Это обстоятельство
делает необходимым приобретения знаний и навыков применения этих методов для
анализа и синтеза цифровых устройств управления объектами и устройствами [2].
1 Абстрактный синтез дискретного автомата
Рассмотрим содержание и особенности определенных
этапов синтеза на примере.
Пусть требуется синтезировать асинхронный
автомат Мура начальное описание, которого представлено вход-выходной
последовательностью и таблицей соответствия:
дискретный
автомат сигнал триггер
.
Определяем мощность входного и
выходного множества Мх=5 Му=4.Строим первичную таблицу переходов-выходов
автомата Мура, как показано в соответствии с таблицей 1.
Таблица 1.1 Первичная таблица
переходов-выходов автомата Мура
х
|
Состояния
S и
выходные сигналы Y
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
-
|
|
|
-
|
-
|
|
|
-
|
-
|
-
|
|
-
|
-
|
|
|
-
|
-
|
|
|
|
|
|
-
|
-
|
-
|
|
|
-
|
-
|
-
|
-
|
-
|
|
-
|
-
|
-
|
-
|
|
|
-
|
|
|
-
|
Задача минимизации автомата сводится возможности
максимального уменьшения числа внутренних состояний без изменения закона их
функционирования.
Решение этой задачи выполним методом Ауфенкампа
и Хона основанного на понятии эквивалентных состояний.
Эквивалентным состоянием называется sn
и sm такие состояния
которым во-первых соответствуют одинаковые входные сигналы y(t)
а во вторых переход из состояний sn
и sm под воздействием
любого символа приводит к одному и тому же эквивалентному состоянию [3].
Алгоритм минимизации:
. Методом последовательного разбиения
выделяем все попарно эквивалентные состояния.
. Объединяем эквивалентные состояния в
одиночные классы у1 у2 и выделяем в каждом классе по одному состоянию для
выполнения последующих этапов при разбиении на классы пустые клетки во внимание
не принимаются.
. Строим вторичную таблицу
переходов-выходов в которой каждый класс состояний представляем только одним
эквивалентным состоянием.
Рисунок 1 - Первичный граф переходов-выходов
автомата Мура
Первое разбиение состояний на классы выполняем
по выходным сигналам как показано в таблице 2. Анализ показывает что в классе
у1 состояние s1 не является
эквивалентным основным состоянием этого класса так как при поступлении сигнала
х1 автомат переходит из состояния s1
в класс состояний у2 в отличии от других состояний класса переводящих автомат
под действием сигнала х1 в состояния класса у1 [4].
Таблица 2 - Разбиение на классы автомата Мура
х
|
Состояния
S и
выходные сигналы Y
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-
|
-
|
-
|
-
|
-
|
|
-
|
-
|
|
-
|
|
-
|
|
-
|
|
-
|
-
|
|
-
|
|
-
|
-
|
-
|
|
|
-
|
|
|
|
|
|
-
|
-
|
|
-
|
-
|
-
|
|
-
|
-
|
-
|
|
-
|
-
|
|
-
|
|
|
-
|
-
|
-
|
|
Кл.
|
|
|
|
|
|
|
Таблица 3 - Переходы-выходы автомата Мура
x
|
Состояния
Г и выходные сигналы Y
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-
|
|
-
|
-
|
-
|
|
|
|
-
|
|
|
-
|
|
-
|
|
|
-
|
|
|
|
|
-
|
|
-
|
-
|
-
|
|
|
|
-
|
|
-
|
|
Таблица 4 - Первичная таблица возбуждения
x
|
Y0
|
Y1
|
Y2
|
Y2
|
Y1
|
Y2
|
Y3
|
Y3
|
|
d1
|
d0
|
d1
|
d0
|
d1
|
d0
|
d1
|
d0
|
d1
|
d0
|
d1
|
d0
|
d1
|
d0
|
d1
|
d0
|
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
|
y0
|
y1
|
y2
|
y*2
|
y3
|
y4
|
y5
|
y*5
|
|
q3
|
q2
|
q1
|
q0
|
q3
|
q2
|
q1
|
q0
|
q3
|
q2
|
q1
|
q0
|
q3
|
q2
|
q1
|
q0
|
q3
|
q2
|
q1
|
q0
|
q3
|
q2
|
q1
|
q0
|
q3
|
q2
|
q1
|
q0
|
q3
|
q2
|
q1
|
q0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a2
|
a1
|
a0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
101
0 |
0
|
0
|
0
|
1
|
1
|
1
|
-
|
-
|
-
|
-
|
0
|
1
|
1
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
---
0 |
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
-
|
-
|
-
|
-
|
-
|
---
0 |
1
|
0
|
-
|
-
|
-
|
-
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
-
|
-
|
-
|
-
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
-
|
---
0 |
1
|
1
|
0
|
1
|
1
|
1
|
-
|
-
|
-
|
-
|
0
|
1
|
1
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
---
1 |
0
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
0
|
0
|
1
|
1
|
-
|
-
|
-
|
-
|
1
|
1
|
0
|
1
|
0
|
101
Таблица 5 - Вторичная таблица
возбуждения
x
|
Y0
|
Y1
|
Y2
|
Y2*
|
|
d1
|
d0
|
d1
|
d0
|
d1
|
d0
|
d1
|
d0
|
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
|
y0
|
y1
|
y2
|
y*2
|
|
q3
|
q2
|
q1
|
q0
|
q3
|
q2
|
q1
|
q0
|
q3
|
q2
|
q1
|
q0
|
q3
|
q2
|
q1
|
q0
|
|
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
|
a2
|
a1
|
a0
|
R3
|
S3
|
R2
|
S2
|
R1
|
S1
|
R0
|
S0
|
R3
|
S3
|
R2
|
S2
|
R1
|
S1
|
R0
|
S0
|
R3
|
S3
|
R2
|
S2
|
R1
|
S1
|
R0
|
S0
|
R3
|
S3
|
R2
|
S2
|
R1
|
S1R0S0
|
0 |
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
-
|
-
|
-
|
-
|
-
|
---
|
0 |
0
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
---
|
0 |
1
|
0
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
0 |
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
-
|
-
|
-
|
-
|
-
|
---
|
1 |
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
---
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Продолжение
таблицы 5
x
|
Y1
|
Y2
|
Y3
|
Y3*
|
|
d1
|
d0
|
d1
|
d0
|
d1
|
d0
|
d1
|
d0
|
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
|
y3
|
y4
|
y5
|
y*5
|
|
q3
|
q2
|
q1
|
q0
|
q3
|
q2
|
q1
|
q0
|
q3
|
q2
|
q1
|
q0
|
q3
|
q2
|
q1
|
q0
|
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
a2
|
a1
|
a0
|
R3
|
S3
|
R2
|
S2
|
R1
|
S1
|
R0
|
S0
|
R3
|
S3
|
R2
|
S2
|
R1
|
S1
|
R0
|
S0
|
R3
|
S3
|
R2
|
S2
|
R1
|
S1
|
R0
|
S0
|
R3
|
S3
|
R2
|
S2
|
R1
|
S1R0S0
|
0 |
0
|
0
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
---
|
0 |
0
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
---
|
0 |
1
|
0
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
-
|
-
|
-
|
-
|
-
|
---
|
0 |
1
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
---
|
1 |
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
111
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Структурный
синтез дискретных автоматов
Структурный
синтез начинается с кодирования входного и выходного алфавита и состояний
автомата.
Количество
разрядов для входных выходных сигналов и состояний определяется в
соответствии с формулой (1)
, (2.1)
где М-мощность
множества соответствующего алфавита;
х-означает
минимальное целое.
Рисунок 2 -
Вторичный граф переходов-выходов автомата Мура
Для автомата
Мура:
, (2.2)
, (2.3)
. (2.4)
Кодирование
входных сигналов автомата Мура представлена как в таблице 4.
Таблица 4 -
Кодирование входных сигналов автомата Мура
Входной сигнал
|
Коды
|
X0
|
0
|
0
|
0
|
X1
|
0
|
0
|
1
|
X2
|
0
|
1
|
0
|
X3
|
0
|
1
|
1
|
X4
|
1
|
0
|
Кодирование
выходных сигналов автомата Мура представлена в таблице 5.
Таблица 5 -
Кодирование выходных сигналов автомата Мура
Выходной сигнал
|
Коды
|
y0
|
0
|
0
|
y1
|
0
|
1
|
y2
|
1
|
0
|
y3
|
1
|
1
|
Одно из
возможных вариантов кодирования состояний автомата Мура представлен в
таблице 6.
Таблица 6 -
Кодирования состояний автомата Мура
Состояния Q
|
Коды
|
|
|
|
|
|
|
0
|
1
|
1
|
1
|
|
0
|
1
|
0
|
1
|
|
0
|
1
|
1
|
0
|
|
0
|
1
|
0
|
0
|
|
0
|
0
|
1
|
1
|
|
0
|
0
|
0
|
1
|
|
1
|
0
|
0
|
1
|
|
1
|
1
|
0
|
1
|
Вторичный граф
переходов-выходов автомата Мили представлен на рисунке 2.
Рисунок 3 -
Структурный граф автомата Мура
На основании
таблицы возбуждения формируем восемь функций возбуждения:
; (2.5)
; (2.6)
; (2.7)
; (2.8)
;
(2.9)
;
(2.10)
; (2.11)
. (2.12)
Выходные
функции и автомата Мура, являясь
функциями состояний, зависят только от четырех переменных Пользуясь таблицей переходов-выходов
автомата Мура, построим таблицу истинности для выходных функций и .
Таблица
7 - Таблица истинности выходных функций автомата Мура
Состояние автомата
|
Состояния триггеров
|
Выходные сигналы
|
|
|
|
|
|
Y
|
|
0
|
0
|
0
|
1
|
|
|
0
|
0
|
1
|
1
|
|
|
0
|
1
|
0
|
0
|
|
|
0
|
1
|
0
|
1
|
|
|
0
|
1
|
1
|
0
|
|
|
0
|
1
|
1
|
1
|
|
|
1
|
0
|
0
|
1
|
|
|
1
|
1
|
0
|
1
|
|
В результате
получим выражения:
; (2.13)
. (2.14)
3.
Моделирование дискретного автомата
Функциональная
схема автомата Мура на RS
- триггерах и элементах И-НЕ представлена в соответствии с рисунком 4.
Для проверки
соответствия синтезированной схемы заданным условиям функционирования
автомата выполним функциональное моделирование полученной схемы при помощи
программы моделирования Electronics
Workbench
[5].
Источником
входных сигналов является генератор двоичных слов, а выходные сигналы
модели автомата индицируется при помощи логического анализатора.
Рисунок 4 -
Генератор слов
Рисунок 5 -
Временные диаграммы функционирования
Рисунок 5 -
Модель автомата Мура
Заключение
В ходе работы
было проведено исследование дискретного автомата Мура, состоящее из :
. Абстрактный
синтез. В котором по вход-выходной последовательности и таблице
соответствия были рассчитаны: первичная и вторичная таблица
переходов-выходов; первичный и вторичный граф переходов-выходов; таблицы
. Дискретный
синтез. В нем была выполнена кодирование входных и выходных сигналов, а так
же состояний автомата Мура. На основании вторичного графа переходов-выходов
был построен граф с кодированными сигналами и состояниями, а на основании
таблицы возбуждения были получены восемь функций возбуждения и две выходные
функции, на основании таблицы истинности выходных сигналов.
. Моделирование
дискретного автомата. На этом этапе была построена функциональная модель
автомата Мура в программе Electronic WorkBench , построенной по выходным
функциям и функциям возбуждения. Запрограммировав генератор слов были
получены временные диаграммы, которые соответствуют вход-выходной
последовательности.
Список
использованных источников
1. Соловьев
В.В.Булатова И.Р.Стандартные программируемые логические устройства
Зарубежная радиоэлектроника.2000 № 4.С.66-76.
. Соловьев
В.В.Булатова И.Р. Архитектуры сложных программируемых логических
интегральных схем Зарубежная радиоэлектроника.2000 № 5.С.62-78.
. Энциклопедия
кибернетики Под ред. В.М.Глушакова. -Киев :Главная редакция украинской
советской энциклопедии,1974.
. Соловьев А.Я.
Основы информатики :Учебник для вузов. -М.: Изд-во МГТУ
им.Н.Э.Баумана,2001.
. Трахтенберг
Б.А .,Барадин Я.М .Конечные автоматы :Поведение и синтез.М.:Наука,1970