Структурная оптимизация логических схем

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

Основными критериями оптимизации при многоуровневом синтезе являются:

1) длина критического пути при прохождении сигнала от входа к выходу схемы (максимальная задержка сигнала);

2) площадь кристалла, занимаемая логической сетью. От указанной площади, в конечном итоге, зависит стоимость проектируемой схемы. Причём, при определении площади сети часто учитывается не только площадь логических элементов, но и площадь межсоединений. Это условие ставит не только задачу минимизации количества узлов (элементов) логической сети, но и количества связей между ними.

Процесс оптимизации включает выполнение двух этапов:

1) исключение из схемы очевидных избыточных элементов;

2) анализ схемы с учётом логической недоопределённости.

Рассмотрим более подробно выполнение указанных этапов.

3.3.1. Исключение из схемы очевидных избыточных элементов.

На первом этапе оптимизации производится исключение из схемы цепочек последовательно соединенных инверторов и элементов, выполняющих одинаковые логические функции. Цепочки инверторов могут образовываться в схемах при покрытии элементами «2И-НЕ» либо «2ИЛИ-НЕ», поскольку для совпадения числовых последовательностей при формальном замещении покрываемых блоков требуется инвертирование входных или выходных последовательностей покрывающих элементов (см. раздел 3.2.1).

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

Указанные алгоритмы первого этапа оптимизации достаточно очевидны и не требуют строгих доказательств.

3.3.2. Анализ схемы с учётом логической недоопределённости.

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

Далее от выхода к входу выполняется анализ отдельных элементов с учётом возможной логической недоопределённости их входных числовых последовательностей. При таком анализе в поступающие на входы логических элементов числовые последовательности вводится неопределённость (звёздочки). Если, например, на входы элемента «2ИЛИ» поступают две какие-либо последовательности, то одну из них можно фиксировать, а во вторую ввести звёздочки на тех местах, на которых в первой последовательности стоят единицы. Ведь, если на один из входов элемента «2ИЛИ» подаётся единица, то на его выходе будет присутствовать единица независимо от состояния на втором входе.

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

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

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

Если подходящая числовая последовательность не найдена, то последовательность проанализированного входа фиксируется и неопределённость вводится в последовательность другого входа.

При анализе входов элемента «2И» всё делается точно так же, но звёздочки в анализируемой последовательности вводятся на тех местах, на которых фиксированная последовательность принимает нулевое значение. Аналогичные правила формирования недоопределённых входных последовательностей можно сформулировать для элементов «2И-НЕ» и «2ИЛИ-НЕ».

Простейший вариант анализа и оптимизация схемы можно рассмотреть на примере покрытия блока «ИСКЛЮЧАЮЩЕЕ ИЛИ» (см. раздел 3.2.2), схема которого на элементах «2И-НЕ» представлена на рис. 3.18. Проведём анализ указанной схемы с учётом логической недоопределённости.

Для элемента – зафиксируем последовательность , поскольку она поступает прямо с входа, и попробуем подобрать последовательность таким образом, чтобы его выходная последовательность не изменилась:

То есть, на нижний вход элемента вместо последовательности , соответствующей инвертированной входной переменной можно подать последовательность . При этом выходная последовательность элемента () не изменится.

Аналогично для элемента – зафиксируем последовательность и попробуем подобрать последовательность таким образом, чтобы его выходная последовательность не изменилась:

Две определённые выше последовательности и не противоречат друг другу и, следовательно, их можно объединить вместе – . Эта последовательность, в свою очередь, не противоречит числовой последовательности элемента «2И-НЕ» (). В результате в схему рис. 3.18 достаточно добавить ещё один элемент «2И-НЕ», на входы которого поступают переменные и , а выход используется для формирования последовательностей и . Окончательная схема реализации блока «ИСКЛЮЧАЮЩЕЕ ИЛИ» представлена на рис. 3.19.

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