Сумматор
Сумматором порядка n называют схему, вычисляющую результат сложения двух n-разрядных двоичных чисел



( здесь ai, bi, ci


Сумматор должен вычислять набор из (n+1)-ой результирующей функции:

задающих соответствующие разряды суммы c.
Обозначим через pi бит переноса из (i-1)-го разряда в i-ый. Тогда нетрудно видеть, что при i =0
c0 = a0 + b0 и p1 = a0

а при 1


ci= pi + ai + bi и pi+1 = (ai





Старший разряд c совпадает с последним переносом: cn=pn.
Рассмотрим теперь построенную выше схему S+ как схему, вычисляющую набор из двух функций: x




Рис. 2.4. Схема SUM1
Действительно, из построения следует, что в вершине p этой схемы вычисляется функция fp = (ai








Теперь из S+ и одноразрядных сумматоров SUM1 соберем схему SUMn для n-разрядного сумматора.

Рис. 2.5. Схема cумматора SUMn
Таким образом мы установили следующее утверждение.
Теорема 2.3.
Для каждого n

Замечание Логические схемы интенсивно исследовались 50-х-70-х годах прошлого столетия. В частности, К. Шеннон и О.Б. Лупанов установили оценки сложности схем для булевых функций от n аргументов. Оказалось, что любую такую функцию можно реализовать со сложностью не большей (по порядку) 2n/n и что "почти все" они имеют не меньшую сложность. При этом до сих пор не известна ни одна последовательность "конкретных" функций fn, сложность которых по порядку превосходила бы линейную функцию.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий