СЖАТИЕ ТАБЛИЦЫ ПЕРЕХОДОВ
Число строк в первоначальной таблице переходов и число вершин графа автомата совпадают с числом внутренних состояний автомата, введенных в процессе задания его функционирования. Поскольку процесс задания недостаточно формализован, введенное число внутренних состояний может быть избыточным.
Уменьшение числа внутренних состояний автомата, или уменьшение количества строк его первоначальной таблицы переходов, позволяет в более компактной форме представить автомат на последующих этапах синтеза и в ряде случаев ведет к более простой реализации будущего устройства. Процесс сокращения размеров таблицы переходов путем объединения ее строк принято называть сжатием таблицы переходов.Две строки таблицы переходов автомата будем называть явно совместимыми, если в этих строках на пересечении с каждым столбцом указаны непротиворечивые значения функции выходов и одинаковые значения функции переходов или в одной строке указаны значения функций переходов и выходов, а в другой значения этих функций не определены (прочерк), или в обеих строках указан прочерк. Два значения функции выходов (два выходных набора) называют непротиворечивыми, если значения каждой выходной переменной в обоих наборах совпадают с точ-
2.4. АСИНХРОННЫЙ АВТОМАТ
За этапом абстрактного синтеза следует этап структурного синтеза, целью которого является построение схемы автомата*. На данном этапе выбирается структурная модель устройства (структурный автомат), наиболее полно отражающая требования к проектируемому дискретному устройству, и осуществляется оптимизация выбранной модели.
Исходным для этапа структурного синтеза является автомат, представленный сжатой таблицей переходов, и набор логических элементов и элементов памяти.На этапе структурного синтеза осуществляется кодирование состояний входа, выхода и внутренних состояний символами из двоичного структурного алфавита, т. е. осуществляется выбор способа представления этих состояний в виде наборов двоичных сигналов. Как уже отмечалось, коды состояний входа и выхода проектируемого устройства зачастую бывают известны из его связи с другими устройствами системы. Однако кодирование внутренних состояний обычно осуществляется в процессе структурного синтеза и существенно зависит от требований к проектируемому устройству, отраженных структурной моделью.
Ниже будем рассматривать устройства, которые выполняются из логических элементов потенциального типа, обладающих свойством усиления сигналов. Память устройства организуется не за счет специально введенных элементов памяти и задержек, а за счет контуров обратных связей и задержек логических элементов. В таких устройствах могут иметь место состязания, обуслов-
*■ Строгое понятие «схема автомата» можно найти, например, в [17].
ленные разбросом задержек, присущих реальным логическим элементам. Устранение состязаний часто связано с введением структурной или временной избыточности [35—37]. Поэтому критерии устойчивости к состязаниям, быстродействия и сложности проектируемого устройства взаимосвязаны.
Рассмотрим реальную комбинационную схему. Логические элементы и соединительные линии между ними, образующие такую схему, обладают внутренними задержками. Суммарную задержку момента изменения сигнала на выходе комбинационной схемы относительно начала изменения сигналов на входе схемы можно промоделировать и указать ее на выходе в виде последовательного соединения выхода комбинационной схемы и элемента задержки [36]. Тем самым можно отобразить свойство инерционности реальной комбинационной схемы моделью, состоящей из идеальной (безынерционной) комбинационной схемы и элементов задержки, вынесенных на ее выходы.
(значению функции выходов автомата), внутреннему состоянию (значению функции переходов автомата) однозначно сопоставлены наборы значений соответствующих сигналов. Значения выходных сигналов безынерционной комбинационной схемы модели определяются булевыми функциями
ванной таблицы переходов автомата, в которой вместо состояний указаны их коды.
2. Синтез комбинационной схемы автомата. На этом этапе анализируется кодированная таблица переходов и строятся таблицы интервалов, на основе которых находятся кратчайшие ДНФ, свободные от состязаний, функций переходов и выходов. По ДНФ' находятся формулы, описывающие комбинационную схему, реализуемую на элементах заданного базиса. В качестве таких элементов в книге рассматриваются элементы ИЛИ—НЕ. Синтез заканчивается представлением схемы автомата в графической форме.