172
правки
Изменения
→Схема
{{Определение
|definition='''Двоичный каскадный сумматор - ''' (англ. ''Binary adder''' ) {{---}} цифровая [[Реализация булевой функции схемой из функциональных элементов|схема]], осуществляющая сложение двух многоразрядных двоичных чисел, с ускоренным формированием разрядов переноса.
}}
Три случая называются следующим образом:
* <mathtex> generate\mathbf{g} \mathtt{enerate}</mathtex> {{---}} "''порождение" '' переноса,* <mathtex>kill\mathbf{k} \mathtt{ill}</mathtex> {{---}} "''уничтожение" '' переноса,* <mathtex>propagate\mathbf{p} \mathtt{ropagate}</mathtex> {{---}} "''проталкивание" '' переноса;.
Поскольку последовательное применение этих трёх действий над переносами принадлежит также одному из этих типов, то можно определить композицию действий над переносами. Обозначим композицию значком <tex>\otimes</tex> и построим таблицу значений (в столбце первый аргумент, в строке — второй):
!colspan="20"|Таблица значений
|-align="center"
| <tex>\otimes</tex> || <tex>\mathbf{k} </tex> || <tex>\mathbf{p} </tex> || <tex>\mathbf{g} </tex>
|-align="center"
| <tex>\mathbf{k} </tex> || <tex>k</tex> || <tex>k</tex> || <tex>g</tex>
|-align="center"
| <tex>\mathbf{p} </tex> || <tex>k</tex> || <tex>p</tex> || <tex>g</tex>
|-align="center"
| <tex>\mathbf{g} </tex> || <tex>k</tex> || <tex>g</tex> || <tex>g</tex>
|-align="center"
|}
* <tex>+ </tex> {{---}} полный сумматор, вычисляет результат сложения,
* <tex>\bigotimes</tex> {{---}} блок вычисления композиции двух переносов,
* <tex>\bigodot</tex> {{---}} блок вычисления <tex>C_{i}</tex>, старшего бита сумматора;.
== Схемная сложность ==
Дерево отрезков вычисляет биты переноса за <tex>O(\log N)</tex>, оставшиеся действия выполняются за <tex>O(1)</tex>. Суммарное время работы {{---}} <tex>O(\log N)</tex>.
== См. также ==
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%B0%D1%81%D0%BA%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D1%81%D1%83%D0%BC%D0%BC%D0%B0%D1%82%D0%BE%D1%80 [Каскадный сумматор]]*[[Сумматор]]*[[Троичный сумматор]]
[[Категория:Дискретная математика и алгоритмы]]
