Файл: Баранов, С. И. Синтез микропрограммных автоматов.pdf

ложений оказывается удобным использовать одновременно сигналы обоих типов. Так, при проектировании ЦВМ часть сигналов устрой­ ства управления, таких, как передача из одного регистра в другой, наращивание счетчиков и т. п., по длительности совпадает с входным сигналом, тактированным синхроимпульсом, тогда как, например, сигналы подачи иа комбинационный сумматор или дешифратор памяти обычно значительно длиннее и определяются временами срабатывания сумматора и дешифратора. Эти сигналы удобно отождествлять с со­ стояниями. Таким образом, соображения практического характера приводят к целесообразности рассмотрения С-автомата — совмещен­ ной модели автоматов Мили и Мура.

Для задания С-автоматов будем также использовать табличный и

таблицами 1-19 и 1-20.

Нетрудно показать, что к полностью Определенному С-автомату можно приме­ нить алгоритм минимизации Ауфенкампа— Хона, если под одноэквивалентными по­ нимать состояния, которые одинаково

отмечены и имеют одинаковые столбцы в таблице выходов. Проводя последовательность разбиений на 1-, 2-, . . . , /г-, k -j- 1-эквивалент- ные классы до совпадения разбиений jrft , и nk, получим разбиение

множества состояний на эквивалентные, после чего замена каждого класса эквивалентности одним состоянием дает минимальный С-авто- мат. В результате применения такого алгоритма к автомату, задан­ ному табл. 1-21 и 1-22, получим минимальный С-автомат, представ­ ленный в табл. 1-23 и 1-24. Опуская промежуточные таблицы, приве­ дем лишь последовательность разбиений при минимизации:

21

Таблица 1-21

22

Глава вторая

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

2-1. Канонический метод структурного синтеза автоматов

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

Под композицией элементарных автоматов [7 ] в общем случае по­ нимается следующее.

Пусть заданы элементарные автоматы 5 Х, . . . , S k. Произведем объединение элементарных автоматов в систему совместно работающих автоматов. Введем в рассмотрение некоторое конечное множество уз­ лов, называемых внешними входными и внешними выходными узлами. Эти узлы отличаются от узлов рассматриваемых элементарных автома­

(как внешних, так и внутренних). С точки зрения совместной работы системы автоматов смысл операции отождествления узлов состоит в том, что элементарный сигнал, попадающий на один из узлов, вхо­ дящих в множество отождествляемых между собой узлов, попадает тем самым на все узлы этого множества. После проведенных отождест­ влений узлов система автоматов превращается в так называемую схему (сеть) автоматов. Будем считать, что автоматы, входящие в схему ав­ томатов, работают совместно, если в каждый момент автоматного вре­ мени на все внешние входные узлы подается набор входных сигналов (структурный входной сигнал схемы) и со всех внешних выходных узлов снимается набор выходных сигналов (структурный выходной сигнал). Следует заметить, что при построении схемы автоматов должны выполняться условия корректности [7].

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

23

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

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

в структурном алфавите автомата. В случае двоичного алфавита каж­ дый входной zf и выходные ws и uh сигналы абстрактного автомата могут быть закодированы векторами длины L, N и D соответственно,

На этапе структурного синтеза предварительно выбираются эле­ ментарные автоматы, из которых затем путем их композиции строится структурная схема полученного на этапе абстрактного синтеза авто­ мата Мили, Мура или С-автомата. Если решение задачи структурного синтеза существует, говорят, что заданная система автоматов струк­ турно полна. Как отмечалось в [7], в настоящее время нет скольконибудь эффективных методов (существенно более простых, чем метод перебора всех вариантов) решения основной задачи структурного син­ теза при любом наборе структурно полных систем элементарных ав­ томатов. Поэтому обычно применяется так называемый канонический метод структурного синтеза, при котором используются элементарные автоматы некоторого специального вида: автоматы с памятью, имею­ щие более одного состояния, и автоматы без памяти — с одним состоя­

Теоретическим обоснованием канонического метода структурного синтеза автоматов является доказанная в [7] теорема о структурной полноте:

24

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

Результатом канонического метода структурного синтеза является система логических уравнений, выражающая зависимость выходных

же время для синтеза любых автоматов с минимальным числом элемен­ тов памяти необходимо в качестве таких элементов выбирать автоматы

Полнота системы переходов означает, что для любой пары состоя­ ний (bm, bs) автомата найдется входной сигнал, переводящий первый элемент этой пары (Ьт ) во второй (bs), т. е. в таком автомате в каждом столбце таблицы переходов должны встречаться все состояния авто­ мата. Полнота системы выходов автомата Мура состоит в том, что каж­ дому состоянию автомата поставлен в соответствие свой особый вы­ ходной сигнал, отличный от выходных сигналов других состояний. Очевидно, что в таком'автомате число выходных сигналов равно числу состояний автомата. Вместе с предыдущим утверждением это приводит к тому, что в автомате Мура с полной системой выходов можно ото­ ждествить состояния автомата с его выходными сигналами. В связи

IS