Сумма́тор в кибернетике — это устройство, преобразующее информационные сигналы (аналоговые или цифровые) в сигнал, эквивалентный сумме этих сигналов; устройство, производящее операцию сложения.
История
1623 год и 1624 год — Вильгельм Шиккард в двух письмах Кеплеру описывает считающие часы, в которых одной из трёх главных частей был механический десятичный 6-разрядный сумматор. 1645 год — Паскаль создал механическую суммирующую машину «Паскалину» с механическим десятичным сумматором. 1673 год — Лейбниц создал механический калькулятор, в котором был механический цифровой десятичный сумматор на механическом счётчике. 1938 год — Джордж Штибиц, сотрудник телефонной компании Bell Laboratories, создал дома, на кухне, первый двоичный сумматор на электромеханических реле «Kitchen-1» Страницы истории. 1938 год Ключевые архитектуры параллельно префиксных сумматоровParallel prefix adders. Kostas Vitoroulis, 2006. Presented to Dr. A. J. Al-Khalili. Concordia University. https://users.encs.concordia.ca/~asim/COEN_6501/Lecture_Notes/Parallel%20prefix%20adders%20presentation.pdf : 1960 год — Склянский опубликовал статью «Conditional-Sum Addition Logic» с первым параллельно префиксным сумматором с radix’ом-2Conditional-Sum Addition Logic. J.Sclansky https://docs.yandex.ru/docs/view?tm=1717059574&tld=ru&lang=en&name=Sklansky-Cond_Sum-IRE.pdf&text=J.%20Sklansky%2C%20%E2%80%9CConditional-Sum%20Addition%20Logic%E2%80%9D%2C%20IRE%20transactions%20on%20computers%2C%201960&url=https%3A%2F%2Fwww.ece.ucdavis.edu%2F~vojin%2FCLASSES%2FEEC280%2FWeb-page%2Fpapers%2FArithmetic%2FSklansky-Cond_Sum-IRE.pdf&lr=213&mime=pdf&l10n=ru&sign=3f86db0f139e3eaf958bf008881d4f19&keyno=0&nosw=1&serpParams=tm%3D1717059574%26tld%3Dru%26lang%3Den%26name%3DSklansky-Cond_Sum-IRE.pdf%26text%3DJ.%2BSklansky%252C%2B%25E2%2580%259CConditional-Sum%2BAddition%2BLogic%25E2%2580%259D%252C%2BIRE%2Btransactions%2Bon%2Bcomputers%252C%2B1960%26url%3Dhttps%253A%2F%2Fwww.ece.ucdavis.edu%2F~vojin%2FCLASSES%2FEEC280%2FWeb-page%2Fpapers%2FArithmetic%2FSklansky-Cond_Sum-IRE.pdf%26lr%3D213%26mime%3Dpdf%26l10n%3Dru%26sign%3D3f86db0f139e3eaf958bf008881d4f19%26keyno%3D0%26nosw%3D1 Сумматор Склянского https://dzen.ru/a/Zm3p0eHkalUCYBHr 1973 год — Когге и Стоун применили в параллельно префиксном сумматоре Склянского несколько иное древо для вычисления операторов G и P, уменьшающее fan-out, но увеличивающее количество логических элементов, и опубликовали статью «A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations» с параллельно префикным сумматром с radix’ом-2A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations. PETER M. KOGGE AND HAROLD S. STONE https://docs.yandex.ru/docs/view?tm=1717059981&tld=ru&lang=en&name=1973-kogge.pdf&text=Kogge%2C%20Stone%2C%20%E2%80%9CA%20Parallel%20Algorithm%20for%20the%20Efficient%20solution%20of%20a%20General%20Class%20of%20Recurrence%20equations%E2%80%9D%2C%20IEEE%2C%201973&url=https%3A%2F%2Fgwern.net%2Fdoc%2Fcs%2Falgorithm%2F1973-kogge.pdf&lr=213&mime=pdf&l10n=ru&sign=26ea6ba2f0c1e7be9fe2d8af5e8a57f0&keyno=0&nosw=1&serpParams=tm%3D1717059981%26tld%3Dru%26lang%3Den%26name%3D1973-kogge.pdf%26text%3DKogge%252C%2BStone%252C%2B%25E2%2580%259CA%2BParallel%2BAlgorithm%2Bfor%2Bthe%2BEfficient%2Bsolution%2Bof%2Ba%2BGeneral%2BClass%2Bof%2BRecurrence%2Bequations%25E2%2580%259D%252C%2BIEEE%252C%2B1973%26url%3Dhttps%253A%2F%2Fgwern.net%2Fdoc%2Fcs%2Falgorithm%2F1973-kogge.pdf%26lr%3D213%26mime%3Dpdf%26l10n%3Dru%26sign%3D26ea6ba2f0c1e7be9fe2d8af5e8a57f0%26keyno%3D0%26nosw%3D1 1980 год — параллельно префиксный сумматор Ладнер-Фишера (Ladner-Fisher) с radix’ом-2 1982 год — параллельно префиксный сумматор Брента-Кунга (Brent-Kung) с radix’ом-2 1987 год — параллельно префиксный сумматор Хана Карлсона (Han Carlson) с radix’ом-2 1999 год — параллельно префиксный сумматор S. Knowles’а с radix’ом-2 1981 год — Линг опубликовал статью «High-speed Binary Adder» с параллельно префиксным сумматором с radix’ом-2High-speed Binary Adder. Huey Ling. https://cseweb.ucsd.edu//classes/fa06/cse246/lingadder.pdf 2000 год — Gurkaynak, Leblebici, Chaousnt и McGuinneess опубликовали статью о сумматоре Когге-Стоуна с radix’ом-4Higher Radix Kogge-Stone Parallel Prefix Adder Architectures. Frank K. Gurkaynak,Yusuf Leblebici, Laurent Chaousnt and Patric J. McGuinneess. IEEE International Symposium on Circuits and Systems. May 26-31. 2000. Geneva. Switzerland https://www.ece.ucdavis.edu/~vojin/CLASSES/EPFL/Papers/higher_r_koggiestone_adder.pdf Cумматор Когге-Стоуна, Radix-4, 16-ти битный, быстрый https://andserkul.narod.ru/AdderRadix4KoggeStone16bit.pdf 2001 год — Beaumont-Smith и Cheng-Chew Lim применили в параллельно префиксном сумматоре Склянского операторы G и P с radix’ом-4 вместо radix-2 и опубликовали статью о параллельно префиксном сумматоре Склянского с radix’ом-4 «Parallel Prefix Adder Design»Parallel Prefix Adder Design. Beaumont-Smith and Cheng-Chew Lim. https://www.researchgate.net/publication/3900704_Parallel_prefix_adder_design Сумматор Beaumont-Smith’а https://dzen.ru/a/ZliE1yPKlFalC_aW
Классификация сумматоров В зависимости от формы представления информации различают сумматоры аналоговые и цифровые.
По способу реализации механические. электромеханические. электронные. пневматические.
По принципу действия На счётчиках, считающие количества импульсов входного сигналах. Функциональные, выдающие на выходах значения логической функции суммы по модулю и логической функции разряда переноса: логические, каждый раз вычисляющие функцию разряда суммы по модулю и функцию разряда переноса табличные, с таблицами заранее вычисленных значений функции разряда суммы по модулю и значений функции разряда переноса записанных: в ПЗУ, ППЗУ (аппаратные) (надёжнее и дешевле логических, так как вместо полупроводников, выполняющих логические вычисления, в ПЗУ используются проводники и изоляторы («прошивки»)) или в ОЗУ (аппаратные и программные).
Табличные сумматоры впервые были применены в калькуляторах построенных на реле в США до второй мировой войны.
По архитектуре Четвертьсумматоры — бинарные (двухоперандные) сумматоры по модулю без разряда переноса, характеризующиеся наличием двух входов, на которые подаются два одноразрядных числа, и одним выходом, на котором реализуется их арифметическая сумма по модулю. Полусумматоры — бинарные (двухоперандные) сумматоры по модулю с разрядом переноса, характеризующиеся наличием двух входов, на которые подаются одноимённые разряды двух чисел, и двух выходов: на одном реализуется арифметическая сумма по модулю в данном разряде, а на другом — перенос в следующий (старший) разряд. Полные сумматоры — тринарные (трёхоперандные) сумматоры по модулю с разрядом переноса, характеризующиеся наличием трёх входов, на которые подаются одноимённые разряды двух складываемых чисел и перенос из предыдущего (более младшего) разряда, и двумя выходами: на одном реализуется арифметическая сумма по модулю в данном разряде, а на другом — перенос в следующий (более старший разряд). Такие сумматоры изначально ориентированы только на показательные позиционные системы счисления. Накапливающие сумматоры — снабжённые собственной внутренней памятью.
По способу действия Последовательные (одноразрядные), в которых обработка разрядов чисел ведётся поочерёдно, разряд за разрядом, на одном и том же одноразрядном оборудовании. Параллельно-последовательные, в которых одновременно параллельно последовательно складываются несколько разрядов пары чисел. Параллельные (многоразрядные), в которых слагаемые складываются одновременно по всем разрядам, и для каждого разряда имеется своё оборудование.
По способу организации переноса С последовательным переносом (Ripple-carry adder, Схема последовательного переноса). С ускоренным групповым переносом (с предвидением переноса) (Carry-lookahead adders, CLA-adders). С ускоренным групповым переносом параллельно префиксные (parallel prefix adders, PPA) (Sklansky adder, Kogge-Stone adder, Beaumont-Smith adder (like Sklansky adder, radix-4)Сумматор Beaumont-Smith’а https://andserkul.narod.ru/Beaumont-Smith.pdf Сумматор Beaumont-Smith’а, radix-4, 16-ти битный https://andserkul.narod.ru/Radix4BeaumontSmith16.pdf , Knowles S. adder, Brent-Kung adder, Ladner-Fischer adder, Han-Carlson adder, Ling adder). С пропуском переноса (Carry-skip adder). Сумматор с условным сложением (Conditional sum adder). С переключением переноса (с выбором переноса) (Carry-select adder). С сохранением переноса (Carry-save adder).
По системе счисления Двоичные Троичные Четверичные Восьмеричные Десятеричные (десятичные) Шестнадцатеричные
Двоичный сумматор Двоичный сумматор может быть описан тремя способами: табличным, в виде таблицы истинности, аналитическим, в виде формулы (СДНФ), графическим, в виде логической схемы. Так как формулы и схемы могут тождественно преобразовываться, то, одной таблице истинности двоичного сумматора могут соответствовать множества различных логических формул и логических схем. Поэтому, с точки зрения получения результата без учёта затрат времени на вычисление суммы, табличный способ определения двоичного сумматора является основным. Обычное табличное и обычное формульное описание сумматора не учитывают времена задержек в реальных логических элементах и не годятся для определения быстродействия реальных сумматоров.
x0=A 1 0 1 0 1 0 1 0 x1=B 1 1 0 0 1 1 0 0 x2= 1 1 1 1 0 0 0 0Название действия (функции) Номер функции 1 0 0 1 0 1 1 0 Бит суммы по модулю 2 F3,150 1 1 1 0 1 0 0 0 Бит переноса F3,232
Единица переноса возникает в 4 случаях из 8.
СДНФ суммы по модулю 2:
СДНФ бита переноса:
Схема, которая обеспечивает сложение двух однобитных чисел А и В без получения бита переноса из предыдущего разряда называют полусумматором.
Полусумматор имеет 4 сигнальных линии: два входа для сигналов, представляющих одноразрядные двоичные числа А и В, и два выхода: сумма А и В по модулю 2 (S) и сигнал переноса в следующий разряд (P). При этом S наименее значимый бит, а P наиболее значимый бит.
Объединив два полусумматора и добавив дополнительную схему ИЛИ, можно создать трёхступенчатый полный сумматор с дополнительным входом Pi-1 (на рисунке 1), который принимает сигнал переноса из предыдущей схемы. Первая ступень на полусумматоре осуществляет сложение двух двоичных чисел и вырабатывает первый частный бит переноса, вторая ступень на полусумматоре осуществляет сложение результата первой ступени с третьим двоичным числом и вырабатывает второй частный бит переноса, третья ступень на логическом элементе 2ИЛИ вырабатывает результирующий бит переноса в старший разряд.
Схема полного сумматора может быть использована в качестве «строительных блоков» для построения схем многоразрядных сумматоров, путём добавления одноразрядных полных сумматоров. Для каждой цифры, которую схема должна быть в состоянии обрабатывать, используется один полный сумматор.
В сумматоре на рис.1 время вычисления суммы по модулю 2 равно 2dt, время вычисления переноса равно 3dt, где dt — время задержки в одном типовом логическом элементе. В m-разрядном сумматоре в худшем случае (единицы переноса во всех разрядах) до последнего разряда сигнал переноса проходит через m-1 разряд, а сумма будет готова ещё через 2dt, поэтому максимальное время сложения равно: . Максимальные времена выполнения сложения и вычисления переноса для большего числа разрядов приведены в таблице 1:Таблица 1. число разрядов сумматора 1 2 4 8 16 32 64 время выполнения сложения, dt 2 5 11 23 47 95 191 время вычисления переноса, dt 3 6 12 24 48 96 192
Двоичный одноразрядный полный сумматор является полной тринарной (трёхоперандной) двоичной логической функцией с бинарным (двухразрядным) выходом. Все три операнда и оба выходных разряда однобитные.
Десятичный сумматор Десятичный сумматор можно задать в виде двух таблиц:с нулём в переносе из предыдущего разряда: