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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

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

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

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

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

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

Рассмотрим один элемент линейного каскадного сумматора - Ripple-carry adder. В некоторых случаях бит переноса [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].

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

• [math] \mathbf{g} \mathtt{enerate}[/math] — порождение переноса,
• [math] \mathbf{k} \mathtt{ill}[/math] — уничтожение переноса,
• [math] \mathbf{p} \mathtt{ropagate}[/math] — проталкивание переноса.

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

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

Таблица значений
[math]\otimes[/math]	[math] \mathbf{k} [/math]	[math] \mathbf{p} [/math]	[math] \mathbf{g} [/math]
[math] \mathbf{k} [/math]	[math]k[/math]	[math]k[/math]	[math]g[/math]
[math] \mathbf{p} [/math]	[math]k[/math]	[math]p[/math]	[math]g[/math]
[math] \mathbf{g} [/math]	[math]k[/math]	[math]g[/math]	[math]g[/math]

Поскольку функция ассоциативна, то можно распространить её на любое количество аргументов. Более того, поскольку для любого действия [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].

См. также

• Каскадный сумматор
• Сумматор
• Троичный сумматор

Источники информации

• Е. Угрюмов "Цифровая схемотехника" 2001г.

• Дк. Ф. Уэйкерли "Проектирование цифровых устройств, том 1." 2002г.

• М.И. Богданович "Цифровые интегральные микросхемы" 1996г.