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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ





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



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



КАФЕДРА  вычислительные машины, системы, комплексы и сети













КУРСОВОЙ ПРОЕКТ



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



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



Расчетно – пояснительная записка

















Разработал студент      гр. ВМо-072                           /       Н.А.Волокитина       /

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

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

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



Нормоконтролер                                                         /                                          /

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



Защищен ________________          Оценка ___________________

                               дата

























ВОРОНЕЖ 2010

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



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



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





ЗАДАНИЕ

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

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





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

 

Студент группы ВМо-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, δ, λ, a1),   (1)

у которого:

Z={z1,…zf…zF} - множество входных сигналов автомата (входной алфавит);

A={a1,…am…aM} - множество состояний автомата (алфавит состояний);

W={w1,…wg…wG} – множество выходных сигналов автомата (выходной алфавит); 

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

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

λ : A х Z   W  –  функция выходов, реализующая отображение D  A х Z на W, которая некоторым парам состояние - входной сигнал (am, zf) ставит в соответствие выходной сигнал автомата wg = λ (am, zf);

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

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

Абстрактный автомат имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения  t = 0,1,2,… В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата, причем в начальный момент времени t(0) автомат может находиться в начальном состоянии a(0) = a1. В момент 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. Иначе, если на вход автомата, установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1), z(2), … - входное слово, то на выходе автомата будут последовательно появляться буквы выходного  алфавита w(0), w(1), w(2), … - выходное слово. Каждому входному слову соответствует определенное выходное слово, структура которого определяется функциями переходов и выходов. 

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





S

                                   Z                                    W

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

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



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

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

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

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



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



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



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

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

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

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



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



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





Рис. 2.

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

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

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



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



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

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

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

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

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

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

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





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

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

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

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

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



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



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

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





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



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

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

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

Задачей логического преобразователя является формирование выходных сигналов УА и функций возбуждения элементов памяти как некоторой системы логических функций, аргументами которых являются переменные х1, . . .хn, d1...dr. Такую систему логических функций принято называть каноническими логическими уравнениями УА, которые и должны реализоваться логическим преобразователем.

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

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

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

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



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



Задание на курсовое проектирование включает в себя следующие исходные данные:

•	Тип управляющего автомата - Мура;

•	Тип синхронных триггерных схем - RS - триггеры;

•	Способ структурного кодирования внутренних состояний управляющего автомата – 2 эффективный способ;

•	Граф - схема алгоритма функционирования управляющего автомата (рисунок 5);

•	Таблица микрокоманд управляющего автомата (таблица 1).





Рис. 5



























Таблица 1

Yi

микрооперации



y1

 y2

y3

y4

y5

y6

y7

Y1

0

0

0

1

1

0

1

Y2

0

1

0

0

0

1

0

Y3

0

1

0

0

1

1

0

Y4

1

0

0

0

1

0

0

Y5

0

1

1

1

0

1

0

Y6

1

0

1

0

0

0

1

Y7

1

1

1

1

0

0

1

Y8

0

1

0

1

1

1

1

Y9

0

1

1

0

0

0

0

Y10

1

0

0

0

0

1

0



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



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

Описание автомата на абстрактном уровне позволяет осуществить анализ его функционирования без учёта конкретно реализуемых функций и V

условии.

Самым важным на этом этапе является минимизация. Минимизация в широком смысле слова - такое преобразование логических функций, которое упрощает их в смысле заданного критерия, то есть - это построение абстрактного автомата, содержащего минимально возможное количество и

состоянии.

Так как функционирование абстрактного автомата в данном курсовом проекте описывается с помощью модели Мили, то необходимо выделить характерные черты данного управляющего автомата.



 Модель Мура.

Закон функционирования автомата типа Мура математически задается следующей системой уравнений (1):

		                               (1)

		где

a(t) – внутреннее состояние автомата в момент времени t (настоящий момент времени);

z (t) – входной сигнал в момент времени t;

w (t) – выходной сигнал в момент времени t;

a (t+1)  - внутреннее состояние автомата в момент времени (t+1)   (в следующий момент времени);

δ - функция переходов; 

λ - функция выходов.

Первое уравнение в (1) отражает тот факт, что переход автомата в следующее состояние a(t+1) осуществляется только с приходом входного сигнала (входного символа) z(t)  в момент времени t. При этом, то конкретное состояние,  в которое перейдет автомат в момент времени (t+1), определятся парой (am, zf), т.е. состоянием автомата a(t) и входным сигналом (символом) z(t) в момент времени t. Функция переходов в автомате типа Мура имеет такой же вид, как и для автомата типа Мили со всеми рассмотренными ранее особенностями математической и технической корректности модели.

		Второе уравнение в  (1) отражает закономерность формирования выходного сигнала (символа) автоматом типа Мура. Из уравнения видно, что выходной сигнал определяется только состоянием автомата в момент времени t и в явном виде не зависит от входного сигнала z(t). Соответствующий  состоянию a(t) выходной сигнал в автомате Мура  формируется  на всем протяжении времени, пока автомат находится в состоянии a(t). В связи с данной особенностью автомата типа Мура говорят, что данный тип автомата формирует "длинные" выходные сигналы, которые однозначно определяются тем состоянием автомата, в котором он находится в данный момент времени.

		Не смотря на то, что состояние выхода автомата Мура не зависит явно от состояния входа, его можно рассматривать как частный случай автоматов Мили. Действительно, так как для автоматов Мура справедливо

		

		a(t) = δ (a(t-1), z(t-1)),    (2)

		

		то справедливо и следующее соотношение:

		

		w(t) = λ (a(t)) = g (a(t-1), z(t-1)).  (3)

		

		Соотношение  (2) показывает, что в автомате Мура выходной сигнал реально зависит от входного сигнала, но только действующего в предыдущий момент времени. Различие между автоматами Мура и Мили состоит в том, что в автоматах Мили выходной сигнал возникает одновременно с вызывающим его входным сигналом, а в автоматах Мура - с опозданием (задержкой) на один такт автоматного времени. Поэтому автоматы Мура можно рассматривать как автоматы Мили, имея в виду, что последовательность состояний выхода автомата Мили опережает на один такт последовательность состояний выхода автомата Мура.

		В теории автоматов доказано, что между автоматами Мили и Мура существует взаимооднозначное соответствие: любой автомат Мили может быть преобразован в эквивалентный ему автомат Мура и наоборот.

		

23При переходе от автомата Мура к автомату Мили число состояний автомата не меняется, тогда как при обратном переходе число состояний в автомате Мура, как правило, возрастает. Таким образом, эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем в теории автоматов возникает задача нахождения минимального (с наименьшим числом состояний) автомата в классе эквивалентных между собой автоматов. 

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

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

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



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



Переход от алгоритмического описания к автоматному осуществляется путём разметки ГСА.



Правила разметки ГСА при реализации автомата по модели Мили:



1. символом начального состояния а1 отмечается вход вершины, следующей за начальной, а также вход конечной вершины ГСА;

2.  входы всех вершин, следующих за операторными, отмечаются различными символами а1. . . аi. . . аn;

2. входы вершин ГСА, следующих за операторными, должны быть отмечены одним единственным символом а;.



Указанные правила разметки сформулированы для однократно выполняемых алгоритмов, при этом конечное состояние УА отождествляется с начальным состоянием.

В данном курсовом проектировании используется инициальный автомат, то есть автомат, в котором до подачи синхронизирующих сигналов элементы блока памяти приводятся в определённые начальные состояния специальным сигналом начальной установки (НУ).

По приведённым выше правилам, произведём разметку заданной граф - схемы алгоритма (рисунок 6).

  







Рис. 6







В результате разметки ГСА определим множество внутренних 

состояний управляющего автомата: А= {а1...а11}, а также мощность этого множества: |A|=n=11.



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



По разметке ГСА (рисунок 6) составим прямую таблицу переходов и выходов.

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

Таблица содержит следующие переменные:

аm - состояние УА, из которого осуществляется переход за один такт автоматного времени;

аs - состояние УА, в которое осуществляется переход за один такт автоматного времени;

Х (am,aS) - логическое условие перехода из аm в аs;

	        Y (аm)     - микрокоманда (подмножество микроопераций), выполняемая автоматом в состоянии  аm  (для автомата типа Мура).

Каждая строка таблицы соответствует одному из путей перехода из одного состояния в другое, имеющемуся в ГСА.

Структура прямой таблицы переходов и выходов представлена таблицей 2.



Таблица 2

am, Y(am)

as

X(am, as )

а1, Y2 

а2

x1x2

а1, Y3

a4

х12

а1, Y8

a6

1

а2, Y4

а3

x4

а2, Y5

a5

x34

а2, Y8

а1

43x5x6

а2, Y7

a1

43x56

a2, Y6

a11

435

a3, Y8

a1

1

a4, Y5

a5

X3

a4, Y8

а1

3x5x6

a4, Y7

a1

3x56

a4, Y6

a11

35

a5, Y8

a1

1

a6, Y2

a7

x3

a6, Y3

a8

3

a7, Y4 

a9

1

a8, Y4

a9

x2

a8, Y5

a10

2

a9, Y6

a11

1

a10, Y6

a11

1

a11, Y7

a1

1





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



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



В данном курсовом проекте для синхронного УА со схемной логикой блок памяти строится на комбинированных синхронных двухтактных  D – триггерах(см. таблицу 3 и рис. 7.).

Триггер - это простейшее устройство с двумя устойчивыми состояниями, предназначенное для ввода, хранения и вывода одного бита информации в двоичных кодах.

Входы триггера и подаваемые на них сигналы делятся на информационные и вспомогательные. Информационные сигналы управляют состоянием триггера, которое определяется значением (0 или 1) сигнала на его основном Q- выходе. С другого Q - выхода снимается инверсный сигнал. При Q = 0 говорят, что триггер находится в нулевом состоянии или состоянии логического 0; при Q = 1 - в единичном состоянии или состоянии логической 1 Вспомогательные сигналы служат для предварительной установки триггера в начальное состояние.

Особенностью комбинированных триггерных схем является то, что наряду с наличием у них синхронно управляемых информационных входов, присутствуют также и входы асинхронной установки S и R триггеров в единичное “1”  и нулевое “0” состояния. Входы асинхронной установки триггеров обозначены на УГО отдельными от синхронных входов зонами. Входы асинхронной установки необходимы для приведения триггеров в некоторые исходные (начальные) состояния, которые в совокупности соответствуют начальному состоянию синтезируемого синхронного управляющего автомата. Сигнал, подаваемый на входы асинхронной установки триггеров для приведения их в начальные состояния, принято называть сигналом сброса (Reset) или начальной установки (Н.У.). Сигнал начальной установки должен воздействовать только на один из асинхронных входов (S или R) каждого триггера. Не задействованные для начальной установки входы триггеров должны быть подключены к дополнительному сигналу, который является постоянным и пассивным для данного типа триггера. 





Таблица 3

R1

S1

C

R

S 

Q



S1    TT      Q





S

C

R





R1              Q             Q+

0

0

0

*

*

0/1

0/1

0

0



0

0

0/1

0/1

0

0



0

1

0

1

0

0



0

1

1

1

0

0



1

0

0

0

0

0



1

0

1

0

0

0



1

1

0/1



Рис. 7 Комбинированный 

синхронный двухтактный

RS - триггер*

0

1

*

*

*

0/1

1

1

0

*

*

*

0/1

0

1

1

*

*

*

0/1

*



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



Единообразное представление всех абстрактных символов, необходимых для задания автомата, называют структурным кодированием входных, выходных сигналов и состоянии автомата.

В настоящее время самым распространённым способом структурного кодирования является двоичное кодирование. Структурное кодирование проводится в два этапа:

1. Определим количество β-двоичных разрядов, необходимое для двоичного представления некоторого множества абстрактных символов. Величина β находится из следующего соотношения:



  = 1 + int ( log2 (|А|-1)),       (4)                                            

 

где:  

 |А|   - мощность множества внутренних состояний УА;

 int ( ) - целая часть.

В пункте 6.1 было определено следующее множество внутренних состояний автомата А = {а1...а11} и мощность этого множества |А| = 11, тогда: 



 = 1 +int(1og2(11- 1))=4.



Так как алгоритм функционирования синтезируемого автомата задан в виде ГСА, то структурного кодирования входных и выходных сигналов производить не нужно. Это обусловлено тем, что при описании работы автомата в виде ГСА каждое логическое условие, и каждый выходной сигнал уже имеют двоичное кодирование.

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

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



a1=3

a2=5

a3=1

a4=4

a5=1

a6=2

a7=1

a8=2

a9=1

a10=1

a11=1















Таблица 4



d4

d3

d2

d1

а1

0

0

0

1

а2

0

0

1

0

a4

0

1

0

0

a6

1

0

0

0

a3

0

0

1

1

a7

0

1

0

1

a5

0

1

1

0

a8

1

1

0

0

a9

1

0

1

0

a10

1

1

1

0

a11

0

1

1

1







6.3  Составление   расширенной    структурной       таблицы           переходов и  выходов

Исходными данными для составления расширенных структурных таблиц переходов и выходов являются таблицы 2 и данные, полученные в результате структурного кодирования состояний автомата (таблица 4).  

Расширенные структурные таблицы переходов и выходов отличаются от таблицы 2  введением дополнительных граф, содержащих информацию о структурном коде состояния автомата в текущий момент времени К(аm), о структурном коде автомата в последующий момент времени К(аs), а также структурный код функции возбуждения блока памяти F(аm,аs), который должен формироваться логическим преобразователем для подготовки перехода автомата из состояния аm  в состояние  аs.

При использовании модифицированных комбинированных синхронных двухтактных D - триггеров функция возбуждения блока памяти находится на основании следующего уравнения:



F(аm , as) = К (as)	       (5)



Из уравнения (5) следует следующая система уравнений:



f1=d2()

f2=d2()

...

fr = dr ().



Для начала по таблице 1 определим микрооперации, выполняемые одновременно при реализации УА каждой из микрокоманд Уi. Полагается, что если микрооперация равна 1, то она выполняется в данной микрокоманде, а если равна 0, то не выполняется. Таким образом, содержимое таблицы 1 можно представить следующим образом:



Y1 = {y4,y5,y7};	

У2 = {y2,y6};

У3 = {y2,y5,y6};	

У4 = {y1,y5};

У5 = {y2,y3,y4,y6};

У6 = {y1,y3,y7};

У7 = {y1,y2,y3,y4,y7};

У8 = {y2,y4,y5,y6,y7};



Для автомата типа Мура структурная расширенная таблица переходов и выходов представлена таблицей 5. В данной таблице в графе У(аm) производится детализация микроопераций, составляющих микрокоманды У(аm), в соответствии с данными, представленными в таблице 1. В качестве структурных кодов используются коды, представленные в таблице 4.



Таблица 5.

am, Y(am)

К(am)

aS

К(as)

X(am, as)

F(am, as )



d4

d3

d2

d1



d4

d3

d2

d1



f4

f3

f2

f1

а1, y2,y6 

0

0

0

1

а2

0

0

1

0

x1x2

0

0

1

0



а1, y2,y5,y6

0

0

0

1

a4

0

1

0

0

х12

0

1

0

0



а1, y2,y4,y5,y6,y7

0

0

0

1

a6

1

0

0

0

1

1

0

0

0



а2, y1,y5

0

0

1

0

а3

0

0

1

1

x4

0

0

1

1



а2, y2,y3,y4,y6

0

0

1

0

a5

0

1

1

0

x34

0

1

1

0



а2, y2,y4,y5,y6,y7

0

0

1

0

а1

0

0

0

1

43x5x6

0

0

0

1



а2, y1,y2,y3,y4,y7

0

0

1

0

a1

0

0

0

1

43x56

0

0

0

1



a2, y1,y3,y7

0

0

1

0

a11

0

1

1

1

435

0

1

1

1



a3, y2,y4,y5,y6,y7

0

0

1

1

a1

0

0

0

1

1

0

0

0

1



a4, y2,y3,y4,y6

0

1

0

0

a5

0

1

1

0

x3

0

1

1

0



a4, y2,y4,y5,y6,y7

0

1

0

0

а1

0

0

0

1

3x5x6

0

0

0

1



a4, y1,y2,y3,y4,y7

0

1

0

0

a1

0

0

0

1

3x56

0

0

0

1



a4, y1,y3,y7

0

1

0

0

a11

0

1

1

1

35

0

1

1

1



a5, y2,y4,y5,y6,y7

0

1

1

0

a1

0

0

0

1

1

0

0

0

1



a6, y2,y6

1

0

0

0

a7

0

1

0

1

x3

0

1

0

1



a6, y2,y5,y6

1

0

0

0

a8

1

1

0

0

3

1

1

0

0



a7, y1,y5

0

1

0

1

a9

1

0

1

0

1

1

0

1

0



a8, y1,y5

1

1

0

0

a9

1

0

1

0

x2

1

0

1

0



a8, y2,y3,y4,y6

1

1

0

0

a10

1

1

1

0

2

1

1

1

0



a9, y1,y3,y7

1

0

1

0

a11

0

1

1

1

1

0

1

1

1



a10, y1,y3,y7

1

1

1

0

a11

0

1

1

1

1

0

1

1

1



a11, y1,y2,y3,y4,y7

0

1

1

1

a1

0

0

0

1

1

0

0

0

1





6.5. Составление логических уравнений для  выходных сигналов и функций возбуждения блока памяти  



Составление логических уравнений для функций возбуждения блока памяти F(аm,аs) сводится к составлению совокупности логических уравнений для каждой отдельной функции возбуждения элементов памяти (f1 …  fr). Логические уравнения записываются как дизъюнкция конъюнкций структурного кода исходного состояния автомата K(am) и комбинации входных сигналов X (аm,аs) по тем строкам таблицы 5, в которых в соответствующем столбце fi  присутствует значение, равное 1.

Для автомата типа Мура, представленного расширенной структурной таблицей 5, логические уравнения для функций возбуждения элементов памяти будут иметь следующий вид:



f1=  +  +  +  +  + 1+ + + + + + 



f2=  +  +  +  +  +  +  +  + + + 



f3= +  +  +  +  +  +  +  + 



f4= +  +  + + 



Для автомата типа Мура логические уравнения функций выходов (yi) формируется на основе графы am, Y (аm) соответствующей структурной таблицы (в данном случае таблицы 6.7). Функции выходов для автомата типа Мура представляют собой дизъюнкции только конъюнкций структурного кода исходного состояния автомата K( am) по тем строкам структурной таблицы, в которых присутствует выходной сигнал yi. Логические уравнения для функций выходов автомата типа Мура не содержат символов входных переменных. Логические уравнения составляются для всех выходных сигналов.

Функции выхода для автомата Мура будут иметь вид:



y1=  +  + 

y2=  +   +   +  +  +  + 

y3=  + 1 + 

y4=  +  +  + 

y5=  +  +  +  +  + 

y6=  +  +  + 

y7=   +   +  + 



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



При реализации системы логических функций на программируемой логической матрице наиболее эффективен метод групповой минимизации. 

Он состоит в следующем: в системе логических уравнений для функций возбуждения и функций выходов отыскиваются группы одинаковых элементарных конъюнкций. Для каждой группы вводится фиктивная переменная с каким - либо индексом. Далее все исходные логические уравнения переписываются в терминах фиктивных переменных. Затем на ПЛМ реализуют элементарные конъюнкции, соответствующие каждой фиктивной переменной и их дизъюнкции в соответствии с уравнениями, содержащими фиктивные переменные.

Введём для одинаковых конъюнкций фиктивные переменные z1 – z22.

Пусть:

z1 = 

z2 = 

z3 = 

z4 = 

z5 = 

z6 = 

z7 = 

z8 = 

z9 = 

z10 = 

z11 = 

z12 = 

z13 = 

z14 = 

z15 = 

z16 = 

z17 = 

z18 = 

z19 = 

z20 = 

z21 = 

z22 = 

z23 = 

z24 = 

z25 = 

z26 = 

z27 = 





Тогда функции возбуждения примут вид:



f1= z4 + z6 + z7 + z8 + z9 + z11+ z12+ z13+ z14+ z20+ z21+ z22

f2= z1+ z4 + z5 + z8 + z10 + z13 + z17 + z18 + z19+ z20+ z21

f3= z3+ z5 + z7 + z8 + z9 + z10 + z12 + z13 + z17

f4= z3+ z16 + z17 + z18+ z19



А функции выходов:



y1= z20 + z22 + z9

y2= z24 + z25  + z14  + z26 + z17 + z27 + z21

y3= z14 + z21 + z22

y4= z23 + z14 + z26 + z21

y5= z23 + z9 + z25 + z26 + z27 + z20

y6= z24 + z14 + z26 + z21

y7= z23  + z14  + z26 + z22





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



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

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

Схема электрическая функциональная управляющего автомата изображена на рисунке 8.











































































































Рис. 7













Как видно из рисунка 7, ПЛМ состоит из блока инверторов входных логических переменных (х1 ...х6) и двух матриц. Матрица И реализует на шинах z1...z22 элементарные конъюнкции с любым набором прямых и инверсных значений логических переменных х1 ...х6, а матрица ИЛИ реализует элементарные дизъюнкции с элементарными конъюнкциями, сформированными на шинах z1...z22. Матрицы И и ИЛИ представляют собой систему перпендикулярных проводников, в узлах пересечения которых располагаются полупроводниковые элементы, реализующие с резисторами нагрузки операции И и ИЛИ. Операция И реализуется при помощи диодов, а операция ИЛИ - при помощи триодов.