3-9. ОЦЕНКА СЛОЖНОСТИ СХЕМ И ФУНКЦИЙ

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

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

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

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

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

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

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

где — число базисных элементов вида использованных при построении данной схемы.

Отметим, что оценка простоты схемы вида (3-23) отражает только состав функциональных элементов а, использованных при построении схемы, но не отражает геометрию этой схемы (напомним, что для ряда функций она может осуществляться просто за счет параллельного или последовательного соединения функциональных элементов в схеме). Если функциональный элемент реализует функцию переменных, то назовем удельной стоимостью этого элемента следующую величину

Рассмотрим теперь некоторый класс функций который мы желаем реализовать в системе базисных элементов Функции являются векторными функциями, так что

и

Другими словами, мы рассматриваем реализацию в данной системе базисных элементов класса -полюсников.

Рассмотрим теперь индекс Шеннона:

Если ввести обозначение

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

Теорема 3-6. Если

то

Если через обозначить число функций из множества то имеет место при тех же условиях (3-27) и (3-28) следующая теорема.

Теорема 3-7. Для достаточно больших имеет место эквивалентность

Если теперь произвести подстановку (3-30) в (3-29), то мы получим:

Рассмотрим более подробно полученный результат. При соотношение (3-31) приобретет вид:

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

Оценку, аналогичную оценке (3-32) для релейно-контактных схем, О. Б. Лупанов получил для схем, в которые входят любые базовые функциональные элементы.

Соотношения (3-30) и (3-32) дают асимптотическую оценку сложности реализации произвольной функции алгебры логики в виде некоторой логической сети. Однако не надо думать, что столь сложно реализуются все функции алгебры логики. Приведенные оценки — это в

некотором смысле оценки сложности реализаций наиболее «плохих» функций.

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