Изменения
Нет описания правки
Зная типы переноса для соседних сумматоров ((i - 1)-го и i-го), можно определить тип переноса для их соединения, считая ci-1 входным битом, а ci+1 — выходным: зная, что случается с битом переноса на каждом шаге, можно рассчитать, что произойдёт за два шага, то есть как зависит ci+1 от ci-1. Если i-й разряд имеет тип k или g, то соединение имеет тот же тип переноса. Если же i-й разряд имеет тип переноса p, то тип переноса для соединения совпадает с типом (i - 1)-го разряда.
Таким образом, вычисление битов переноса ci сводится к вычислению префиксов yi. Оставшиеся действия выполняются за время O(1): достаточно подать биты переноса на входы сумматоров.
== См. также ==
