37369

Выполнить синтез автомата Мили, осуществляющего отображение информации

Курсовая

Информатика, кибернетика и программирование

Для их устранения используют развязывание пар переходов. Развязанными считаются такие пары которые в одном из разрядов кода состояния принимают противоположные значения. Для развязывания пар переходов последовательно рассматривают все пары подлежащие развязыванию и в каком либо разряде кода состояний им присваивается противоположное значение. Если в данном разряде это сделать нельзя то вводится новый разряд пока не будут развязаны все пары.

Русский

2013-09-24

701 KB

10 чел.

PAGE  21

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ РФ

САРАПУЛЬСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ

(филиал ИЖГТУ)

КАФЕДРА «Конструирование и производства  радиоаппаратуры»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе по дисциплине

«Теория автоматов»

(Вариант №50)

Выполнил ст. гр. ___ Ф.И.О

Проверил _______________

САРАПУЛ 2010

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

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

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

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

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

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

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

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

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

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


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

Вариант № 50  

Задания были рассчитаны с помощью формул:

Тип автомата:   NВ mod 2   

Входные слова:   NВ mod 13

Выходные слова: NВ mod 23

Выбор базиса:    NВ mod 5

Определение типов триггера: NВ mod 17,
где
NВ-номер варианта.

В результате получили следующее задание:

  Выполнить синтез автомата Мили, осуществляющего отображение информации:

Синтез выполнить на логических элементах {&, V, -} и типах триггеров E, S, JK.

 


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

   Всякий автомат, реализует некоторое отображение, называемое автоматным и алфавитным. Но не всякое алфавитное отображение является автоматным. Для того чтобы алфавитное отображение могло быть реализовано автоматом, оно должно обладать следующими свойствами:

  1.  Детерминированность – в автоматном отображении должно существовать однозначное соответствие между входными и выходными словами.
  2.  Равенство длин слов – в автоматном отображении должны сохраняться одинаковые длины входных и выходных слов
  3.  Свойство полноты – в автоматном отображении в множество входных слов включаются все их начальные отрезки.
  4.  Свойство соответствия начальных отрезков – в автоматном отображении одинаковым начальным отрезкам входных слов должны соответствовать одинаковые выходные начальные отрезки.

    В задании отображение является алфавитным. Для приведение алфавитного отображения к автоматному мы выполняем следующие действия:

1. Выравнивание длин слов (входных и выходных). Для выравнивания используем нестандартный  способ, то есть, добавляем минимальное число пустых букв к более короткому слову.


2. Пополнение отображения.  Проводим проверку на детерминированность по первым буквам слов. При необходимости слова пополняем пустыми буквами и снова проверяем. В результате получаем:


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

  По полученным отображениям строим граф и таблицу переходов в состояния. После реализации последней буквы автомат возвращают в исходное состояние, либо в произвольное. Затем переходим к следующему отображению. В результате получаем граф (см. рис. 1).

Рисунок  «Формализованное описание работы автомата (граф)»

По построенному графу заполняем таблицу переходов (см. табл. 1).

Таблица  «Формализованное описание работы автомата (таблица переходов)»

a1

a2

a3

C0

C5/ β

C3/ β

C1

-/-

C1

-/-

C2/ b1

-/-

-/-

C2

C0/b2

-/-

-/-

C0/b3

C3

C4/ β

-/-

-/-

-/-

C4

C6/ β

-/-

C1/b2

-/-

C5

C6/ b1

-/-

C2/ β

-/-

C6

-/-

-/-

C7/b2

C2/ b2

C7

-/-

C0/b2

-/-

-/-

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

   Минимизация заключается в исключении лишних состояний автомата и основана на разделении состояний на эквивалентные. Состояния называются эквивалентными, если при установке автомата в эти состояния они не обнаруживают разницы в поведении (при подаче одних и тех же входных букв на выходе одни и те же буквы). Минимизация состоит в последовательном разбиении состояний на классы по числу букв, на которые автомат одинаково реагирует. Затем каждую группу обозначают новым состоянием и перестраивают таблицу переходов. Выделяем первый эквивалентный класс. Разобьем состояния на группы в соответствии с одинаковым выходным состоянием. Затем рассматриваем переходы автомата под воздействием входных букв и выделяем одинаковые группы. Минимизацию проводим до тех пор, пока группы не перестанут расщепляться.

                                                                       

              0 3                 1 2                    4 6 7                       5      

а1           5 4                  0                     6 --                       6

         С0     С3             С1        С2               С4С6         С7            С5

а1         5   4                   1   0                    6 -            -           6

а2         3   -                    -   -        8            - -            -           -

а3         1   -                    -   -         4           1 7          -           2           

       -    -                    -    0        -           - 2           -            -

          С0     С3           С1     С2                  С4С6           С7          С5

       -     -                -       0                    - 2              -         -           

  Группы достигли минимума и больше не расщепляются. Найдены эквивалентные классы. Так как все группы состоят из одного элемента, то можно сделать вывод, что построенный граф является минимальным. Вследствие того, что каждый элемент является группой, перекодировать состояния нет смысла. Поэтому все остается в том же виде.


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

    

      Вследствие того, что каждый элемент является группой, перекодировать состояния нет смысла. Поэтому таблица переходов и выходов остается в прежнем виде (см. табл. 2).

   Таблица  «Таблица переходов и выходов автомата»

a1

a2

a3

C0

C5/ β

C3/ β

C1

-/-

C1

-/-

C2/ b1

-/-

-/-

C2

C0/b2

-/-

-/-

C0/b3

C3

C4/ β

-/-

-/-

-/-

C4

C6/ β

-/-

C1/b2

-/-

C5

C6/ b1

-/-

C2/ β

-/-

C6

-/-

-/-

C7/b2

C2/ b2

C7

-/-

C0/b2

-/-

-/-


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

     Переход автомата из одного состояния в другое подразумевает переключение его элементов памяти. Но так как каждый элемент памяти имеет свою задержку включения, а длины цепей для сигналов переключения триггеров различны, то могут возникнуть состязания или гонки. Для их устранения используют развязывание пар переходов. Развязанными считаются такие пары, которые в одном из разрядов кода состояния принимают противоположные значения. Для развязывания пар переходов последовательно рассматривают все пары, подлежащие развязыванию, и в каком либо разряде кода состояний им присваивается противоположное значение. Если в данном разряде это сделать нельзя, то вводится новый разряд, пока не будут развязаны все пары. Затем проводят минимизацию числа разрядов, отбрасывая 1-й разряд и снова пытаясь развязать пары.

   Сначала составляем множество пар переходов для каждой входной буквы
(см. табл. 3).

Таблица  «Множество пар переходов для каждой входной буквы»

М1{а1}

М2{а2}

М3{а3}

М4{}

С0С5

С0С3

С0С1

С2С0

С2С0

С7С0

С4С1

С6С2

С3С4

С5С2

С4С6

С6С7

С5С6

В каждом множестве развязываем пары между собой(см. табл. 4).

Таблица  «Развязывание пар переходов»

Z1

Z2

Z3

Z4

Z5

Z6

C0

0

0

0

0

0

1

C1

1

0

0

0

1

1

C2

1

1

0

0

0

0

C3

1

1

1

0

1

1

C4

1

1

1

1

1

1

C5

0

1

1

1

0

0

C6

0

0

1

1

1

0

C7

0

0

0

1

1

0

Развязывание пар переходов:

Множество М1:

С0С5 и С2С0  разв. по опр

С0С5 и С3С4  разв. по Z1

С0С5 и С4С6  разв. по Z5

С0С5 и  С5С6 по опр.

С2С0 и С3С4 разв. по Z3

С2С0 и С4С6 разв. по Z3

С2С0 и С5С6 разв. по Z3

С3С4 и С4С6  по опр.

С3С4 и С5С6 разв. по Z1

С4С6 и С5С6 по опр.

Множество М2:

С0С3 и С7С0 по опр.

Множество М3:

С0С1 и С4С1 по опр.

С0С1 и С5С2 разв. по Z2

С0С1 и С6С7 разв. по Z4

С4С1 и С5С2 разв. по Z5

С4С1 и С6С7 разв. по Z1

С5С2 и С6С7 разв. по Z5

Множество М4:

С2С0 и С6С2 разв. по опр

Вычеркиваем Z1 и повторяем все действия.

Множество М1:

С0С5 и С2С0  разв. по опр

С0С5 и С3С4  разв. по Z5

С0С5 и С4С6  разв. по Z5

С0С5 и  С5С6 по опр.

С2С0 и С3С4 разв. по Z3

С2С0 и С4С6 разв. по Z3

С2С0 и С5С6 разв. по Z3

С3С4 и С4С6  по опр.

С3С4 и С5С6 разв. по Z6

С4С6 и С5С6 по опр.

Множество М2:

С0С3 и С7С0 по опр.

Множество М3:

С0С1 и С4С1 по опр.

С0С1 и С5С2 разв. по Z2

С0С1 и С6С7 разв. по Z4

С4С1 и С5С2 разв. по Z5

С4С1 и С6С7 разв. по Z6

С5С2 и С6С7 разв. по Z5

Множество М4:

С2С0 и С6С2 разв. по опр

Вычеркиваем Z2 и повторяем все действия.

Множество М1:

С0С5 и С2С0  разв. по опр

С0С5 и С3С4  разв. по Z5

С0С5 и С4С6  разв. по Z5

С0С5 и  С5С6 по опр.

С2С0 и С3С4 разв. по Z3

С2С0 и С4С6 разв. по Z3

С2С0 и С5С6 разв. по Z3

С3С4 и С4С6  по опр.

С3С4 и С5С6 разв. по Z6

С4С6 и С5С6 по опр.

Множество М2:

С0С3 и С7С0 по опр.

Множество М3:

С0С1 и С4С1 по опр.

С0С1 и С5С2 разв. по Z4

С0С1 и С6С7 разв. по Z4

С4С1 и С5С2 разв. по Z5

С4С1 и С6С7 разв. по Z6

С5С2 и С6С7 разв. по Z5

Множество М4:

С2С0 и С6С2 разв. по опр

Вычеркиваем Z3 и повторяем все действия.

Множество М1:

С0С5 и С2С0  разв. по опр

С0С5 и С3С4  разв. по Z5

С0С5 и С4С6  разв. по Z5

С0С5 и  С5С6 по опр.

С2С0 и С3С4 разв. по Z5

С2С0 и С4С6 разв. по Z4

С2С0 и С5С6 разв. по Z4

С3С4 и С4С6  по опр.

С3С4 и С5С6 разв. по Z6

С4С6 и С5С6 по опр.

Множество М2:

С0С3 и С7С0 по опр.

Множество М3:

С0С1 и С4С1 по опр.

С0С1 и С5С2 разв. по Z4

С0С1 и С6С7 разв. по Z4

С4С1 и С5С2 разв. по Z5

С4С1 и С6С7 разв. по Z6

С5С2 и С6С7 разв. по Z5

Множество М4:

С2С0 и С6С2 разв. по опр

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

Таблица  «Ранжирование состояний по числу переходов в них»

Состояние

С0

С1

С2

С3

С4

С5

С6

С7

Кол-во переходов

3

2

3

1

1

1

2

1

В соответствии с ранжированием состояния кодируются следующим образом:

C0 → 000

C2 → 001

C1 → 010

C6 → 011

C3 → 100

C4 → 101

C5 → 110

C7 → 111

Также закодируем входные и выходные буквы (см. табл. 6):

Таблица  «Кодирование входных и выходных букв»

X1

X2

Y1

Y2

а1

0

0

b1

0

0

а2

0

1

b2

0

1

а3

1

0

b3

1

0

1

1

1

1

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


Таблица  «Кодированная таблица переходов и выходов автомата»

Qt 

Qt+1

X1

X2

Z1

Z2

Z3

Z1

Z2

Z3

Y1

Y2

С0

0

0

0

0

0

1

1

0

1

1

0

1

0

0

0

1

0

0

1

1

1

0

0

0

0

0

1

0

1

1

1

1

0

0

0

-

-

-

-

-

С2

0

0

0

0

1

0

0

0

0

1

0

1

0

0

1

1

0

0

0

1

-

-

-

-

-

1

1

0

0

1

0

0

0

1

0

С1

0

0

0

1

0

-

-

-

-

-

0

1

0

1

0

0

0

1

0

0

1

0

0

1

0

-

-

-

-

-

1

1

0

1

0

-

-

-

-

-

С6

0

0

0

1

1

-

-

-

-

-

0

1

0

1

1

-

-

-

-

-

1

0

0

1

1

1

1

1

0

1

1

1

0

1

1

0

0

1

0

1

С3

0

0

1

0

0

1

0

1

1

1

0

1

1

0

0

-

-

-

-

-

1

0

1

0

0

-

-

-

-

-

1

1

1

0

0

-

-

-

-

-

С4

0

0

1

0

1

0

1

1

1

1

0

1

1

0

1

-

-

-

-

-

1

0

1

0

1

0

1

0

0

1

1

1

1

0

1

-

-

-

-

-

С5

0

0

1

1

0

0

1

1

0

1

0

1

1

1

0

-

-

-

-

-

1

0

1

1

0

0

0

1

1

1

1

1

1

1

0

-

-

-

-

-

С7

0

0

0

1

1

-

-

-

-

-

0

1

0

1

1

0

0

0

0

1

1

0

0

1

1

-

-

-

-

-

1

0

0

1

1

-

-

-

-

-

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

Рисунок  «Карты Карно для функции переключения триггеров»

Рисунок  «Карты Карно для функций»

  

  В результате минимизации получились следующие функции:

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

Таблица  «Работа JK триггера»

J

K

Qt+1

J

K

0

0

Qt

0

0

0

b1

0

1

0

0

1

1

b2

1

0

1

1

0

b3

1

1

1

1

1

b4

1

Примем b3=0.

Примем b1=0, b2=0.

Рисунок  «Карты Карно для JK триггера»

Таблица 9 «Работа E триггера»

RE

SE

Qt+1

R

S

0

0

Qt

0

0

b1

0

0

1

1

0

1

0

1

1

0

0

1

0

1

0

1

1

Qt

1

1

b3

b4

Примем b1=0, b3=1.

Примем b4=0.

Рисунок  «Карты Карно для E триггера»

Таблица 10 «Работа S триггера»

RS

SS

Qt+1

R

S

0

0

Qt

0

0

b1

0

0

1

1

0

1

0

1

1

0

0

1

0

1

0

1

1

1

1

1

b2

b2

Примем b1=1, b2=1.

Рисунок  «Карты Карно для S триггера»


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

  Так как в первоначальный момент времени состояние элемента в памяти не определено, то необходимо принудительно установить автомат в исходное состояние. Сигнал «установка» вводится в схему дизъюнктивно в соответствии с законом переключения триггера. Для введения синхронизации используется конъюнкция.

  Исходное состояние С0 → 000

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

В задании на курсовой проект указан базис И-ИЛИ-НЕ.

Все полученные функции удовлетворяют данному базису, поэтому остаются в неизменном виде.

  

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

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

  1.  Карпов Ю.Г «Теория автоматов».
  2.  Баранов С. И. «Синтез микропрограммных автоматом»
  3.  Поспелов Д. А. «Логические методы анализа и синтеза схем»
  4.  Лекции по дисциплине «Теория автоматов» к.т.н. доцент Петухов К. Ю.


 

А также другие работы, которые могут Вас заинтересовать

70311. Изучение фотолиза триптофана и триптофановых остатков в белках под действием УФ-излучением методом флуориметрии 1.96 MB
  Вторичное излучение исследуется в следующих случаях: исследуемая молекула испускает излучение в неудобной спектральной области и 2 исследуемая молекула вообще не способна к флуоресценции. Другой вариант действий в такой ситуации химическая модификация исследуемых соединений с целью...
70312. Методика построения моделей парной линейной регрессии и оценки их качества 252 KB
  Содержание: Выбор и построение модели Проверка соответствия модели выборочным данным Прогнозирование проверка соответствия модели новым данным Резюме Была построена модель линейной связи между переменными DPI и PCE. Анализируя диаграмму рассеяния исследуемых данных приходим...
70314. ПОДАТКОВИЙ МЕНЕДЖМЕНТ: КОНСПЕКТ ЛЕКЦІЙ 1.36 MB
  Конспект лекцій з дисципліни «Податковий менеджмент» охоплює питання ведення обліку платників податків, порядку нарахування податків та облік фактично внесених сум, методики проведення камеральних і документальних перевірок, правильності нарахування й своєчасності сплати...