Синтез цифрового конечного автомата Мура

 

Содержание

Расчет задания

Получение автоматного отображения

Построение формализованного описания работы автомата

Минимизация числа внутренних состояний автомата

Кодирование состояний автомата

Построение кодированной таблицы переходов и выходов автомата

Построение функций переключения для заданных типов триггеров

Введение синхронизации и установки автомата в исходное состояние

Получение функции автомата в требуемом базисе

Построение функциональной схемы автомата

Построение временных диаграмм работы автомата

Список использованной литературы

Расчет задания

Вариант № 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

0101111000010110000011010001000111010010111111010000100111010000001000110001110100100001011101101

Вычеркиваем

Таблица 18

опопОпопопопопопопопоп

Таблица 19

опопопопопопопопопопопопопопопопопопопопопоп

Таблица 20

опопопопопопопопопопопоп

Таблица 21

опопопТаблица 22

опопопопопопопопопоп

Таблица 23

опопопопопопопопопопопопопопТаблица 24

опопопопопопопопопопопоп

Таблица 25

опопоп

Таблица 26

опопопопоп

Таблица 27

опопопоп

Таблица 28

опопопоп

Таблица 29

опоп

Таблица 30

100111100000000110000011011001000110100101111111000011001110100000010001100001101001100010110110101

Вычеркиваем

Таблица 31

опопОпопопопопопопопоп

Таблица 32

опопопопопопопопопопопопопопопопопопопопопоп

Таблица 33

опопопопопопопопопопопоп

Таблица 34

опопоп

Таблица 35

опопопопОпопопопопопТаблица 36

опопопопопопопопопопопопопоп

Таблица 37

опопопопопопопопопопопоп

Таблица 38

опопоп

Таблица 39

опопопопопопопоп

Таблица 40

опопопопоп

Таблица 41

опопопоп

Таблица 42

опопопоп

Таблица 43

опоп

Таблица 44

001111000000111100000011011110100010100101011111100000110111010010000100110000110100110001010101101010

Вычеркиваем

Таблица 45

опопОпопопопопопопопоп

Таблица 46

опопопопопопопопопопопопопопопопопопопопопоп

Таблица 47

опопопопопопопопопопопоп

Таблица 48

опопопТаблица 49

опопопопОпопопопопоп

Таблица 50

опопопопопопопопопопопопопопТаблица 51

опопопопопопопопопопопоп

Таблица 52

опопоп

Таблица 53

опопопопопопопопТаблица 54

опопопопоп

Таблица 55

опопопопТаблица 56

опопопоп

Таблица 57

опоп

Таблица 58

01111010000111100000001101111100011110010101111100001101110100100001011000011010011001010111101010

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

41444424444443

В результате экономичного кодирования получили:

Таблица 59

00000001001000110100010101100111100010011010101111001101

Таблица 60

00011011

Таблица 61

00011011

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

Таблица 62

QtQt+1000000000011010000010111100000110011110000101011000001100111010001011011100001000111110001001111000010000000010010110100100010101100110010001100000011000000010011110100100011101100110011100100000100000000010100110100100100101100110100011000000101000001010101110101100101101101110101011101000110000001010110110101100110101101110110100001000111000001010111110101100111101101110111101001001000000001011000110101101000101101111000010001001001000010011001110110101001101110111001100010001010000010011010110110101010101110111010100110001011010010011011101110101011----10111011001010001100----00011100101100101100----00111100110000001101000111011101----11101101----11111101----11

Построение функций переключения для заданных типов триггеров

Проводим построение карт Карно для переходов и входов триггеров. Наносим значения и проводим совместную минимизацию.

Рисунок 2

Рисунок 3

Рисунок 4

После минимизации получаем функции У1 и У2.

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

Таблица 63

DVQt+1VD 00Qt00010011110Qt101011111

Рисунок 5

. D V

-0 1 0

-1 1 1

. D V

-0 1 0

-1 0 0

Таблица 64

RTQRT00Q00001010110010111100

Рисунок 6

. R T

-0 0 1

Таблица 65

JKQKJ00Q00001001110110111110

Рисунок 7

Таблица 66

JKQKJ 00Q00001001110110111110

Рисунок 8

Введение синхронизации и установки автомата в исходное состояние

цифровой автомат мур

Получение функции автомата в требуемом базисе

Построение временных диаграмм работы автомата

Рисунок 9

Список использованной литературы

1.Карпов Ю.Г «Теория автоматов».

2.Баранов С.И. «Синтез микропрограммных автоматом»

.Поспелов Д.А. «Логические методы анализа и синтеза схем»

4.Лекции по дисциплине «Теория автоматов» к.т.н. доцент Петухов К.Ю.

Содержание Расчет задания Получение автоматного отображения Построение формализованного описания работы автомата Минимизация числа внутренних со

Больше работ по теме: