Сумматор (электроника)

Цифровая схема, которая вычисляет суммы на входах

Сумматор , или сумматор , ^[1] — это цифровая схема , выполняющая сложение чисел. Во многих компьютерах и других типах процессоров сумматоры используются в арифметико-логических устройствах (АЛУ). Они также используются в других частях процессора, где используются для вычисления адресов , индексов таблиц , операторов увеличения и уменьшения и подобных операций.

Хотя сумматоры могут быть созданы для многих представлений чисел , таких как двоично-десятичное число или избыточное число-3 , наиболее распространенные сумматоры работают с двоичными числами . В тех случаях, когда для представления отрицательных чисел используется дополнение до двух или дополнение до единиц , просто преобразовать сумматор в сумматор-вычитатель . Другие представления чисел со знаком требуют больше логики вокруг базового сумматора.

История

В 1937 году Клод Шеннон продемонстрировал бинарное сложение в своей дипломной работе в Массачусетском технологическом институте. ^[2]

Двоичные сумматоры

Половина сумматора

Полусумматор складывает две одиночные двоичные цифры и . Он имеет два выхода: sum ( ) и перенос ( ). Сигнал переноса представляет собой переполнение следующей цифры многозначного сложения. Значение суммы составляет . Простейшая конструкция полусумматора, изображенная справа, включает в себя логические элементы исключающее ИЛИ и логический элемент И для . Булева логика для суммы (в данном случае ) будет тогда как для переноса ( ) будет . С добавлением логического элемента ИЛИ для объединения выходов переноса два полусумматора можно объединить в полный сумматор. ^[3] Полусумматор складывает два входных бита и генерирует перенос и сумму, которые являются двумя выходами полусумматора. Входные переменные полусумматора называются битами добавления и сложения. Выходными переменными являются сумма и перенос. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle S}$ ${\displaystyle C}$ ${\displaystyle 2C+S}$ ${\displaystyle S}$ ${\displaystyle C}$ ${\displaystyle S}$ ${\displaystyle A\oplus B}$ ${\displaystyle C}$ ${\displaystyle A\cdot B}$

Таблица истинности для полусумматора:

Различные цифровые логические схемы с полусумматором:

• 
  Полусумматор в действии.
• 
  Схема полусумматора, реализованная с одним логическим элементом XOR и одним логическим элементом AND .
• 
  Схема полусумматора, реализованного с пятью вентилями И-НЕ .
• 
  Схематическое обозначение 1-битного полусумматора.

Полный сумматор

Полный сумматор складывает двоичные числа и учитывает входящие и исходящие значения. Однобитный полный сумматор складывает три однобитных числа, часто записываемых как , и ; и являются операндами и немного заимствованы из предыдущего, менее значимого этапа. ^[4] Полный сумматор обычно является компонентом каскада сумматоров, которые складывают 8, 16, 32 и т. д. битные двоичные числа. Схема выдает двухбитовый выходной сигнал. Выходной перенос и сумма обычно представляются сигналами и , где сумма равна . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C_{in}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C_{in}}$ ${\displaystyle C_{out}}$ ${\displaystyle S}$ ${\displaystyle 2C_{out}+S}$

Полный сумматор можно реализовать разными способами, например, с помощью специальной схемы транзисторного уровня или состоящей из других вентилей. Наиболее распространенная реализация:

${\displaystyle S=A\oplus B\oplus C_{in}}$

${\displaystyle C_{out}=(A\cdot B)+(C_{in}\cdot (A\oplus B))}$

Приведенные выше выражения для и могут быть получены с помощью карты Карно для упрощения таблицы истинности. ${\displaystyle S}$ ${\displaystyle C_{in}}$

В этой реализации последний логический элемент ИЛИ перед выходным сигналом переноса может быть заменен логическим элементом исключающее ИЛИ без изменения результирующей логики. Это связано с тем, что, когда A и B оба равны 1, член всегда равен 0 и, следовательно, может быть только 0. Таким образом, входы последнего элемента ИЛИ никогда не могут быть одновременно 1 (это единственная комбинация, для которой OR и XOR выходы разные). ${\displaystyle (A\oplus B)}$ ${\displaystyle (C_{in}\cdot (A\oplus B))}$

Благодаря свойству функциональной полноты вентилей И-НЕ и ИЛИ-НЕ, полный сумматор также может быть реализован с использованием девяти вентилей И-НЕ , ^[5] или девяти вентилей ИЛИ-НЕ .

Использование только двух типов вентилей удобно, если схема реализуется с использованием простых интегральных микросхем, которые содержат только один тип вентилей на кристалл.

Полный сумматор также можно составить из двух полусумматоров, подключив и к входу одного полусумматора, затем приняв его сумму на выходе в качестве одного из входов второго полусумматора и в качестве другого его входа, и, наконец, выходов переноса из два полусумматора подключены к логическому элементу ИЛИ. Суммарный выход второго полусумматора является окончательным выходом суммы ( ) полного сумматора, а выходной сигнал логического элемента ИЛИ — окончательным выходом переноса ( ). Критический путь полного сумматора проходит через оба вентиля XOR и заканчивается на бите суммы . Предполагая, что для завершения вентиля XOR требуется 1 задержка, задержка, вызванная критическим путем полного сумматора, равна: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle S}$ ${\displaystyle C_{in}}$ ${\displaystyle S}$ ${\displaystyle C_{out}}$ ${\displaystyle S}$

${\displaystyle T_{\text{FA}}=2\cdot T_{\text{XOR}}=2D}$

Критический путь переноса проходит через один логический элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» в сумматоре и через 2 логических элемента (И и ИЛИ) в блоке переноса, и поэтому, если для завершения логических элементов «И» или «ИЛИ» требуется 1 задержка, задержка составит:

${\displaystyle T_{\text{c}}=T_{\text{XOR}}+T_{\text{AND}}+T_{\text{OR}}=D+D+D=3D}$

Таблица истинности для полного сумматора:

Инвертирование всех входов полного сумматора также инвертирует все его выходы, что можно использовать при разработке быстрых сумматоров с пульсирующим переносом, поскольку нет необходимости инвертировать перенос. ^[6]

Различные цифровые логические схемы с полным сумматором:

• 
  Полный сумматор в действии.
• 
  Схема полного сумматора, реализованная с двумя логическими элементами исключающее ИЛИ , двумя логическими элементами И и одним логическим элементом ИЛИ .
• 
  Схема полного сумматора, реализованного с девятью вентилями И-НЕ .
• 
  Схема полного сумматора, реализованного с девятью вентилями ИЛИ .
• 
  Полный сумматор с инвертированными выходами с однотранзисторной задержкой распространения переноса в КМОП ^[6]
• 
  Схематический символ 1-битного полного сумматора с _входом C и _{выходом} C , нарисованными по бокам блока, чтобы подчеркнуть их использование в многобитном сумматоре.

Сумматоры, поддерживающие несколько битов

Сумматор с пульсирующим переносом

Показана 4-битный сумматор с логической блок-схемой

Десятичный четырехзначный сумматор с пульсирующим переносом. FA = полный сумматор, HA = полусумматор.

Можно создать логическую схему, используя несколько полных сумматоров для сложения N -битных чисел. Каждый полный сумматор вводит значение предыдущего сумматора. Этот тип сумматора называется сумматором со пульсирующим переносом (RCA), поскольку каждый бит переноса «переносится» к следующему полному сумматору. Заметим, что первый (и только первый) полный сумматор можно заменить половинным сумматором (в предположении, что ). ${\displaystyle C_{in}}$ ${\displaystyle C_{out}}$ ${\displaystyle C_{in}=0}$

Схема сумматора с пульсирующим переносом проста, что позволяет сократить время проектирования; однако сумматор со пульсирующим переносом работает относительно медленно, поскольку каждый полный сумматор должен ждать, пока бит переноса будет вычислен из предыдущего полного сумматора. Задержку вентиля можно легко рассчитать, проверив полную схему сумматора. Каждый полный сумматор требует трех уровней логики. В 32-битном сумматоре со пульсирующим переносом имеется 32 полных сумматора, поэтому задержка критического пути (худший случай) равна 3 (от входа до переноса в первом сумматоре) + 31 × 2 (для распространения переноса в последних сумматорах) = 65 задержки на воротах. ^[7] Общее уравнение для наихудшего случая задержки для n -битного сумматора с пульсациями переноса, учитывающее как сумму, так и биты переноса, выглядит следующим образом:

${\displaystyle T_{\text{CRA}}(n)=T_{\text{HA}}+(n-1)\cdot T_{\text{c}}+T_{\text{s}}=}$ ${\displaystyle T_{\text{FA}}+(n-1)\cdot T_{c}=}$ ${\displaystyle 3D+(n-1)\cdot 2D=(2n+1)\cdot D}$

Конструкция с переменной полярностью переноса и оптимизированными вентилями И-ИЛИ-Инверт может работать примерно в два раза быстрее. ^{[8] [6]}

Сумматор с переносом вперед

4-битный сумматор с опережением переноса

64-битный сумматор с просмотром вперед

Чтобы сократить время вычислений, инженеры разработали более быстрые способы сложения двух двоичных чисел с помощью сумматоров с упреждающим переносом (CLA). Они работают путем создания двух сигналов ( и ) для каждой битовой позиции в зависимости от того, распространяется ли перенос из менее значимой битовой позиции (по крайней мере, один вход имеет значение 1), генерируемый в этой битовой позиции (оба входа равны 1), или убит в этой битовой позиции (оба входа равны 0). В большинстве случаев это просто выходная сумма полусумматора и выходной сигнал переноса того же сумматора. После генерации и создаются переносы для каждой битовой позиции. Некоторые продвинутые архитектуры с упреждающим переносом — это цепочка переноса Манчестера , сумматор Брента-Кунга (BKA) ^[9] и сумматор Когге-Стоуна (KSA). ^{[10] [11]} ${\displaystyle P}$ ${\displaystyle G}$ ${\displaystyle P}$ ${\displaystyle G}$ ${\displaystyle P}$ ${\displaystyle G}$

Некоторые другие архитектуры многобитных сумматоров разбивают сумматор на блоки. Можно изменять длину этих блоков в зависимости от задержки распространения цепей, чтобы оптимизировать время вычислений. Эти сумматоры на основе блоков включают в себя сумматор с пропуском переноса (или обходом переноса) , который будет определять значения для каждого блока, а не для каждого бита, и сумматор с выбором переноса , который предварительно генерирует сумму и значения переноса для любого возможного входа переноса ( 0 или 1) в блок, используя мультиплексоры для выбора соответствующего результата, когда известен бит переноса. ${\displaystyle P}$ ${\displaystyle G}$

Объединив несколько сумматоров с переносом вперед, можно создать еще более крупные сумматоры. Это можно использовать на нескольких уровнях для создания еще более крупных сумматоров. Например, следующий сумматор представляет собой 64-битный сумматор, который использует четыре 16-битных CLA с двумя уровнями блоков прогнозируемого переноса .

Другие конструкции сумматора включают сумматор с выбором переноса , сумматор условной суммы , сумматор с пропуском переноса и сумматор с полным переносом.

Сумматоры переноса-сохранения

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

Компрессоры 3:2

Полный сумматор можно рассматривать как компрессор с потерями 3:2 : он суммирует три однобитных входных сигнала и возвращает результат в виде одного двухбитного числа; то есть он отображает 8 входных значений в 4 выходных значения. Так, например, двоичный ввод 101 приводит к выводу 1 + 0 + 1 = 10 (десятичное число 2). Выполнение представляет собой первый бит результата, а сумма представляет собой нулевой бит. Аналогичным образом, полусумматор можно использовать в качестве компрессора с потерями 2:2 , сжимая четыре возможных входных сигнала в три возможных выходных сигнала.

Такие компрессоры можно использовать для ускорения суммирования трех и более слагаемых. Если количество слагаемых равно трем, макет известен как сумматор переноса-сохранения . Если количество слагаемых равно четырем и более, необходимо более одного слоя компрессоров, и возможны различные конструкции схемы: наиболее распространенными являются деревья Дадды и Уоллеса . Этот тип схем чаще всего используется в схемах умножителей , поэтому эти схемы также известны как умножители Дадды и Уоллеса.

Квантовые сумматоры

Квантовый полный сумматор с использованием вентилей Тоффоли и CNOT . Вентиль CNOT, который на этом рисунке окружен пунктирным квадратом, можно опустить, если не требуется невычисление для восстановления выхода B.

Используя только квантовые логические элементы Тоффоли и CNOT , можно создавать квантовые полные и полусумматоры. ^{[12] [13] [14]} Те же схемы могут быть реализованы и в классических обратимых вычислениях , поскольку и CNOT, и Тоффоли также являются классическими логическими вентилями .

Поскольку квантовое преобразование Фурье имеет низкую сложность схемы , его также можно эффективно использовать для сложения чисел. ^{[15] [16]}

Аналоговые сумматоры

Как и в двоичных сумматорах, объединение двух входных токов эффективно складывает эти токи. В рамках ограничений аппаратного обеспечения недвоичные сигналы (т.е. с основанием выше 2) могут складываться для вычисления суммы. Этот метод , также известный как «суммирующий усилитель», ^[17] можно использовать для уменьшения количества транзисторов в суммирующей схеме.

Смотрите также

• Двоичный множитель
• вычитатель
• Электронный микшер — для добавления аналоговых сигналов.

Рекомендации

1. Сингх, Аджай Кумар (2010). Проектирование цифровых СБИС. Прентис Холл Индия. п. 321. ИСБН 9788120341876– через Google Книги.
2. «Компьютерные схемы :: Учебник CC 210» . textbooks.cs.ksu.edu .
3. Ланкастер, Джеффри А. (2004). Проектирование и разработка программного обеспечения Excel HSC. Паскаль Пресс. п. 180. ИСБН 978-1-74125175-3.
4. Мано, М. Моррис (1979). Цифровая логика и компьютерный дизайн . Прентис-Холл . стр. 119–123. ISBN 978-0-13-214510-7.
5. Теджа, Рави (15 апреля 2021 г.), Схемы половинного и полного сумматора , получено 27 июля 2021 г.
6. Фишер, П. "Einfache Schaltungsblöcke" (PDF) . Университет Гейдельберга. Архивировано из оригинала (PDF) 5 сентября 2021 г. Проверено 05 сентября 2021 г.
7. Сатпати, Пинаки (2016). Проектирование и реализация сумматора Carry Select с использованием T-Spice. Якорное академическое издательство. п. 22. ISBN 978-3-96067058-2.
8. Берджесс, Нил (2011). Быстрые сумматоры с пульсирующим переносом в СБИС КМОП стандартных ячеек. 20-й симпозиум IEEE по компьютерной арифметике . стр. 103–111.
9. Брент, Ричард Пирс ; Кунг, Сян Те (март 1982 г.). «Обычная схема для параллельных сумматоров». Транзакции IEEE на компьютерах . С-31 (3): 260–264. дои : 10.1109/TC.1982.1675982. ISSN  0018-9340. S2CID  17348212. Архивировано из оригинала 24 сентября 2017 года.
10. Когге, Питер Майкл ; Стоун, Гарольд С. (август 1973 г.). «Параллельный алгоритм эффективного решения общего класса рекуррентных уравнений». Транзакции IEEE на компьютерах . С-22 (8): 786–793. дои : 10.1109/TC.1973.5009159. S2CID  206619926.
11. Рейндерс, Неле; Деэн, Вим (2015). Проектирование энергоэффективных цифровых схем сверхнизкого напряжения . Аналоговые схемы и обработка сигналов (1-е изд.). Чам, Швейцария: Springer International Publishing AG, Швейцария . дои : 10.1007/978-3-319-16136-5. ISBN 978-3-319-16135-8. ISSN  1872-082X. LCCN  2015935431.
12. Фейнман, Ричард П. (1986). «Квантово-механические компьютеры». Основы физики . ООО «Спрингер Сайенс энд Бизнес Медиа». 16 (6): 507–531. Бибкод : 1986FoPh...16..507F. дои : 10.1007/bf01886518. ISSN  0015-9018. S2CID  122076550.
13. «Пример кода: квантовый полный сумматор» . QuTech (Технологический университет Делфта (TU Delft) и Нидерландская организация прикладных научных исследований (TNO)).
14. Дибьенду Чаттерджи, Ариджит Рой (2015). «Схема квантового полусумматора на основе трансмонов». Успехи теоретической и экспериментальной физики . 2015 (9): 093А02. Бибкод : 2015PTEP.2015i3A02C. дои : 10.1093/ptep/ptv122 .
15. Дрейпер, Томас Г. (7 августа 2000 г.). «Дополнение о квантовом компьютере». arXiv : Quant-ph/0008033 .
16. Руис-Перес, Лидия; Хуан Карлос, Гарсия-Эскартин (2 мая 2017 г.). «Квантовая арифметика с квантовым преобразованием Фурье». Квантовая обработка информации . 16 (6): 152. arXiv : 1411.5949v2 . Бибкод : 2017QuIP...16..152R. дои : 10.1007/s11128-017-1603-1. S2CID  10948948.
17. «Суммирующий усилитель представляет собой сумматор напряжения на операционном усилителе» . 22 августа 2013 г.

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

• Лю, Цо-Кай; Хохулин, Кейт Р.; Шиау, Лих-Эр; Мурога, Сабуро (январь 1974 г.). «Оптимальные однобитные полные сумматоры с различными типами вентилей». Транзакции IEEE на компьютерах . Лаборатории Белла: IEEE . С-23 (1): 63–70. дои : 10.1109/TC.1974.223778. ISSN  0018-9340. S2CID  7746693.
• Лай, Хун Чи; Мурога, Сабуро (сентябрь 1979 г.). «Минимальные двоичные параллельные сумматоры с вентилями NOR (NAND)». Транзакции IEEE на компьютерах . ИИЭЭ . С-28 (9): 648–659. дои : 10.1109/TC.1979.1675433. S2CID  23026844.
• Мид, Карвер; Конвей, Линн (1980) [декабрь 1979 г.]. Введение в системы СБИС (1-е изд.). Ридинг, Массачусетс, США: Аддисон-Уэсли . Бибкод : 1980aw...книга.....М. ISBN 978-0-20104358-7. Проверено 12 мая 2018 г.
• Давио, Марк; Дешан, Жан-Пьер; Тайзе, Андре (1983). Цифровые системы с реализацией алгоритмов (1-е изд.). Исследовательская лаборатория Philips , Брюссель, Бельгия: John Wiley & Sons , межнаучное издание Wiley. ISBN 978-0-471-10413-1. LCCN  82-2710.
• Гослинг, Джон (январь 1971 г.). «Обзор методов высокоскоростного сложения». Учеб. ИЭЭ . 188 (1): 29–35. дои : 10.1049/piee.1971.0004.

Внешние ссылки

• СМИ, связанные с сумматорами (цифровыми схемами), на Викискладе?
• Аппаратные алгоритмы арифметических модулей, включая описание нескольких схем сумматора с цифрами.
• 8-битный полный сумматор и вычитатель — демонстрация интерактивного полного сумматора, созданного на JavaScript исключительно для учебных целей.
• Интерактивное моделирование полного сумматора (требуется Java), интерактивная схема полного сумматора, созданная с помощью онлайн-симулятора схем Teahlab.
• Интерактивное моделирование половинного сумматора (требуется Java), схема половинного сумматора, построенная с помощью симулятора схем Teahlab.
• 4-битное моделирование полного сумматора, созданное в Verilog, и сопровождающее его видеоруководство по Ripple Carry Full Adder.
• Ширрифф, Кен (ноябрь 2020 г.). «Реверс-инжиниринг схемы упреждающего переноса в процессоре Intel 8008».