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

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

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

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

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

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

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

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

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

Разработал студент гр. ВМо-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

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

Математической моделью дискретного устройства является абстрактный ав­томат, определяемый как шестикомпонентный кортеж, или вектор [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 в качестве элементного базиса для ЛП предоставляется возможность реализа­ции в рамках данного курсового проекта УА достаточной сложности при ком­пактном его графическом изображении в виде схемы электрической функцио­нальной.

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

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

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

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

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

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

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

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

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

Рис. 5

Таблица 1

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), определятся парой (a_m, z_f ), т.е. состоянием автомата 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) показывает, что в автомате Мура выходной сигнал ре­ально зависит от входного сигнала, но только действующего в предыдущий момент времени. Различие между автоматами Мура и Мили состоит в том, что в автоматах Мили выходной сигнал возникает одновременно с вызывающим его входным сигналом, а в автоматах Мура - с опозданием (задержкой) на один такт автоматного времени. Поэтому автоматы Мура можно рассматри­вать как автоматы Мили, имея в виду, что последовательность состояний вы­хода автомата Мили опережает на один такт последовательность состояний выхода автомата Мура.

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

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

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

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

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

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

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

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

2. входы всех вершин, следующих за операторными, отмечаются раз­лич­ными символами а₁ . . . а_i . . . а_n ;

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

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

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

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

Рис. 6

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

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

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

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

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

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

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

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

Х (a_m ,a_S ) - логическое условие перехода из а_m в а_s ;

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

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

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

Таблица 2

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

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

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

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

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

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

Таблица 3

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

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

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

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

b = 1 + int ( log₂ (|А|-1)), (4)

где:

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

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

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

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

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

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

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

a₁ =3

a₂ =5

a₃ =1

a₄ =4

a₅ =1

a₆ =2

a₇ =1

a₈ =2

a₉ =1

a₁₀ =1

a₁₁ =1

Таблица 4

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

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

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

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

F(а_m , a_s ) = К (a_s ) (5)

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

f₁ =d₂ ()

f₂ =d₂ ()

...

f_r = d_r ().

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

Y₁ = {y_4, y_5, y₇ };

У₂ = {y_2, y₆ };

У₃ = {y_2, y_5, y₆ };

У₄ = {y_1, y₅ };

У₅ = {y_2, y_3, y_4, y₆ };

У₆ = {y_1, y_3, y₇ };

У₇ = {y_1, y_2, y_3, y_4, y₇ };

У₈ = {y_2, y_4, y_5, y_6, y₇ };

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

Таблица 5.

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

Составление логических уравнений для функций возбуждения блока па­мяти F(а_m ,а_s ) сводится к составлению совокупности логических уравнений для каждой отдельной функции возбуждения элементов памяти (f₁ … f_r ). Логиче­ские уравнения записываются как дизъюнкция конъюнкций структурного кода исходного состояния автомата K(a_m ) и комбинации входных сигналов X (а_m ,а_s ) по тем строкам таблицы 5, в которых в соответствующем столбце f_i присутст­вует значение, равное 1.

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

f₁ = + + + + + ₁ + + + + + +

f₂ = + + + + + + + + + +

f₃ = + + + + + + + +

f₄ = + + + +

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

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

y₁ = + +

y₂ = + + + + + +

y₃ = + ₁ +

y₄ = + + +

y₅ = + + + + +

y₆ = + + +

y₇ = + + +

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

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

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

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

Пусть:

z₁ =

z₂ =

z₃ =

z₄ =

z₅ =

z₆ =

z₇ =

z₈ =

z₉ =

z₁₀ =

z₁₁ =

z₁₂ =

z₁₃ =

z₁₄ =

z₁₅ =

z₁₆ =

z₁₇ =

z₁₈ =

z₁₉ =

z₂₀ =

z₂₁ =

z₂₂ =

z₂₃ =

z₂₄ =

z₂₅ =

z₂₆ =

z₂₇ =

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

f₁ = z₄ + z₆ + z₇ + z₈ + z₉ + z₁₁ + z₁₂ + z₁₃ + z₁₄ + z₂₀ + z₂₁ + z₂₂

f₂ = z₁ + z₄ + z₅ + z₈ + z₁₀ + z₁₃ + z₁₇ + z₁₈ + z₁₉ + z₂₀ + z₂₁

f₃ = z₃ + z₅ + z₇ + z₈ + z₉ + z₁₀ + z₁₂ + z₁₃ + z₁₇

f₄ = z₃ + z₁₆ + z₁₇ + z₁₈ + z₁₉

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

y₁ = z₂₀ + z₂₂ + z₉

y₂ = z₂₄ + z₂₅ + z₁₄ + z₂₆ + z₁₇ + z₂₇ + z₂₁

y₃ = z₁₄ + z₂₁ + z₂₂

y₄ = z₂₃ + z₁₄ + z₂₆ + z₂₁

y₅ = z₂₃ + z₉ + z₂₅ + z₂₆ + z₂₇ + z₂₀

y₆ = z₂₄ + z₁₄ + z₂₆ + z₂₁

y₇ = z₂₃ + z₁₄ + z₂₆ + z₂₂

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

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

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

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

Рис. 7

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