2.5. СОСТЯЗАНИЯ В АСИНХРОННОМ АВТОМАТЕ
Целью структурного синтеза является получение схемы автомата, т. е. комбинационной схемы с обратными связями. Напомним, что специальные элементы памяти в цепях обратной связи не используются, поскольку память автомата реализуется за счет естественных задержек элементов комбинационной схемы.
Как следует из гл. 1, в комбинационной схеме во время переходного процесса могут возникнуть состязания, вызванные как неодновременностью изменения сигналов, так и наличием естественных задержек элементов. Асинхронный автомат (рис. 2.8) отражает возможность появления состязаний из-за неравенства вынесенных суммарных задержек комбинационной схемы. Однако, как было показано в гл. 1, при анализе некоторых видов состязаний требовалось учитывать естественные задержки отдельных логических элементов. Следовательно, для учета всех видов состязаний в устройстве с памятью необходимо допустить наличие естественных задержек логических элементов комбинационной схемы автомата.
место логические и функциональные состязания, анализ которых можно свести к анализу состязаний в комбинационной схеме, поскольку они имеют одинаковую природу. Тем не менее остановимся подробнее на функциональных состязаниях, поскольку они накладывают специфические требования на выполнение структурного синтеза. Дело в том, что если состязания в комбинационной схеме могут привести лишь к кратковременным ошибочным сигналам на ее выходах, то в схеме автомата с памятью из-за состязаний возможны «длительные» ошибки, ведущие к неверному функционированию автомата после появления ошибочных выходных и промежуточных сигналов.
Логические состязания, возникающие в схеме автомата, можно устранить путем построения ДНФ, свободных от состязаний, для каждой из булевых функций систем (2.1) и (2.2) . Более подробно этот вопрос будет рассмотрен в § 2.7.
Обобщим понятие «функциональные состязания» на случай многовыходной комбинационной схемы. Для этого представим выражения (2.1) и (2.2), описывающие комбинационную схему автомата, в виде следующей системы булевых функций:
занному в таблице переходов, сопоставлен переход между соседними входными наборами, то, очевидно, в автомате отсутствуют состязания между входными переменными. Ограничение на переходы между соседними входными наборами является фактически ограничением на условия работы синтезируемого авто* мата, которое надо учитывать в начале логического проектиро* вания. Однако в некоторых случаях этого можно не требовать и допускать изменение значений более чем одной входной переменной при смене входных наборов автомата. Тем самым в автомате допускается существование условий состязаний между входными переменными, если при этом не нарушается предписанный автомату закон функционирования. Например, в табл. 2.12 показан фрагмент таблицы переходов (одна строка), анализ которого выявляет возможность изменения значений двух входных переменных. Так, при изменении входного набора от (010) к (100) интервал перехода содержит четыре набора: {(000), (010), (ПО), (100)}. Любому из этих наборов соответствуют одно и то же состояние выхода К\ и внутреннее состояние к\. Следовательно, условия состязаний между входными переменными Хі и х2 в данном случае не приводят к появлению ошибок. Аналогично можно проанализировать каждую строку таблицы переходов и выяснить, имеются ли в автомате состязания между входными переменными. В случае, когда такие состязания обнаруживаются, следует изменить условия работы (таблицу переходов) автомата, если это возможно по системным соображениям. Если же такое изменение нельзя произвести, можно вос- пользоватьсья другими структурными моделями автомата [23, 24],
рассмотрение которых выходит за рамки книги.
Ограничимся- классом таблиц переходов, для которых состязания между входными переменными отсутствуют.Состязания между промежуточными переменными (гонки). Гонки в автомате возникают из-за того, что при переходе автомата из одного внутреннего состояния В: поѵгое ппомежѵточньте сигналы изменяются неоянпнпеменнп
Как следует из данного примера, даже если коды входных и внутренних состояний являются соседними, в автомате имеются условия существенных состязаний, которые могут привести к ошибочному функционированию. В общем случае для обеспечения устойчивости автомата к существенным состязаниям требуется введение в обратные связи специальных искусственных задержек или фильтров [22, 35]. Интуитивно ясно, что эти меры нужны, чтобы обеспечить изменение промежуточных сигналов на входах комбинационной схемы лишь после того, как все изменения входных сигналов будут восприняты всеми элементами схемы. Однако если предположить, (см. § 2.8), что соединительные линии между логическими элементами схемы обладают нулевыми задержками, то устойчивость автомата к существенным состязаниям можно обеспечить без использования задержек путем специальных преобразований схемы автомата.
при составлении таблицы переходов. Этот способ может повлечь необходимость введения дополнительных внутренних состояний автомата и преобразования таблицы переходов автомата в таблицу, не являющуюся нормальной. Способ устранения состязаний между выходными сигналами будет иллюстрироваться на примерах синтеза в § 2.9.
Согласно вышеизложенному в схеме асинхронного автомата могут иметь место состязания следующих видов: между входными сигналами, между выходными сигналами, гонки, логические, существенные.
Необходимость устранения состязаний первых двух видов учитывается при построении таблицы переходов автомата, по которой производится структурный синтез.
Устойчивость автомата к гонкам достигается за счет выбора соответствующего кода внутренних состояний. Логические состязания устраняются путем построения ДНФ, свободных от состязаний, для каждой из булевых функций, описывающих комбинационную схему автомата. И наконец, устойчивость автомата к существенным состязаниям достигается за счет соответствующей организации схемы автомата.1.6. ПРОТИВОГОНОЧНОЕ КОДИРОВАНИЕ
На данном этапе синтеза асинхронного автомата необходимо выбрать код внутренних состояний, сопоставляя каждому внутреннему состоянию набор значений промежуточных переменных. Кодирование внутренних состояний определяет не только число обратных связей автомата и число булевых функций, реализуемых комбинационной схемой, но и многие важные свойства синтезируемого автомата и прежде всего его устойчивость к гонкам.
Кодирование внутренних состояний, позволяющее обеспечить устойчивость автомата к гонкам, будем называть противозаконным. Противогоночный код внутренних состояний дает возможность такого задания системы булевых функций переходов и выходов, при котором в комбинационной схеме не возникают функциональные состязания, обусловленные изменениями значений промежуточных переменных. Способ реализации этой возможности будет описан в следующем параграфе, а сейчас рассмотрим два основных подхода к построению противогоночного кода внутренних состояний [32].
В соответствии с определением функциональных состязаний условия гонок возникают в том случае, если во время перехода изменяются значения нескольких промежуточных переменных. Если внутренние состояния закодированы соседним
кодом, то промежуточные переменные никогда не изменяются одновременно и гонки в автомате невозможны. Поэтому наличие соседнего кода внутренних состояний может служить достаточным условием отсутствия гонок в автомате.
Первый подход к рассматриваемой задаче заключается в соседнем кодировании внутренних состояний. Его особенностью является то, что внутренним состояниям, связанным переходом, последовательно приписываются соседние наборы значений фиксированного числа промежуточных переменных.
При неудачном исходе кодирования предпринимается попытка увеличить длину кода и процесс повторяется сначала. Следует отметить ограниченность данного подхода, поскольку соседнее кодирование возможно далеко не для всех таблиц переходов. Для таких таблиц можно попытаться произвести соседнее кодирование, видоизменив таблицу переходов, путем ввода, например, дополнительных состояний [18]. Обычно это сопровождается перебором большого числа вариантов. Кроме того, введение дополнительных состояний может вызвать снижение быстродействия синтезируемого автомата. Поэтому соответствующие методы преобразования и кодирования таблиц переходов рассматривать не будем.Суть второго подхода состоит в поразрядном способе образования противогоночного кода с использованием необходимого и достаточного условия противогоночного кодирования. Опишем данный способ для нормальных таблиц переходов модели Мили.
ходит путем определения безызбыточного покрытия таблицы по тому или иному критерию. Например, кратчайшему покрытию соответствует правильный код минимальной длины. Такому коду соответствует автомат с минимальным числом обратных связей. Однако при этом часто не удается получить автомат с наименьшим числом логических элементов. Построение правильного кода, при котором синтезируемый автомат имеет минимальную
Для сравнения приведем таблицу переходов модели Мили для синтезируемого формирователя (табл. 2.17). В этом случае автомат имеет два внутренних состояния, для кодирования которых достаточно ввести промежуточную переменную у. Система уравнений выходов и переходов содержит три уравнения, в то время как для модели Мура потребовалось лишь два уравнения.
Приведем еще один пример. Определим правильный код внутренних состояний для таблицы переходов счетного триггера
