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

редактировать

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

Содержание

1 Определение
2 Структура
3 См. Также
4 Ссылки

Определение

EFSM определяется как 7-кортеж $M = ( I, O, S, D, F, U, T) {\ displaystyle M = (I, O, S, D, F, U, T)}$ $M = (I, O, S, D, F, U, T)$ где

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

Структура

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

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

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

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

См. также

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

Ссылки

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