Сумматор: как сложить два числа проводами

Сумматор — это схема из логических вентилей, которая складывает двоичные числа. На входы подают биты слагаемых, на выходах появляются биты суммы. Внутри нет ничего, кроме вентилей И, ИЛИ и исключающего ИЛИ, соединённых проводами.

Сложение — это таблица

В игре у Вас было 5 монет, Вы подобрали ещё 7, и на экране сразу появилось 12. Телефон не считает на пальцах: ответ выдаёт схема. Соберём её сами.

В уроке Двоичная система счисления вся таблица сложения уместилась в четыре правила:

0 + 0 = 0
0 + 1 = 1
1 + 1 = 10      пишем 0, единица переходит в следующий разряд
1 + 1 + 1 = 11  пишем 1, единица переходит в следующий разряд

Первые три правила описывают сложение двух битов, четвёртое — трёх: к двум битам добавилась единица «в уме». Начнём с двух.

Ответ удобно всегда записывать двумя цифрами: 00, 01 или 10. Правая цифра остаётся в своём разряде — назовём её суммой. Левая уходит в соседний разряд — это перенос. Получается таблица с двумя входами и двумя выходами:

Это обычная таблица истинности. А под таблицу истинности можно подобрать вентили.

Полусумматор

Посмотрите на столбцы выходов по отдельности. Сумма равна единице, когда входы разные, — так работает исключающее ИЛИ. Перенос равен единице, только когда на обоих входах единицы, — это вентиль И. Оба вентиля знакомы Вам по уроку Логические вентили.

Значит, биты A и B нужно подать сразу на два вентиля. Такая схема называется полусумматором: она складывает два бита и выдаёт бит суммы и бит переноса.

Приставка «полу» появилась не случайно. Схема складывает только два бита. А в столбике, начиная со второго разряда, их бывает три: два бита слагаемых и перенос, пришедший справа.

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

Полный сумматор — схема с тремя входами: бит A, бит B и входной перенос из соседнего младшего разряда. Выходов по-прежнему два: сумма и выходной перенос.

Заучивать таблицу не нужно. Сосчитайте единицы на входах и запишите их количество двоичным числом: ни одной — 00, одна — 01, две — 10, три — 11. Левая цифра — выходной перенос, правая — сумма.

Полный сумматор собирают из готовых деталей — двух полусумматоров и одного вентиля ИЛИ:

1. Первый полусумматор складывает A и B.
2. Второй складывает сумму первого с входным переносом. Его сумма — это бит суммы всей схемы.
3. Вентиль ИЛИ объединяет переносы обоих полусумматоров: если хотя бы один выдал единицу, она уходит в следующий разряд.

Проверим на строке A = 1, B = 0, входной перенос 1. Первый полусумматор: сумма 1, перенос 0. Второй складывает 1 и 1: сумма 0, перенос 1. Вентиль ИЛИ получает 0 и 1 и выдаёт 1. Итог — сумма 0, выходной перенос 1, как в таблице.

В полусумматоре два вентиля, значит, в полном сумматоре их 2 + 2 + 1 = 5.

Цепочка: складываем числа целиком

Один полный сумматор обслуживает один разряд. Чтобы сложить числа из четырёх разрядов, берут четыре полных сумматора и соединяют их цепочкой: выходной перенос каждого подключают ко входному переносу соседа слева. На входной перенос младшего разряда подают 0 — справа от него никого нет.

Сложим 0101 и 0111, то есть 5 и 7. Двигаемся справа налево, как в столбике.

вес разряда         8   4   2   1
A                   0   1   0   1
B                   0   1   1   1
входной перенос     1   1   1   0
---------------------------------
сумма               1   1   0   0
выходной перенос    0   1   1   1

• Вес 1: 1 + 1 + 0 — две единицы. Сумма 0, перенос 1.
• Вес 2: 0 + 1 + 1 — снова две. Сумма 0, перенос 1.
• Вес 4: 1 + 1 + 1 — три единицы. Сумма 1, перенос 1.
• Вес 8: 0 + 0 + 1 — одна. Сумма 1, перенос 0.

На выходах 1100₂ = 8 + 4 = 12. Всё сходится: 5 + 7 = 12.

Представьте четырёх учеников за длинной партой. У каждого на листке два бита — свой разряд двух чисел. Назвать ответ сразу может только крайний справа. Остальные ждут, пока сосед справа шепнёт, есть ли перенос. Цепочка сумматоров работает так же.

Разрядов можно взять сколько угодно: для восьми нужно 8 полных сумматоров, для шестидесяти четырёх — 64, то есть 320 вентилей.

Когда сумма не помещается

Выходной перенос самого старшего сумматора подключать некуда. Что он означает?

Сложим на той же схеме 11 и 6: 1011 + 0110. Правильный ответ — 17, а это 10001₂, пять разрядов. Четыре выхода суммы покажут 0001, то есть 1, а пятая цифра окажется на выходе переноса.

Так электронные часы после 23:59 показывают 00:00. Если не смотреть на дату, кажется, что время пошло назад. Дата здесь играет роль переноса: она сообщает, что счёт перешёл через край.

Единица на выходе переноса старшего разряда — признак переполнения: сумма не поместилась в отведённые разряды. Этот провод не бросают: по нему остальная схема узнаёт, что четырём битам результата верить нельзя.

Почему перенос ограничивает скорость

Вентиль переключается очень быстро, но не мгновенно. Сложим 1111 и 0001. Перенос возникает в младшем разряде и пробегает через все четыре сумматора. Пока он в пути, старшие биты суммы показывают неверное значение — им ещё не «шепнули».

Чем длиннее цепочка, тем дольше ждать. В сумматоре на 64 разряда перенос в худшем случае проходит в 16 раз больше ступеней, чем в нашем четырёхразрядном. Это и ограничивает скорость сложения.

Инженеры придумали схемы ускоренного переноса: они вычисляют переносы сразу для нескольких разрядов, не дожидаясь соседей. Такие схемы сложнее, вентилей в них больше, и мы их не разбираем. Сложение при этом остаётся тем же самым.

Частые вопросы

Сумматор понимает, что складывает числа?

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

Зачем нужен полусумматор, если есть полный?

Из двух полусумматоров собирают полный, так что это удобная деталь. Младшему разряду полусумматора хватило бы: переноса справа у него нет. Но обычно и туда ставят полный сумматор — свободный вход ещё пригодится.

Один сумматор складывает сразу несколько чисел?

Нет, ровно два. Чтобы сложить три числа, сначала складывают первые два, а потом прибавляют к результату третье.

Коротко

• Сумматор — схема из вентилей, которая складывает двоичные числа.
• Полусумматор складывает два бита: сумму даёт исключающее ИЛИ, перенос — вентиль И.
• Полный сумматор складывает три бита: два бита слагаемых и входной перенос. Его собирают из двух полусумматоров и вентиля ИЛИ.
• Многоразрядный сумматор — цепочка полных сумматоров: перенос передаётся от младшего разряда к старшему.
• Перенос из старшего разряда означает, что сумма чисел без знака не поместилась в разряды.
• Чем длиннее цепочка, тем дольше идёт перенос, поэтому в процессорах его ускоряют дополнительными схемами.

Складывать схема уже умеет. Как заставить тот же сумматор вычитать и сравнивать числа — в уроке Вычитание, сравнение и АЛУ.