Сумматор с переключением переноса

В электронике, сумматор с переключением переноса^[1] является особым видом реализации сумматора, который является логическим элементом вычисляющим ${\displaystyle (n+1)}$-битную сумму двух ${\displaystyle n}$-битных чисел. Сумматор с переключением переноса является простым, но более быстрым, имея уровень глубины вентилей ${\displaystyle O({\sqrt {n}})}$.

Сумматор с переключением переноса обычно состоит из двух сумматоров с последовательным переносом и мультиплексора. Сложение двух n-битных чисел сумматор с переключением переноса делается двумя сумматорами (поэтому нужны два сумматора с последовательным переносом) для того, чтобы выполнить вычисление дважды, один раз с предположением переноса равным нулю и другой предполагая единице. После того, как два результата вычислены, правильная сумма и правильный перенос затем выбираются мультиплексором, как только правильный перенос становится известен.

Число битов в каждом блоке переключения переноса может быть одинаковым или неодинаковым. В случае блоков одинакового размера, оптимальная задержка происходит для блока размером ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$. В случае блоков неодинакового размера, размер блока должен иметь задержку, от входов слагаемых A и B до выхода переноса, равную задержке цепи мультиплексора впереди него, так что выходной перенос вычисляется только единожды. ${\displaystyle O({\sqrt {n}})}$ задержка является производной размера одинаковых блоков, где идеальное число полно-сумматорных элементов на блок является равным квадратному корню от числа складываемых битов, так как это даст равное число задержек мультиплексора.

Основной строительный блок

Выше приведён основной строительный блок сумматора с переключением переноса, где размер блока равен 4. Два 4-битных сумматора с последовательным переносом мультиплексируются вместе, где результирующие биты переноса и суммы переключаются входом переноса. Так как один сумматор с последовательным переносом предполагает входной перенос 0, а другой предполагает входной перенос 1, то переключение, какой сумматор имел правильное предположение, с помощью действительного входного переноса даёт требуемый результат.

Сумматор с блоками одинакового размера

16-битный сумматор с переключением переноса с одинаковыми блоками размером 4 может быть создан из трёх таких блоков и 4-битного сумматора с последовательным переносом. Так как входной перенос является известным с начала вычислений, блок переключения переноса не нужен для первых четырёх битов. Задержка этого сумматора будет четыре задержки полного сумматора, плюс три задержки мультиплексора.

Сумматор с блоками неодинакового размера

16-битный сумматор с переключением переноса с блоками неодинакового размера может быть создан похожим образом. Здесь мы показали сумматор с блоками размером 2-2-3-4-5. Это разбиение является идеальным, когда задержка полного сумматора равна задержке мультиплексора, что является маловероятным. Общая задержка равна двум задержкам полного сумматора, и четырём задержкам мультиплексора. Мы пытались сделать задержку через две цепи переноса и задержку переноса на предыдущей стадии равными.

Комбинирование с сумматорами других структур

Эта конструкция сумматора может быть дополнена сумматором с ускоренным переносом для генерации входов мультиплексора, давая таким образом даже большую производительность чем сумматор с параллельным префиксом одновременно потенциально уменьшая площадь. Пример показан в статье сумматор Когге-Стоуна.