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

  • Вид работы:
    Курсовая работа (т)
  • Предмет:
    Информатика, ВТ, телекоммуникации
  • Язык:
    Русский
    ,
    Формат файла:
    MS Word
    1,81 Мб
  • Опубликовано:
    2013-02-04
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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


0

0

0

1

1

0

1

1



Таблица 61



0

0

0

1

1

0

1

1


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

Таблица 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.     Лекции по дисциплине «Теория автоматов» к.т.н. доцент Петухов К.Ю.


Не нашли материал для своей работы?
Поможем написать уникальную работу
Без плагиата!