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



Pdf көрінісі
бет8/26
Дата07.04.2020
өлшемі3,29 Mb.
#61783
1   ...   4   5   6   7   8   9   10   11   ...   26
Байланысты:
Petcold Kod-Taynyy-yazyk-informatiki.535358

Глава 12

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

Сложение — основное арифметическое действие, и потому,

если мы хотим построить компьютер (а в этом и заключается

тайная цель моей книги), надо прежде всего разобраться, как

создать устройство, которое складывало бы два числа. Когда

вы сделаете это, то поймете, что сложение — это практически



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

работав суммирующее устройство, мы окажемся на пути к со-

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

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

числения траектории полета на Марс, игры в шахматы и обо-

гащения провайдеров Интернета.

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

моздким, неуклюжим, медленным и шумным, по крайней мере

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

ми. Самое интересное, что мы соберем его из простейших элек-

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

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

реле, объединенных в различные логические вентили. В этом

сумматоре не будет ни единой детали, не изобретенной мини-

мум 120 лет назад. Что особенно приятно, мы не будем зах-

ламлять всей этой электроникой вашу квартиру. Мы постро-

им сумматор на бумаге и в воображении.

Наш сумматор работает только с двоичными числами и

лишен некоторых современных прелестей. В нем, например,


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 транзистора (или боль-

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

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




Достарыңызбен бөлісу:
1   ...   4   5   6   7   8   9   10   11   ...   26




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет