Аналогично вентиль ИЛИ с двумя инвертированными входами эквивалентен вентилю И-НЕ.
Выход равен 0, только если оба входа равны 1.
Эти две пары эквивалентных схем представляют электрическое воплощение законов Огастеса де Моргана, еще одного математика викторианской эпохи, который был на девять лет старше Буля. Его книга «Формальная логика» была опубликована в 1847 году, согласно преданию, в один день с книгой Буля «Математический анализ логики». На самом деле на занятия логикой Буля подвигла открытая вражда между де Морганом и другим британским математиком, связанная с обвинениями в плагиате (история оправдала де Моргана). С самого начала де Морган осознал важность прозрений Буля. Он бескорыстно поощрял Буля и помогал ему в исследованиях, однако сегодня он, к сожалению, почти забыт, а в памяти потомков остались только его знаменитые законы.
Законы де Моргана проще всего выразить следующим образом.
A и B — два булевых операнда. В первом выражении они инвертируются, а затем объединяются с помощью булева оператора И. Это эквивалентно объединению двух операндов с помощью булева оператора ИЛИ и последующему инвертированию результата (соответствует оператору ИЛИ-НЕ). Во втором выражении два оператора инвертируются, а затем объединяются с помощью булева оператора ИЛИ. Это эквивалентно объединению двух операндов с помощью булева оператора И и последующему инвертированию результата (соответствует оператору И-НЕ).
Законы де Моргана — важный инструмент для упрощения булевых выражений, а значит, для упрощения схем. История показала, что именно в этом заключалось значение работы Клода Шеннона для инженеров-электриков. Однако чрезмерное упрощение схем не является целью этой книги. Нам важно собрать работающую схему, а не сделать так, чтобы она работала как можно проще. Этим мы и займемся в следующей главе — соберем работающую счетную машину.
Глава 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-битным числом.
