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

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

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

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

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

Обозначения:

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

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

• Generate(g): если [math]X_{i} = Y_{i} = 1[/math],  то [math]C_{i+1} = 1[/math]
• Kill(k): если [math]X_{i} = Y_{i} = 0[/math],  то [math]C_{i+1} = 0[/math],
• Propagate(p): если [math]X_{i} \ne Y_{i}[/math],  то [math]C_{i+1} = C_{i}[/math],

Обозначим композицию действий над переносами значком [math]\bigotimes[/math] и построим таблицу значений(в столбце первый аргумент, в строке — второй):

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

Пример

Замечание: так как значение [math]x \otimes p = x[/math], функцию [math]\bigotimes[/math] можно определить как последнее не "p".

Схема

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

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

Обозначения

• [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