схем из ФЭ

Задача анализа: для данной СФЭ (1) получить систему булевых уравнений (2).

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

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

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

Пример. Для функции

(3)

Схема, соответствующая суперпозиции в правой части формулы (3), показана на рис. 8.

° ° °

Рис. 8

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

Справедливо следующее утверждение.

Теорема. Существует алгоритм, который для каждой системы булевых функций строит минимальную схему .

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

,

и, следовательно, искомая схема имеет один выход.

Сложность минимальной схемы обозначим через . Будем рассматривать задачу синтеза не для отдельной функции , а для всего класса функций от переменных. Качество алгоритмов синтеза сравнивается путем сопоставления так называемых функций Шеннона. Пусть

, ,

– минимальная сложность схем, реализующих , которые получаются при помощи алгоритма .

Функции , называются функциями Шеннона, причем очевидно, что

.

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