Каскадный сумматор — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 22: Строка 22:
 
* [http://en.wikipedia.org/wiki/Adder_(electronics) en.wikipedia.org/wiki/Adder ]
 
* [http://en.wikipedia.org/wiki/Adder_(electronics) en.wikipedia.org/wiki/Adder ]
 
* [http://rain.ifmo.ru/cat/view.php/vis/arithmetics/binary-addition-2002/algorithm ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ ]
 
* [http://rain.ifmo.ru/cat/view.php/vis/arithmetics/binary-addition-2002/algorithm ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ ]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]

Версия 22:29, 16 января 2012

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

Как известно, с помощью полного сумматора можно сложить 2 одноразрядных двоичных числа. Для сложения двух [math]n[/math]-разрядных двоичных чисел можно использовать [math]n[/math] полных сумматоров.

При сложении двух чисел в [math]i[/math]-том разряде складываются [math]a_i[/math], [math]b_i[/math] и входной бит переноса (carry-in bit) [math]c_i[/math]. Младший разряд суммы записывается в [math]i[/math]-й разряд ответа ([math]s_i[/math]), а старший становится выходным битом переноса (carry-out bit) [math]c_{i+1}[/math] и используется при сложении в следующем разряде.

При этом в первый входной бит переноса подаётся ноль, а последний бит переноса даёт старший разряд суммы.

Прежде чем сложить [math]i[/math]-ые биты, надо ждать выходного бита переноса от сложения [math] i-1 [/math] битов, то есть сумма в каждом разряде может зависеть от суммы предыдущих разрядов. Поэтому сложение с помощью каскадного сумматора выполняется за время [math]O(n)[/math].


Ripple carry adder.png


См. также

Cсылки