6 Задача синтеза дискретного автомата с памятью

При решении задачи синтеза дискретного автомата различают несколько этапов [2].

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

Процесс преобразования информации реальным дискретным автоматом рассматривается как процесс преобразования входных последовательностей (входных слов) в выходные.

Результатом первого этапа синтеза является задание автомата одним и стандартных способов, например, в виде таблиц переходов и выходов или графа.

На втором этапе основная задача – определение объема памяти автомата минимально необходимого для его функционирования. Объем памяти автомата 𝒗 однозначно связан с числом внутренних состояний 𝒫: 𝒫 или 𝒗=, где символ ]x[ означает ближайшее целое, не меньшее x. Задача минимизации памяти автомата сводится к задаче минимизации числа его внутренних состояний. Это задача нахождения автомата, эквивалентного найденному на первом этапе, но имеющему вместе с тем наименьшее возможное число состояний. Результатом второго этапа синтеза является таблица переходов и выходов автомата, выполняющего поставленные условия работы и имеющего вместе с тем наименьшее возможное число внутренних состояний.

На третьем этапе синтеза ставится задача кодирования состояний входа и выхода теми элементарными двоичными сигналами, которые передаются по реальным входным и выходным каналам, а также кодирование внутренних состояний автомата (установление соответствия между внутренними состояниями автомата и состояниями его элементов памяти, число которых теперь уже известно).

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

Полученная таблица состояний служит исходной для четвертого этапа синтеза, на котором, используя методы минимизации и синтеза, известные для комбинационных дискретных автоматов, синтезируется комбинационная часть автомата в выбранной системе элементов.

На пятом этапе синтеза производится проверка работоспособности автомата и преобразование его структуры с целью обеспечения заданной надежности функционирования. Это связано с необходимостью учета всех возможных искажений сигналов, обусловленных используемыми элементами. В некоторых случаях может оказаться, что при данной структуре автомата нельзя подобрать параметры используемых элементов, обеспечивающих требуемое функционирование автомата. Тогда необходимо преобразовать и дополнить структуру так, чтобы гарантировать заданную надежность. Таким образом, этап надежностного синтеза включает электрический и временной расчеты элементов схемы. Заключительным этапом синтеза, шестым, являются размещение деталей на платах, составление монтажных схем и технической документации.