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


 

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

71227. Измерение коэффициента трансформации трансформатора тока 25.7 KB
  У встроенных трансформаторов тока коэффициент трансформации проверяется на всех ответвлениях. В случае, когда ответвления встроенных трансформаторов тока не имеют маркировки или она недостаточно четка, необходимо проверить ее и маркировать на основании результатов...
71228. Изучение испытательных стендов и измерительных приборов 157.11 KB
  Для пуска электродвигателя и регулирования нагрузки реостат с пультом управления. На щетке приборов вмонтирован тахометр об термометр воды тв манометр масла м и циферблат цф показывает силу торможения испытываемого двигателя кг датчик тахометра соединен с карданным валом...
71229. Створення проекту у середовищі Visual Fox Pro 9.0. Проектування бази даних, таблиць у складі бази даних та вільних таблиць 71.72 KB
  Мета: Засвоїти методи створення баз даних. Вивчити типи полів таблиць. Хід роботи Створіть новий проект за допомогою майстра. Створено проект під назвою KompShop за допомогою майстра.
71230. Исследование битовых полей машинного кода с помощью дизассемблера 110.46 KB
  Например запись команды UBFX R1 R0 0 1 в дизассемблере будет выглядеть следующим образом 0100 а hexфайле 0001 Исследование назначения битовых полей машинного кода заданной команды. Задана команда UBFX. Возьмем для примера команду UBFX продублируем ее с разным размером извлекаемого...
71231. Создание и компиляция проекта в среде IAR. Написание простейшего модуля на языке Assembler 139.57 KB
  Целью данной работы является ознакомление с одной из популярнейших сред разработки программ для микроконтроллеров IAR Embedded Workbench IDE. Последовательность действий при создании проекта: Создадим новый проект Project=>Create New Project.
71232. Исследование влияния величины внешнего давления горной породы на крепь ствола обсадной колонны во временном интервале 37.27 KB
  Цель работы: Получение навыков работ с применением ЭВМ и расчетных программ при исследовании процессов взаимодействия крепи ствола обсадной колонны и горной породы во времени. Исходные данные: Внутренний радиус трубы м Внешний радиус трубы м Внешний радиус цементной оболочки...
71233. Исследование влияния факторов процесса установившейся циркуляции бурового раствора по трубам и затрубном пространстве на величину суммарных гидравлических потерь 98.47 KB
  Цель работы: Получение навыков работ с применением ЭВМ и расчетных программ при исследовании процессов движения жидкости по трубам и затрубном пространстве скважины. Исходные данные: Плотность, кг/м3 Динамическое напряжение сдвига, Па Пластическая вязкость...
71234. Исследование влияния оттока (протока) бурового раствора через стенку скважины на величину гидравлических потерь в затрубном пространстве скважины 44.06 KB
  Цель работы: Получение навыков работ с применением ЭВМ и расчетных программ при исследовании процессов движения жидкости по трубам и затрубном пространстве скважины с возможным оттоком и притоком бурового раствора. Исходные данные: Подача насосов м3 с Объемная проницаемость...
71235. Статистическая сводка и группировка 20.94 KB
  Цель работы: овладеть методикой проведения группировок для определения взаимосвязи изучаемых признаков и изучения состава однородной совокупности. Порядок выполнения работы Осуществить аналитическую группировку статистических данных для определения взаимосвязи...