- •Проектирование автоматов
- •Проектирование автоматов
- •5.7. Упражнения 90
- •Введение
- •1. Абстрактные автоматы
- •1.1. Эквивалентность автоматов
- •1.2. Минимизация автоматов
- •1.2.1. Минимизация полностью определенного автомата
- •1.2.2. Минимизация частичного автомата
- •1.3. Композиция автоматов
- •1.3.1. Параллельное соединение
- •1.3.2. Последовательное соединение
- •1.3.3. Соединение с обратной связью
- •1.3.4. Соединение в сеть
- •1.4 Декомпозиция автомата
- •1.4.1. Задача декомпозиции
- •1.4.2. Разбиения со свойствами подстановки
- •1.4.3. Метод декомпозиции
- •1.5. Упражнения Эквивалентность автоматов
- •Минимизация полностью определённого автомата.
- •Декомпозиция автоматов
- •2. Структурные автоматы
- •2.1. Автоматная полнота и теорема в.М.Глушкова
- •2.2. Гонки в автомате
- •2.2.1. Кодирование состояний
- •2.2.2. Понятие о гонках. Противогоночное кодирование
- •2.3. Проектирование автомата
- •2.4. Упражнение Кодирование
- •Синтез автомата
- •3. Синтез схем
- •3.1. Определения
- •3.2. Функциональная полнота базиса
- •3.2.1. Классы функций
- •3.2.2. Монотонные функции
- •3.2.3. Самодвойственные функции
- •3.2.4. Линейные функции
- •3.2.5. Функции, сохраняющие константу
- •3.2.6. Функциональная полнота
- •3.3. Топологические ограничения в схемах
- •3.3.1. Плоские схемы
- •3.3.2. Ограничения на глубину связи в схеме
- •3.4. Методы синтеза схем
- •3.4.1. Метод факторизации
- •3.4.2. Метод декомпозиции
- •3.4.3. Синтез схем в классическом базисе.
- •3.4.4. Синтез схем в монофункциональном базисе.
- •3.5. Упражнения Функциональная полнота
- •Синтез схем
- •4. Эксперименты над автоматами
- •4.1. Построение диагностических деревьев
- •4.2. Диагностические и установочные эксперименты
- •4.2.1. Дерево преемников
- •4.2.2. Диагностический эксперимент
- •4.2.3. Установочный эксперимент
- •4.3. Упражнения Диагностические эксперименты
- •Установочные эксперименты
- •5. Формальные грамматики
- •5.1. Языки и порождающие их грамматики
- •5.2. Примеры фрагментов описаний в языках программирования.
- •5.3. Порождающая грамматика
- •5.4. Классы языков и грамматик
- •5.5. Язык, понимаемый устройством
- •5.6. Автоматные языки
- •5.7. Упражнения
- •Библиографический список
- •Проектирование автоматов
- •620002, Екатеринбург, Мира, 19
2. Структурные автоматы
2.1. Автоматная полнота и теорема в.М.Глушкова
В структурном автомате входные и выходные переменные представляются не в абстрактном виде через символы алфавита, а в виде наборов значений сигналов на входных и выходных полюсах автомата. Как правило, эти сигналы принимают двоичные значения, обозначаемые как 0 и 1. Автомат имеет вид, показанный на рис.2.1.
Состоянию автомата сопоставляется совокупное состояние автоматов, называемых элементами памяти. Каждый из таких автоматов может находиться в одном из двух состояний, обозначаемые как 1 и 0. Тогда каждому состоянию автомата будет сопоставлен двоичный вектор состояний элементов памяти, и это сопоставление называют кодированием состояний.
Таким образом, структурный автомат представляется в виде композиции комбинационной (логической) схемы и элементов памяти, связанных со схемой, как показано на рис. 2.2. Входными переменными схемы являются входные переменные автомата - сигналы x1,x2, …,xn, и переменные t1, n2,…,tk, определяющие текущее состояние автомата, выходные переменные реализуются на выходах y1, y2,…, ym. Выходы схемы v1, v2,…,vk определяют переход автомата в следующее состояние.
Все переменные, приведенные на рис. 2.2, – двоичные, то есть принимают значение из множества {0,1}.
Переход от абстрактного автомата к структурному осуществляется через процедуру кодирования входов, выходов и состояний абстрактного автомата.
Кодирование входных переменных состоит в сопоставлении каждому символу входного алфавита абстрактного автомата набора значений двоичных переменных <x1, x2, …,xn> таким образом, чтобы каждый символ алфавита имел уникальный, отличный от других символов, вектор. Чтобы это можно было сделать, число n должно быть таким, чтобы выполнялось условие N2n, где N – число символов входного алфавита.
Точно также, кодировка M символов выходного алфавита требует, чтобы число m обеспечивало равенство M2m, а кодировка K символов алфавита состояний была связана с числом k равенством K2k.
Функции vj называются функциями возбуждения элементов памяти, и они должны переводить элементы памяти в состояния, соответствующие следующему состоянию автомата. Вид этих функций зависит от того, какие элементы памяти используются.
Из сказанного следует, что для того, чтобы построить структурный автомат, достаточно
иметь возможность по выходам элементов памяти однозначно определять текущее состояние автомата. Значит, элемент памяти должен быть автоматом Мура, выходные переменные которого совпадают с их состояниями. Говорят, что такие автоматы обладают полнотой выходов,
иметь возможность перевести элемент памяти из любого состояния в любое другое с помощью одного входного сигнала. Это значит, что в его таблице переходов в каждом столбце должны присутствовать все состояния. Говорят, что такие автоматы имеют полноту переходов.
Сформулируем всё сказанное в виде теоремы, определяющей, какие свойства должны быть у множества элементов, чтобы из них можно было построить любой автомат. В теореме нетривиальным назван автомат, имеющий более одного состояния. Функциональная полнота необходима для того, чтобы можно было построить схему, реализующую любые заданные функции (см. рис.2.2).
Теорема об автоматной полноте В.М.Глушкова.
Достаточными условиями автоматной полноты множества элементов является наличие в нём хотя бы одного нетривиального автомата, обладающего полнотой выходов и переходов, и множества логических элементов, обладающих функциональной полнотой.
Простейшими автоматами Мура, обладающими полнотой выходов и переходов, являются автоматы, представленные в табл.1 и табл.2. Они имеют два состояния, обозначенные как 0 и 1, два входных сигнала – z1 и z2. Выходные сигналы совпадают с состояниями и обозначаются так же, как 0 и 1.
Таблица 2.1 |
|
Таблица 2.2 |
||||
|
0 |
1 |
|
0 |
1 |
|
z1 |
0 |
0 |
z1 |
0 |
1 |
|
z2 |
1 |
1 |
z2 |
1 |
0 |
Первой таблице соответствует автомат, называемый триггером типа линия задержки, второй – счётный триггер.
В триггере типа линия задержки состояние автомата определяется только входным сигналом и не зависит от текущего состояния элемента: единичный входной сигнал устанавливает триггер в единичное состояние, нулевой сигнал – в нулевое состояние.
В счётном триггере при поступлении входного сигнала, равного нулю, элемент остаётся в том же состоянии, что и был. При единичном сигнале состояние элемента меняется с 0 на 1 и с 1 на 0.
При кодировке могут использоваться различные критерии: мини-мальная результирующая схема автомата, обеспечение правильного функционирования автомата во времени с учётом временных характеристик элементов схемы и другие.