Расширенный конечный автомат
![]() | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
В обычном конечном автомате переход связан с набором входных булевых условий и набором выходных булевых функций. В модели расширенного конечного автомата (EFSM) переход может быть выражен «оператором if », состоящим из набора триггерных условий . Если все условия триггера удовлетворены, запускается переход, переводящий машину из текущего состояния в следующее состояние и выполняющий указанные операции с данными .
Определение
[ редактировать ]EFSM определен [1] как 7-кортеж где
- S — набор символических состояний,
- I — набор входных символов,
- O — набор выходных символов,
- D — n-мерное линейное пространство. ,
- F – набор разрешающих функций ,
- U — набор функций обновления ,
- T – переходное отношение,
Структура
[ редактировать ]Архитектура EFSM. Модель EFSM состоит из следующих трех основных комбинационных блоков (и нескольких регистров).
- FSM-блок: обычный конечный автомат, реализующий графы переходов состояний модели EFSM.
- A-блок: арифметический блок для выполнения операции с данными, связанной с каждым переходом. Работа этого блока регулируется выходными сигналами блока FSM.
- E-блок: блок для оценки условий запуска, связанных с каждым переходом. Входными сигналами этого блока являются переменные данных, а выходными — набор двоичных сигналов, принимаемых на вход блоком FSM. Информация о избыточных вычислениях извлекается путем анализа взаимодействия между тремя основными блоками. Используя эту информацию, некоторые входные операнды арифметического блока и блока оценки могут быть заморожены посредством входного стробирования в определенных условиях времени выполнения, чтобы уменьшить ненужные переключения в проекте. На уровне архитектуры, если каждая оценка триггера и операция с данными рассматриваются как атомарное действие, то EFSM предполагает реализацию с практически минимальным энергопотреблением.
Циклическое поведение EFSM можно разделить на три этапа:
- В E-блоке оцените все условия запуска.
- В блоке FSM вычислите следующее состояние и сигналы, управляющие A-блоком.
- В A-блоке выполните необходимые операции с данными и перемещения данных.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Ченг, КТ; Кришнакумар, А.С. (1993). «Автоматическая генерация функциональных тестов с использованием расширенной модели конечного автомата». Международная конференция по автоматизации проектирования (DAC) . АКМ. стр. 86–91.