Универсальный многополюсник

Сложность универсального многополюсника.

Дешифратор порядка.

У дешифратора имеется входов ( и ) и единственный выход . Допустим, что на входах первых переменных двоичный набор , который является двоичным представлением числа , то есть . Тогда на выходе дешифратора будет значение входа : .

Дешифратор реализует следующую двоичную функцию:

(*)

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

, где

· – сложность мультиплексора;

· – умножение выходов мультиплексора на соответствующие входы дешифратора. Элементарные конъюнкции от переменных, т.е. таких умножений ;

· – всевозможные дизъюнкции слагаемых в формуле (*). Количество слагаемых равно числу двоичных наборов от переменных.

Входами этого многополюсника являются переменные , а выходами , где , и эти выходы соответствуют всевозможным функциям от n переменных.

Утверждение. Сложность многополюсника

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

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

Что и требовалось доказать.

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

Дата добавления: 2017-01-13