37369

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

Курсовая

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

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

Русский

2013-09-24

701 KB

11 чел.

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


 

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

76316. Проблема коллатерального кровообращения и роль кафедры в ее разработке 28.98 KB
  Проблема коллатерального кровообращения и роль кафедры в ее разработке Коллатеральное кровообращениекк это процесс доставки крови по окольным путям кровотока в обход локальных нарушений проходимости магистральных сосудов. Основным источником развития коллатералей являются анастомозы сосудов.Вовлечение в окольный кровоток максимального колва сосудов до 5 суток 2. Стабилизация кк 28 мес Признаки сформировавшихся сосудовколлатералий: равномерное расширение просвета на протяжении всего анастомоза крупноволокнистая извилистость...
76317. Коллатерали — боковые или обходные пути кровотока 13.64 KB
  Для понимания коллатерального кровообращения необходимо знать те анастомозы которые соединяют между собой системы различных сосудов по которым устанавливается коллатеральный ток крови в случае их непроходимости. Анастомозы между ветвями крупных артериальных магистралей снабжаюших основные части тела аорта сонные артерии подключичные подвздошные артерии и др. Анастомозы между ветвями одной крупной артериальной магистрали ограничивающиеся пределами ее разветвления называются внутрисистемными. Не менее важны анастомозы между системами...
76318. Круги кровообращения. Особенности строения венозного русла печени 68.57 KB
  Большой круг кровообращения: Начало: левый желудочек сердца Аорта; оттуда кровь распространяется по всему телу. Верхняя и нижняя полая вены Правое предсердие Из правого предсердия кровь поступает в правый желудочек через трикуспидальный клапан откуда начинается малый круг кровообращения. Кровь поступает в желудочки; створки клапанов закрываются. Кровь проталкивается в аорту и лёгочный ствол.
76319. Особенности кровообращения у плода. Изменение кровообращения после рождения 51.86 KB
  Артериальная кровь к зародышу поступает из плаценты по пупочной вене в теле зародыша расположенной в серповидной связке печени. Плацентарная кровь поступает в нижнюю полую вену и смешивается с венозной кровью нижней половины тела плода. Эта смешанная кровь поступает в правое предсердие. По верхней полой вене к сердцу поступает венозная кровь от головы шеи и верхних конечностей.
76320. Микроциркуляторное русло, его звонья и особенности строения. Сосудистая сеть почки 6.22 KB
  Сосудистая сеть почки звенья микроциркуляторного русла: артериальное капиллярное 3венозное Артериальное звено представлено артериолами и прекапиллярами артериолы имеют 3 стенки: интимамедиа и адвентиция у прекапилляров в месте отхождения от артериол есть прекапиллярный сфинктер Капиллярное звено капилляры с непрерывной эндотелиальной выстилкой капилляры фенестрированныев почечном тельцеэндокринных органах слмзистой жктсосудистом сплетении мозга капилляры синусоидныев печениселезенкекостном мозе и коре надпочечников Венозное...
76321. Верхняя полая вена, ее корни, притоки, анастомозы с нижней полой и воротной венами 76.63 KB
  zygos Кавакавальные анастомозы 1на переднейстенке груднойи брюшной полостей анастомозируют v.cv inferior 2на боковой стенке грудной и брюшной полостей анастомозируют vv.lumbles 4венозные сплетения позвоночного столба plexus venosi vertebrlis interni в эпидуральной пространстве и plexus venosi vertebrlis externi расположенного на передней и задней поверхности позвоночного столба Портокавальные анастомозы 1на передней брюшной стенке анастомозируют v.prumbilicles 2в стенке прямой кишки анастомозируют v.