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


 

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

48517. Средневековая, религиозно-христианская философия 53.04 KB
  Особенно Платоновское учение о сверхъестественных сущностях Аристотелевская концепция Бога как перводвиготеля всего сущего учение о форме как организующей силе и Аристотелевская концепция Логоса стоическая теория судьбы с предопределенностью Бытия человека. Вера в существование реальности Бессмертия Бога и при определенных условиях – вера в бессмертие человека. А поскольку человек неизбежно вступает в отношения с Богом то и познание человека его сущности и его души отыскание истинного пути человека к Богу также входит в предмет и...
48518. Финансовый учет. Конспект лекций 2.88 MB
  ФИНАНСОВЫЙ УЧЕТ Конспект лекции Утверждено на заседании кафедры БУХГАЛТЕРСКОГО УЧЕТА Протокол № 13 от 20. Утверждено на заседании кафедры бухгалтерского учета. Финансовый учет. Излагаются основные вопросы учета денежных и расчетных операций предприятий; текущих и долгосрочных обязательств; собственного капитала и обеспечения обязательств; основных средств и нематериальных активов; инвестиций и прямых необоротных активов; запасов; труда и его оплаты; расходов основной деятельности и калькулирования себестоимости продукции; прочих...
48519. Органічні сполуки 291.2 KB
  Хімічні властивості: реакція горіння. CH4 O2 = CO2 H2O; при нагріванні метану до 1000С без доступу кисню відбувається реакція розкладу. CH4 = C H2; метан реагує з хлором відбувається реакція галогенування. реакція нітрування – взаємодія з азотною кислотою.
48520. ЭКОЛОГИЧЕСКОЕ ПРАВО 31 KB
  Основные понятия окружающей природной среды и экологии. Механизм природопользования и охраны окружающей природной среды. Понятие механизма природопользования и охраны окружающей природной среды. Структура механизма природопользования и охраны окружающей природной среды.
48521. Экономика недвижимости 737 KB
  Для эффективного ведения бизнеса предприниматель должен хорошо разбираться в вопросах экономики недвижимости. Предметом экономики недвижимости как научной дисциплины является изучение теории и практики проведения операций с недвижимостью а также изучение организации и функционирования хозяйственного механизма в этой области деятельности. Учебная дисциплина Экономика недвижимости преследует следующие цели: 1.
48522. Стратегічний аналіз, його місце в управлінні економікою підприємства 479.5 KB
  Стратегічний аналіз його місце в управлінні економікою підприємства Зміст завдання і організація стратегічного аналізу Стратегічний аналіз це комплексне дослідження позитивних і негативних факторів які можуть вплинути на економічне становище підприємства в перспективі а також шляхів досягнення стратегічних цілей підприємства. За допомогою стратегічного аналізу готується комплексний стратегічний план розвитку підприємства здійснюється науково обґрунтована всебічна і своєчасна підтримка прийняття стратегічних управлінських рішень....
48523. СОВРЕМЕННЫЕ ПРОБЛЕМЫ ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ. КОНСПЕКТ ЛЕКЦИЙ 1.02 MB
  Способы представления знаний Численность населения на земном шаре 30 октября 2011 г. По данным Xerox 46 специальных знаний компаний не использующих систем управления знаниями заключены в документации разного рода. Для любой организации желающей преуспеть в сегодняшней глобальной информационной экономике необходима интеллектуальная исчерпывающая и простая в использовании система для управления знаниями а также система доступа к знаниям и система приобретения новых знаний. Тематика управления и представления знаний получает...
48524. ФИНАНСОВЫЙ РЫНОК 163.5 KB
  Понятие финансового рынка и его структура Финансовый рынок это совокупность экономических отношений связанных с распределением финансовых ресурсов куплейпродажей временно свободных денежных средств и ценных бумаг. Итак финансовый рынок это отношения между населением производителями и государством по поводу перераспределения свободных денежных средств на основе полной экономической самостоятельности механизма саморегуляции рыночной экономики внутрии межотраслевого движения финансовых ресурсов. Как экономическая категория...
48525. ОСНОВЫ ЭКОНОМЕТРИКИ 4.15 MB
  Эконометрические модели Оценивание неизвестных параметров модели: Верификация модели Прогноз на основе линейной модели