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

Материал из Викиконспекты
Перейти к: навигация, поиск

Рассмотрим один элемент полного сумматора:

Полный сумматор 1.png
Где [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}, Y_{i}, C_{i}[/math], и введем условные обозначения:

x y [math] C_i \rightarrow C_{i+1} [/math] Условные обозначения Действие
0 0 0 k(kill) Поглощение переноса
0 1 [math] P_1 [/math] p(propagate) Перенос переноса
1 0
1 1 1 g(generate) Порождение переноса


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

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


Пример:
Пример компазиции.png
Таким образом функцию [math]\bigotimes[/math] можно определить как последнее не "P".

Пусть [math]f_{i}\epsilon \left \{k,p,g\right \}[/math], тогда: [math]C_{i}=(f_{1}\bigotimes f_{2}\bigotimes f_{3}\bigotimes...\bigotimes f_{i})_{(0)}[/math].

Пусть элемент Первый элемент.png возвращает [math]\bigotimes[/math] двух функций,
а элемент Второй элемент.png возвращает [math]C'[/math], старший бит сумматора.


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