1632
правки
Изменения
м
== См. также ==
*[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 Каскадный сумматор]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Схемы из функциональных элементов]]
rollbackEdits.php mass rollback
{{Определение
|definition='''Двоичный каскадный сумматор''' (англ. ''Binary adder'') {{---}} цифровая [[Реализация булевой функции схемой из функциональных элементов|схема]], осуществляющая сложение двух многоразрядных двоичных чисел, с ускоренным формированием разрядов переноса.
}}
Рассмотрим один элемент [[Каскадный сумматор|линейного каскадного сумматора - Ripple-carry adder]]. В некоторых случаях бит переноса <tex>C_{i+1}</tex> зависит только от значений <tex>X_{i}</tex> и <tex>Y_{i}</tex>:
* если <tex>X_{i} = Y_{i} = 1</tex>, то <tex>C_{i+1} = 1</tex>,* если <tex>X_{i} = Y_{i} = 0</tex>, то <tex>C_{i+1} = 0</tex>;
Иначе (<tex>X_i \neq Y_i</tex>) бит переноса не изменяется, то есть <tex>C_{i + 1} = C_i</tex>.
Три случая называются следующим образом:
* '''G'''<tex> \mathbf{g} \mathtt{enerate }</tex> {{---}} "''порождение" '' переноса,* '''K'''<tex> \mathbf{k} \mathtt{ill }</tex> {{---}} "''уничтожение" '' переноса,* '''P'''<tex> \mathbf{p} \mathtt{ropagate }</tex> {{---}} "''проталкивание" '' переноса.
Поскольку последовательное применение этих трёх действий над переносами принадлежит также одному из этих типов, то можно определить композицию действий над переносами. Обозначим композицию значком <tex>\otimes</tex> и построим таблицу значений (в столбце первый аргумент, в строке — второй):
[[Файл:Пример компазиции.png|right|450px|thumb|Пример композиции]]
{| borderclass="3wikitable" align="center" style="color: blue; background-color:#ccffcc;" cellpadding="103" !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>x</tex> выполняется равенство <tex>x \otimes p = x</tex>, то функцию от нескольких действий можно определить как "последнее не <tex>p</tex>".
Сумматор состоит из двух частей. Первая часть {{---}} это группа полных сумматоров, вычисляющих ответ. Вторая часть {{---}} [[Дерево_отрезков._Построение|дерево отрезков]], с помощью которого вычисляется бит переноса.
[[Файл:Двоичный_каскадный_сумматор.png|450px|left|thumb|Схема двоичного каскадного сумматора]]
''' Обозначения '''
* <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://bookfi.net/book/637011 М.И. Богданович "Цифровые интегральные микросхемы" 1996г.]
