Как работает логический сумматор: сумма и перенос

Как сложить 7 и 9 одними выключателями

Логические вентили складывают двоичные числа, формируя для каждого разряда бит суммы и бит переноса. Полный сумматор принимает также перенос из предыдущего разряда. В сумматоре с последовательным переносом каждый перенос должен пройти через вентили, прежде чем окончательный ответ установится.

На бумаге 7 + 9 занимает одну строку: 6 в единицах, 1 в переносе, ответ 16. У компьютера нет ни бумаги, ни представления о том, что такое число. Есть выключатели, которые включены или выключены. Как их совокупность получает 16 из 7 и 9?

Плата выше отвечает на этот вопрос слой за слоем, а затем показывает и другие схемы. Сначала открыт 4-битный сумматор с последовательным переносом: восемь выключателей вдоль переднего края задают A и B от 0 до 15, за ними стоят двадцать логических вентилей, а сзади пять светодиодов показывают результат. После переключения медные дорожки, передающие 1, светятся. Свет проходит через вентили со скоростью, заданной ползунком «Задержка вентиля». Панель в углу показывает входы и светодиоды одновременно в двоичной и десятичной записи.

Ползунок «Схема» выбирает одну из 15 схем на одинаковых микросхемах вентилей. Здесь есть отдельный вентиль, полусумматор, полный сумматор, 4-битный и 8-битный сумматоры с последовательным переносом, сумматор с упреждением переноса, сумматор-вычитатель, компаратор, мультиплексор, 7-сегментный дешифратор, SR-защёлка, D-триггер, счётчик, небольшое АЛУ и задача из четырёх NAND. Все используют одну симуляцию, поэтому можно сравнить число вентилей и время установления.

Числа из двух цифр

В десятичной записи каждый разряд в десять раз весомее правого соседа: единицы, десятки, сотни. В двоичной всё так же, только множитель равен двум. Веса разрядов составляют 1, 2, 4 и 8, поэтому четыре бита хранят любое число от 0 (0000) до 15 (1111). На плате A0 соответствует единицам, A3 восьмёркам. Маленькие числа под выключателями показывают их веса.

Семь равно 4 + 2 + 1, то есть 0111. Девять равно 8 + 1, то есть 1001. Их сумма 16 требует пятого разряда с весом 16, и ответ записывается как 10000. Этот пятый разряд представляет светодиод переноса C4. Если сумма больше 15, только он позволяет показать её полностью.

Двоичная запись удобна электронике: провод должен находиться лишь в одном из двух чётко различимых состояний. Не нужно отличать 3 вольта от 3,5 вольта, достаточно различать высокий и низкий уровни. Это гораздо легче надёжно повторять миллиарды раз в секунду.

Транзистор как переключатель

Для первого опыта выберите «Один вентиль» ползунком «Схема», затем «Провод» под моделью. Выключатель X соединяет светодиод с питанием через перемычку. Светодиод точно повторяет выключатель: 1 включает свет, 0 выключает.

При выборе «Транзистор» появляется NPN-транзистор с тремя выводами. Малый ток в средний вывод, базу, позволяет гораздо большему току течь между двумя другими, коллектором и эмиттером. Светодиод загорается. Без тока базы он гаснет. Получился переключатель, которым управляет электричество вместо пальца.

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

Вентили из пар транзисторов

Когда один переключатель управляет другим, можно строить логические решения. Современные микросхемы используют MOSFET двух типов. Транзисторы с n-каналом проводят при высоком входе, с p-каналом при низком. CMOS объединяет их так, что одна цепь поднимает выход к питанию, а другая опускает к земле. При любом входе проводит ровно одна цепь. Непереключающийся вентиль почти не потребляет ток. Это свойство, показанное Chih-Tang Sah и Frank Wanlass в Fairchild в 1963 году, позволяет телефону содержать миллиарды транзисторов и не плавиться.

Подсчёт транзисторов показывает, что стоимость вентилей различается:

AND, с которого обычно начинают знакомство, требует больше деталей, чем NAND. В CMOS естественны инвертирующие функции, поскольку n-канальная цепь тянет выход вниз. Два n-канальных транзистора последовательно делают это только при двух входных 1, что даёт NAND. Параллельное соединение даёт NOR. Для AND нужен ещё инвертор. «Транзисторы в микросхеме» показывает число на каждом корпусе, а «Один вентиль» позволяет перебрать все семь типов и простой провод.

У NAND есть ещё одно свойство. Только из NAND можно собрать NOT, соединив оба входа, AND из NAND и NOT, OR с предварительной инверсией обоих входов и любую другую функцию. На этом основана последняя задача: в лаборатории под управлением выбираются входы четырёх NAND. При правильном соединении выход совпадает с XOR во всех четырёх строках.

Полусумматор: XOR для суммы, AND для переноса

Посмотрим на таблицу XOR. В двоичной системе 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, а 1 + 1 = 10: в текущем разряде 0, в переносе 1. Правая цифра каждого ответа точно совпадает со столбцом XOR. Перенос равен 1 только в последней строке, что соответствует AND.

Значит, XOR и AND с одинаковыми двумя входными битами складывают их. Эта пара называется полусумматором. На его отдельной плате она стоит сама по себе, а в 4-битном сумматоре служит первым блоком каждого бита. При A = 1 и B = 1 XOR даёт сумму 0, AND перенос 1.

Полный сумматор: три бита на входе, два на выходе

Для единиц достаточно полусумматора, но в остальных разрядах нужно сложить три величины: бит A, бит B и перенос справа. Полный сумматор делает это двумя полусумматорами и OR. Для каждого бита на плате используются обозначения:

1. p = A xor B и g = A and B (первый полусумматор)
2. S = p xor C и t = p and C (второй полусумматор добавляет входной перенос C)
3. Выходной перенос = g or t

OR никогда не получает две единицы одновременно. Если A и B равны 1, p равен 0, и t не может быть 1. Он лишь объединяет два источника переноса: разряд создал его сам (g) или пропустил полученный перенос (t). Восемь строк таблицы полного сумматора охватывают все случаи. Максимум, 1 + 1 + 1 = 3, даёт перенос 1 и сумму 1.

Пять вентилей на бит при четырёх битах дают 20 вентилей 4-битного сумматора. Выходной перенос каждого полного сумматора соединён со входным переносом левого соседа, как перенос единицы при счёте на бумаге. Поэтому перенос называется последовательным. Во время работы таблица в углу отмечает используемую строку каждого бита: бит 0 может стоять на 1 1 0, пока бит 3 ждёт на 0 1 1.

Почему перенос медленный

Ни один вентиль не отвечает мгновенно. После изменения входов выход меняется чуть позже. Это время называется задержкой вентиля, или задержкой распространения. Модель задаёт каждому вентилю ровно одну единицу задержки, а ползунок растягивает её от 0,05 до 2,4 секунды для наблюдения.

Для 7 + 9, начиная с состояния 0 + 0, получается такая последовательность:

Каждому биту нужны две задержки для передачи переноса: одна у AND, создающего t, другая у OR, создающего выходной перенос. Через четыре бита последний перенос приходит после 8 задержек. Худший случай 4-битной платы требует 9, что соответствует 2n + 1 при n = 4 битах. «Задержка на микросхеме» показывает момент последней смены выхода. Вдоль цепочки переноса числа растут: 2, 4, 6, 8.

В течение этих 8 задержек видны неверные ответы. После задержки 6 панель может показать 01000, то есть 8. Ничего не сломалось: это сумма, вычисленная до прихода переноса. У настоящих схем тоже бывают краткие ложные выходы, называемые глитчами. Поэтому процессор ждёт фиксированное время прохождения самого медленного пути и лишь затем читает сумматор. Это ожидание влияет на тактовую частоту. «Временная диаграмма» показывает те же изменения как сигналы, поднимающиеся и опускающиеся до установления.

8-битная плата ясно показывает цену такой цепочки. Восемь полных сумматоров дают 40 вентилей. В 255 + 1 перенос проходит через каждый бит, и светодиоды устанавливаются после 16 задержек, вдвое позже, чем при 15 + 1 на 4-битной плате. Аналогичный 64-битный сумматор потребовал бы в худшем случае 129 задержек. Для пошагового просмотра служат «По одной задержке» и кнопка «Следующая задержка» под моделью.

Вычисление переносов заранее

Быстрые сумматоры не ждут последовательного переноса. Разряд сам создаёт перенос, когда g = A and B равен 1, и пропускает полученный, когда p = A xor B равен 1. Оба сигнала готовы во всех разрядах одновременно после одной задержки. Через них каждый перенос можно расписать полностью:

• C1 = g0 + p0 C0
• C2 = g1 + p1 g0 + p1 p0 C0
• C3 = g2 + p2 g1 + p2 p1 g0 + p2 p1 p0 C0
• C4 = g3 + p3 g2 + p3 p2 g1 + p3 p2 p1 g0 + p3 p2 p1 p0 C0

C2 означает перенос в бит 2, если бит 1 создал его, если бит 1 пропускает перенос от бита 0 или если биты 1 и 0 оба пропускают входной перенос. Каждая строка состоит из AND и следующего за ними OR. Поэтому все переносы приходят через три задержки, а суммы ещё через одну. Плата с упреждением использует 26 вентилей. Для 15 + 1 ей нужны 4 задержки вместо 8 у последовательной схемы. Таблица показывает P, G и перенос каждого бита.

Цена заключена в AND. Уже C4 требует AND и OR с 5 входами каждый. С ростом разрядности выражения удлиняются. Поэтому широкие сумматоры объединяют небольшие четырёхбитные блоки упреждения и второй уровень упреждения между ними. Gerald Rosenberger из IBM подал заявку на патент двоичного сумматора с упреждением переноса в 1957 году. Charles Babbage заметил ту же проблему столетием раньше и спроектировал предсказание переносов для своей аналитической машины. Сейчас 4-битный сумматор с быстрым переносом можно найти в каталоге: Texas Instruments по-прежнему предлагает SN74LS283.

Вычитание тем же сумматором

Компьютеру не обязателен отдельный вычитатель. В дополнительном коде, обычном представлении отрицательных чисел, минус B получается инверсией всех битов B и прибавлением 1. Поэтому A − B равно A + (not B) + 1.

Плата сумматора-вычитателя добавляет по XOR перед каждым битом B. При выключенном SUB он пропускает бит без изменения, при включённом инвертирует. Та же линия SUB подаёт входной перенос, добавляя 1. В примере 5 − 7 число B = 0111 превращается в 1000, сумматор вычисляет 0101 + 1000 + 1 = 1110. Как 4-битное число со знаком 1110 означает −2. Без знака это 14, что тоже верно в своём смысле: 5 − 7 + 16 = 14. Значение одних и тех же битов зависит от прочтения, и панель показывает оба варианта.

Число со знаком из 4 битов лежит лишь от −8 до 7, поэтому не все ответы помещаются. Зелёный светодиод V обнаруживает переполнение через XOR переноса в старший бит и переноса из него. При их различии он горит. 7 + 1 при выключенном SUB зажигает его: 0111 + 0001 = 1000 читается как −8. Дополнительный ряд XOR добавляет задержку в начале, вентиль V ещё одну в конце, и худший случай требует 11 задержек.

Сравнение двух чисел

Как схема решает, что 9 больше 5? Как при сравнении записанных чисел: по старшему различающемуся разряду. Компаратор делает это для каждого бита. A > B означает A = 1 и B = 0, то есть AND с инвертором на B. A < B означает обратное. Биты равны, если ни одно условие не выполнено; это NOR двух результатов.

Затем учитывается старшинство. A больше, если так говорит бит 3, либо бит 3 равен, а бит 2 говорит «больше», либо биты 3 и 2 равны, а бит 1 говорит «больше», и так далее. Четыре AND объединяет OR, как в упреждении переноса. 1001 и 0101 впервые различаются в бите 3, где у A единица. Светодиод A > B загорается после 4 задержек; худший случай требует 5. Плата использует 29 вентилей. TI SN74LS85 делает то же в одном корпусе и имеет дополнительные входы для сравнения длинных чисел несколькими микросхемами.

Выбор входа и построение цифры

Ещё две схемы используют AND, объединённые через OR.

Мультиплексор выбирает. Плата 4 к 1 имеет четыре входа данных D0 до D3 и два бита выбора. Каждый вход данных идёт в AND с 3 входами, принимающий также биты выбора или их инверсии. При любой настройке открыт ровно один AND, и OR передаёт его бит в Y. Семь вентилей, три задержки. От регистрового файла процессора до переключателя источника телевизора мультиплексор встречается везде, где один провод должен нести один из нескольких сигналов.

Дешифратор рисует. У 7-сегментного индикатора семь светодиодных полосок от a до g. Каждая цифра зажигает свой набор: 1 включает b и c, 8 все семь. Для каждого сегмента можно перечислить включающие его цифры и упростить список до суммы произведений, нескольких AND, объединённых OR. Именно так рассчитан дешифратор платы: 4 инвертора, 28 общих AND и 7 OR, всего 39 вентилей и три задержки от выключателя до сегмента. Кроме 0 до 9 он рисует шестнадцатеричные A до F. TI SN74LS47 представляет серийный вариант для 0 до 9.

Схемы, которые помнят

Все предыдущие схемы забывают. Меняются выключатели, следом меняется выход; прошлое ни на что не влияет. Для памяти нужна петля.

SR-защёлка состоит из двух NOR, выход каждого подан на другой. При S = 0 и R = 0 петля хранит прежнее Q = 1 или Q = 0, пока есть питание. Единица на S принудительно ставит Q в 1, на R в 0. После установки Q можно выключить S, и Q останется 1. Это один бит памяти из восьми транзисторов.

У защёлки есть запрещённый вход. При S = 1 и R = 1 оба выхода равны 0. Если одновременно убрать оба сигнала, вентили вступают в гонку. В модели с одинаковыми задержками петля никогда не устанавливается: выходы одновременно меняются при каждой задержке, о чём сообщает панель. Реальная защёлка не бывает идеально симметричной, поэтому одна сторона побеждает. Но какая и через какое время, предсказать нельзя. Это называют метастабильностью, и цифровые устройства проектируют так, чтобы избежать её в нормальной работе.

D-триггер устраняет проблему, принимая данные только в один момент. На плате используется схема из шести NAND, как в микросхеме 7474. Пока такт низкий или высокий, D может меняться сколько угодно без изменения Q. Только при росте CLK с 0 до 1 Q принимает D и хранит его до следующего нарастающего фронта. В 49 152 случайных шагах D и CLK это правило соблюдалось каждый раз.

Подсчёт тактовых импульсов

Поставим рядом четыре триггера, добавим небольшую схему для текущего числа плюс один и вернём результат на входы D. Каждый тактовый импульс загружает следующее число. 4-битный счётчик делает это 30 вентилями: 24 NAND в четырёх триггерах и шестью вентилями сумматора. Бит 0 меняется всегда; бит 1, когда бит 0 равен 1; бит 2, когда биты 1 и 0 равны 1; бит 3, когда все три младших бита равны 1.

Кнопка «Тактовый импульс» показывает порядок. Фронт приходит ко всем четырём триггерам одновременно. Их выходы меняются через две задержки, а схема прибавления единицы готовит следующее число задолго до нового импульса. Все биты меняются по одному фронту, поэтому счётчик называется синхронным, как TI SN74LS161A. После 1111 он возвращается к 0000. За 40 импульсов он без ошибок прошёл от 0 до 15 и снова по кругу.

АЛУ из тех же деталей

Арифметико-логическое устройство процессора выполняет сами вычисления. 4-битное АЛУ показывает принцип на 59 вентилях. Для каждого бита параллельно вычисляются A + B, A − B, A AND B и A OR B. Два бита операции выбирают результат через те же AND и OR, что в мультиплексоре. Код 00 складывает, 01 вычитает с рядом XOR сумматора-вычитателя, 10 выполняет AND, 11 выполняет OR.

Все четыре результата вычисляются постоянно; биты операции только выбирают видимый. Так работают и настоящие АЛУ. Поэтому длиннейший путь, здесь 13 задержек, длиннее пути отдельного сумматора. В 12 AND 10 записи 1100 и 1010 имеют общую единицу только в бите 3. Ответ 1000, то есть 8.

Сколько длится задержка вентиля?

Модель считает задержки, а реальные детали измеряют их в наносекундах. Texas Instruments указывает типичную задержку NAND SN74HC00 при 4,5 V как 9 ns, старого SN74LS00 как 9 до 10 ns, а SN74AC00 при 5 V примерно 5 ns. Реле медленнее в миллион раз: документация Omron G5V-1 допускает время срабатывания до 5 ms.

Умножим это на длиннейший путь. 4-битному сумматору с последовательным переносом нужны 9 задержек. С вентилями типа 74HC00 он установится примерно за 81 ns, чего хватает для двенадцати миллионов сложений в секунду. С реле той же схеме нужны 45 ms. Лаборатория под управлением рассчитывает это для выбранной платы. Современный процессор складывает 64-битные числа миллиарды раз в секунду потому, что его вентили быстрее в тысячи раз, а сумматоры используют упреждение, а не потому, что логика стала другой.

Проверка каждой схемы

Каждую схему сверили с таблицей истинности для всех возможных входов. 4-битный сумматор выдавал A + B + C0 для всех 512 комбинаций и устанавливал правильный ответ за 9 задержек после каждого из 262 144 возможных изменений входа. 8-битный проверили на всех 131 072 суммах и 400 000 случайных изменениях. Сумматор с упреждением устанавливался за 4 задержки, сумматор-вычитатель за 11, компаратор за 5, мультиплексор и дешифратор за 3. АЛУ укладывалось в 13 после каждого из 1 048 576 изменений. Для памяти проверяли последовательности: установку, хранение и сброс защёлки, случайные такт и данные триггера, 40 импульсов счётчика.

На плате можно повторить несколько примеров:

• 15 + 1 на последовательном сумматоре: все четыре переноса проходят цепочку, и через 8 задержек светодиоды показывают 10000.
• 15 + 1 на сумматоре с упреждением: тот же ответ через 4 задержки.
• 5 + 2: переносов нет, ответ 0111 (7) готов через 2 задержки.
• 5 − 7 на сумматоре-вычитателе: 1110, то есть −2.

Чем модель отличается от настоящей микросхемы

• Все вентили имеют одинаковую задержку. В реальности XOR медленнее NAND, вентиль с большим числом подключённых входов медленнее нагруженного одним входом, а задержки зависят от температуры и питания.
• Каждый провод проходится за 0,85 задержки вентиля независимо от длины. Короткие дорожки реальной платы практически мгновенны, а внутри микросхемы длинные провода могут быть медленнее вентилей.
• Сигналы идеально равны 0 или 1. Реальные напряжения нарастают и спадают за некоторое время; здесь нет шума, нагрева и ограничений нагрузочной способности.
• На микросхему приходится один вентиль. Реальные корпуса содержат четыре NAND или шесть инверторов. Им нужны выводы питания, развязывающие конденсаторы и подтягивающие резисторы, которых здесь нет.
• Транзистор на стенде изображён одиночным биполярным переключателем, а число транзисторов на микросхемах рассчитано для CMOS.

От алгебры Boole к релейным сумматорам

В 1854 году George Boole опубликовал The Laws of Thought. В этой алгебре логические утверждения соединяются операциями, похожими на умножение и сложение, а символы 1 и 0 играют особую роль. Книга была о рассуждении, а не о машинах.

Связь со схемами появилась в 1937 году. Магистрант MIT Claude Shannon написал A Symbolic Analysis of Relay and Switching Circuits. Он показал, что последовательные и параллельные выключатели подчиняются правилам алгебры Boole. Поэтому схемы можно проектировать и упрощать алгебраически, а не подбором. В последней главе были примеры, включая двоичный сумматор. Статья на основе работы вышла в Transactions of the American Institute of Electrical Engineers в 1938 году и получила Alfred Noble Prize.

В том же году сотрудник Bell Labs George Stibitz собрал демонстрационный сумматор из реле. Он назвал его Model K в честь кухонного стола, на котором собирал. Десять лет спустя, в декабре 1947 года, John Bardeen и Walter Brattain в группе William Shockley в Bell Labs создали первый работающий транзистор. Все трое разделили Нобелевскую премию по физике 1956 года за исследования полупроводников и открытие транзисторного эффекта.

От реле к миллиардам транзисторов

Первые большие компьютеры использовали доступные переключатели. Z3, созданный Konrad Zuse в 1941 году, имел 2300 реле. Harvard Mark 1, законченный в 1944 году, использовал 3500, синхронизируемых кулачковым валом длиной пятьдесят футов. Colossus работал в Bletchley Park с начала 1944 года на 2500 электронных лампах. ENIAC, представленный в University of Pennsylvania в феврале 1946 года, требовал 18 000 вакуумных ламп и занимал комнату 30 на 50 футов, примерно 9 на 15 метров. TX-0 из MIT 1956 года стал первым универсальным программируемым компьютером на транзисторах. Каждый помещался во вставную «бутылочку» для замены, как у лампы.

Затем вентили перешли на кремний. В 1961 году Fairchild объявила одну из первых планарных интегральных схем: триггер с четырьмя транзисторами и пятью резисторами. Серия TTL-логики 7400 компании Texas Instruments продавалась в дешёвых пластиковых корпусах с 1966 года и вскоре заняла более половины рынка логики. Многие детали, например четыре NAND в SN7400, продаются до сих пор. Apollo Guidance Computer впервые полетел на Apollo 7 в 1968 году. Он был построен в основном из одного типа микросхемы с двумя NOR по 3 входа, по несколько тысяч на компьютер.

В 1965 году Gordon Moore предсказал ежегодное удвоение числа компонентов на кристалле, позже изменив срок на два года. Intel 4004 в 1971 году разместил целый 4-битный процессор с 2300 транзисторами на одном кристалле. Хронология Computer History Museum указывает 2250. Apple M1 2020 года содержит 16 миллиардов, примерно в семь миллионов раз больше, а графические процессоры NVIDIA Blackwell 2024 года содержат 208 миллиардов. Внутри них арифметику по-прежнему выполняют сумматоры, мультиплексоры и триггеры, подобные показанным на плате.