Москва 2001 г тайный язык информатики Чарльз Петцольд ббк 32. 973. 26–018

154

Глава двенадцатая

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

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

Роль дисплея для отображения результата будет играть ряд

лампочек.

И все же эта машина будет находить сумму двух чисел,

причем почти так же, как это происходит в современном ком-

пьютере.

Сложение двоичных чисел очень похоже на сложение де-

сятичных. Чтобы сложить два десятичных числа, например,

245 и 673, вы разбиваете задачу на несколько простых шагов.

На каждом шаге требуется сложить две десятичных цифры. В

данном примере суммирование начинается с цифр 5 и 3. Сде-

лать это гораздо проще, если вы на каком-то жизненном этапе

выучили таблицу сложения.

Важное различие между десятичными и двоичными чис-

лами в том, что таблица сложения для двоичных чисел значи-

тельно проще аналогичной таблицы для десятичных чисел.

+

0

1

0

0

1

1

1

10

Если бы вы учились в дельфиньей школе, вам пришлось бы

учить именно эту таблицу. Вы, наверное, читали бы ее вслух,

хором.

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

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

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

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

Можно переписать эту таблицу с дополнительным нуля-

ми, чтобы каждый результат был двухбитовой величиной.

+

0

1

0

00

01

1

01

10

Результат сложения пары двоичных чисел, представленный

подобным образом, содержит 2 бита: разряд суммы (sum bit) и

разряд переноса (carry bit). Теперь можно разделить таблицу

155

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

сложения двоичных чисел на две, первая из которых предназ-

начена для разряда суммы.

+ сумма

0

1

0

0

1

1

1

0

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

+ перенос

0

1

0

0

0

1

0

1

Двоичное сложение удобно рассматривать именно с такой точ-

ки зрения, так как в нашем сумматоре суммы и переносы бу-

дут вычисляться раздельно. Построение сумматора состоит в

проектировании схемы, которая выполняла бы эти операции.

Работа в двоичной системе здорово упрощает нашу задачу, так

как все части схемы — переключатели, лампочки и провода —

могут символизировать двоичные разряды.

Как и в десятичном сложении, мы будем складывать циф-

ры столбец за столбцом, начиная с крайнего правого:

01100101

+10110110

100011011

Заметьте, что при сложении цифр в третьем столбце спра-

ва 1 переносится в следующую колонку. То же самое происхо-

дит в шестом, седьмом и восьмом столбцах справа.

Какого размера двоичные числа мы собираемся складывать?

Конечно, воображаемый сумматор в принципе способен скла-

дывать числа любой разрядности. Но давайте ограничимся

разумной длиной и будем складывать числа не длиннее 8 би-

тов, т. е. в диапазоне от 0000-0000 до 1111-1111, или в десятич-

ном выражении от 0 до 255. Сумма двух 8-битовых чисел мо-

жет достигать значения 1-1111-1110, или 510.

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

примерно так.

156

Глава двенадцатая

1

0

1

0

На пульте размещены два ряда переключателей по 8 в каж-

дом. Это устройство ввода, которое мы будем использовать

для ввода 8-разрядных чисел. В нем нижнее положение пере-

ключателя (выключен) соответствует вводу 0, а верхнее (вклю-

чен) — вводу 1. Устройство вывода в виде ряда из 9 лампочек

находится в нижней части пульта. Эти лампочки будут пока-

зывать ответ. Горящая лампочка соответствует 1, выключен-

ная — 0. Нам нужны 9 лампочек, так как сумма двух 8-разряд-

ных чисел может быть 9-разрядным числом.

В остальном сумматор состоит из логических вентилей,

соединенных разными способами. Переключатели будут вы-

зывать срабатывание реле в логических вентилях, которые

подадут питание на нужные лампочки. Например, чтобы сло-

жить 0110-0101 и 1011-0110, мы включим переключатели, как

показано на рисунке.

1

0

1

0

Горящие лампочки показывают ответ — 1-0001-1011 (пока

примем его на веру — ведь мы еще ничего не собирали!).

Я говорил в предыдущей главе, что намерен в этой книге

активно использовать реле. Создаваемый нами 8-разрядный

сумматор будет состоять из 144 реле, по 18 для каждой из 8 пар

157

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

битов, которые мы будем складывать. Если бы я показал вам

схему соединений всех этих реле, вы определенно посинели бы.

Нет абсолютно никакой надежды, что кто-то сумеет разобрать-

ся в хитросплетениях схемы, состоящей из 144 реле. Чтобы не

сойти с ума до срока, мы предпримем модульный подход к ре-

шению этой проблемы, а помогут нам логические вентили.

Вполне вероятно, что вы уже увидели связь между логи-

ческими вентилями и двоичным сложением. Для этого доста-

точно взглянуть на таблицу переноса разряда при сложении

двух однобитовых чисел.

+ перенос

0

1

0

0

0

1

0

1

Она ведь совершенно идентична таблице с результатами ра-

боты вентиля И, описанного в предыдущей главе.

И

0

1

0

0

0

1

0

1

Итак, вентиль И считает перенос разряда при сложении двух

двоичных цифр.

Ага! Мы подбираемся к сути. Очередной шаг состоит, ви-

димо, в проверке, ведут ли себя какие-нибудь реле следующим

образом:

+ сумма

0

1

0

0

1

1

1

0

Это вторая часть задачи сложения пары двоичных цифр. Раз-

ряд суммы получается не столь прямолинейно, как разряд пе-

реноса, но в дальнейшем мы решим и эту проблему.

Для начала сообразим, что вентиль ИЛИ дает почти то, что

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

ИЛИ

0

1

0

0

1

1

1

1

158

Глава двенадцатая

Результат действия вентиля И-НЕ тоже близок к нашим по-

требностям, кроме верхней левой ячейки таблицы.

И-НЕ

0

1

0

1

1

1

1

0

Подключим к одним и тем же входам вентиль ИЛИ и вен-

тиль И-НЕ.

Выход ИЛИ

Выход И-НЕ

Вход А

Вход В

В следующей таблице возможные сигналы на выходах со-

единенных вентилей ИЛИ и И-НЕ сравниваются с тем, что

нужно для сумматора.

Вход А

Вход В Выход ИЛИ

Выход И-НЕ

Что нужно

0

0

0

1

0

0

1

1

1

1

1

0

1

1

1

1

1

1

0

0

Обратите внимание: единица на выходе нам нужна, только если

единице равны выход вентиля ИЛИ и выход вентиля И-НЕ.

Это наводит на мысль, что два этих выхода могут быть входа-

ми вентиля И.

Выход

Вход А

Вход В

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

159

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

Отметим, что во всей схеме по-прежнему всего два входа и

один выход. Два входа принадлежат как вентилю ИЛИ, так и

вентилю И-НЕ. Два выхода от вентиля ИЛИ и от вентиля И-

НЕ идут на вход вентиля И, который и выдает необходимый

нам результат.

Вход А

Вход В

Выход ИЛИ

Выход И-НЕ

Выход И

0

0

0

1

0

0

1

1

1

1

1

0

1

1

1

1

1

1

0

0

У созданной нами схемы есть собственное имя — исключаю-

щее ИЛИ (Exclusive OR, Искл-ИЛИ). Исключающей схема на-

звана потому, что ее выход равен 1, если единичный сигнал

есть на входе А или на входе В, но не на обоих. Чтобы не рисо-

вать каждый раз вентили ИЛИ, И-НЕ и И, мы будем исполь-

зовать для схемы Искл-ИЛИ обозначение:

Выход

Входы

Оно очень похоже на символ вентиля ИЛИ за исключением

того, что на нем со стороны входа нарисована еще одна кри-

вая линия. Поведение вентиля Искл-ИЛИ проиллюстрирова-

но в таблице.

Искл-ИЛИ

0

1

0

0

1

1

1

0

Вентиль Искл-ИЛИ — последний, подробно описанный в этой

книге. На практике иногда применяют еще один вентиль —

вентиль совпадения (coincidence gate) или  эквивалентности

(equivalence), выход которого равен 1, только если сигналы на

обоих входах одинаковы. На выходе вентиль совпадения ве-

дет себя противоположно вентилю Искл-ИЛИ, поэтому обо-

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

Подведем итог. Сложение двух двоичных чисел приводит

к появлению бита суммы и бита переноса.

160

Глава двенадцатая

+ сумма

0

1

0

0

1

1

1

0

+ перенос

0

1

0

0

0

1

0

1

Разряд суммы двух двоичных чисел задается выходом венти-

ля Искл-ИЛИ, а разряд переноса — выходом вентиля И.

Искл-ИЛИ

0

1

0

0

1

1

1

0

И

0

1

0

0

0

1

0

1

Для сложения двух двоичных цифр А и В мы можем объеди-

нить два этих вентиля.

Разряд переноса

Разряд суммы

Вход А

Вход В

Чтобы не рисовать многократно вентили И и Искл-ИЛИ, за-

меним эту схему обозначением

Разряд суммы

Вход А

Вход В

Разряд переноса

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

A

B

С

П

161

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

Полусумматором (half-adder) эта схема названа неспроста. Ко-

нечно, он складывает две двоичные цифры и выдает разряд

суммы и разряд переноса. Но подавляющее большинство дво-

ичных чисел записывается несколькими битами. Наш полу-

сумматор не делает одной важной вещи: не прибавляет к сум-

ме возможный разряд переноса от предыдущего суммирова-

ния. Допустим, мы складываем два двоичных числа, как пока-

зано ниже:

1111

+1111

11110

Полусумматор можно использовать только для сложения край-

него правого столбца: 1 плюс 1 равно 0, и 1 идет в перенос. Для

второго столбца справа из-за переноса нам на самом деле нуж-

но сложить три двоичных цифры. То же относится и к осталь-

ным столбцам. Каждое последующее сложение двух двоичных

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

Чтобы сложить три двоичных цифры, нам нужны два по-

лусумматора и вентиль ИЛИ:

Выход для

суммы

Вход для

переноса

Выход для

переноса

Вход А

Вход В

Полусум-

матор

A

B

C

П

Полусум-

матор

A

B

С

П

Чтобы разобраться в работе этой схемы, начнем со входов А и

В в первом полусумматоре (том, что слева). Результатом его

работы являются сумма и перенос. Эту сумму нужно приба-

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

подаются на вход второго полусумматора. Сумма из второго

полусумматора будет окончательной суммой. Два переноса из

полусумматоров попадают на входы вентиля ИЛИ. В этом

месте, конечно, можно использовать еще один полусумматор,

который выполнит необходимые действия. Но, проанализи-

ровав возможные варианты, вы убедитесь, что выходы для

переноса из двух полусумматоров никогда не будут одновре-

менно равны 1. Для их сложения вполне достаточно вентиля

162

Глава двенадцатая

ИЛИ, который действует аналогично вентилю Искл-ИЛИ, если

его входы не равны 1 одновременно.

Теперь назовем эту схему полным сумматором (full adder)

и введем для нее обозначение (расшифровка английских обо-

значений будет дана чуть позже):

Выход для суммы

Вход А

Вход B

Выход для переноса

Полный 

сумматор

Вход для переноса

A

B

S

CO

CI

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

нации входных и выходных сигналов полного сумматора.

Вход А Вход В

Вход

Выход

Выход для

для переноса

для суммы

переноса

0

0

0

0

0

0

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

0

1

1

0

0

1

1

0

1

1

0

1

0

1

1

1

1

1

1

Я говорил чуть раньше, что для всего сумматора нам пона-

добится 144 реле. Теперь я могу пояснить это число. В каждом

вентиле И, ИЛИ и И-НЕ по 2 реле. Таким образом, вентиль

Искл-ИЛИ построен из 6 реле. Полусумматор состоит из вен-

тиля Искл-ИЛИ и вентиля И, т. е. из 8 реле. Каждый полный

сумматор состоит из двух полусумматоров и одного вентиля

ИЛИ, итого 18 реле. Для нашего сумматора нам нужны 8 пол-

ных сумматоров. Всего получается 144 реле.

Вспомним пульт управления с переключателями и лам-

почками.

163

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

1

0

1

0

Можем приступать к соединению полных сумматоров с пере-

ключателями и лампочками.

Начнем с того, что соединим два крайних правых переклю-

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

V

V

Полный

сумматор

Выход

для переноса

A

B

S

CO

CI

Выход 

для суммы

Вход для

переноса

При сложении двух двоичных чисел первый столбец цифр,

которые вы складываете, не похож на другие тем, что в отли-

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

переноса из предыдущего столбца. Поэтому вход для перено-

са у первого полного сумматора соединяется с землей. Это зна-

чит, что его значение всегда 0. Конечно, разряд переноса мо-

жет появиться в результате сложения первой пары двоичных

чисел.

Со следующей парой переключателей и следующей лам-

почкой полный сумматор соединяется так:

164

Глава двенадцатая

V

V

Вход для

переноса

Полный

сумматор

Выход для

переноса

A

B

S

CO

CI

Выход для переноса из первого полного сумматора становит-

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

для сложения всех последующих столбцов аналогичны. Раз-

ряд переноса из одного столбца подается на вход для переноса

следующего столбца.

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

единяется с последним полным сумматором так:

V

V

Вход для переноса

Полный

сумматор

A

B

S

CO

CI

Последний выход для переноса соединяется с девятой лам-

почкой.

Готово!

Теперь изобразим все восемь полных сумматоров (Full

Adder, FA) сразу, подключив все выходы для переноса (Carry

Out, CO) к последующим входам для переноса (Carry In, CI) и

обозначив сумму буквой S (Sum).

165

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

Выход для переноса

8-битовая сумма

Вход для 

переноса

A B CI

FA 

CO S

A B CI

FA 

CO S

A B CI

FA 

CO S

A B CI

FA 

CO S

A B CI

FA 

CO S

A B CI

FA 

CO S

A B CI

FA 

CO S

A B CI

FA 

CO S

Наконец, введем единое обозначение для 8-битового сум-

матора. Его входы обозначены буквами от А

0

 до А

7

 и от В

0

 до

В

7

, а выходы — буквами от S

0

 до S

7

.

Выход для переноса

8-битовый сумматор

Вход 

для 

переноса

Вход для числа А

Вход для числа В

A

7

...A

0

B

7

...B

0

S

7

...S

0

Выход для суммы

CO

CI

Отдельные биты многобитового числа часто обозначают бук-

вами с нижними индексами. Биты A

0

, B

0

 и S

0

 называются млад-

шими (least-significant), а A

7

, B

7

 и S

7

 —  старшими  (most-

significant). Ниже в качестве примера показано соответствие

буквенных обозначений разрядам двоичного числа 0110-1001.

A

7

A

6

A

5

A

4

A

3

A

2

A

1

A

0

0

1

1

0

1

0

0

1

Индексы начинаются с 0 и увеличиваются с продвижением ко

все более значимым цифрам, так как они соответствуют пока-

зателю степени двойки.

2

7

2

6

2

5

2

4

2

3

2

2

2

1

2

0

0

1

1

0

1

0

0

1

Если вы умножите каждую степень двойки на расположенную

под ней цифру, а затем сложите результаты, то получите деся-

тичный эквивалент суммы — 64 + 32 + 8 + 1 = 105.

166

Глава двенадцатая

8-битовый сумматор можно изобразить и так:

8

8

8

CO

CI

Выход для переноса

Вход для переноса

8-битовый

сумматор

Вход А

 Вход В

A

7

...A

0

B

7

...B

0

S

7

...S

0

Восьмерки внутри стрелок означают, что каждая из них соот-

ветствует группе из 8 отдельных сигналов. Восьмиразрядность

числа подчеркивается также нумерацией символов A

7

… A

0

,

B

7

… B

0

 и S

7

… S

0

.

Создав один 8-битовый сумматор, вы легко построите и

второй. Их можно расположить  каскадом для сложения 16-

битовых чисел.

Выход

для 

переноса

Вход

для переноса

8-битовый

сумматор

Выход для

переноса

Вход 

для

переноса

8-битовый

сумматор

Вход А 

(старшие 

8 битов)

8

8

8

8

Вход В

(старшие 8 битов)

Вход А

(младшие 8 битов)

8

8

Вход В

(младшие

8 битов)

CO

CI

CO

CI

16-битовая сумма

A

7

...A

0

A

15

...A

8

B

7

...B

0

B

15

...B

8

S

7

...S

0

S

15

...S

8

Выход для переноса сумматора справа соединяется с входом

для переноса сумматора слева. Сумматор слева получает на

входе 8 старших цифр двух складываемых чисел и выдает на

выходе 8 старших разрядов результата.

Теперь вы можете спросить: «Неужели в компьютерах сло-

жение действительно осуществляется именно так?»

167

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

В общем, да, но не совсем.

Во-первых, сумматор может работать быстрее, чем тот, с

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

ход переноса от младшей пары цифр требуется для сложения

со следующей парой цифр, выход переноса второй пары цифр

требуется для третьей пары цифр и т. д. Скорость суммирую-

щей схемы равна произведению числа битов на скорость дей-

ствия одного полного сумматора. Такой перенос называется

сквозным (ripple). В быстродействующих сумматорах с помо-

щью дополнительной цепи реализован ускоренный (look-ahead)

перенос.

Во-вторых (и это более важно), в компьютерах больше не

используют реле! Лишь первые цифровые компьютеры, создан-

ные в начале 1930-х, были основаны на реле и чуть позже на ва-

куумных лампах. Сегодняшние компьютеры собирают из тран-

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

что и реле. Разница в том, что они гораздо быстрее, компактнее,

тише, экономичнее и дешевле. Для создания 8-битового сумма-

тора вам по-прежнему потребуется 144 транзистора (или боль-

ше, если вы решите заменить сквозной перенос ускоренным), но

схема будет иметь микроскопические размеры.

жүктеу/скачать 3,29 Mb.

Достарыңызбен бөлісу: