Сначала подключим два крайних правых переключателя и крайнюю правую лампочку к полному сумматору.
Когда вы начинаете складывать два двоичных числа, первый столбец цифр отличается от остальных тем, что не может содержать бит переноса из предыдущего столбца. В первом столбце нет бита переноса, поэтому вход для переноса полного сумматора соединяется с землей, то есть его значением является 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 транзистора (или больше, если вы хотите заменить сквозной перенос схемой ускоренного переноса), однако при этом размер схемы микроскопический.
Глава 13А как насчет вычитания?
Убедившись в том, что реле действительно можно соединить для сложения двоичных чисел, зададимся вопросом: «А как насчет вычитания?» Не бойтесь показаться смешным, задавая его. На самом деле вы довольно проницательны. Сложение и вычитание в некотором смысле дополняют друг друга, однако механика у этих операций разная. Сложение предполагает последовательное продвижение от крайнего правого столбца цифр до крайнего левого. Каждое значение, перенесенное из одного столбца, прибавляется к следующему. При вычитании мы ничего не переносим; мы заимствуем, а это действие предполагает использование довольно запутанного механизма.
Давайте рассмотрим типичную задачу на вычитание с заимствованием.
Начнем решение с крайнего правого столбца. Сначала мы замечаем, что 6 больше 3, поэтому нам нужно занять 1 у 5, а затем вычесть 6 из 13, в результате чего получается 7. Мы помним, что заняли 1 у 5, поэтому вместо 5 имеем 4, что меньше 7, поэтому занимаем 1 у 2, вычитаем 7 из 14 и получаем 7. Мы заняли 1 у 2, поэтому у нас есть только единица, из которой вычитаем 1 и получаем 0. Наш ответ — 77.
Как же заставить группу логических вентилей следовать такой странной логике?
Не будем даже пытаться. Вместо этого используем небольшой трюк, позволяющий вычитать без заимствования. Это порадовало бы Полония («Не занимай и не ссужай») и всех остальных. Кроме того, подробное рассмотрение процесса вычитания полезно, поскольку напрямую связано с использованием двоичных кодов для хранения в компьютерах отрицательных чисел.
Числа, участвующие в операции вычитания, называются уменьшаемым и вычитаемым. Вычитаемое вычитается из уменьшаемого, результатом является разность.
Чтобы произвести вычитание без заимствования, сначала нужно вычесть вычитаемое из 999, а не из уменьшаемого.
В данном случае используем число 999, поскольку числа, участвующие в операции, состоят из трех цифр. Если бы они были четырехзначными, мы бы использовали число 9999. При вычитании числа из строки девяток получаем число, называемое дополнением до девяти. Дополнение числа 176 до девяти — 823. Это работает и в обратную сторону: дополнение числа 823 до девяти — 176. Вся прелесть в том, что вне зависимости от значения вычитаемого вычисление его дополнения до девяти никогда не требует заимствования.
После вычисления дополнения вычитаемого до девяти нужно прибавить к нему исходное уменьшаемое.
Наконец, прибавить 1 и вычесть 1000.
Вот и всё. Мы получили такой же результат, как и раньше, ни разу не прибегнув к заимствованию.
Почему это работает? Исходная задача на вычитание такова:
253 – 176.
Если к этому выражению прибавить и вычесть любое число, результат останется прежним. Так что давайте прибавим и вычтем 1000:
253 – 176 + 1000 – 1000.
Выражение эквивалентно следующему:
253 – 176 + 999 + 1 – 1000.
Теперь числа можно перегруппировать:
253 + (999 – 176) + 1 – 1000.
Это соответствует вычислению, которое я продемонстрировал с использованием дополнения до девяти. Мы заменили одно вычитание двумя вычитаниями и двумя сложениями, избавившись при этом от всех нежелательных заимствований.
А если вычитаемое больше уменьшаемого? Рассмотрим такой пример.
Обычно вы смотрите на подобную задачу и думаете: «Хм, вычитаемое больше уменьшаемого, поэтому придется поменять числа местами, выполнить вычитание и не забыть о том, что результат будет отрицательным». Вы можете произвести перестановку чисел в голове и записать ответ следующим образом.
Процесс выполнения данного расчета без заимствований несколько отличается от предыдущего примера. Как и раньше, мы начинаем с вычитания вычитаемого (253) из 999 для получения дополнения до девяти.
Теперь прибавим дополнение до девяти к исходному уменьшаемому.
На этом этапе в более раннем примере для получения окончательного результата мы могли прибавить 1 и вычесть 1000. Однако в данном случае эта стратегия не сработала бы, поскольку нам пришлось бы вычесть 1000 из 923, что в действительности потребовало бы вычесть 923 из 1000, и без заимствований мы бы не обошлись.
Вместо этого, по аналогии с прибавлением 999, вычтем 999.
Сразу становится очевидным, что наш ответ будет отрицательным, поэтому следует поменять числа местами и вычесть 922 из 999. Это опять же не требует заимствований, а ответ совпадает с ожидаемым.
Этот метод применим и к двоичным числам, работать с которыми оказывается проще, чем с десятичными. Давайте посмотрим, как это работает.
Вот исходная задача на вычитание.
После преобразования чисел в двоичные получаем следующую задачу.
Шаг 1. Вычесть вычитаемое из 11111111 (что соответствует 255).
При работе с десятичными числами вычитаемое вычиталось из строки девяток, а результат назывался дополнением до девяти. При работе с двоичными числами вычитаемое вычитается из строки единиц, результат — дополнение до единицы. Заметьте, что нам на самом деле не нужно выполнять вычитание, чтобы вычислить дополнение до единицы, поскольку каждый 0 в исходном числе превращается в 1 в дополнении до единицы, а каждая 1 превращается в 0. По этой причине дополнение до единицы иногда также называется отрицанием или инверсией. (Сейчас вы, вероятно, вспомнили о том, что в главе 11 мы конструировали устройство, называемое инвертором, которое меняло 0 на 1, а 1 на 0.)
Шаг 2. Прибавить дополнение вычитаемого до единицы к уменьшаемому.
Шаг 3. Прибавить к результату 1.
Шаг 4. Вычесть 100000000 (что соответствует 256).
Результат эквивалентен десятичному числу 77.
Давайте попробуем еще раз, поменяв числа местами. В десятичной системе счисления задача на вычитание выглядит так.
В двоичной системе — так.
Шаг 1. Вычесть вычитаемое из 11111111, чтобы получить дополнение до единицы.
Шаг 2. Прибавить дополнение вычитаемого до единицы к уменьшаемому.
Теперь нужно как-то вычесть из результата число 11111111. Когда исходное вычитаемое меньше уменьшаемого, для этого достаточно прибавить 1 и вычесть 100000000. Однако эту операцию нельзя выполнить без заимствования. Вместо этого мы вычитаем результат из числа 11111111.