Расширенный конечный автомат

В обычном конечном автомате переход связан с набором входных булевых условий и набором выходных булевых функций. В модели расширенного конечного автомата (EFSM) переход может быть выражен «оператором if », состоящим из набора триггерных условий . Если все условия триггера удовлетворены, запускается переход, переводящий машину из текущего состояния в следующее состояние и выполняющий указанные операции с данными .

Определение

EFSM определен ^[1] как 7-кортеж $M=(I,O,S,D,F,U,T)$ где

S — набор символических состояний,
I — набор входных символов,
O — набор выходных символов,
D — n-мерное линейное пространство. $D_{1}\times \ldots \times D_{n}$ ,
F – набор разрешающих функций $f_{i}:D\rightarrow \{0,1\}$ ,
U — набор функций обновления $u_{i}:D\rightarrow D$ ,
T – переходное отношение, $T:S\times F\times I\rightarrow S\times U\times O$

Структура

Архитектура EFSM. Модель EFSM состоит из следующих трех основных комбинационных блоков (и нескольких регистров).

FSM-блок: обычный конечный автомат, реализующий графы переходов состояний модели EFSM.
A-блок: арифметический блок для выполнения операции с данными, связанной с каждым переходом. Работа этого блока регулируется выходными сигналами блока FSM.
E-блок: блок для оценки условий запуска, связанных с каждым переходом. Входными сигналами этого блока являются переменные данных, а выходными — набор двоичных сигналов, принимаемых на вход блоком FSM. Информация о избыточных вычислениях извлекается путем анализа взаимодействия между тремя основными блоками. Используя эту информацию, некоторые входные операнды арифметического блока и блока оценки могут быть заморожены посредством входного стробирования в определенных условиях времени выполнения, чтобы уменьшить ненужные переключения в проекте. На уровне архитектуры, если каждая оценка триггера и операция с данными рассматриваются как атомарное действие, то EFSM предполагает реализацию с практически минимальным энергопотреблением.

Циклическое поведение EFSM можно разделить на три этапа:

В E-блоке оцените все условия запуска.
В блоке FSM вычислите следующее состояние и сигналы, управляющие A-блоком.
В A-блоке выполните необходимые операции с данными и перемещения данных.

См. также

Абстрактная государственная машина

Ссылки

^ Ченг, КТ; Кришнакумар, А.С. (1993). «Автоматическая генерация функциональных тестов с использованием расширенной модели конечного автомата». Международная конференция по автоматизации проектирования (DAC) . АКМ. стр. 86–91.

[1] Ченг, КТ; Кришнакумар, А.С. (1993). «Автоматическая генерация функциональных тестов с использованием расширенной модели конечного автомата». Международная конференция по автоматизации проектирования (DAC) . АКМ. стр. 86–91.

[1]