Изменения

{{Определение|definition='''Каскадный сумматор''' (англ. ''ripple-carry adder'') {{---}} логическая [[Реализация булевой функции схемой из функциональных элементов|цепьсхема]], осуществляющая сложение многоразрядных двоичных чисел.}}Как известно, с помощью [[Сумматор|полного сумматора]] можно сложить 2 одноразрядных двоичных числа. Для сложения двух <tex>n</tex>-разрядных двоичных чисел можно использовать <tex>n</tex> полных сумматоров.

Как известно, с помощью [[Сумматор|полного сумматора]] можно сложить 2 одноразрядных двоичных числа. Для сложения двух N-разрядных двоичных чисел можно использовать N полных сумматров. При сложении двух чисел в <tex>i</tex>-том разряде складываются <TeX>a_i</TeX>,<Tex>b_i</TeX> и входной бит переноса (англ. ''carry-in bit'') <TeX>c_i</TeX>. Младший разряд суммы записывается в <tex>i</tex>-й разряд ответа (<TeX>s_i</TeX>), а старший становится выходным битом переноса (англ. ''carry-out bit'') <TeX>c_{i+1}</TeX> и используется при сложении в следующем разряде.

Составить схему на основе каскадного сумматора достаточно просто, но такой сумматор работает относительно медленно.ДействительноПри этом в первый входной бит переноса подаётся ноль, прежде чем сложить i-ые биты надо ждать входного бита а последний бит переноса от сложения i-1 битов. Таким образом сложение происходит за время О(N)даёт старший разряд суммы.

==Cсылки Источники информации ==* [http://en.wikipedia.org/wiki/Adder_(electronics) en.wikipedia.org/wiki/Wikipedia {{---}} Adder (electronics)]* [http://rain.ifmo.ru/cat/view.php/vis/arithmetics/binary-addition-2002/algorithm ДИСКРЕТНАЯ МАТЕМАТИКАКаскадное сложение] [[Категория: АЛГОРИТМЫ Дискретная математика и алгоритмы]] [[Категория: Схемы из функциональных элементов ]]