Задачи логического проектирования комбинационных схем

 

В процессе логического проектирования можно выделить четыре основные задачи – две задачи синтеза и две задачи анализа.

2.3.1. Абстрактный синтез схемы.

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

 

2.3.2. Абстрактный анализ схемы.

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

 

2.3.3. Структурный синтез схемы.

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

Решение задачи структурного синтеза разбивается на три этапа.

Абстрактно-структурный синтез. На этом этапе сложная схема делится на более простые части – производится декомпозиция. Можно выделить два основных вида декомпозиции – параллельную и последовательную (по типу соединения разделённых блоков). Критерием разделения является уменьшение общей сложности описания схемы.

Процедура декомпозиции продолжается до тех пор, пока имеется возможность разделения блоков схемы на более простые составляющие.

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

3. Покрытие абстрактной схемы заданными логическими элементами. На данном этапе производится формальное замещение получившихся при детализации блоков их реализацией на логических элементах заданного типа. Этот этап в литературе обычно называется технологическим отображением (technology mapping).

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

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

 

2.3.4. Структурный анализ схемы.

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

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

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

Рассмотрим более подробно алгоритмы и методы решения задач структурного синтеза и анализа логических схем.