Сумматор с переносом выбора - Carry-select adder

В электронике переносной сумматор это особый способ реализовать сумматор, который является логическим элементом, который вычисляет ${\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-битного сумматора с пульсационным переносом. Поскольку перенос известен в начале вычислений, блок выбора переноса не требуется для первых четырех битов. Задержка этого сумматора будет составлять четыре полных задержки сумматора плюс три задержки MUX.

Сумматор переменного размера

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

Сумматор условной суммы

А сумматор условной суммы рекурсивная структура, основанная на сумматоре с выбором переноса. В сумматоре условной суммы уровень MUX выбирает между двумя п / 2-битовые входы, которые сами построены как сумматор условной суммы. Нижний уровень дерева состоит из пар 2-битных сумматоров (1 полусумматор и 3 полных сумматора) плюс 2 однобитовых мультиплексора.

Сумматор условной суммы страдает от очень большого разветвление промежуточных выходов переноса. Разветвление может достигать п / 2 на последнем уровне, где ${\displaystyle c_{n/2-1}}$ управляет всеми мультиплексорами из ${\displaystyle s_{n/2}}$ к ${\displaystyle s_{n-1}}$.

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

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

Пример показан в Когге – Стоун гадюка статья.

дальнейшее чтение

• Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы». квадиблок. В архиве из оригинала 2018-07-03. Получено 2018-07-16.