Изменения

'''Каскадный сумматор''' {{---}} логическая [[Реализация булевой функции схемой из функциональных элементов|цепьсхема]], осуществляющая сложение многоразрядных двоичных чисел.

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

Составить схему на основе каскадного сумматора достаточно простоПри сложении двух чисел в <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> и используется при сложении в следующем разряде. Действительно При этом в первый входной бит переноса подаётся ноль, прежде а последний бит переноса даёт старший разряд суммы. Прежде чем сложить <tex>i</tex>-ые биты, надо ждать входного выходного бита переноса от сложения <tex> i-1 </tex> битов, то есть сумма в каждом разряде может зависеть от суммы предыдущих разрядов. Таким образом, Поэтому сложение происходит с помощью каскадного сумматора выполняется за время О<tex>O(Nn)</tex>.