Синтез цифрового конечного автомата Мура
Содержание
Расчет задания
Получение автоматного отображения
Построение формализованного описания работы автомата
Минимизация числа внутренних состояний автомата
Кодирование состояний автомата
Построение кодированной таблицы переходов и выходов автомата
Построение функций переключения для заданных типов триггеров
Введение синхронизации и установки автомата в исходное состояние
Получение функции автомата в требуемом базисе
Построение функциональной схемы автомата
Построение временных диаграмм работы автомата
Список использованной литературы
Расчет задания
Вариант № 37
Задания были рассчитаны с помощью
формул:
Тип автомата: NВ mod 2
Входные слова: NВ mod 13
Выходные слова: NВ mod 23
Выбор базиса: NВ mod 5
Определение типов триггера: NВ mod
17
В результате получили следующее
задание:
Выполнить синтез автомата Мура,
осуществляющего отображение информации:
Синтез выполнить на
логических элементах {
}
и типах триггеров DV, RT, JK.
Получение автоматного
отображения
Всякий автомат,
реализует некоторое отображение, называемое автоматным и алфавитным. Но не
всякое алфавитное отображение является автоматным. Для того чтобы алфавитное
отображение могло быть реализовано автоматом, оно должно обладать следующими
свойствами:
1. Детерминированность
2. Равенство длин слов
. Свойство полноты.
. Свойство соответствия
начальных отрезков.
В задании отображение является
алфавитным. Для приведение алфавитного отображения к автоматному мы выполняем
следующие действия:
. Выравнивание длин слов (входных и
выходных). Для выравнивания используем нестандартный способ.
. Пополнение отображения. В
результате имеем следующее автоматное отображение.
Построение формализованного описания
работы автомата
По полученным отображениям строим
граф и таблицу переходов в состояния. После реализации последней буквы автомат
возвращают в исходное состояние, либо в произвольное. В результате получаем
граф (см. рис. 1).
Рисунок 1
«Формализованное отображение автомата (граф)»
По построенному графу заполняем
таблицу переходов (см. табл. 1).
Таблица 1 «Таблица
переходов и выходов автомата»
Минимизация числа внутренних
состояний автомата
Минимизация заключается в исключении
лишних состояний автомата и основана на разделении состояний на эквивалентные.
Состояния называются эквивалентными, если при установке автомата в эти
состояния они не обнаруживают разницы в поведении (при подаче одних и тех же
входных букв на выходе одни и те же буквы). Минимизация состоит в
последовательном разбиении состояний на классы по числу букв, на которые
автомат одинаково реагирует. Затем каждую группу обозначают новым состоянием и
перестраивают таблицу переходов. Выделяем первый эквивалентный класс. Разобьем
состояния на группы в соответствии с одинаковым выходным состоянием. Затем
рассматриваем переходы автомата под воздействием входных букв и выделяем
одинаковые группы. Минимизацию проводим до тех пор, пока группы не перестанут
расщепляться.
1 8 9 0 2 4 5 13 0 6 7
10 12 0 3 11 14
1 1 9 11 1 - - - - 1 -
- - - - 1 13 - -
1 8 9 0 2 4 5 13 0 6 7
10 12 0 11 14 3 11 14
1 1 9 11 1 - - - - 1 -
- - - - 1 - - 13 - -
1 8 9 0 2 4 5 13 0 6 7
10 12 0 11 14 3 11 14
1 1 9 11 1 - - - - 1 -
- - - - 1 13 - 13 - -
1 8 9 0 2 4 5 13 0 6 7
10 12 0 11 14 3 11 14
8 6 - 10 8 3 - - - - 8 -
- - - - 8 - - - 8 - - -
8 9 0 4 5 13 2 4 5 13 0
6 7 10 12 0 11 14 3 11 14
6 - 10 8 - - - - 3 - -
- - 8 - - - - 8 - - - 8 - - -
1 9 11 1 - - - - 1 - -
- - - 1 13 - 13 - -
8 9 0 4 5 13 2 4 5 13 0
6 7 10 12 0 11 14 3 11 14
2 - 9 3 - - - - - - - 3
- - - - 3 - - - - -
8 9 0 4 5 13 2 4 5 13 0
6 7 10 12 0 11 14 3 11 14
14 - 5 - 5 11 10 2 5 11
10 - 7 14 12 13 - 12 11 4 12 11
8 9 0 4 0 5 013 2 4 0 6
10 0 7 0 12 0 11 0 14 3
14 - 5 - 5 - 11 - 10 2
5 - 7 12 - 14 - 13 - 12 - 11 4
8 9 0 4 0 5 013 2 0 6 0
10 0 7 0 12 0 11 0 14 3
14 - 5 - 5 - 11 - 10 2
- 7 - 12 - 14 - 13 - 12 - 11 4
2 - 9 3 - 3 - 3 - - 3 -
3 - 3 - 3 - 3 - 3 - -
6 - 10 8 - 8 - 8 - 3 8
- 8 - 8 - 8 - 8 - 8 - -
1 9 11 1 - 1 - 1 - - 1
- 1 - 1 - 1 - 1 - 1 - 13
Полученные группы
больнее не расщепляются. Найдены эквивалентные классы. Далее проводим
перекодирование.
Построение кодированной таблицы
переходов и выходов автомата
После кодирования строим новую
таблицу переходов, в соответствии с кодировкой (см. табл. 2).
Таблица 2 «Кодированная
таблица переходов и выходов»
Построение функций переключения для
заданных типов триггеров
Переход автомата из одного состояния
в другое подразумевает переключение его элементов памяти. Но так как каждый
элемент памяти имеет свою задержку включения, а длины цепей для сигналов
переключения триггеров различны, то могут возникнуть состязания или гонки. Для
их устранения используют развязывание пар переходов. Развязанными считаются
такие пары, которые в одном из разрядов кода состояния принимают
противоположные значения. Для развязывания пар переходов последовательно
рассматривают все пары, подлежащие развязыванию, и в каком либо разряде кода
состояний им присваивается противоположное значение. Если в данном разряде это
сделать нельзя, то вводится новый разряд, пока не будут развязаны все пары.
Затем проводят минимизацию числа разрядов, отбрасывая 1-й разряд и снова
пытаясь развязать пары.
Таблица 3
Таблица 4
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 5
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 6
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 7
Таблица 8
|
|
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 9
|
|
оп
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 10
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 11
Таблица 12
Начиная с
развязываются по
определению
Таблица 13
Таблица 14
Таблица 15
Таблица 16
Таблица 17
|
|
|
|
|
|
|
|
|
|
|
0
|
1
|
|
0
|
1
|
1
|
1
|
|
|
|
1
|
0
|
0
|
0
|
0
|
|
|
|
|
|
1
|
0
|
1
|
1
|
0
|
|
0
|
|
|
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
|
|
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
|
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
|
|
1
|
1
|
1
|
1
|
1
|
1
|
|
|
|
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
|
|
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
|
|
0
|
0
|
0
|
|
0
|
0
|
1
|
|
|
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
|
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
|
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
|
|
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
|
Вычеркиваем
Таблица 18
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
Оп
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 19
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 20
|
опопоп
|
|
|
|
|
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 21
Таблица 22
|
|
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 23
|
|
оп
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 24
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 25
Таблица 26
Таблица 27
Таблица 28
Таблица 29
Таблица 30
|
|
|
|
|
|
|
|
|
|
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
|
|
0
|
0
|
0
|
0
|
|
0
|
0
|
|
|
|
0
|
1
|
1
|
0
|
|
0
|
0
|
|
|
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
|
|
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
|
|
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
|
|
1
|
1
|
1
|
1
|
1
|
|
|
|
|
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
|
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
|
|
|
0
|
0
|
0
|
0
|
0
|
1
|
|
0
|
|
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
|
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
|
|
0
|
0
|
0
|
1
|
0
|
1
|
|
|
|
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
Вычеркиваем
Таблица 31
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
Оп
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 32
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 33
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 34
Таблица 35
|
|
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
Оп
|
|
оп
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 36
|
|
оп
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 37
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 38
Таблица 39
Таблица 40
Таблица 41
Таблица 42
Таблица 43
Таблица 44
|
|
|
|
|
|
|
|
|
|
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
|
|
|
0
|
0
|
0
|
|
0
|
0
|
1
|
1
|
|
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
|
|
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
|
|
0
|
1
|
0
|
0
|
0
|
1
|
|
|
|
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
|
|
1
|
1
|
1
|
1
|
1
|
|
1
|
0
|
|
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
|
|
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
|
|
0
|
0
|
0
|
0
|
1
|
|
0
|
|
|
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
|
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
|
|
0
|
0
|
1
|
0
|
1
|
0
|
|
1
|
|
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
Вычеркиваем
Таблица 45
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
Оп
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 46
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 47
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 48
Таблица 49
|
|
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
Оп
|
|
оп
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 50
|
|
оп
|
|
|
|
|
|
|
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 51
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
оп
|
|
|
оп
|
|
оп
|
|
|
|
|
оп
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 52
Таблица 53
Таблица 54
Таблица 55
Таблица 56
Таблица 57
Таблица 58
|
|
|
|
|
|
|
|
|
|
|
1
|
1
|
1
|
1
|
0
|
1
|
|
|
|
0
|
0
|
|
0
|
0
|
1
|
1
|
1
|
|
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
|
|
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
|
|
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
|
|
|
1
|
1
|
1
|
1
|
|
1
|
0
|
|
|
|
0
|
0
|
0
|
1
|
1
|
0
|
|
1
|
|
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
|
|
0
|
0
|
0
|
1
|
|
0
|
|
|
|
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
|
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
|
|
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
|
|
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
|
В результате развязывания мы
получили 8 разрядов, что, несомненно, много. Поэтому для развязывания применяем
экономичное кодирование. В этом случае состояния ранжируют по числу переходов в
них. Состояние с наибольшим числом переходов ставят в соответствии код из
нулей.
|
|
4
|
|
|
1
|
|
|
4
|
|
|
4
|
|
|
4
|
|
|
4
|
|
|
2
|
|
|
4
|
|
|
4
|
|
|
4
|
|
|
4
|
|
|
4
|
|
|
4
|
|
|
3
|
В результате экономичного
кодирования получили:
Таблица 59
|
|
|
|
|
|
|
0
|
0
|
0
|
0
|
|
|
0
|
0
|
0
|
1
|
|
|
0
|
0
|
1
|
0
|
|
|
0
|
0
|
1
|
1
|
|
|
0
|
1
|
0
|
0
|
|
|
0
|
1
|
0
|
1
|
|
|
0
|
1
|
1
|
0
|
|
|
0
|
1
|
1
|
1
|
|
|
1
|
0
|
0
|
0
|
|
|
1
|
0
|
0
|
1
|
|
|
1
|
0
|
1
|
0
|
|
|
1
|
0
|
1
|
1
|
|
|
1
|
1
|
0
|
0
|
|
|
1
|
1
|
0
|
1
|
Таблица 60
Таблица 61
По результатам экономичного
кодирования и таблицы переходов строим кодированную таблицу переходов и выходов
автомата.
Таблица 62
|
|
|
Qt
|
Qt+1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
|
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
|
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
|
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
|
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
|
1
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
|
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
|
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
|
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
|
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
|
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
0
|
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
|
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
0
|
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
|
1
|
0
|
1
|
0
|
1
|
1
|
-
|
-
|
-
|
-
|
1
|
0
|
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
|
|
0
|
0
|
1
|
1
|
0
|
0
|
-
|
-
|
-
|
-
|
0
|
0
|
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
|
1
|
0
|
1
|
1
|
0
|
0
|
-
|
-
|
-
|
-
|
0
|
0
|
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
|
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
|
0
|
1
|
1
|
1
|
0
|
1
|
-
|
-
|
-
|
-
|
1
|
1
|
|
1
|
0
|
1
|
1
|
0
|
1
|
-
|
-
|
-
|
-
|
1
|
1
|
|
1
|
1
|
1
|
1
|
0
|
1
|
-
|
-
|
-
|
-
|
1
|
1
|
Построение функций переключения для
заданных типов триггеров
Проводим построение карт Карно для
переходов и входов триггеров. Наносим значения и проводим совместную
минимизацию.
Рисунок 2
Рисунок 3
Рисунок 4
После минимизации получаем функции
У1 и У2.
Для определения входов триггеров
используем таблицы переключения триггеров. Строим карты Карно и определяем что
будет подаваться на вход триггеров.
Таблица 63
|
D
|
V
|
Qt+1
|
|
|
V
|
D
|
|
0
|
0
|
Qt
|
0
|
0
|
|
|
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
|
1
|
0
|
Qt
|
1
|
0
|
1
|
0
|
|
1
|
1
|
1
|
1
|
1
|
|
|
Рисунок 5
. D V
-0 1 0
-1 1 1
. D V
-0 1 0
-1 0 0
Таблица 64
|
R
|
T
|
Q
|
|
|
R
|
T
|
|
0
|
0
|
Q
|
0
|
0
|
|
0
|
|
0
|
1
|
|
0
|
1
|
0
|
1
|
|
1
|
0
|
0
|
1
|
0
|
|
|
|
1
|
1
|
|
1
|
1
|
0
|
0
|
Рисунок 6
. R T
-0 0 1
Таблица 65
|
J
|
K
|
Q
|
|
|
K
|
J
|
|
0
|
0
|
Q
|
0
|
0
|
|
0
|
|
0
|
1
|
0
|
0
|
1
|
|
1
|
|
1
|
0
|
1
|
1
|
0
|
1
|
|
|
1
|
1
|
|
1
|
1
|
0
|
|
Рисунок 7
Таблица 66
|
JKQKJ
|
|
|
|
|
|
|
|
0
|
0
|
Q
|
0
|
0
|
|
0
|
|
0
|
1
|
0
|
0
|
1
|
|
1
|
|
1
|
0
|
1
|
1
|
0
|
1
|
|
|
1
|
1
|
|
1
|
1
|
0
|
|
Рисунок 8
Введение синхронизации и установки
автомата в исходное состояние
цифровой автомат мур
Получение функции автомата в
требуемом базисе
Построение временных диаграмм работы
автомата
Рисунок 9
Список использованной литературы
1. Карпов Ю.Г «Теория автоматов».
2. Баранов С.И. «Синтез микропрограммных автоматом»
. Поспелов Д.А. «Логические методы анализа и синтеза схем»
4. Лекции по дисциплине «Теория автоматов» к.т.н. доцент
Петухов К.Ю.