Сумматор с переносом и выбором

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

Строительство

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

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

Базовый строительный блок

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

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

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

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

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

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

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

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

Объединение с другими сумматорными структурами

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

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

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

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