СИНТЕЗ АВТОМАТОВ СТРУКТУРНЫЙ

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

Исходными данными для этапа С. а. с. являются инициальный автомат, заданный как шестерка и некоторый набор автоматов конечных (т. н. элементарных автоматов, или элементов). Задача заключается в том, чтобы реализовать автомат, т. е. его оператор автоматный в некоторой сети логической над заданным набором элементов. При этом состояния автомата необходимо представлять (кодировать) совокупностью состояний элементов, входящих в логическую сеть, а входные и выходные сигналы автомата , т. е. элементы множеств X и Y, — наборами входных и выходных сигналов элементов. Такие наборы наз. соответственно структурными состояниями (или кодами внутр. состояний), структурными входными и структурными выходными сигналами.

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

Элементарные автоматы разделяют на автоматы с памятью, т. е. автоматы, имеющие более одного состояния (запоминающие элементы), и автоматы без памяти (логические элементы ЦВМ). Минимальное число элементов с памятью, необходимое для реализации данного автомата, определяется числом его состояний N. Если элементы с памятью имеют максимум состояний, и то число элементов памяти должно быть по крайней мере п. Иногда по некоторым соображениям (напр., с целью уменьшения числа логич. элементов) число элементов с памятью выбирается большим, чем минимальное.

Обычно на практике структурный алфавит и алфавит состояний являются двоичными алфавитами. Логич. элементы в этом случае реализуют ф-ции алгебры логики, а запоминающие элементы наз. элементами задержки или различного рода триггерами (по аналогии с реальными электр. схемами, имеющими два устойчивых состояния). Когда набор элементов в своем составе имеет элементы, реализующие полную систему ф-ций алгебры логики, то в процессе структурного синтеза строятся канонические ур-ния, устанавливающие зависимость сигналов, подаваемых на входы запоминающих элементов, от выходных сигналов этих элементов и сигналов, подаваемых на вход всего автомата. Это делается следующим образом: пусть — элемент памяти с ф-цией переходов Выбирают необходимое число к экземпляров автомата В.

Различные внутр. состояния автомата отождествляют с различными наборами состояний запоминающих элементов. Этот процесс наз. кодированием состояний автомата и является неоднозначным. Способ кодирования выбирают, исходя из требований, налагаемых на структурную схему. Такими требованиями могут быть сложность схемы, отсутствие т. н. «гонок», определенный вид ф-ций возбуждений, который необходим для реализации схемы заранее выбранными логич. элементами. После кодирования состояния автомата будут обозначены -мерными векторами. Двуместная ф-цпя выходов автомата превратится в -местную, а ф-ция переходов заменяется системой к из (-одноместных ф-ций переходов в элементах памяти. Следующим шагом является построение ф-ций возбуждений элементов памяти. Значение каждой ф-ции при выбранном состоянии автомата и входном сигнале х определяется как входной сигнал элемента памяти, вызывающий переход в этом элементе, обусловленный ф-цией переходов. Ф-ции возбуждения, приравненные к определяемым ими входным сигналам дают канонические ур-ния для обратных связей в автомате . Затем следует этап логич. (комбинационного) синтеза, на котором требуется построить ф-ции возбуждений и. выходов из элементарных логич. ф-ций, реализуемых выбранными логич. элементами. См. также Автоматов синтез.

Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. е. 464—469]; Колдуэлл С. Логический синтез релейных устройств. Пер. с англ. М., 1962; Фистер М. Логическое проектирование цифровых вычислительных машин. Пер. с англ. К., 1964. Т. Н. Риздвянецкая.