Двоичный каскадный сумматор

Определение:

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

Принцип работы

Полный сумматор

Используемые обозначения: [math]X_{i}, Y_{i}[/math] — [math]i[/math]-ый разряд суммируемых чисел, [math]C_{i}, C_{i+1}[/math] — биты переноса, [math]F_{i}[/math] — результат сложения.

Рассмотрим один элемент линейного каскадного сумматора. В некоторых случаях бит переноса [math]C_{i+1}[/math] зависит только от значений [math]X_{i}[/math] и [math]Y_{i}[/math]:

• если [math]X_{i} = Y_{i} = 1[/math], то [math]C_{i+1} = 1[/math]
• если [math]X_{i} = Y_{i} = 0[/math], то [math]C_{i+1} = 0[/math]

Иначе ([math]X_i \neq Y_i[/math]) бит переноса не изменяется, то есть [math]C_{i + 1} = C_i[/math].

Три случая называются следующим образом:

• Generate — "порождение" переноса
• Kill — "уничтожение" переноса
• Propagate — "проталкивание" переноса

Поскольку последовательное применение этих трёх действий над переносами принадлежит также одному из этих типов, то можно определить композицию действий над переносами. Обозначим композицию значком [math]\otimes[/math] и построим таблицу значений (в столбце первый аргумент, в строке — второй):

Пример композиции

[math]\otimes[/math]	k	p	g
k	k	k	g
p	k	p	g
g	k	g	g

Поскольку функция ассоциативна, то можно распространить её на любое количество аргументов. Более того, поскольку для любого действия [math]x[/math] выполняется равенство [math]x \otimes p = x[/math], то функцию от нескольких действий можно определить как "последнее не [math]p[/math]".

Схема

Схема двоичного каскадного сумматора

Сумматор состоит из двух частей. Первая часть — это группа полных сумматоров, вычисляющих ответ. Вторая часть — дерево отрезков, с помощью которого вычисляется бит переноса.

Обозначения

• "[math]+[/math]" — полный сумматор, вычисляет результат сложения.
• [math]\bigotimes[/math] вычисляет композицию двух переносов.
• [math]\bigodot[/math] возвращает [math]C_{i}[/math], старший бит сумматора.

Схемная сложность

Дерево отрезков вычисляет биты переноса за [math]O(\log N)[/math], оставшиеся действия выполняются за [math]O(1)[/math]. Суммарное время работы — [math]O(\log N)[/math].

Ссылки

• Дискретная математика: алгоритмы
• Wikipedia