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


 

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

79185. Техника и технознание в футурологических теориях. Особенности развития техники в постиндустриальном обществе 15.58 KB
  Концепция информационного общества является разновидностью теории постиндустриального общества. Капитал и труд как основа индустриального общества уступают место информации и знанию в информационном обществе. Теория технотронного общества по З.Бжезинскому социологическая концепция исходящая из того что новые технологии и электроника являются решающим фактором социально-экономических изменений и социального прогресса конвергенции различных систем и предопределяют вступление общества в технотронную эру.
79186. Философский дискурс техники и технознания, его сущность, предмет и специфика в общей системе философского знания. Философия науки и философия техники в их соотношении 38 KB
  Здесь переплетается несколько критических путей развития естествознания и технознания: развитие теории подобия освоение новых форм подобия физических процессов в том числе на основе принципов симметрии спиральноколиброванных фиббоначиевыми рядами процессов развития в природе освоение технологий гибридного моделирования в том числе на основе теории гибридных интеллектуальных систем В. Венда; развитие термодинамического и вышедшего из него синергетического моделирования; развитие теории планирования эксперимента на базе...
79187. Техника как объект философской рефлексии: типология основных концепций. Смысл и сущность технической деятельности. Проблема технико-технологической демаркации 41 KB
  Сам Поппер характеризует свои интересы в этой области следующим образом: В то время меня интересовал не вопрос о том когда теория истиннаldquo; и не вопрос когда теория приемлема Я поставил перед собой другую проблему. Отсюда следовало что любая теория претендующая на то чтобы быть научной должна быть выводима из опыта. Любая развитая теория формулируется не для реальных а для идеальных объектов. Теория строится на базе предпосылок прямо противоречащих опыту.
79188. Проблематика генезиса техники и научного статуса технознания. Историко-философские проблемы развития науки и техники, типология основных подходов 46.5 KB
  Историкофилософские проблемы развития науки и техники типология основных подходов. В современной литературе по философии техники можно выделить следующие основные подходы к решению проблемы изменения соотношения науки и техники: 1 техника рассматривается как прикладная наука; 2 процессы развития науки и техники рассматриваются как автономные но скоординированные процессы; 3 наука развивалась ориентируясь на развитие технических аппаратов и инструментов; 4 техника науки во все времена обгоняла технику повседневной жизни;...
79189. Специфика технознания, философско-методологические аспекты соотношения с фундаментальной и прикладной наукой 34 KB
  Выявление специфики технических наук осуществляется обычно следующим образом: технические науки сопоставляются с естественными и общественными науками и параллельно рассматривается соотношение фундаментальных и прикладных исследований. При этом могут быть выделены следующие позиции: 1 технические науки отождествляются с прикладным естествознанием; 2 естественные и технические науки рассматриваются как равноправные научные дисциплины; 3 в технических науках выделяются как фундаментальные так и прикладные исследования. Технические науки...
79190. Техническая и научная рациональность в их соотношении. Типология рациональных обобщений в технознании, историческая эволюция и современные тенденции 54 KB
  Техническая и научная рациональность в их соотношении. Эффективность лишь самый общий признак рациональных действий и если сводить рациональность лишь к нему то можно впасть в ошибку слишком широкого определения. Рациональность это свойство выбора между альтернативами поведения человека: осмысление им окружающей действительности и последующие действия могут в большей или меньшей степени ей соответствовать. Рациональность категория мышления отражающая следование при достижении цели обусловленным эффективностью методологических нормам...
79191. Проблематика соотношения рационального и иррационального в технознании. Техника как артефакт 41.5 KB
  Именно здесь выступает контур грандиозной картины: как без внешних принуждений и насилия привести человека к хорошей и счастливой жизни в разреженном воздухе рациональности Отсюда вытекает дополнительный пункт при рассмотрении ошибки в дискурсе о рациональности. пища тоже; явления же первой природы интересуют нас или как сырье то есть опять как момент техники или как экологические условия параметры которых мы должны поддерживать для жизни человека а следовательно это тоже продукт нашей деятельности или как эстетический феномен...
79192. Проблема онтологического статуса техники. Абстракция и идеализация в технознании, особенности идеального объекта технической теории 31.5 KB
  Их следует отличать от объектов реальности. Реальные объекты представлены в эмпирическом познании в образе идеальных объектов обладающих жестко фиксированным и ограниченным набором признаков. Ни одна теория не строится без применения таких объектов. Идеализированные теоретические объекты в отличие от эмпирических объектов наделены не только теми признаками которые мы можем обнаружить в реальном взаимодействии объектов опыта но и признаками которых нет ни у одного реального объекта.
79193. Философско-методологические аспекты соотношения науки и техники. Методология технознания и проектирования в соотношении с научной методологией 17.83 KB
  Философскометодологические аспекты соотношения науки и техники. В современной литературе по философии техники можно выделить следующие основные подходы к решению проблемы изменения соотношения науки и техники: техника рассматривается как прикладная наука; процессы развития науки и техники рассматриваются как автономные но скоординированные процессы; наука развивалась ориентируясь на развитие технических аппаратов и инструментов; техника науки во все времена обгоняла технику повседневной жизни; до конца XIX в. Рассмотрение техники как...