Канонический метод структурного синтеза
Основной задачей структурной теории является задача построения композиций автоматов. Из элементарных автоматов (ЭА) строят более сложные автоматы.
Композиции могут быть последователь- ными, паралельными и смешаными. Число состояний автомата, получен- ного в результате композиции несколь- ких, равно произведению чисел состоя- ний этих автоматов.
Если из некоторого набора ЭА можно построить любой автомат, то набор структурно полон. Для произвольных структурно полных систем нет алгоритма построения ком- позиций (кроме перебора и проверки всех схем).
Для определенного класса ЭА есть канонический метод структурного синтеза. Метод оперирует с ЭА Мура, облада- ющими полнотой системы переходов и выходов, и комбинационными логичес- кими элементами.
Полнота переходов - возможность пере- хода от любого Si(t) к любому Si(t+1). Полнота выходов - взаимная однозначность Y = F(S). ( Любое S(t) можно «опознать» по Y(t). ) Обычно берутся ЭА Мура с двумя сос- тояниями.
Поведение ЭА Мура удобно описывать матрицами переходов. ЭА типа Д.
Неопределенность в таблице переходов означает непредсказуемость поведения ЭА. Неопределенность в матрице переходов означает возможность фиксации любого значения.
ЭА типа JK.
Матрицы переходов описывают функции возбуждения ЭА, задающие значения входов ЭА в такте t, которые обеспечивают переход ЭА к такту (t+1) из текущего состояния к требуемому.
Основная идея канонического метода структурного синтеза автоматов в сведении задачи к синтезу КС.
Этапы алгоритма 1. Кодирование входного, выходного и афавита состояний символами структур- ного алфавита.
Пример
2.Построение кодированных таблиц (функций) переходов и выходов. Представление кодированных функций таблицами, а не в другой форме, не обязательно, но удобно.
159
3. Построение функций возбуждения для ЭА. Полагаем, что тип каждого ЭА задан. Выбор типов ЭА, как и вариантов коди- рования алфавитов, здесь не рассматри- ваем.
Пример (продолжение). Предположим, что ЭА0 - типа Д, а ЭА1 - типа JK.
4. Построение схемы.
Имея функции выходов и возбужде- ния, можно построить реализующие их КС. Методы синтеза КС нам изве- стны. ЛЭ должны образовывать функ- ционально полный набор.
Пример (окончание).
Сложность построенной схемы в основ- ном определяется сложностью КС j и КС f. Оценить сложность этих КС мож- но по числу реализуемых функций и по числу их аргументов. (Для конкретных бф оценка может уточняться.)
Каноническая реализация автоматов Мили и Мура подобна и в общем случае имеет такой вид:
Автомат Мили:
Автомат Мура :
Популярное: Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (592)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |