Сложность мультиплексора порядка

1) Мультиплексор порядка

Входами являются переменных , а выходами - переменные . На выходах реализуются всевозможные элементарные конъюнкции (“r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> ”) . – произвольный набор.

Допустим, что на входе набор и этот набор соответствует двоичному представлению числа . Тогда i- выход мультиплексора будет равен , а все остальные выходы , то есть -ый выход мультиплексора реализует следующую логическое умножение: , где – двоичное представление числа :

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

Оценим сложность мультиплексора более точно, используя полученную оценку. Для этого рассмотрим мультиплексоры порядка от переменных и мультиплексор от оставшихся переменных . Примем , то есть разобьем все переменные на группы. К первой группе относим переменные первой половины , а ко второй группе – переменные второй половины. На выходах реализуются всевозможные элементарные конъюнкции от переменных , а на выходах мультиплексора r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> реализуются всевозможные элементарные конъюнкции переменных . Каждую конъюнкцию от переменных можно получить логическим умножением двух конъюнкций: конъюнкции переменных и конъюнкции переменных . Поэтому общую схему мультиплексора можем представить следующим образом:

Как показано ранее,

Поэтому общая сложность мультиплексора порядка

6.2 Сложность дешифратора порядка n.

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