Глава 12 Двоичный сумматор

Сложение — простейшая арифметическая операция. Если мы хотим создать компьютер (а именно в этом заключается цель этой книги), сначала нужно найти способ создания устройства, складывающего два числа. По сути, компьютеры выполняют только операцию сложения. Если нам удастся сконструировать механизм, умеющий складывать, мы окажемся способны создать устройство, использующее операцию сложения для того, чтобы вычитать, умножать, делить, рассчитывать платежи по ипотеке, отправлять ракеты на Марс, играть в шахматы и вносить путаницу в наши телефонные счета.

Сумматор, который мы построим, будет большим, нескладным, медленным и шумным по сравнению с современными калькуляторами и компьютерами. Самое интересное заключается в том, что мы соберем эту машину из простых электрических устройств, о которых говорили в предыдущих главах, — переключателей, лампочек, проводов, батарейки и реле, объединенных в различные логические вентили. Этот сумматор будет состоять исключительно из деталей, которые уже были изобретены 120 лет назад. Особенно хорошо то, что нам не нужно ничего собирать в своей гостиной; вместо этого мы можем конструировать на бумаге и в уме.

Эта машина будет работать исключительно с двоичными числами, в ней будут отсутствовать некоторые современные функции. Вы не сможете использовать клавиатуру для ввода чисел, подлежащих сложению; вместо этого будет ряд переключателей. Роль дисплея для отображения результатов в этом сумматоре исполнит ряд лампочек.

Однако машина сумеет сложить два числа, и она сделает это фактически как компьютер.

Сложение двоичных чисел похоже на сложение десятичных. Если хотите сложить два десятичных числа, например 245 и 673, вы разбиваете задачу на более простые этапы. На каждом этапе складываете две десятичные цифры. В данном примере начинаете со сложения 5 и 3. Эта задача решается быстрее, если вы знаете таблицу сложения.

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

Если вы выросли среди дельфинов, вероятно, вы в школе учили эту таблицу, громко произнося:

0 плюс 0 равно 0,

0 плюс 1 равно 1,

1 плюс 0 равно 1,

1 плюс 1 равно 0, 1 в уме.

Вы можете добавить в эту таблицу нули так, чтобы каждый результат представлял 2-битное значение.

Таким образом, результатом сложения пары двоичных чисел являются два бита, которые называются разрядом суммы и разрядом переноса (1 плюс 1 равно 0, 1 в уме). Теперь мы можем разделить таблицу сложения двоичных чисел на две таблицы. Первая — для разряда суммы.

Вторая — для разряда переноса.

Сложение двоичных чисел удобно рассматривать так, поскольку наш сумматор выполняет операции суммирования и переноса отдельно. Для создания двоичного сумматора потребуется сконструировать схему, выполняющую эти операции. Работа исключительно в двоичной системе счисления значительно упрощает задачу, поскольку все части схемы — переключатели, лампочки и провода — могут представлять двоичные цифры.

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

Обратите внимание: при сложении значений в третьем столбце справа 1 переносится в следующий столбец. Это происходит снова в шестом, седьмом и восьмом столбцах справа.

Какого размера двоичные числа мы хотим сложить? Поскольку мы создаем сумматор прямо в уме, то можем сделать так, чтобы он складывал очень длинные числа. Однако давайте будем благоразумными и ограничимся двоичными числами длиной до восьми бит, то есть будем складывать двоичные числа в диапазоне от 0000 0000 до 1111 1111 (десятичные от 0 до 255). Сумма двух 8-битных чисел может достигать двоичного значения 1 1111 1110 (десятичного значения 510).

Пульт управления нашим двоичным сумматором может выглядеть так.

На этом пульте есть два ряда по восемь переключателей. Этот набор переключателей — устройство ввода, которое мы будем использовать для ввода двух 8-битных значений. В этом устройстве выключенный переключатель (положение вниз) соответствует значению 0, а включенный (положение вверх) — 1, как в случае с настенными переключателями в вашем доме. Устройство вывода в нижней части пульта — ряд из девяти лампочек, которые отобразят результат сложения. Негорящая лампочка соответствует значению 0, горящая — 1. Нам требуется девять лампочек, поскольку сумма двух 8-битных чисел может быть 9-битным числом.

В остальном сумматор будет состоять из логических вентилей, соединенных различными способами. Переключатели будут активировать реле в логических вентилях, которые, в свою очередь, будут зажигать нужные лампочки. Например, если мы хотим сложить числа 0110 0101 и 1011 0110 (из предыдущего примера), включаем соответствующие переключатели.

Загоревшиеся лампочки показывают результат: 1 0001 1011. По крайней мере, мы на это надеемся. Мы ведь еще не собрали устройство!

В предыдущей главе я упомянул, что в этой книге буду использовать множество реле. Для 8-битного сумматора, который мы создаем, требуется не менее 144 реле — по восемнадцать для каждой из восьми пар битов, которые складываем. Если бы я показал готовую схему, вы бы наверняка испугались. Никому не под силу разобраться в схеме, состоящей из ста сорока четырех хитро соединенных реле. Вместо этого мы будем решать такую задачу поэтапно, используя логические вентили.

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

Вероятно, вы узнали в ней результат работы вентиля И.

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

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

Это вторая часть задачи при сложении пары двоичных цифр. Вычислить значение разряда суммы оказывается не так просто, как значение разряда переноса, но мы справимся и с этой сложностью.

Первое, что нужно понять, — это то, что результат работы вентиля ИЛИ близок к тому, что нам нужно, за исключением значения в правом нижнем углу.

Результат работы вентиля И-НЕ также близок к тому, что нам требуется, за исключением значения в верхнем левом углу:

Итак, давайте подключим вентили ИЛИ и И-НЕ к одним и тем же входам.

В следующей таблице представлены выходные сигналы вентилей ИЛИ и И-НЕ и их сравнение с тем, что мы хотим получить от сумматора.

Заметьте, что мы хотим получить значение 1, только если выходные сигналы обоих вентилей ИЛИ и И-НЕ равны 1. Это говорит о том, что эти два выходных сигнала могут являться входными сигналами для вентиля И.

То, что нужно.

Обратите внимание: во всей этой схеме по-прежнему есть только два входа и один выход. Два входа относятся к обоим вентилям ИЛИ и И-НЕ. Выходные сигналы вентилей ИЛИ и И-НЕ подаются на вход вентиля И, и это дает именно тот результат, к которому мы стремимся.

На самом деле у этой схемы есть название: вентиль исключающее ИЛИ (Искл-ИЛИ, оно же — сложение по модулю 2). Она называется так потому, что выход равен 1, если вход A равен 1 или вход B равен 1, но не оба одновременно. Вместо того чтобы рисовать вентили ИЛИ, И-НЕ и И, мы можем использовать обозначение, которым инженеры-электрики показывают вентиль Искл-ИЛИ.

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

Вентиль Искл-ИЛИ — это последний логический элемент, который будет подробно описан в этой книге. Иногда в электротехнике используется шестой вентиль, называющийся вентилем совпадения или эквивалентности, поскольку выход равен 1 только при одинаковых сигналах на входе. Вентиль совпадения на выходе действует противоположно вентилю Искл-ИЛИ, поэтому его обозначение аналогично обозначению вентиля Искл-ИЛИ, но дополнено кружком со стороны выхода[17].

Давайте повторим все, что уже знаем. При сложении двух двоичных чисел получается бит суммы и бит переноса.

Для получения этих результатов можно использовать следующие два вентиля.

Разряд суммы двух двоичных чисел задается выходом вентиля Искл-ИЛИ, а разряд переноса — выходом вентиля И, поэтому можно комбинировать вентили И и Искл-ИЛИ для сложения двух двоичных цифр A и B.

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

Существует причина, по которой эта схема называется полусумматором. Разумеется, она складывает две двоичные цифры и выдает бит суммы и бит переноса. Однако длина подавляющего большинства двоичных чисел превышает один бит. То, что полусумматор не может сделать, так это прибавить возможный бит переноса, получившийся в результате предыдущей операции сложения. Представьте, что складываем два двоичных числа.

Мы можем использовать полусумматор только для сложения цифр в правом крайнем столбце: 1 плюс 1 равно 0, 1 переносится. В случае со вторым столбцом справа нам, по сути, нужно сложить три двоичные цифры из-за переноса. И это касается всех остальных столбцов. Каждая последующая операция сложения двух двоичных цифр может включать бит переноса из предыдущего столбца.

Для сложения трех двоичных цифр понадобятся два полусумматора и вентиль ИЛИ, соединенные следующим образом.

Чтобы разобраться в этой схеме, начнем со входов A и B первого полусумматора слева. Результат — бит суммы и бит переноса. Эта сумма должна быть добавлена к переносу из предыдущего столбца, поэтому они являются входами для второго полусумматора. Сумма, полученная от второго полусумматора, — окончательная. Два переноса из полусумматоров — входы для вентиля ИЛИ. Может показаться, что здесь нужен второй полусумматор, и такая схема, безусловно, сработала бы. Однако если вы проанализируете все возможности, то обнаружите, что оба переноса из двух полусумматоров никогда не равны 1. Вентиля ИЛИ достаточно для их сложения, поскольку он действует так же, как вентиль Искл-ИЛИ, если оба входных сигнала одновременно не равны 1.

Вместо многократного перерисовывания этой схемы можем просто назвать ее полным сумматором.

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

В начале этой главы я сказал, что для создания сумматора потребуются 144 реле. Вот как я это понял: для каждого вентиля И, ИЛИ и И-НЕ требуются по два реле. Таким образом, вентиль Искл-ИЛИ состоит из шести реле. Полусумматор — это вентиль Искл-ИЛИ и вентиль И, поэтому для его создания необходимы восемь реле. Каждый полный сумматор — два полусумматора и вентиль ИЛИ, то есть 18 реле. Нам нужны восемь полных сумматоров для создания 8-битной машины, или 144 реле.

Вспомните наш исходный пульт управления с переключателями и лампочками.

Теперь мы можем начать присоединять переключатели и лампочки к полному сумматору.

Сначала подключим два крайних правых переключателя и крайнюю правую лампочку к полному сумматору.

Когда вы начинаете складывать два двоичных числа, первый столбец цифр отличается от остальных тем, что не может содержать бит переноса из предыдущего столбца. В первом столбце нет бита переноса, поэтому вход для переноса полного сумматора соединяется с землей, то есть его значением является 0 бит. Разумеется, в результате сложения первой пары двоичных цифр может получиться бит переноса. Этот выход переноса — вход для следующего столбца.

Для следующих двух цифр и лампочки вы используете полный сумматор, подключенный так.

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

Наконец, восьмая и последняя пара переключателей подключена к последнему полному сумматору.

Здесь последний выход для переноса подключен к девятой лампочке.

Вот еще один способ изобразить схему из восьми полных сумматоров (full adder, FA), в которой каждый выход для переноса (CO) подключен к следующему входу для переноса (CI).

Представим единое обозначение 8-битного сумматора, входы обозначим буквами от A0 до A7 и от B0 до B7, выходы — буквами от S0 до S7 (от sum — «сумма»).

Это распространенный способ обозначения отдельных битов многобитного числа. Биты A0, B0 и S0 являются младшими, а биты A7, B7 и S7 — старшими. Например, вот как с помощью этих букв с индексами можно было бы представить двоичное число 0110 1001.

Индексы начинаются с 0 и увеличиваются по мере перехода ко все более значимым цифрам, поскольку они соответствуют показателю степени двойки.

Если вы умножите каждую степень двойки на цифру, расположенную под ней, и сложите результаты, получите десятичный эквивалент числа 0110 1001, который равен 64 + 32 + 8 + 1, или 105.

По-другому 8-битный сумматор можно изобразить так.

Восьмерки внутри стрелок указывают на то, что каждая из них — это группа из восьми отдельных сигналов. Индексы символов A7 … A0, B7 … B0 и S7 … S0 также обозначают восьмиразрядность числа.

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

Выход для переноса правого сумматора связан со входом для переноса левого. Левый сумматор в качестве входных значений принимает самые старшие восемь цифр двух слагаемых и в качестве выходного значения выдает самые старшие восемь цифр.

Теперь вы можете спросить: «Неужели компьютеры действительно складывают числа именно так?»

В принципе да. Но не совсем.

Во-первых, сумматоры могут быть быстрее тех, которые мы описали. Если вы посмотрите на то, как работает эта схема, то поймете, что выход переноса от младшей пары цифр необходим для сложения со следующей парой, выход переноса от второй пары цифр — для сложения с третьей парой и т. д. Общая скорость сумматора равна количеству битов, умноженному на скорость одного полного сумматора. Это называется сквозным переносом. Быстрые сумматоры используют дополнительные схемы ускоренного переноса.

Во-вторых (и это самое главное), компьютерам больше не нужно реле! Однако первые цифровые компьютеры, созданные в начале 1930-х годов, использовали реле, позднее — вакуумные лампы. Современные компьютеры создаются на основе транзисторов. Транзисторы в основном функционируют так же, как и реле, однако (как мы увидим далее) они намного быстрее, компактнее, тише, дешевле и потребляют гораздо меньше энергии. Для построения 8-битного сумматора по-прежнему требуются 144 транзистора (или больше, если вы хотите заменить сквозной перенос схемой ускоренного переноса), однако при этом размер схемы микроскопический.