Возможно, эта статья содержит оригинальное исследование. |
Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. |
Сумма́тор в кибернетике — это устройство, преобразующее информационные сигналы (аналоговые или цифровые) в сигнал, эквивалентный сумме этих сигналов[1]; устройство, производящее операцию сложения.
История
править- 1623 год и 1624 год — Вильгельм Шиккард в двух письмах Кеплеру описывает считающие часы, в которых одной из трёх главных частей был механический десятичный 6-разрядный сумматор[2].
- 1645 год — Паскаль создал механическую суммирующую машину «Паскалину» с механическим десятичным сумматором.
- 1673 год — Лейбниц создал механический калькулятор, в котором был механический цифровой десятичный сумматор на механическом счётчике.
- 1938 год — Джордж Штибиц, сотрудник телефонной компании Bell Laboratories, создал дома, на кухне, первый двоичный сумматор на электромеханических реле "Kitchen-1"[3]
Ключевые архитектуры параллельно префиксных сумматоров[4]:
- 1960 год - Склянский опубликовал статью "Conditional-Sum Addition Logic" с первым параллельно префиксным сумматором с radix'ом-2[5][6][неавторитетный источник]
- 1973 год - Когге и Стоун применили в параллельно префиксном сумматоре Склянского несколько иное древо для вычисления операторов G и P, уменьшающее fan-out, но увеличивающее количество логических элементов, и опубликовали статью "A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations" с параллельно префикным сумматром с radix'ом-2[7]
- 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'ом-2[8]
- 2001 год - Beaumont-Smith и Cheng-Chew Lim одни из первых применили в параллельно префиксном сумматоре Склянского операторы G и P с radix'ом-4 вместо radix-2 и опубликовали статью о параллельно префиксном сумматоре с radix'ом-4 "Parallel Prefix Adder Design"[9][10][неавторитетный источник]
Классификация сумматоров
правитьВ зависимости от формы представления информации различают сумматоры аналоговые и цифровые[1].
По способу реализации
правитьПо принципу действия
править- На счётчиках, считающие количества импульсов входного сигналах.
- Функциональные, выдающие на выходах значения логической функции суммы по модулю и логической функции разряда переноса:
- логические, каждый раз вычисляющие функцию разряда суммы по модулю и функцию разряда переноса
- табличные, с таблицами заранее вычисленных значений функции разряда суммы по модулю и значений функции разряда переноса записанных:
Табличные сумматоры впервые были применены в калькуляторах построенных на реле в США до второй мировой войны.
По архитектуре
править- Четвертьсумматоры — бинарные (двухоперандные) сумматоры по модулю без разряда переноса, характеризующиеся наличием двух входов, на которые подаются два одноразрядных числа, и одним выходом, на котором реализуется их арифметическая сумма по модулю.
- Полусумматоры — бинарные (двухоперандные) сумматоры по модулю с разрядом переноса, характеризующиеся наличием двух входов, на которые подаются одноимённые разряды двух чисел, и двух выходов: на одном реализуется арифметическая сумма по модулю в данном разряде, а на другом — перенос в следующий (старший) разряд.
- Полные сумматоры — тринарные (трёхоперандные) сумматоры по модулю с разрядом переноса, характеризующиеся наличием трёх входов, на которые подаются одноимённые разряды двух складываемых чисел и перенос из предыдущего (более младшего) разряда, и двумя выходами: на одном реализуется арифметическая сумма по модулю в данном разряде, а на другом — перенос в следующий (более старший разряд). Такие сумматоры изначально ориентированы только на показательные позиционные системы счисления[источник не указан 5012 дней].
- Накапливающие сумматоры - снабжённые собственной внутренней памятью.
По способу действия
править- Последовательные (одноразрядные), в которых обработка разрядов чисел ведётся поочерёдно, разряд за разрядом, на одном и том же одноразрядном оборудовании.
- Параллельно-последовательные, в которых одновременно параллельно последовательно складываются несколько разрядов пары чисел.
- Параллельные (многоразрядные), в которых слагаемые складываются одновременно по всем разрядам, и для каждого разряда имеется своё оборудование.
- С последовательным переносом (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)[14][15][16], Knowles S. adder[17], Brent-Kung adder, Ladner-Fischer adder[18], Han-Carlson adder[19], Ling adder).
- С пропуском переноса (Carry-skip adder)[20].
- Сумматор с условным сложением (Conditional sum adder)[21].
- С переключением переноса (с выбором переноса[22]) (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 |
Двоичный одноразрядный полный сумматор является полной тринарной (трёхоперандной) двоичной логической функцией с бинарным (двухразрядным) выходом. Все три операнда и оба выходных разряда однобитные.
Десятичный сумматор
правитьДесятичный сумматор можно задать в виде двух таблиц:
с нулём в переносе из предыдущего разряда:
+ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
---|---|---|---|---|---|---|---|---|---|---|
+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
3 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
5 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
6 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
7 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
8 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
9 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
и с единицей в переносе из предыдущего разряда:
+ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
---|---|---|---|---|---|---|---|---|---|---|
+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
или в виде одной таблицы, в которой единица переноса из предыдущего разряда смещает на одну колонку вправо:
+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
3 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
5 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
6 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
7 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
8 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
9 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
C соответствующей прошивкой как десятичный сумматор (десятеричный) могут работать шестнадцатеричный сумматор и двадцатисемиричный сумматор-вычитатель на ПЗУ.
Направления развития сумматоров
правитьБыстродействия параллельных сумматоров вполне достаточно для быстрого сложения небольшого количества чисел фиксированной длины.
Так как поразрядное сложение по природе своей последовательно, то при очень большом количестве сложений более выгодно перенастроить то же самое оборудование (АЛУ) для одновременного или не очень одновременного параллельного выполнения нескольких последовательных сложений.
Например, параллельный 64-разрядный двоичный сумматор из 64 двоичных сумматоров со сложными схемами ускоренного переноса сложит 1 пару 64-битных чисел в лучших схемах приблизительно за 5dt, а 32 пары 64-битных чисел приблизительно за 32*5dt=160dt.
32 последовательных двоичных сумматора без схем ускоренного переноса бит за битом сложат 32 пары 64-битных чисел приблизительно за 64*2dt=128dt.
32 последовательных четверичных сумматора без схем ускоренного переноса сложат 32 пары 64-битных чисел приблизительно за (64/lg24)*2dt=64dt.
32 последовательных шестнадцатеричных сумматора без схем ускоренного переноса сложат 32 пары 64-битных чисел приблизительно за (64/lg216)*2dt=32dt.
32 последовательных двухсотпятидесятишестиричных сумматора без схем ускоренного переноса сложат 32 пары 64-битных чисел приблизительно за (64/lg2256)*2dt=16dt, т.е. приблизительно в десять раз быстрее, чем параллельный 64-битный сумматор со схемами ускоренного переноса.
32 последовательных четыретысячидевяностошестиричных сумматора без схем ускоренного переноса сложат 32 пары 64-битных чисел приблизительно за (64/lg24096)*2dt=10,67dt.
См. также
правитьПримечания
править- ↑ 1 2 Словарь по кибернетике / Под редакцией академика В. С. Михалевича. — 2-е. — Киев: Главная редакция Украинской Советской Энциклопедии имени М. П. Бажана, 1989. — 751 с. — (С48). — 50 000 экз. — ISBN 5-88500-008-5.
- ↑ Считающие часы Вильгельма Шиккарда . Дата обращения: 6 октября 2012. Архивировано 10 ноября 2016 года.
- ↑ Архивированная копия . Дата обращения: 7 марта 2011. Архивировано 9 октября 2009 года. Страницы истории. 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
- ↑ Conditional-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
- ↑ A 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
- ↑ High-speed Binary Adder. Huey Ling. https://cseweb.ucsd.edu//classes/fa06/cse246/lingadder.pdf
- ↑ 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
- ↑ Сумматор, 4-битный, полный, параллельногрупповой (табличный), на ПЗУ . Дата обращения: 8 сентября 2016. Архивировано 17 сентября 2016 года.
- ↑ Hardware algorithms for arithmetic modules . Дата обращения: 27 апреля 2013. Архивировано 9 апреля 2007 года.
- ↑ Adder Designs . Дата обращения: 27 апреля 2013. Архивировано 4 февраля 2020 года.
- ↑ Parallel Prefix Adder Desine. Beaumont-Smith A., Cheng-Chew L. Department of Electrical and Electronic Engineering, The University of Adelaide, Australia. 2001 . Дата обращения: 9 марта 2023. Архивировано 7 марта 2023 года.
- ↑ Сумматор Beaumont-Smith'а https://andserkul.narod.ru/Beaumont-Smith.pdf
- ↑ Сумматор Beaumont-Smith'а, radix-4, 16-ти битный https://andserkul.narod.ru/Radix4BeaumontSmith16.pdf
- ↑ A Family of Adders. Simon Knowles. Element 14, Aztec Centre, Bristol, UK. Дата обращения: 9 марта 2023. Архивировано 7 марта 2023 года.
- ↑ Ladner, Fischer, “Parallel Prefix Computation”, ACM, 1980 . Дата обращения: 9 марта 2023. Архивировано 9 марта 2023 года.
- ↑ Han, Carlson, “Fast Area-Efficient VLSI Adders, IEEE, 1987 . Дата обращения: 9 марта 2023. Архивировано 9 марта 2023 года.
- ↑ 3 Сложение и вычитание двоичных чисел. Двоичные сумматоры. Стр.30. Рис.12.Схема сумматора с пропуском переноса carry-skip adder . Дата обращения: 13 сентября 2016. Архивировано 19 сентября 2016 года.
- ↑ Conditional-Sum Addition Logic. Sklansky J. IRE Transaction on Electronic Computer. 1960. p.226. Дата обращения: 9 марта 2023. Архивировано 7 марта 2023 года.
- ↑ Таненбаум Э.- Архитектура компьютера. стр.130 . Дата обращения: 21 апреля 2013. Архивировано 10 ноября 2013 года.
Литература
править- Угрюмов Е. П. Элементы и узлы ЭЦВМ. М.: Высшая школа, 1976. — 232 с.
- Угрюмов Е. П. Цифровая схемотехника. — СПб.: БХВ-Петербург, 2001. — 528 с.
- Жан М. Рабаи, Ананта Чандракасан, Боривож Николич. 11. Проектирование арифметических блоков: Сумматор // Цифровые интегральные схемы. Методология проектирования = Digital Integrated Circuits. — 2-е изд. — М.: Вильямс, 2007. — С. 912. — ISBN 0-13-090996-3.
Ссылки
править- Сумматор — статья из Большой советской энциклопедии.
- Сумматор — статья из Большой советской энциклопедии.
В статье есть список источников, но не хватает сносок. |