Основные особенности теории синхронных автоматов

МЕЖДУНАРОДНЫЙ ИНСТИТУТ КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ

ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ И ЭНЕРГЕТИЧЕСКИХ СИСТЕМ

КАФЕДРА информатики и вычислительной техники 

ЗАДАНИЕ

На курсовой проект

по дисциплине " ТЕОРИЯ АВТОМАТОВ"

Тема проекта: "Синтез синхронного управляющего автомата"

 

Студент группы ВМо-072          Волокитина Надежда Александровна

                                                                 ^{фамилия, имя, отчество}

Номер варианта___ 9 – 2.14 ____________________________________

Технические условия: тип управляющего автомата – Мура; способ кодирования внутренних со­стоя­ний автомата –эффективный 2 способ; тип триггерных схем – комбинированные син­хронные двухтакт­ные RS - триггеры; элементная база логического преобразователя – двух­уровневая программи­руемая логиче­ская матрица; количество входных сигналов УА – 6; ко­личество выходных сигналов (микроопераций) УА – 7; количество микрокоманд УА – 10; количество микроопераций в каждой микрокоманде – 2..5; количество операторных вершин ГСА – 13; количество условных вершин ГСА – 8; разновидность УА – инициальный.

Содержание и объем проекта

расчетно - пояснительная записка – страниц формата А4, поясняющие текст, рисунки, рас­четы, таб­лицы, схема электрическаяфункциональная УА.

_

Задание принял студент гр. ВМо-072                                      / Н.А.Волокитина /

                                                   ^{подпись, дата                                      инициалы, фамилия}             

Руководитель                                                                              / C.H. Плотников   /

                                                   ^{подпись, дата                                      инициалы, фамилия}             

 

Замечания руководителя.

Содержание

ОСновная часть……………………………………………………………...….6

1. Основные особенности теории синхронных автоматов…….………..….…6

 2. Общие принципы построения и реализации синхронных

управляющих автоматов………………………………………..…..……...7

2.1 Обобщённая структура и принцип функционирования

           синхронных управляющих автоматов.……………….…..……..…........7

2.2 Последовательность синтеза синхронных управляющих

           автоматов………………………………………………………..…..…….8

2.3 Начальная формализация задачи синтеза УА……………..……….…9

3. Исходные данные для курсового проектирования…………….…..…......11

4. Автоматное описание управляющего автомата………………..…..……..12

5. Анализ граф _- схемы алгоритма синтезируемого управляющего

    автомата и детализация его структурной схемы. Исходные данные

    для курсового проектирования………………………….…..………..…......14

5.1 Анализ и разметка граф-схемы алгоритма…………..……..………..14

     5.2 Описание управляющего автомата с помощью таблиц переходов

и вы­ходов. …………………………………………….……………….15

6. Структурный синтез управляющего автомата со схемной

реализа­цией логики управления. ………………..………….…………....16

6.1 Тип элементов памяти. ………….…..…………………..…………...16

6.2 Структурное кодирование входных, выходных сигналов и

  состоя­ний автомата. ………….…..………..……………..…………..17

6.3 Детализация блока памяти…………………………………………...19

6.4 Составление расширенной структурной    таблицы       

       пере­ходов и выходов………………………………………………...20

6.5. Составление логических уравнений для выходных сигналов и

  функций возбуждения блока памяти ……………………………....21

6.6 Минимизация логических функций возбуждения и выходов….….22

7. Разработка и оформление схемы электрической функциональной

   синте­зиро­ванного синхронного управляющего автомата…………………23

ЗАКЛЮЧЕНИЕ……………………………………………………….……….……25

Литература………………………………………………………….………….26

 

Основные особенности теории синхронных автоматов

 

Математической моделью дискретного устройства является абстрактный ав­томат, определяемый как шестикомпонентный кортеж, или вектор [4 - 11]:

S = (Z, A,W, δ, λ, a₁), (1)

у которого:

Z={z₁,…z_f…z_F} - множество входных сигналов автомата (входной алфавит);

A={a₁,…a_m…a_M} - множество состояний автомата (алфавит состояний);

W={w₁,…w_g…w_G} – множество выходных сигналов автомата (выходной ал­фа­вит);

δ: A х Z ®  A – функция переходов автомата, реализующая отображение D_δ  A х Z на A.

Другими словами, функция δ некоторым парам состояние - входной сиг­нал (a_m, z_f) ставит в соответствие состояние автомата a_s = δ (a_m, z_f), a_s A;

λ: A х Z ®  W – функция выходов, реализующая отображение D_  A х Z на W, которая некоторым парам состояние - входной сигнал (a_m, z_f) ста­вит в соответствие выходной сигнал автомата w_g = λ (a_m, z_f);

a₁ A – начальное состояния автомата.

Под алфавитом здесь понимается непустое множество попарно различ­ных символов. Элементы алфавита называются буквами, а конечная упоря­дочен­ная последовательность букв - словом в данном алфавите.

Абстрактный автомат имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,… В каждый момент t дискретного времени автомат находится в не­ко­тором состоянии a(t) из множества состояний автомата, причем в началь­ный момент времени t(0) автомат может находиться в начальном состоянии a(0) = a₁. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе бу­кву входного алфавита z(t) Z. В соответствии с функцией выхо­дов он выдает в тот же момент времени t букву выходного алфавита      w(t) = λ (a(t)_, z(t)) и в соответствии с функцией переходов перейдет в сле­дующее состояние a(t +1)=δ (a(t)_, z(t)), причем a(t +1) A, а w(t) W. Смысл поня­тия абстрактного авто­мата состоит в том, что он реализует неко­торое отображе­ние множества слов входного алфавита Z в множество слов выход­ного алфа­вита W. Иначе, если на вход автомата, установленного в на­чальное состояние a₁, подавать буква за буквой некоторую последователь­ность букв входного алфавита z(0), z(1), z(2), … - входное слово, то на вы­ходе автомата будут по­следовательно появ­ляться буквы выходного алфавита w(0), w(1), w(2), … - выходное слово. Каж­дому входному слову соответст­вует опреде­ленное вы­ходное слово, структура которого определяется функ­циями пере­ходов и вы­ходов.

Таким образом, на уровне абстрактной теории понятие "работа автомата" понимается как преобразование входных слов в выходные слова. Структур­ной моделью нулевого уровня абстрактного автомата является модель, пред­став­лен­ная на рис. 1.

 

                              Z                               W

Рис. 1 Структурная модель абстрактного автомата

(нулевой уровень)

 

Чтобы задать конечный автомат S, необходимо описать все компоненты вектора S = (Z, A,W, δ, λ, a₁), т.е. входной и выходной алфавиты и алфавит со­стояний, а также функции переходов и выходов. Среди множества состоя­ний может быть выделено начальное состояния автомата a₁, в котором авто­мат на­ходится в момент t = 0. 

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

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

Надежную работу автомата легче обеспечить, если его выполнить в виде синхронного автомата, однако максимальным быстродействием обладают асин­хронные автоматы. В то же время основой всех синхронных автоматов явля­ются асинхронные автоматы.

 

2. Общие принципы построения и реализации синхронных управ­ляю­щих автоматов.

2.1 Обобщённая структура и принцип функционирования синхрон­ных управляющих автоматов.

 

Управляющий автомат (УА) генерирует последовательность управ­ляю­щих сигналов из множества у₁... у_m (сигналы у₁... у_m называются микроопе­рациями, каждый из сигналов может принимать только одно из значений 1 или 0), предписанную микропрограммой У; и соответствующую значениям логиче­ским условий х₁...х_n. При выполнении процессором пакета микропро­грамм на его входы последовательно подаются коды операции, ко­торые соот­ветствуют той или иной микропрограмме. На входы процессора

могут поступать внешние сигналы логических условий, а с выходов сни­маться сигналы для управления внешними устройствами.

Переход на новый шаг алгоритма осуществляется только с приходом спе­циального сигнала синхронизации (S).

Выходные сигналы у₁...у_m могут иметь различную длительность. Ма­те­ма­тической моделью управляющих автоматов, формирующих короткие вы­ходные сигналы, является модель Мили, а для автоматов, формирующих длинные вы­ходные сигналы - модель Мура.

 

     2.2 Последовательность синтеза синхронных управляющих автома­тов.

 

Синтезируемый УА на уровне «чёрного ящика» представим так, как пока­зано на рисунке 2.

 

Рис. 2.

В данном курсовом проекте синхронный управляющий автомат,

реализуется некоторым алгоритмом функционирования, который формально за­даётся таким начальным языком описания как граф - схема алгоритма (ГСА).

ГСА - это ориентированный связный граф, включающий вершины четырёх ти­пов: начальную, конечную, операторную и условную (рисунок 3). Конеч­ная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет. У начальной и операторной вершин по одному вы­ходу, у ус­ловной - два выхода, помеченных символами 1 и 0. конечная вер­шина выхо­дов не имеет.

 

ГСА удовлетворяет следующим условиям:

 

1) входы и выходы вершин соединяются друг с другом с помощью дуг, направленных всегда от выхода ко входу;

2) каждый выход соединён только с одним входом;

3) любой вход соединяется, по крайней мере, с одним выходом;

4) любая вершина ГСА лежит, по крайней мере, на одном пути из на­чаль­ной вершины к конечной;

5) в каждой условной вершине записывается один из элементов множе­ства Х={ х₁...х_n } логических условий (разрешается в различных ус­лов­ных вершинах запись одинаковых элементов множества Х);

6) один из выходов условной вершины, помеченный «0» или «1», мо­жет соединяться с её входом;

7) в каждой операторной вершине записывается оператор (микроко­манда) У; - подмножество множества микроопераций У={ у₁...у_m } (разрешается запись в различных операторных вершинах одинаковых микрокоманд).

 

а), б) - начальная и конечная вершины; в) - операторная вершина;

г) - условная вершина.

Рис. 3 Графическое представление вершин ГСА.

На первом этапе формализации алгоритм функционирования УА раз­би­ва­ется на ряд шагов, выполняемых последовательно. В процессе такого раз­биения выделяются все операции по выполнению алгоритма, а также ус­ловия выполне­ния этих операции на каждом конкретном шаге.

Выполняемые операции заносятся в операторные вершины ГСА, а ус­ло­вия перехода от одного оператора к другому - в условные вершины.

 

 2.3 Современная элементная база для реализации логических пре­обра­зо­вателей и блоков памяти управляющих автоматов.

 

Структура управляющего автомата во многом зависит от принципа его построения.

Принцип схемной логики (жёсткая логика) предусматривает реализа­цию множества состояний автомата блоком памяти (БП) на запоминающих элемен­тах (триггеры), а функции выходов и переходов формируются логиче­ским пре­образователем (ЛП). Алгоритм функционирования УА в этом случае пол­ностью определяется схемой соединения его элементов.

 

Рис. 4. Первый уровень структурной реализации УА.

 

ЛП представляет собой комбинационную схему. БП содержит r эле­мен­тов памяти, которыми для синхронных автоматов являются специально разра­ботан­ные синхронные элементарные автоматы с памятью, которые стали на­зывать триггерами.

Наибольшее распространение получили несколько разновидностей син­хронных триггеров, которые получили следующие наименования: RS - триг­гер, D - триггер, Т - триггер, JK - триггер. Отличаются данные триггеры коли­чест­вом информационных и управляющих сигналов, а также способами за­писи в них хранимой информации.

Блок памяти на своих выходах d₁..d_r должен формировать двоичный код, который соответствует номеру текущего шага алгоритма УА, или теку­щему внутреннему состоянию автомата. Предварительно все возможные внутренние состояния УА обозначаются некоторыми абстрактными симво­лами, которым затем ставятся в однозначное соответствие двоичные струк­турные коды. На входы блока памяти должны воздействовать сигналы f₁... f_r, которые форми­руются ЛП и в совокупности образуют двоичный код, со­ответ­ствующий струк­турному коду следующего внутреннего состояния УА. Сово­купность одновре­менно формируемых сигналов f₁... f_r принято назы­вать функцией возбуждения блока памяти, а каждый отдельный сигнал f₁... f_r - функциями возбуждения элементов памяти.

Задачей логического преобразователя является формирование выход­ных сиг­налов УА и функций возбуждения элементов памяти как некоторой сис­темы логических функций, аргументами которых являются переменные х₁,...х_n, d₁...d_r. Такую систему логических функций принято называть кано­ниче­скими логическими уравнениями УА, которые и должны реализоваться логи­ческим преобразователем.

В качестве элементного базиса для реализации ЛП выбрана двухуров­не­вая программируемая логическая матрица (ПЛМ). Это обусловлено тем, что в настоящее время ПЛМ являются весьма доступными, для широкого пользова­те­лей, высоко экономичными как для серийного, так и для разового производ­ства изделий вычислительной техники, ориентированы на реализа­цию сис­темы ло­гических функций, представленных в дизъюнктивных нор­мальных формах (ДНФ).

 Весьма существенным является также и то, что при использовании ПЛM в качестве элементного базиса для ЛП предоставляется возможность реализа­ции в рамках данного курсового проекта УА достаточной сложности при ком­пактном его графическом изображении в виде схемы электрической функцио­нальной.

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

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