Условное сложение суммы

Условная сумма сумматор (CSA , для краткости) представляет собой электронную схему для добавления многозначных двоичных чисел (см также добавление сети ).

CSA складывает два n-значных двоичных числа, поэтому имеет 2n входов. Поскольку результат может включать перенос , имеется n + 1 выходов.

В сумматоре пульсации переноса биты двух слагаемых суммируются параллельно, но любые переносы передаются последовательно от полного сумматора к полному сумматору, поэтому время работы довольно велико. CSA, с другой стороны, вычисляет сумму в соответствии с принципом « разделяй и властвуй» . Однако, поскольку еще не ясно, существует ли переходящий остаток, все должно быть рассчитано дважды (с переходом и без него). Правильные результаты выбираются с помощью логики.

функциональность

• Входящие битовые последовательности рекурсивно делятся пополам, пока не останется только 1-битных частей.
• Они складываются.
• Теперь результаты снова добавляются рекурсивно.

Проблема, возникающая при использовании этого метода, заключается в том, что неизвестно, имеют ли менее значимые дополнения перенос, когда 1-битные части добавляются параллельно. Чтобы решить эту проблему, все добавления просто выполняются как с переносом, так и без него, а затем выбирается правильный результат в зависимости от предшественника.

Этот принцип позволяет складывать почти за логарифмическое время .