Изменения
Нет описания правки
==Каскадный сумматор ==
'''Каскадный сумматор''' - логическая цепь, осуществляющая сложение много разрядных многоразрядных двоичных чисел.
При сложении двух чисел в i-том разряде складываются a[i],b[i] и входной бит переноса (carry-in bit) c[i]. Младший разряд суммы записывается в i-й разряд ответа (s[i]), а старший становится выходным битом переноса (carry-out bit) c[i+1] и используется при сложении в следующем разряде.
Сложение с предвычислением переносов
В каскадном сумматоре бит переноса ci вычисляется в момент времени i. Значения ai и bi, однако, известны с самого начала. В некоторых случаях они определяют бит переноса ci:
если ai = bi = 0, то ci = 0 (перенос "поглощается" (kill))
если ai = bi = 1, то ci = 1 (перенос "порождается" (generate))
Однако если один из битов ai и bi равен 1, а другой 0, то ci-1 существен; именно,
если ai != bi, то ci = ci-1 (перенос "распространяется" (propagate))
Каждому разряду, следовательно, соответствует один из трёх типов переноса (carry statuses): k (kill), g (generate) или p (propagate). Этот тип известен заранее, что позволяет уменьшить время работы схемы сложения.
Зная типы переноса для соседних сумматоров ((i - 1)-го и i-го), можно определить тип переноса для их соединения, считая ci-1 входным битом, а ci+1 — выходным: зная, что случается с битом переноса на каждом шаге, можно рассчитать, что произойдёт за два шага, то есть как зависит ci+1 от ci-1. Если i-й разряд имеет тип k или g, то соединение имеет тот же тип переноса. Если же i-й разряд имеет тип переноса p, то тип переноса для соединения совпадает с типом (i - 1)-го разряда.
Таким образом, вычисление битов переноса ci сводится к вычислению префиксов yi. Оставшиеся действия выполняются за время O(1): достаточно подать биты переноса на входы сумматоров.
