Что такое структурный автомат
Структурные автоматы
1. Основные понятия. Канонический метод структурного синтеза автоматов. Теорема Глушкова о структурной полноте
2. Основные этапы канонического метода структурного синтеза
2.1 Кодирование алфавитов автомата
2.2 Выбор элементов памяти автомата
2.3 Выбор функционально-полной системы логических элементов
2.4 Построение уравнений булевых функций возбуждения и выходов автомата
2.5 Построение функциональной схемы автомата
3. Пример канонического метода структурного синтеза
4.1 Элементы памяти с одним информационным входом
4.2 Элементы памяти с двумя информационными входами
4.3 Матрица переходов элемента памяти
5. Кодирование состояний и выходов автомата и сложность
6. Обеспечение устойчивости функционирования цифровых автоматов. Гонки в автоматах
6.1 Методы устранения гонок в автоматах
Тема курсовой работы «Структурные автоматы» по дисциплине «Прикладная теория управления автоматами».
— основные понятия структурных автоматов;
— канонический метод структурного синтеза автоматов;
— теорему Глушкова о структурной полноте;
— основные этапы канонического метода структурного синтеза;
— примеры канонического метода структурного синтеза;
— кодирование состояний и выходов автомата и сложность комбинационных схем;
— обеспечение устойчивости функционирования цифровых автоматов;
— гонки в автоматах;
— методы устранения гонок в автоматах и др.
1. Основные понятия. Канонический метод структурного синтеза автоматов. Теорема Глушкова о структурной полноте
Вслед за этапом абстрактного синтеза автоматов, заканчивающимся минимизацией числа состояний, следует этап структурного синтеза, цепью которого является построение схемы, реализующей автомат из логических элементов заданного типа.
Если абстрактный автомат был лишь математической моделью дискретной системы, то в структурном автомате учитывается структура входных и выходных сигналов автомата, а также его внутреннее устройство на уровне структурных схем. Структурным синтезом занимается структурная теория автоматов, основной задачей которой является нахождение общих приемов построения структурных схем автоматов на основе композиции элементарных автоматов, принадлежащих к заранее заданному конечному числу типов.
Под композицией элементарных автоматов в общем случае понимается следующее.
В структурной теории как входные так и выходные каналы считаются состоящими из элементарных входных (выходных) каналов. По всем элементарным входным (выходным) каналам могут передаваться только элементарные сигналы.
Рисунок 1- Структурный автомат
Набор возможных значений сигналов, подаваемых на один внешний входной (выходной) узел, называется структурным входным (выходным) алфавитом автомата. Алфавит должен быть конечным.
Структурный входной алфавит, размерность которого равна трем:
Векторное представление входных и выходных сигналов называется структурным входным выходным сигналом, соответственно.
Предполагается, что все входящие в композицию автоматы имеют один и тот же структурный алфавит и работают в одном и том же автоматном времени. В настоящее время наиболее распространенным структурным алфавитом является двоичный, что объясняется простотой его представления в современных элементах и приборах. Кроме того, для двоичного алфавита наиболее разработан аппарат булевых функций, позволяющий производить многие операции над схемой формально. Поэтому в дальнейшем при решении задач структурного синтеза автоматов будет использоваться в основном двоичный, структурный алфавит.
Предположим, что в каждый момент автоматного времени структурный выходной сигнал схемы однозначно определяется поступившей к этому времени конечной последовательностью структурных входных сигналов, начальными состояниями входящих в схему автоматов и сделанными при построении схемы отождествлениями узлов. В этом случае построенную схему будем рассматривать как некоторый автомат S, а саму схему назовем структурной схемой этого автомата.
На этапе структурного синтеза предварительно выбираются элементарные автоматы, из которых затем путем их композиции строится структурная схема полученного на этапе абстрактного синтеза автомата Мили, Мура или C-автомата. Если решение задачи структурного синтеза существует, говорят, что заданная система автоматов структурно полна.
Теоретическим обоснованием канонического метода структурного синтеза автоматов является доказанная в теорема о структурной полноте (теорема Глушкова):
Всякая система элементарных автоматов, которая содержит автомат Мура с нетривиальной памятью, обладающий полной системой переходов и полной системой выходов, и какую-либо функционально полную систему логических элементов, является структурно полной.
Существует общий конструктивный прием (канонический метод структурного синтеза), позволяющий в рассматриваемом случае свести задачу структурного синтеза произвольных автоматов к задаче синтеза комбинационных схем.
Результатом канонического метода структурного синтеза является система логических уравнений, выражающая зависимость выходных сигналов автомата (функции выходов автомата) и сигналов, подаваемых на входы запоминающих элементов, от сигналов, приходящих на вход всего автомата в целом, и сигналов, снимаемых с выхода элементов памяти (функции возбуждения элементов памяти автомата). Эти уравнения называютсяканоническими.
Для правильной работы схем, очевидно, нельзя разрешать, чтобы сигналы на входе запоминающих элементов непосредственно участвовали в образовании выходных сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы. В связи с этим запоминающими элементами должны быть не автоматы Мили, а автоматы Мура (см. уравнения функционирования этих автоматов).
Очевидно, что в таком автомате число выходных сигналов равно числу состояний автомата. Вместе с предыдущим утверждением это приводит к тому, что в автомате Мура с полной системой выходов можно отождествить состояния автомата с его выходными сигналами. В связи с этим в автоматах памяти мы будем использовать одни и те же обозначения и для состояний, и для выходных сигналов, т. е. отмеченная таблица переходов в автоматах Мура с полной системой выходов превращается просто в таблицу переходов. Автомат Мура в табл. 1. удовлетворяет условиям полноты системы переходов и выходов.
Наличие функционально полной системы логических элементов позволяет реализовать булеву функцию любой степени сложности.
После выбора элементов памяти и кодирования состояний синтез структурного автомата сводится к синтезу комбинационной схемы, реализующей канонические уравнения.
Автомат памяти также можно рассматривать на абстрактном и структурном уровнях. Абстрактный автомат памяти имеет один входной и один выходной каналы. При переходе от абстрактного автомата к структурному автомату входные и выходные сигналы должны быть закодированы соответствующими двоичными наборами.
2. Основные этапы канонического метода структурного синтеза
В каноническом методе структурного синтеза можно выделить несколько основных этапов:
1. Кодирование алфавитов автомата.
2. Выбор элементов памяти.
3. Выбор функционально полной системы логических элементов.
4. Запись и минимизация канонических уравнений.
5. Построение функциональной схемы автомата.
Исходными данными для начала работы данного метода являются абстрактный цифровой автомат с памятью, заданный таблицей переходов и выходов. Рассмотрим подробнее каждый из этапов канонического метода.
На структурном уровне каждая буква входного алфавита x 
Х, каждая буква выходного алфавита y Y и каждая буква алфавита состояний а А кодируется двоичными векторами (двоичными наборами), число компонент которых определяется следующим образом:
Абстрактный автомат Мили задан таблицей переходов и выходов (табл. 2.). Выполнить кодирование алфавитов автомата.
| А\ Х | x1 | x2 |
| a1 | a2 /y1 | a3 /y3 |
| a2 | a1 /y2 | a2 /y1 |
| a3 | a2 /y2 | a1 /y1 |
Выпишем алфавиты автомата и определим длины векторов кодов алфавитов:
Заполним таблицы кодирования:
Структурные автоматы
1. Основные понятия. Канонический метод структурного синтеза автоматов. Теорема Глушкова о структурной полноте
2. Основные этапы канонического метода структурного синтеза
2.1 Кодирование алфавитов автомата
2.2 Выбор элементов памяти автомата
2.3 Выбор функционально-полной системы логических элементов
2.4 Построение уравнений булевых функций возбуждения и выходов автомата
2.5 Построение функциональной схемы автомата
3. Пример канонического метода структурного синтеза
4.1 Элементы памяти с одним информационным входом
4.2 Элементы памяти с двумя информационными входами
4.3 Матрица переходов элемента памяти
5. Кодирование состояний и выходов автомата и сложность
6. Обеспечение устойчивости функционирования цифровых автоматов. Гонки в автоматах
6.1 Методы устранения гонок в автоматах
Тема курсовой работы «Структурные автоматы» по дисциплине «Прикладная теория управления автоматами».
Цель работы – рассмотреть:
Вслед за этапом абстрактного синтеза автоматов, заканчивающимся минимизацией числа состояний, следует этап структурного синтеза, цепью которого является построение схемы, реализующей автомат из логических элементов заданного типа.
Если абстрактный автомат был лишь математической моделью дискретной системы, то в структурном автомате учитывается структура входных и выходных сигналов автомата, а также его внутреннее устройство на уровне структурных схем. Структурным синтезом занимается структурная теория автоматов, основной задачей которой является нахождение общих приемов построения структурных схем автоматов на основе композиции элементарных автоматов, принадлежащих к заранее заданному конечному числу типов.
Под композицией элементарных автоматов в общем случае понимается следующее.
Пусть заданы элементарные автоматы S1. Sk. Произведем объединение элементарных автоматов в систему совместно работающих автоматов. Введем в рассмотрение некоторое конечное множество узлов, называемых внешними входными и внешними выходными узлами. Эти узлы отличаются от узлов рассматриваемых элементарных автоматов, которые носят название внутренних. Композиция автомата состоит в том, что в полученной системе элементарных автоматов S1. Sk и внешних узлов производится отождествление некоторых узлов (как внешних, так и внутренних). С точки зрения совместной работы системы автоматов смысл операции отождествления узлов состоит в том, что элементарный сигнал, попадающий на один из узлов, входящих в множество отождествляемых между собой узлов, попадает тем самым на все узлы этого множества, После проведенных отождествлений узлов система автоматов превращается в так называемую схему (сеть) автоматов. Будем считать, что автоматы, входящие в схему автоматов, работают совместно, если в каждый момент автоматного времени на все внешние входные узлы подается набор входных сигналов (структурный входной сигнал схемы) и со всех внешних выходных узлов снимается набор выходных сигналов (структурный выходной сигнал).
В структурной теории как входные так и выходные каналы считаются состоящими из элементарных входных (выходных) каналов. По всем элементарным входным (выходным) каналам могут передаваться только элементарные сигналы.
Рисунок 1- Структурный автомат
Набор возможных значений сигналов, подаваемых на один внешний входной (выходной) узел, называется структурным входным (выходным) алфавитом автомата. Алфавит должен быть конечным.
Структурный входной алфавит, размерность которого равна трем:
Векторное представление входных и выходных сигналов называется структурным входным выходным сигналом, соответственно.
Предполагается, что все входящие в композицию автоматы имеют один и тот же структурный алфавит и работают в одном и том же автоматном времени. В настоящее время наиболее распространенным структурным алфавитом является двоичный, что объясняется простотой его представления в современных элементах и приборах. Кроме того, для двоичного алфавита наиболее разработан аппарат булевых функций, позволяющий производить многие операции над схемой формально. Поэтому в дальнейшем при решении задач структурного синтеза автоматов будет использоваться в основном двоичный, структурный алфавит.
Предположим, что в каждый момент автоматного времени структурный выходной сигнал схемы однозначно определяется поступившей к этому времени конечной последовательностью структурных входных сигналов, начальными состояниями входящих в схему автоматов и сделанными при построении схемы отождествлениями узлов. В этом случае построенную схему будем рассматривать как некоторый автомат S, а саму схему назовем структурной схемой этого автомата.
На этапе структурного синтеза предварительно выбираются элементарные автоматы, из которых затем путем их композиции строится структурная схема полученного на этапе абстрактного синтеза автомата Мили, Мура или C-автомата. Если решение задачи структурного синтеза существует, говорят, что заданная система автоматов структурно полна.
Теоретическим обоснованием канонического метода структурного синтеза автоматов является доказанная в теорема о структурной полноте (теорема Глушкова):
Всякая система элементарных автоматов, которая содержит автомат Мура с нетривиальной памятью, обладающий полной системой переходов и полной системой выходов, и какую-либо функционально полную систему логических элементов, является структурно полной.
Существует общий конструктивный прием (канонический метод структурного синтеза), позволяющий в рассматриваемом случае свести задачу структурного синтеза произвольных автоматов к задаче синтеза комбинационных схем.
Результатом канонического метода структурного синтеза является система логических уравнений, выражающая зависимость выходных сигналов автомата (функции выходов автомата) и сигналов, подаваемых на входы запоминающих элементов, от сигналов, приходящих на вход всего автомата в целом, и сигналов, снимаемых с выхода элементов памяти (функции возбуждения элементов памяти автомата). Эти уравнения называются каноническими.
Для правильной работы схем, очевидно, нельзя разрешать, чтобы сигналы на входе запоминающих элементов непосредственно участвовали в образовании выходных сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы. В связи с этим запоминающими элементами должны быть не автоматы Мили, а автоматы Мура (см. уравнения функционирования этих автоматов).
Очевидно, что в таком автомате число выходных сигналов равно числу состояний автомата. Вместе с предыдущим утверждением это приводит к тому, что в автомате Мура с полной системой выходов можно отождествить состояния автомата с его выходными сигналами. В связи с этим в автоматах памяти мы будем использовать одни и те же обозначения и для состояний, и для выходных сигналов, т. е. отмеченная таблица переходов в автоматах Мура с полной системой выходов превращается просто в таблицу переходов. Автомат Мура в табл. 1. удовлетворяет условиям полноты системы переходов и выходов.
Наличие функционально полной системы логических элементов позволяет реализовать булеву функцию любой степени сложности.
После выбора элементов памяти и кодирования состояний синтез структурного автомата сводится к синтезу комбинационной схемы, реализующей канонические уравнения.
Автомат памяти также можно рассматривать на абстрактном и структурном уровнях. Абстрактный автомат памяти имеет один входной и один выходной каналы. При переходе от абстрактного автомата к структурному автомату входные и выходные сигналы должны быть закодированы соответствующими двоичными наборами.
2. Основные этапы канонического метода структурного синтеза
В каноническом методе структурного синтеза можно выделить несколько основных этапов:
1. Кодирование алфавитов автомата.
2. Выбор элементов памяти.
3. Выбор функционально полной системы логических элементов.
4. Запись и минимизация канонических уравнений.
5. Построение функциональной схемы автомата.
Исходными данными для начала работы данного метода являются абстрактный цифровой автомат с памятью, заданный таблицей переходов и выходов. Рассмотрим подробнее каждый из этапов канонического метода.
2.1 Кодирование алфавитов автомата
На структурном уровне каждая буква входного алфавита x 
Х, каждая буква выходного алфавита yY и каждая буква алфавита состояний аА кодируется двоичными векторами (двоичными наборами), число компонент которых определяется следующим образом:
Абстрактный автомат Мили задан таблицей переходов и выходов (табл. 2.). Выполнить кодирование алфавитов автомата.
Выпишем алфавиты автомата и определим длины векторов кодов алфавитов:
Заполним таблицы кодирования:
| А\ X | 0 | 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 Выбор функционально-полной системы логических элементов
Функционирование структурного автомата во времени предполагает управление переключением каждого элементарного автомата его памяти в соответствии со структурной таблицей переходов синтезируемого автомата. Последнее осуществляется с помощью специальной комбинационной схемы, подключаемой к информационным входам элементарного автомата памяти и реализующей булевы функции, управляющие его переключением.
Такие булевы функции называются функциями возбуждения элемента памяти и, в общем случае, различных функций возбуждения столько, сколько различных информационных входов имеется у элементарных автоматов памяти в синтезируемом структурном автомате.
Если векторная функция переходов задает переход из одного вектора состояния структурного автомата в другой вектор состояния под воздействием двоичного вектора входного сигнала, то векторная функция возбуждения автомата задает двоичный вектор, который нужно подать на входы элементов памяти автомата, чтобы обеспечить требуемый переход (в соответствии с векторной функцией переходов автомата).
2.4 Построение уравнений булевых функций возбуждения и выходов автомата
Кодирование и выбор системы элементов однозначно определяют комбинационную часть автомата: вначале строится таблица истинности функций возбуждения элементов памяти автомата, получившая название таблицы функций возбуждения; канонические уравнения функций возбуждения выписываются исходя из построенной таблицы. Полученная аналитическая запись булевой функции возбуждения (для каждого элемента памяти автомата) может быть минимизирована любым из известных методов. Исходными данными для построения таблицы функций возбуждения являются структурная таблица переходов автомата и таблица переходов элемента памяти. Обрамление таблицы функций возбуждения, т.е. идентификация ее строк и столбцов полностью совпадает с обрамлением структурной таблицы переходов синтезируемого автомата. Клетки, расположенные внутри таблицы функций возбуждения, заполняются специальным образом.
Рисунок 2- Структурная схема автомата Мура
Рисунок 3- Структурная схема автомата Мили
Получение канонических уравнений булевых функций выходов структурного автомата проще и может быть сделано непосредственно по структурной таблице выходов автомата. Структурная таблица выходов автомата есть таблица истинности булевых функций выходов автомата. Иными словами, уравнения булевых функций выходов автомата не зависят от типа используемых элементов памяти, однако зависят от их количества.
Если синтезируемый автомат является автоматом Мура, то задача построения уравнений булевых функций возбуждения решается так же. Уравнения булевых функций выходов автомата Мили строятся несколько иначе. Последнее связано с различиями в способах построения структурных таблиц выходов автомата Мили и Мура. После проведения этапа кодирования состояний автомата и кодирования выходных сигналов получаем структурную таблицу выходов автомата, которая является таблицей истинности булевых функций выходов автомата.
2.5 Построение функциональной схемы автомата
На основании полученных выражений для булевых функций возбуждения элементов памяти автомата и булевых функций выходов автомата строятся комбинационная схема функций возбуждения и комбинационная схема формирования выходных сигналов автомата. Элементы памяти подключаются к построенным комбинационным схемам. Функциональная схема автомата Мура отлична только комбинационной схемой формирования выходных сигналов, которая строится на основании уравнений для булевых функций выходов. Отметим, что реализация комбинационных схем может быть выполнена в любом функционально-полном базисе.
3. Пример канонического метода структурного синтеза
Пусть задан абстрактный автомат Мили таблицей переходов и выходов (табл. 7.). Используя логические элементы И, ИЛИ, НЕ и элементарный автомат Мура (элемент памяти), заданный табл. 8.