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

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


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

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

  • [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]\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].


Ссылки