Структурные автоматы

СОДЕРЖАНИЕ
 
Введение
1. Основные понятия.Канонический метод структурного синтеза автоматов. Теорема Глушкова оструктурной полноте
2. Основные этапы каноническогометода структурного синтеза
2.1 Кодирование алфавитов автомата
2.2 Выбор элементов памяти автомата
2.3 Выбор функционально-полнойсистемы логических элементов
2.4 Построение уравнений булевыхфункций возбуждения и выходов автомата
2.5 Построение функциональной схемыавтомата
3. Пример канонического методаструктурного синтеза
4. Элементы памяти
4.1 Элементы памяти с одниминформационным входом
4.2 Элементы памяти с двумяинформационными входами
4.3 Матрица переходов элемента памяти
5. Кодирование состояний и выходовавтомата и сложность
комбинационных схем
6. Обеспечение устойчивостифункционирования цифровых автоматов. Гонки в автоматах
6.1 Методы устранения гонок вавтоматах
Выводы
Литература

 
Введение
Тема курсовой работы «Структурныеавтоматы» по дисциплине «Прикладная теория управления автоматами».
Цельработы – рассмотреть: — основные понятия структурных автоматов; — канонический метод структурного синтеза автоматов; — теорему Глушкова о структурной полноте;— основныеэтапы канонического метода структурного синтеза;— примерыканонического метода структурного синтеза;— кодированиесостояний и выходов автомата и сложность комбинационных схем;— обеспечениеустойчивости функционирования цифровых автоматов;— гонкив автоматах;— методыустранения гонок в автоматах и др.
1. Основныепонятия. Канонический метод структурного синтеза автоматов. Теорема Глушкова оструктурной полноте
Вслед за этапом абстрактногосинтеза автоматов, заканчивающимся минимизацией числа состояний, следует этапструктурного синтеза, цепью которого является построение схемы, реализующейавтомат из логических элементов заданного типа.
Если абстрактный автоматбыл лишь математической моделью дискретной системы, то в структурном автоматеучитывается структура входных и выходных сигналов автомата, а также еговнутреннее устройство на уровне структурных схем. Структурным синтезомзанимается структурная теория автоматов, основной задачей которой являетсянахождение общих приемов построения структурных схем автоматов на основе композицииэлементарных автоматов, принадлежащих к заранее заданному конечному числутипов.
Под композициейэлементарных автоматов в общем случае понимается следующее.
Пусть заданы элементарныеавтоматы S1,...,Sk. Произведем объединение элементарных автоматов в систему совместноработающих автоматов. Введем в рассмотрение некоторое конечное множество узлов,называемых внешними входными и внешними выходными узлами. Эти узлы отличаютсяот узлов рассматриваемых элементарных автоматов, которые носят названиевнутренних. Композиция автомата состоит в том, что в полученной системеэлементарных автоматов S1,...,Sk и внешних узлов производитсяотождествление некоторых узлов (как внешних, так и внутренних). С точки зрениясовместной работы системы автоматов смысл операции отождествления узлов состоитв том, что элементарный сигнал, попадающий на один из узлов, входящих вмножество отождествляемых между собой узлов, попадает тем самым на все узлыэтого множества, После проведенных отождествлений узлов система автоматовпревращается в так называемую схему (сеть) автоматов. Будем считать, чтоавтоматы, входящие в схему автоматов, работают совместно, если в каждый моментавтоматного времени на все внешние входные узлы подается набор входных сигналов(структурный входной сигнал схемы) и со всех внешних выходных узлов снимаетсянабор выходных сигналов (структурный выходной сигнал).
В структурной теории как входные так ивыходные каналы считаются состоящими из элементарных входных (выходных)каналов. По всем элементарным входным (выходным) каналам могут передаватьсятолько элементарные сигналы.
/>
Рисунок 1- Структурныйавтомат
 
Набор возможных значенийсигналов, подаваемых на один внешний входной (выходной) узел, называетсяструктурным входным (выходным) алфавитом автомата. Алфавит должен бытьконечным.
Входной и выходной сигналызадаются конечными упорядоченными наборами элементарных сигналов, называемымивекторами, а составляющие их элементарные сигналы — компоненты векторов. Числокомпонентов вектора — это размерность алфавита.
Например, X={x1, x2, x3, x4, x5} — входной алфавит абстрактного автомата.
Структурный входнойалфавит, размерность которого равна трем:
X1=000, x2=001, x3=010, x4=011, x5= 100.
Векторное представлениевходных и выходных сигналов называется структурным входным выходным сигналом,соответственно.
Предполагается, что всевходящие в композицию автоматы имеют один и тот же структурный алфавит иработают в одном и том же автоматном времени. В настоящее время наиболеераспространенным структурным алфавитом является двоичный, что объясняетсяпростотой его представления в современных элементах и приборах. Кроме того, длядвоичного алфавита наиболее разработан аппарат булевых функций, позволяющийпроизводить многие операции над схемой формально. Поэтому в дальнейшем при решениизадач структурного синтеза автоматов будет использоваться в основном двоичный,структурный алфавит.
Предположим, что в каждыймомент автоматного времени структурный выходной сигнал схемы однозначноопределяется поступившей к этому времени конечной последовательностьюструктурных входных сигналов, начальными состояниями входящих в схему автоматови сделанными при построении схемы отождествлениями узлов. В этом случае построеннуюсхему будем рассматривать как некоторый автомат S, а саму схему назовем структурной схемой этого автомата.
Построенный таким образомавтомат S есть результат композиции элементарных автоматов S1,...,Sk. В отличие от абстрактного C-автомата, имеющего один входной и два выходных канала, на которыепоступают сигналы во входном и выходных алфавитах автомата, структурный автоматимеет входные и выходные каналы, на которых появляются сигналы в структурномалфавите автомата. В случае двоичного алфавита каждый входной и выходныесигналы абстрактного автомата могут быть закодированы векторами различной длинысоответственно, компоненты которых принимают два значения — нуль и единицу.
Наэтапе структурного синтеза предварительно выбираются элементарные автоматы, изкоторых затем путем их композиции строится структурная схема полученного наэтапе абстрактного синтеза автомата Мили, Мура или C-автомата.Если решение задачи структурного синтеза существует, говорят, что заданнаясистема автоматов структурно полна.
Внастоящее время нет сколько-нибудь эффективных методов (существенно болеепростых, чем метод перебора всех вариантов) решения основной задачиструктурного синтеза при любом наборе структурно полных систем элементарныхавтоматов. Поэтому обычно применяется так называемый канонический методструктурного синтеза, при котором используются элементарные автоматы некоторогоспециального вида: автоматы с памятью, имеющие более одного состояния, иавтоматы без памяти — с одним состоянием. Автоматы первого класса носятназвание элементов памяти, а автоматы второго класса — комбинационных илилогических элементов.
Теоретическим обоснованиемканонического метода структурного синтеза автоматов является доказанная втеорема о структурной полноте (теорема Глушкова):
Всякая система элементарныхавтоматов, которая содержит автомат Мура с нетривиальной памятью, обладающийполной системой переходов и полной системой выходов, и какую-либо функциональнополную систему логических элементов, является структурно полной.
Существует общийконструктивный прием (канонический метод структурного синтеза), позволяющий врассматриваемом случае свести задачу структурного синтеза произвольных автоматовк задаче синтеза комбинационных схем.
Результатом каноническогометода структурного синтеза является система логических уравнений, выражающаязависимость выходных сигналов автомата (функции выходов автомата) и сигналов,подаваемых на входы запоминающих элементов, от сигналов, приходящих на входвсего автомата в целом, и сигналов, снимаемых с выхода элементов памяти(функции возбуждения элементов памяти автомата). Эти уравнения называютсяканоническими.
Для правильной работысхем, очевидно, нельзя разрешать, чтобы сигналы на входе запоминающих элементовнепосредственно участвовали в образовании выходных сигналов, которые по цепямобратной связи подавались бы в тот же самый момент времени на эти входы. Всвязи с этим запоминающими элементами должны быть не автоматы Мили, а автоматыМура (см. уравнения функционирования этих автоматов).
Таким образом, структурнополная система элементарных автоматов должна содержать хотя бы один автоматМура. В то же время для синтеза любых автоматов с минимальным числом элементовпамяти необходимо в качестве таких элементов выбирать автоматы Мура, имеющиеполную систему переходов и полную систему выходов — так называемые полные автоматы.
Рассмотрим полнотуавтоматов памяти на примере автомата Мура. (табл. 1.) Полнота системы переходовозначает, что для любой пары состояний (am,…, аs) автомата найдется входной сигнал, переводящий первыйэлемент этой пары am вовторой — as т. е. в таком автомате в каждомстолбце таблицы переходов должны встречаться все состояния автомата. Полнотасистемы выходов автомата Мура состоит в том, что каждому состоянию автоматапоставлен в соответствие свой особый выходной сигнал, отличный от выходныхсигналов других состояний.Таблица 1. У
y1
y2
y3 A\X
x1
x2
x3
a1
a1
a2
a3
a2
a3
a1
a2
a3
a2
a3
a1
Очевидно,что в таком автомате число выходных сигналов равно числу состояний автомата.Вместе с предыдущим утверждением это приводит к тому, что в автомате Мура сполной системой выходов можно отождествить состояния автомата с его выходнымисигналами. В связи с этим в автоматах памяти мы будем использовать одни и те жеобозначения и для состояний, и для выходных сигналов, т. е. отмеченная таблицапереходов в автоматах Мура с полной системой выходов превращается просто втаблицу переходов. Автомат Мура в табл. 1. удовлетворяет условиям полнотысистемы переходов и выходов.
Наличие функциональнополной системы логических элементов позволяет реализовать булеву функцию любойстепени сложности.
После выбора элементовпамяти и кодирования состояний синтез структурного автомата сводится к синтезукомбинационной схемы, реализующей канонические уравнения.
Автомат памяти такжеможно рассматривать на абстрактном и структурном уровнях. Абстрактный автоматпамяти имеет один входной и один выходной каналы. При переходе от абстрактногоавтомата к структурному автомату входные и выходные сигналы должны бытьзакодированы соответствующими двоичными наборами.

 2. Основныеэтапы канонического метода структурного синтеза
В каноническом методе структурногосинтеза можно выделить несколько основных этапов:
1. Кодирование алфавитовавтомата.
2. Выбор элементовпамяти.
3. Выбор функциональнополной системы логических элементов.
4. Запись и минимизацияканонических уравнений.
5. Построение функциональной схемы автомата.
Исходными данными для начала работы данного методаявляются абстрактный цифровой автомат с памятью, заданный таблицей переходов ивыходов. Рассмотрим подробнее каждый из этапов канонического метода.2.1 Кодированиеалфавитов автомата
На структурном уровнекаждая буква входного алфавита x />Х, каждая буквавыходного алфавита y/>Y и каждая буква алфавита состояний а/>А кодируется двоичными векторами(двоичными наборами), число компонент которых определяется следующим образом:
Kвх >= int(log2|X|); Kвых >= int(log2|Y|); Kсост>=int(log2|A|);
где int — ближайшее большее целое число.
|Х|, |У|, |А| — мощностьалфавита входного, выходного и состояний, соответственно. Мощностью алфавитаназывается количество различных символов входящих в этот алфавит.
Процесс замены буква алфавита (X, У,А) абстрактного автомата двоичными векторами носит название кодирования иописывается таблицами кодирования. Таблица кодирования имеем следующий вид: влевой части перечисляются все символы абстрактного алфавита, а в правой — соответствующие им двоичные векторы.
Рассмотрим пример.
Абстрактный автомат Милизадан таблицей переходов и выходов (табл. 2.). Выполнить кодирование алфавитовавтомата.
Таблица2А\ Х
x1
x2
a1
a2/y1
a3/y3
a2
a1/y2
a2/y1
a3
a2/y2
a1/y1
Выпишем алфавиты автоматаи определим длины векторов кодов алфавитов:   
X={x1,x2};Kвх >= int(log2|2|)=1,
Y={y1,y2,y3};Kвых >= int(log2|3|)=2,
A={a1,a2,a3}; Kсост >= int(log2|3|)=2.
Заполнимтаблицы кодирования:
Таблица3
x1
x2 1
/>

Результирующая таблица — структурнаятаблица переходов и выходов автомата (табл. 6.) Получением структурной таблицыпереходов -выходов автомата заканчивается этап кодирования.
Таблица 6.А\ X 1 00 01/00 10/10 01 00/01 01/00 10 01/01 00/00
В общем случае, каждой кодируемойбукве может быть присвоен произвольный двоичный вектор, но обязательно дверазличные буквы одного алфавита должны кодироваться различными векторами. Коды,соответствующие символам различных алфавитов могут совпадать, в рассмотренномпримере — коды выходных сигналов и состояний.
На данном этапецелесообразно отметить, что способ кодирования состояний в значительной степениопределяют сложность реализации комбинационных схем. Существуют специальныеспособы кодирования, обеспечивающие получение экономичных схем. Они будутрассмотрены ниже. 2.2 Выбор элементов памяти автомата
Замена таблицы переходовавтомата на структурную таблицу переходов приводит к тому, что функцияпереходов (аi,xj) автомата становится векторной. Иными словами, аргументами такой функцииявляются все возможные пары двоичных векторов (ai,xj), а сама функция принимает значениеиз множества A двоичных векторов состоянийавтомата. В соответствии со структурной таблицей переходов автомата еговекторная функция переходов каждой паре двоичных векторов ставит в соответствиеопределенный двоичный вектор ak, что на абстрактном уровне определяется соотношением аk = (аi, хj).Из этого следует, что структурный автомат должен запоминать двоичный векторкаждого очередного состояния автомата, для чего служат элементы памяти(запоминающие элементы, триггеры).
При каноническом методеструктурного синтеза автоматов в качестве элементов памяти используются элементарныеавтоматы Мура с двумя состояниями, обладающие полной системой переходов ивыходов.
Полнота системы переходовавтомата в общем случае означает, что для любой пары состояний автоматасуществует входной сигнал, переводящий элементарный автомат из одного состоянияв другое. Таблица переходов элементарного автомата с полной системой переходовдолжна содержать в каждой своей строке все возможные состояния.
Полнота системы выходовозначает, что различным состояниям автомата соответствуют различные выходныесигналы. Обычно нулевому состоянию элементарного автомата соответствует нулевойвыходной сигнал, единичному — единичный.
Очевидно,что число элементов памяти структурного автомата равно числу компонент вектораего состояний. 2.3 Выбор функционально-полнойсистемы логических элементов
Функционирование структурногоавтомата во времени предполагает управление переключением каждого элементарногоавтомата его памяти в соответствии со структурной таблицей переходовсинтезируемого автомата. Последнее осуществляется с помощью специальнойкомбинационной схемы, подключаемой к информационным входам элементарногоавтомата памяти и реализующей булевы функции, управляющие его переключением.
Такие булевы функцииназываются функциями возбуждения элемента памяти и, в общем случае, различныхфункций возбуждения столько, сколько различных информационных входов имеется уэлементарных автоматов памяти в синтезируемом структурном автомате.
Функция возбуждениялюбого элемента памяти является произвольной булевой функцией и для еереализации комбинационной схемой необходимо использовать какую-либофункционально-полную систему логических элементов. Теоретическим фундаментомканонического метода структурного синтеза автоматов с памятью является теоремао структурной полноте, из которой следует, что для построения структурногоавтомата необходимо кроме элементов памяти иметь комбинационную схему,реализующую булевы функции возбуждения элементов памяти автомата, а длявыработки выходных сигналов структурного автомата — специальную комбинационнуюсхему формирования выходных сигналов автомата.
Функция возбужденияструктурного автомата является векторной. Ее аргументами являются пары двоичныхвекторов (аi, хj).- а значением функции — двоичныйвектор, каждая i-я компонента которого есть значение булевой функциивозбуждения i-го элемента памяти автомата, определяющая тот двоичный сигнал,который необходимо подать на вход i-го элемента памяти для обеспечения егопереключения в соответствии с требованиями структурной таблицы переходов.
Если векторная функцияпереходов задает переход из одного вектора состояния структурного автомата вдругой вектор состояния под воздействием двоичного вектора входного сигнала, товекторная функция возбуждения автомата задает двоичный вектор, который нужноподать на входы элементов памяти автомата, чтобы обеспечить требуемый переход(в соответствии с векторной функцией переходов автомата).
Последнее означает, чтопеременными, от которых зависит векторная функция возбуждения, являются те же переменные,что и для векторной функции переходов автомата, т. е. выходы всех элементовпамяти автомата и входы автомата. Поэтому структурный автомат Мура, в общемслучае, может быть представлен структурной схемой (рис. 2), а структурныйавтомат Мили — структурной схемой (рис. 3).
Буквами б1,…бц на рисунках обозначены выходы элементов памяти. Буквами ц1,…,цj обозначеныбулевы функции возбуждения элементов памяти. Для простоты положим, что каждыйэлемент памяти структурного автомата имеет один информационный вход. Буквами w1,...,wj обозначены выходные каналы автомата, где j — число выходных каналов автомата. Буквами z1,…,zm – входные каналы.2.4 Построениеуравнений булевых функций возбуждения и выходов автомата
Кодирование и выборсистемы элементов однозначно определяют комбинационную часть автомата: вначалестроится таблица истинности функций возбуждения элементов памяти автомата,получившая название таблицы функций возбуждения; канонические уравнения функцийвозбуждения выписываются исходя из построенной таблицы. Полученнаяаналитическая запись булевой функции возбуждения (для каждого элемента памятиавтомата) может быть минимизирована любым из известных методов. Исходными даннымидля построения таблицы функций возбуждения являются структурная таблицапереходов автомата и таблица переходов элемента памяти. Обрамление таблицыфункций возбуждения, т.е. идентификация ее строк и столбцов полностью совпадаетс обрамлением структурной таблицы переходов синтезируемого автомата. Клетки,расположенные внутри таблицы функций возбуждения, заполняются специальнымобразом.

/>
Рисунок 2- Структурная схема автомата Мура
/>
Рисунок 3- Структурнаясхема автомата Мили
Получение каноническихуравнений булевых функций выходов структурного автомата проще и может бытьсделано непосредственно по структурной таблице выходов автомата. Структурнаятаблица выходов автомата есть таблица истинности булевых функций выходовавтомата. Иными словами, уравнения булевых функций выходов автомата не зависятот типа используемых элементов памяти, однако зависят от их количества.
Если синтезируемыйавтомат является автоматом Мура, то задача построения уравнений булевых функцийвозбуждения решается так же. Уравнения булевых функций выходов автомата Милистроятся несколько иначе. Последнее связано с различиями в способах построенияструктурных таблиц выходов автомата Мили и Мура. После проведения этапакодирования состояний автомата и кодирования выходных сигналов получаемструктурную таблицу выходов автомата, которая является таблицей истинностибулевых функций выходов автомата.2.5 Построениефункциональной схемы автомата
На основании полученных выражений длябулевых функций возбуждения элементов памяти автомата и булевых функций выходовавтомата строятся комбинационная схема функций возбуждения и комбинационнаясхема формирования выходных сигналов автомата. Элементы памяти подключаются кпостроенным комбинационным схемам. Функциональная схема автомата Мура отличнатолько комбинационной схемой формирования выходных сигналов, которая строитсяна основании уравнений для булевых функций выходов. Отметим, что реализациякомбинационных схем может быть выполнена в любом функционально-полном базисе.

 3.  Пример канонического методаструктурного синтеза
Пусть задан абстрактныйавтомат Мили таблицей переходов и выходов (табл. 7.). Используя логическиеэлементы И, ИЛИ, НЕ и элементарный автомат Мура (элемент памяти), заданныйтабл. 8.
Таблица 7.А\ Х
x1
x2
x3
a1
a2/y3
a3/y4
a2/y2
a2 -
a1/y3
a3/y1
a3
a1/y2 -
a3/y3 А\ Х
x1
x2
x3
a1
a2/y3
a3/y4
a2/y2
a2 -
a1/y3
a3/y1
a3
a1/y2 -
a3/y3
Таблица 8
r1
r2
b1
b1
b2
b2
b2
b1
Выполним кодирование алфавитовавтомата (табл. 7.)
Выпишем алфавиты автомата и определимдлины векторов кодов алфавитов:
Х = {x1, x2,x3}; Kвх >= int(log2|3|)=2,
У = {y1, y2,y3, y4}; Kвых >= int(log2|3|)= 2,
А = {a1, a2, а3}; Kсост >= int(log2|3|)= 2.
Заполнимтаблицы кодирования (табл. 9 – 11):

Таблица9.Х
z1
z2
x1
x2 1
x3 1
Таблица10У
w1
w2
y1 1
y2
y3 1 1
y4 1
Таблица11А
1
2
a1
a2 1
a3 1 1
Каждый разряд вектора кода обозначим символомс соответствующим номером. Входные — z, выходные — w, состояния – а.
Таблица 12
z1z2
12 00 01 10 00 01/11 11/01 01/00 01 - 00/11 11/10 11 00/00 - 11/11
Врезультате получим таблицу переходов и выходов структурного автомата (табл. 12.).Выполним кодирование элементарного автомата Мура (табл. 8.):
— выпишем алфавиты автомата иопределим длины векторов кодов алфавитов,
R={r1,r2};Kвх >= int(log2|2|)=1,
В = {b1, b2};Kсост >= int(log2|2|)=1;
-заполнимтаблицы кодирования:
/>
Структурная таблица переходов элементарного автоматаМура имеет вид (табл. 15.):
Таккак абстрактный автомат имеет три состояния, каждое из которых кодируется двумяразрядами, то структурный автомат будет содержать два запоминающих элемента.
Теперь задача сводится к синтезукомбинационной схемы, реализующей канонические уравнения:
w1=l(a1,a2.z1,z2), w2= l(a1, a2, z1, z2) — функции выходов автомата
j1= f(a1,a2.z1,z2), j2= f(a1,a2.z1,z2) — функции возбуждения элементовпамяти автомата.
Функции w1, w2 можно получить непосредственно изотмеченной таблицы переходов структурного автомата как дизъюнкцию конъюнкций,соответствующих тем наборам (1,2.z1,z2), на которых эти функции принимают значения 1. Но болееудобно пользоваться так называемой таблицей формирования функций возбуждения ифункций выходов автомата, в которой в табличной форме задана система булевыхфункций (табл. 16). Заполним эту таблицу, используя коды соответствующихалфавитов и таблицу переходов и выходов абстрактного автомата. Для заполненияколонок j1, j2 необходимо воспользоваться еще и таблицей элемента памяти(табл. 15).
Для заполнения функций возбужденияэлементов памяти рассматривается переход из исходного состояния (12) в состояние перехода (12). За первый разряд 1 отвечает первый элемент памяти (его функция j1), за второй 2- второйэлемент памяти (его функция j2).
В таблице проставляется значениевходного сигнала, который обеспечивает соответствующий переход. Количество функцийвозбуждения элементов памяти автомата зависит от количества разрядов векторакода состояния и от количества информационных входов самого запоминающего элемента.Рассмотрим, например, что будет со структурным автоматом, если он находится всостоянии 01, и на его вход поступил сигнал 10.
Как видно из таблицы переходовструктурный автомат перейдет в состояние 11. Этот переход складывается из двухпереходов элементов памяти: 1-й из 0 в 1, 2-й из 1 в 1. По таблице 15 определимвходные сигналы элемента памяти, обеспечивающие эти переходы: это 0 и 1., ит.д. В клетку соответствующего перехода запишем вектор функции возбуждения,вызывающий данный переход.
Таблица16.Исходное состояние Входной сигнал Состояние перехода Функции возбуждения эл-в памяти Выходной сигнал
a1
a2
z1
z2
a1
a2
j1
j2
w1
w2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
/>
/>
/>
/>/>
По таблице 16 запишем аналитическиевыражения канонических уравнений:
/>
Z1      Z2
Рисунок4- Структурная схема автомата
Не занимаясь минимизациейканонический уравнений, построим схему электрическую функциональную (рис. 5).

 4. Элементыпамяти
В качестве элементов памятиструктурного автомата обычно используются триггеры. Как уже было сказано, сточки зрения прикладной теории цифровых автоматов, триггер — это элементарныйавтомат Мура, обладающий полной системой переходов и полной системой выходов.
Триггер характеризуется числоминформационных входов, внутренних состояний, числом выходных сигналов и т.д.выходные сигналы триггера отождествляются с его внутренними состояниями, именнопоэтому таблица переходов совпадает с таблицей выходов и триггер задаетсятолько одной из них (таблицей переходов). Как правило, триггер формирует какпрямой сигнал, так и инверсный.
Рассмотрим некоторые из этаповканонического метода более подробно, с применением специальных методов.
/>
Рисунок 5- Функциональная схемаавтомата 
 4.1 Элементы памяти с одниминформационным входом
Существует только 4 типа запоминающихэлементов с одним информационным входом, имеющих полную систему переходов ивыходов: D-триггер, Т-триггер, />-триггер, />-триггер. Таблицы их переходовпредставлены табл. 17 — 20. соответственно, а условные графические изображениятриггеров представлены на рис. 6. Входы D, T, />/> называются информационными.
Таблицы переходов триггеровсоставляются только для информационных входов. Остальные входы являютсявспомогательными. В частности, вход C — вход для подключения синхросерии (о чем будет сказано ниже). Каждый изтриггеров имеет два выхода. Появление единичного сигнала на выходе, помеченномна рисунках символом q,означает, что триггер находится в единичном состоянии. Появление единичногосигнала на выходе /> говорит о нулевом состоянии.
/>
/>
а)                         б)                в)                       г )
Рисунок 6- Условное графическоеобозначение триггеров:
а)D-триггер; б) Т-триггер; в) D-триггер; г) T-триггер

В таблицах переходов две первыеколонки одинаковые — в них перечислены все возможные комбинации входногосигнала и состояния элемента памяти. Для того, чтобы элементарный автомат имелполную систему переходов, колонку Q(t+1) следует заполнить таким образом,чтобы во второй и третьей колонках встречались все возможные типы переходов(00, 01, 10, 11). Для триггера типа D колонка Q(t+1) и Dсовпадают, т.к. выходной сигнал отождествляется с состоянием, то это означает,что данный элемент является элементом задержки на 1 такт. Его характеристическоеуравнение имеет вид:
Q(t+1)=d(Q(t), D(t))= DQ v D/> = D.
Триггер типа Т изменяет своесостояние только при подаче на его вход «1». Это триггер со счетным входом. Егохарактеристическое уравнение имеет вид:
Q(t+1 )=d(Q(t), Т(t))= />Q v T/>.4.2 Элементыпамяти с двумя информационными входами
Триггеры с двумя информационнымивходами имеют различное построение в зависимости от режимов использованияимеющихся входов. Основными, наиболее распространенными двухвходовымитриггерами являются RS-триггер, JK-триггер, синхронизированный D-триггер. Рассмотрим подробнее каждыйиз них.
RS-триггер
Название этого элемента происходит отанглийских слов «set-reset» — «установка-сброс». Он имеет дваустановочных входа: S -установка в 1, R — установка в ноль (сброс). Работаописывается таблицей переходов (табл. 21). На 6 и 7 наборах функция неопределена, т.к. считается, что нет необходимости устанавливать данный триггерв положение «1» и «О» одновременно. Таким образом, входная комбинация 11 для RS-триггераявляется запрещенной и не должна возникать в реальных условиях работы.
Характеристическое уравнение послеего преобразования и минимизации имеет вид:
Q(t+1 )=d(Q(t), R(t), S(t))= />Q v S.
Это соотношение показывает, что принулевом сигнале на входе «установка в ноль» (R=0) RS-триггер является дизъюнктором накапливающего типа. Оносуществляет логическое сложение содержимого триггера Q(t) и сигнала S(t), после чего результат операции записывается вместо первогослагаемого. В частном случае, при обнуленном триггере, осуществляется запись втриггер той информации, которая поступила на вход S. Условное графическоеобозначение RS-триггера представлено на рис. 7.а).
/>
/>
а)                         б)                         в)
Рисунок 7- Условное графическоеобозначение триггеров:
а) RS-триггер; б) JK-триггер; в)синхронизированный D-триггер.

 
J-K-триггер
Он имеет два установочных входа: J — установка в 1, К — установка в ноль. Работа описывается таблицей переходов(табл. 22). Для него не существует запрещенных наборов входных сигналов.
Характеристическое уравнение послеего преобразования и минимизации имеет вид:
Q(t+1)=d(Q(t), J(t), К (t)) = KQ v QJ.
Изэтого соотношения следует, что JK-триггерявляется универсальным, имеющим два режима работы.
1) Режим записи и храненияинформации, пришедшей по входу J,если триггер заранее был обнулен, поскольку работа обнуленного JK-триггера описывается уравнениемRS-триггера. Данный режим называется RS-режимом.
2) Режим счета, который возникает приобеспечении одинаковых сигналов на обоих входах. Поскольку такой режимописывается уравнением, аналогичным уравнению Т-триггера, то его можно назватьТ-режимом. Условное графическое обозначение JK-триггера представлено на рис. 7.б.
D-триггер
Триггер имеет также 2 входа:информационный (D) и синхронизирующий(С). Функция на выходе триггера принимает значение информационного сигнала,если есть разрешающий сигнал по входу C (С=1). При отсутствии разрешающего сигнала (С=0), значение функциизамораживается, т.е. остается равным содержимому триггера на предыдущем такте.Работа описывается таблицей переходов (табл. 23.).
Характеристическое уравнение триггераимеет вид:
Q(t+1 )=d(Q(t), D(t), С(t))= />Q v DC.

Из чего следует, что D-триггерявляется переключателем накапливающего типа: он пропускает на выход либосигнал, приходящий по условной шине D, либо сигнал, приходящий по условной шинеQ(t), в зависимости от значения управляющего сигнала С. Условноеграфическое обозначение триггера представлено на рис. 7.в.4.3 Матрицапереходов элемента памяти
Элемент памяти (триггер) может бытьзадан одним из нескольких способов: сокращенной таблицей переходов, полнойтаблицей переходов, характеристическим уравнением, матрицей переходов.Рассмотрим последний способ.
Для каждого из 4-х возможныхпереходов элементарного автомата (00, 01, 10, 11) всегда найдется значениевходного сигнала, равное 0 или 1, которое вызывает данный переход. Еслиэлементарный автомат имеет 2 или более входов, то на некоторые переходызначения входных сигналов, действующих на одном или другом входе, оказываютсянесущественными.
Количество строк матрицы всегда равно4 (по количеству возможных переходов), количество столбцов равно числу входныхсигналов. Элемент матрицы bisk представляет собой значение входного сигнала xk под действием которого элементарныйавтомат перейдет из состояния i всостояние s. При этом bisk всегда равняется 0 или 1, илинеопределен, если он не влияет на данный переход.
Матрица переходов элементарногоавтомата составляется по таблице переходов.
Рассмотрим пример построения матрицыпереходов триггера.
Пусть триггер, в общем случае, задансокращенной таблицей переходов (табл. 24.). Построить полную таблицу переходовтриггера и матрицу переходов.

/>
Полная таблица переходов триггера, построеннаяпо сокращенной, представлена в таблице 25. По полной таблице переходов запишемкомбинации входных сигналов, соответствующих всем возможным переходам (табл. 26.)Таким образом:
1. Для перехода «0-0» Х=0, Y может быть равен 0 или 1
2. Для перехода «0-1» Х=1, Y может быть равен 0 или 1
3. Для перехода «1-0» Хможет быть равен 0 или 1, а Y=0.
4.Для перехода «1-1» Х может быть равен 0 или 1, а Y=1.
Тогдаматрица переходов триггера запишется в виде:
0-0
b1 0-1 1
b2 1-0
b3 1-1
b4 1
где    b1,b2,b3,b4 — произвольные сигналы (0 или 1).
Как правило, значение двух различныхкоэффициентов bi, и bs из одной строки матрицы являютсязависимыми друг от друга и нахождение этой зависимости с ростом числаинформационных входов усложняется. Установление точной взаимозависимости междувходными переменными триггера является обязательным условием, обеспечивающимвозможность максимального упрощения схем с памятью. В основе методики лежиттаблица, в которой представлены возможные сочетания входных переменных и соответствующиеим описания (табл. 27.).
/>
С учетом доопределений входныхпеременных матрицы переходов некоторых стандартных триггеров имеют вид (таб. 28.)

Таблица 28.Матрицы переходовтриггеровТриггер-D Триггер-Т Триггер-RS Триггеp-JK Q(t) Q(t+1) D Q(t) Q(t+1) Т Q(t) Q(t+1) R S Q(t) Q(t+1) К J 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 

 5. Кодированиесостояний и выходов автомата и сложность комбинационных схем
Анализ канонического методаструктурного синтеза показал, что различные варианты кодирования состоянийавтомата приводят к различным выражениям для функций возбуждения и функцийвыходов.
В рассмотренном ранее примере кодысостояний автомата принимали значения: a1=00, a2=01, а3=11. Если принятькоды: a1=01, а2=01, а3=00, то таблицапереходов структурного автомата примет вид (табл. 29).
Если в качестве запоминающегоэлемента применить D-триггер, то таблица формирования функций возбуждения будетсовпадать с данной таблицей. Тогда функции примут вид:
Таблица 29 ZlZ2
a1a2 00 01 10 01 10 00 10 10 - 01 00 00 01 - 00
/>;
/>;
Если сравнить с предыдущимрезультатом, то нетрудно сделать вывод, что реализация этих выражений комбинационнойсхемой проще.
В данном случае при кодированиисостояний был использован весовой метод, который может быть использован и длякодирования выходных сигналов.
Алгоритм весового метода кодирования:
1. Каждому выходному сигналу у,ставится в соответствие целое число Pi, равное числу появлений сигнала уi в таблице выходов автомата.
2. Числа Pi сортируются по убыванию.
3. Выходной сигнал yi с наибольшим весом (Pi max) кодируются кодом, содержащим все 0(00...00).
4. Следующие L выходных сигналов (где L- число разрядов в двоичном векторе выходного сигнала) посписку убывания веса (см п. 2) кодируются кодами, содержащими одну 1 (00...01,00...10,… ,10...00).
5. Для кодирования следующих посписку убывания выходных сигналов используются все коды, содержащие двеединицы, затем три единицы и т.д., пока не будут закодированы все выходныесигналы.
В результате получаем такоекодирование, при котором чем чаще встречается выходной сигнал в таблицевыходов, тем меньше единиц содержится в его коде.
Кодирование внутренних состоянийдвоичными символами оказывает существенное влияние на стоимость комбинационнойчасти схемы автомата. Оптимальное кодирование даст минимальную стоимость,однако алгоритм эффективного кодирования неизвестен. Тем не менее, прикодировании внутренних состояний автомата используются различные эвристическиеалгоритмы, позволяющие, по крайней мере в некоторых случаях получить кодирование,близкое к оптимальному.
Д.А.Морозом предложен эвристический алгоритм кодирования внутренних состояний автоматов,основанный на минимизации суммарного числа изменений состояний элементов памятиавтомата на всех переходах автомата.
При таком критерии уменьшаетсясложность схем, реализующих дизъюнкции на входах элементов памяти, т.е.минимизируется комбинационная схема автомата. Для оценки кодирования вводитсякоэффициент эффективности кодирования:
Kэф= W/P;

где    Р — общее количество переходовавтомата,
W — весовая функция: W=tij
где    tij — расстояние Хэмминга между кодамисостояний аi и аj, равное числу элементов памяти,изменяющих свое состояние на данном переходе.
Отметим, что при определении весовойфункции суммирование производится по всем переходам автомата. Коэффициентэффективности позволяет оценить сложность комбинационной схемы автомата: чемменьше его значение, тем меньше сложность комбинационной схемы, и оптимальный вариант- Kэф=1.
Алгоритм состоит из следующих шагов:
1. Построить матрицу М, составленнуюиз всех пар номеров (ar, br) переходов автомата.
2. Переставить строки в матрице такимобразом, чтобы в каждой последующей строке содержался хотя бы один элемент изпредыдущих строк.
3. Закодируем состояния из первойстроки матрицы М следующим образом: Ka1=00...00,Kb1=00...01.
4. Вычеркнем из матрицы М первуюстроку с закодированными состояниями. Получим матрицу М'.
5. В начальной строке матрицы М'закодирован один элемент. Выберем из первой строки матрицы М' незакодированныйэлемент и обозначим его .
6. Построим матрицу M, выбрав из матрицы М' строки,содержащие у. Пусть В={1,2,...,f,...,F} — множество элементов из матрицы My, которые уже закодированы. Их кодыобозначим через К1, К2,.../>, Кf,..., КF соответственно.
7. Для каждого Кgf (f=1, 2,...,F)найдем C1gf— множество кодов, отстоящих от Кgf на расстояние Хэмминга, равное 1 иеще не занятых для кодирования состояний автомата. Построим множество />.
Если D1 =0, то строим новое множество />, где /> - множество кодов, у которыхкодовое расстояние с кодом Kf равно 2. Если и D2 =0, строим D3 и т.д., пока не найдем />. Пусть />.
8. Для каждого Кg находим wgf=|Kg — Kf|2 — расстояние Хэммингамежду Кg и всеми используемыми кодами Kf(f=1, 2, ...,F).
9. Находим />
10. Из /> выбираем К, у которого Wg=Wgmin. Элемент у кодируем кодом К.
11.Из матрицы М' вычеркиваем строки, в которых оба элемента закодированы, врезультате чего получаем новую матрицу, которую также обозначаем М’. Если вматрице М' не осталось ни одной строки, переходим к п. 12, иначе к п. 5.
12. Вычисляем функцию /> где tij=|Kj-Kj|2.
13. Конец.
Оценкой качества кодирования порассмотренному алгоритму может служить число K=W/P, где P — число переходов в автомате. Очевидно, что K>=1, причем, чем меньше значение K, тем лучше результат кодирования.
Рассмотрим пример кодированияавтомата, заданного таблицей переходов и выходов.

/>
1. Строим матрицу М:
Кодируем первую строку: K1=00;K2=01;
2. Вычеркиваем из матрицы М 1-юстроку (1-3) и 6-ю строку (3-1). Получаем матрицу М', в первой строке которойнезакодирован элемент 4. Обозначим =4 и запишем матрицу M,. В матрице M закодированы 1 и З: В={1,3}={00,01} /> Находим W:
W10=|00| |10|=3;            W11=|00| |11|=3;
|10|+|01|                         |11|+|01|
Выбираем K4=10.
Вычеркнем из М' строку (1-4). Получимновую матрицу М', в первой строке которой не закодирован элемент 2. Обозначим g=2 и запишем матрицу М2. Вматрице М2 закодированы элементы 3, 4:
Вg={3,4}={01,10} />

/>
Вычислим K=W/P=9/8=1,125.
 

 6.Обеспечение устойчивости функционирования цифровых автоматов. Гонки в автоматах
Одна из главных задач, решаемых наэтапе структурного синтеза синхронных цифровых автоматов с памятью, заключаетсяв обеспечении устойчивости их функционирования. Понятие устойчивости связано сразработкой такой принципиальной электрической схемы автомата, котораяобеспечивала бы его функционирование в соответствии с таблицей переходов ивыходов автомата.
Неправильное функционированиеавтомата (неустойчивая его работа) связано с особенностями физическойреализации логических элементов и элементов памяти его схемы, а такжеразличными величинами задержек распространения сигнала в элементах икомбинационных схемах.
Рассмотрим процесс обеспечения устойчивостифункционирования автомата более подробно. После поступления очередного входногосигнала и формирования сигналов возбуждения на входах элементов памяти автоматпереходит в новое состояние. При этом происходит формирование новых сигналоввозбуждения по цепям обратных связей (с выходов элементов памяти черезлогические элементы на входы элементов памяти), и автомат переходит в новоесостояние и т. д.
Таким образом, автомат, в общемслучае, не может остановиться в каком-то определенном состоянии и начинаетфункционировать в режиме генератора состояний. Для устранения такого эффектаиспользуют синхросерию — последовательность специальных (обычно прямоугольных)сигналов, подаваемых на входы элементов памяти и разрешающих поступление очередныхсигналов возбуждения на входы элементов памяти только с приходом очередногосинхросигнала. При отсутствии синхросигнала сигнал возбуждения не поступает навход элемента памяти, и элемент памяти цифрового автомата не переключается, т.е. остается в каком-то состоянии.
Практически подключение синхросерииосуществляется к специальным входам элемента памяти, обозначаемым символом C на рисунках и называемымсинхровходами. Введение синхросерии, однако, не обеспечит устойчивогофункционирования автомата, если не учитывать некоторые особенности. Если припереходе из одного состояния в другое должны изменять свои состояния сразунесколько элементов памяти, то между ними начинаютсясостязания. Тотэлемент, который выиграет состязания, по цепям обратной связи может изменитьсигналы на входах других элементов памяти до того, как они изменят своисостояния. Это может привести к переходу автомата в состояние, непредусмотренное графом.
Если в процессе перехода из состоянияаm в состояние аs под действием входного сигнала xi автомат может оказаться в некоторомпромежуточном состоянии (аi,аk) в зависимости от того, какой изэлементов памяти выиграл состязания, но, затем, при этом же входном сигналеперейдет в состояние аs,то такие состязания называются допустимыми, или не критическими. Но еслипроизойдет переход в состояние аk (не предусмотренное графом переходов автомата) иправильность работы автомата нарушается, то такие состязания называютсянедопустимыми (критическими) илигонками.Пусть автомат долженвыполнить переходы, изображенные на рис. 8.
/>
Рисунок 8
Возможны следующие ситуации:
а) если очередной синхросигнал навходы элементов памяти автомата поступает раньше, чем кончились переходныепроцессы в его комбинационной схеме возбуждения и элементах памяти послепоступления входного сигнала хi, то возможно неправильное формирование сигнала возбужденияна входе одного или нескольких элементов памяти автомата, т. е. автомат можетвместо перехода из состояния аm в состояние аs по входному сигналу xi осуществить ложный переход внекоторое состояние аtпо тому же самому входному сигналу xi;
б) еслидлительность входного сигнала хi превышаетдлительность перехода автомата из состояния аm в состояние аs, то автомат может (при поступлении очередногосинхросигнала) проскочить состояние аs и попасть сразу в состояние аk за счет двойного срабатыванияавтомата по входному сигналу хi. Иными словами, состояние аs может оказаться неустойчивым.6.1 Методыустранения гонок в автоматах
Для обеспечения устойчивогофункционирования автомата нужно разнести во времени момент подачи информации навходы его элементов памяти и момент снятия информации с выходов элементовпамяти. При таком разнесении формирование очередного сигнала возбуждения любогоэлемента памяти в момент появления синхросигнала осуществляется только по значениямсостояний элементов памяти в предшествующий момент времени, а переходныепроцессы в элементах памяти не влияют на формирование сигнала возбуждения(выходы элементов памяти отключены).
Естественно, что период следованиясинхросигналов при этом должен выбираться исходя из учета окончания переходныхпроцессов, связанных с задержками распространения входного для автомата сигналапо логическим элементам комбинационной схемы возбуждения. В результатеустойчивость функционирования цифрового автомата может быть обеспечена,например, использованием двухэтажной памяти. В этом случае каждый элементпамяти дублируется, и перепись информации из нижнего элемента памяти в верхнийосуществляется по отсутствию синхросигнала (рис. 9.).
Сигналы обратных связей, используемыедля формирования функций возбуждения, и сигналы выходов автомата снимаются свыходов элемента памяти верхнего яруса. При такой организации памяти автоматаотсутствует опасность формирования повторного сигнала возбуждения по одному итому же синхросигналу и перехода автомата в новое состояние. Последнее связанос тем, что переход в рабочее состояние автомата завершается после окончаниядействия синхросигнала.
Однако использование двойной памятиавтомата приводит к замедлению работы автомата. Если обычно периодсинхросигналов выбирается из расчета, что сигнал возбуждения элемента памятиуспеет пройти по самой длинной цепочке логических элементов и переключитьэлемент памяти, то здесь период нужно удлинить по крайней мере на 3t где t- задержка распространения сигнала в логическом элементе (1t- на инвертор и 2t- на второй элемент памяти).
В случаях, когда из соображенийбыстродействия двухэтажную память использовать нельзя, прибегают к многофазнойсистеме тактирования входных сигналов автомата. Так, для случая двухфазнойсинхронизации синхросериями CC1 и CC2 вместо одного входного сигналаxi, (рис. 8) используются два разных: хi • СС1 и xi • СС2 (рис. 10).
/>
Рисунок 9
/>
Рисунок 10
Таким способом устойчивостьфункционирования автомата обеспечивается автоматически. При двухфазнойсинхронизации необходимо, чтобы все дуги графа переходов автомата можно было быразметить символами CC1 иCC2 так, что для любой вершины графавсе выходящие из нее дуги отмечались бы символом одной синхросерии (например,СС1, а все дуги, заходящие в ту же вершину графа переходов автомата,— символомдругой синхросерии (например, СС2). Если граф переходов автомата содержитконтур нечетной длины, то такая разметка невозможна.
Однако ее можно сделать, преобразовавконтур нечетной длины в контур четной длины, добавив дополнительную вершину илисостояние автомата с пустым выходным сигналом. Задача преобразованияпроизвольного графа с нечетными контурами к графу с четными контурами решаетсяметодами теории графов, в частности с использованием понятия цикпоматическогочисла графа и метода построения матрицы фундаментальных циклов графа.
Кроме описанных выше случаев, устойчивостьфункционирования цифрового автомата с памятью может быть частично обеспечена спомощью специальных мер, принятых относительно устранения в схеме автоматаэффекта гонок. Это связано с тем, что элементы памяти имеют различные временасрабатывания. Различны также задержки сигналов возбуждения, поступающих навходы элементов памяти по цепочкам логических элементов различной длины.
Если при переходе автомата из одного состояния вдругое, должны переключиться сразу несколько элементов памяти, то между ниминачинаются гонки, (состязания), что может привести к неправильной работеавтомата. В самом деле, при переходе автомата из состояния ai;в состояние ajна некоторый, хотя и очень короткий, промежуток времени может возникнуть промежуточноесостояние автомата, отличное от ai и aj. Например, припереходе из ai (0110) в aj (1010) изменяют свое состояниедва первых элемента памяти. Из-за состязаний может возникнуть состояние 1110(или 0010), которое может привести к изменению состояния третьего иличетвертого элемента памяти.
В последнем случае после окончания переходныхпроцессов автомат уже не попадает в состояние aj. При использованиидвухэтажной памяти гонки в автомате не возникают, так как изменение состоянияавтомата происходит в то время, когда синхросигнал отсутствует.
Следует заметить, что современная элементная базавключает в себя элементы памяти с уже встроенной двухэтажной памятью (например,JK-триггер). Существует еще один способ устранения гонок в автоматах, связанныйсо специальным кодированием состояний автомата, которое называетсяпротивогоночным кодированием.
Частным случаем противогоночного кодированияявляется соседнее кодирование, при котором состояния автомата, связанные дугойна графе переходов, кодируются двоичными векторами, отличающимися друг от другатолько в одном разряде. Для проведения соседнего кодирования в графе переходовавтомата не должно быть контуров нечетной длины. Примеры графов переходов автоматов,состояния которых закодированы соседним образом, представлены на рис.
Отметим, что проблема состязаний инекоторые другие вопросы обеспечения устойчивости работы автоматов возниклилишь с появлением потенциальной элементной базы. Используемая ранее (в ЭВМвторого поколения) импульсно-потенциальная элементная база предусматривалаприменение статических триггеров со встроенной задержкой.
При этом величина задержки выбираласьбольшей длительности импульсного сигнала, поступающего на вход триггера. Темсамым переходные процессы формирования сигналов на выходах элементов памятиавтомата начинались лишь после окончания входного импульсного сигнала и, следовательно,не оказывали воздействие на входы этих же элементов памяти по цепям обратнойсвязи. Нечто подобное осуществляется теперь в потенциальной элементной базевведением не совпадающих во времени серий синхронизирующих сигналов, вособенности при организации двухэтажной памяти.
Вывод
 
В процессе выполнения курсовой работы мыознакомились с: — основными понятиями структурных автоматов; — каноническим методом структурного синтеза автоматов; — теоремой Глушкова о структурной полноте; — основными этапами канонического метода структурного синтеза; — примерами канонического метода структурного синтеза; — кодированием состояний и выходов автомата и сложностью комбинационных схем; — обеспечением устойчивости функционирования цифровых автоматов; — гонкой в автоматах; — методами устранения гонок в автоматах.

Литература
1.Самофалов К.Г., Романкевич А.М., и др. Прикладная теория цифровых автоматов. — Киев. “Вища школа” 1987.
2. Соловьев Г.Н. Арифметическиеустройства ЭВМ. — М. “Энергия”. 1978.
3. Савельев А.Я. Прикладная теорияцифровых автоматов — М. “Высшая школа”. 1987.
4. Каган Б.М. Электронныевычислительные машины и системы. — М. Энергоатомиздат. 1985.
5. Лысиков Б.Г. Арифметические илогические основы цифровых автоматов. — Минск. “Вышэйшая школа”. 1980.