logo
кр одмита

7.4. Автомат с абстрактным состоянием. Булев автомат

Широко распространенным типом автомата является модель, описываемая одной многозначной внутренней переменной q и многими входными и выходными булевыми переменными х1, х2, … , хп и у1, у2, … , ут. Поведение такого автомата задается системой уравнений

q+ = х1, х2, … , хп; q;

y1 = 1х1, х2, … , хп; q;

y2 = 2х1, х2, … , хп; q;

…

ym = mх1, х2, … , хп; q,

более компактно представляемой в векторной форме

q+ = х, q;

y = х, q.

Функции  и  отличаются от введенных ранее  и  только тем, что многозначные входная и выходная переменные оказались замененными на соответствующие булевы векторы, но внутренняя переменная осталась многозначной.

Описанная модель называется автоматом с абстрактным состоянием. Ею удобно пользоваться на начальных этапах логического проектирования дискретных устройств, когда вход и выход устройства описываются как некоторые множества булевых переменных, имеющих конкретную техническую интерпретацию, в то время как множество внутренних переменных представляется пока в простейшей форме, в виде одной многозначной переменной q. Число значений переменной q полагается равным числу различных состояний автомата, при котором он может реализовать заданное функциональное отношение между входом и выходом.

Если заменить внутреннюю переменную qна соответствующий булев векторz  (z1, z2, … , zk), то получится система уравнений, в которой все переменные и все функции оказываются булевыми:

z1+ = 1х1, х2, … , хп; z1, z2, … , zk;

z2+ = 2х1, х2, … , хп; z1, z2, … , zk;

…

zk+ = kх1, х2, … , хп; z1, z2, … , zk;

y1 = 1х1, х2, … , хп; z1, z2, … , zk;

y2 = 2х1, х2, … , хп; z1, z2, … , zk;

…

ym = mх1, х2, … , хп; z1, z2, … , zk.

Эта модель называется булевым автоматом. Ее также можно представить в компактной векторной форме:

z+ = х, z;

y = х, z.

Булев автомат в определенном смысле ближе к реальным дискретным устройствам, поскольку его переменные непосредственно реализуются физическими переменными устройства, в частности, на типичных для современной техники элементах с двумя устойчивыми состояниями. Векторы х, у и z показывают структуру абстрактных символов а и b и состояния q. Приведенная выше система функций соответствует структуре, изображенной на рис. 7.2, где КС – комбинационная схема, реализующая приведенную выше систему, а П – блок памяти, осуществляющий задержку на период между соседними моментами времени.

Переменная zi представляет состояние i-го двоичного элемента памяти, а выражение

zi+ = iх1, х2, … , хп; z1, z2, … , zk

надо понимать так, что состояние i-го элемента памяти определяется значениями входных символов и состояниями элементов памяти в предыдущий момент времени.

х1  у1

х2  у2

… …

хп ут

z1  z1+

z2  z2+

… …

zk zk+

… …

Рис. 7.2. Структура булева автомата