кр гаряев. Чарльз Петцольд - Код_ тайный язык информатики-Манн, Иванов и Фе. Книга принадлежит Контакты владельца Культовая книга талантливого преподавателя стала для многих первым уверенным шагом в программировании
 Скачать 6.11 Mb.
|
|
+ перенос 0 1 0 0 0 1 0 1 Вероятно, вы узнали в ней результат работы вентиля И. И 0 1 0 0 0 1 0 1 Таким образом, вентиль И вычисляет значение разряда переноса при сло- жении двух двоичных цифр. Ага! Мы определенно делаем успехи. Наш следующий шаг, похоже, заклю- чается в том, чтобы убедить некоторые реле вести себя так: Глава 12. Двоичный сумматор 151 + сумма 0 1 0 0 1 1 1 0 Это вторая часть задачи при сложении пары двоичных цифр. Вычислить значение разряда суммы оказывается не так просто, как значение разряда пе- реноса, но мы справимся и с этой сложностью. Первое, что нужно понять, — это то, что результат работы вентиля ИЛИ близок к тому, что нам нужно, за исключением значения в правом нижнем углу. ИЛИ 0 1 0 0 1 1 1 1 Результат работы вентиля И-НЕ также близок к тому, что нам требуется, за исключением значения в верхнем левом углу: И-НЕ 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 152 Код Заметьте, что мы хотим получить значение 1, только если выходные сиг- налы обоих вентилей ИЛИ и И-НЕ равны 1. Это говорит о том, что эти два выходных сигнала могут являться входными сигналами для вентиля И. Выход Вход А Вход В То, что нужно. Обратите внимание: во всей этой схеме по-прежнему есть только два вхо- да и один выход. Два входа относятся к обоим вентилям ИЛИ и И-НЕ. Выход- ные сигналы вентилей ИЛИ и И-НЕ подаются на вход вентиля И, и это дает именно тот результат, к которому мы стремимся. Вход А Вход В Выход ИЛИ Выход И-НЕ Что требуется 0 0 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 На самом деле у этой схемы есть название: вентиль исключающее ИЛИ (Искл-ИЛИ, оно же — сложение по модулю 2). Она называется так потому, что выход равен 1, если вход A равен 1 или вход B равен 1, но не оба одно- временно. Вместо того чтобы рисовать вентили ИЛИ, И-НЕ и И, мы можем использовать обозначение, которым инженеры-электрики показывают вен- тиль Искл-ИЛИ. Выход Входы Это обозначение очень похоже на обозначение вентиля ИЛИ, но имеет дополнительную кривую линию со стороны входа. Искл-ИЛИ 0 1 0 0 1 1 1 0 Глава 12. Двоичный сумматор 153 Вентиль Искл-ИЛИ — это последний логический элемент, который будет подробно описан в этой книге. Иногда в электротехнике используется шестой вентиль, называющийся вентилем совпадения или эквивалентности, поскольку выход равен 1 только при одинаковых сигналах на входе. Вентиль совпадения на выходе действует противоположно вентилю Искл-ИЛИ, поэтому его обо- значение аналогично обозначению вентиля Искл-ИЛИ, но дополнено круж- ком со стороны выхода *. Давайте повторим все, что уже знаем. При сложении двух двоичных чи- сел получается бит суммы и бит переноса. + сумма 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. Разряд переноса Разряд суммы Вход А Вход В Вместо многократного перерисовывания вентилей И и Искл-ИЛИ можно просто нарисовать схему, подобную следующей. * В общем случае кружок со стороны выхода означает инверсию результата операции. Прим. науч. ред. 154 Код Выход суммы (sum, S) Вход А Вход В Выход переноса (carry out, CO) Полусумматор A B S CO Существует причина, по которой эта схема называется полусумматором. Разумеется, она складывает две двоичные цифры и выдает бит суммы и бит переноса. Однако длина подавляющего большинства двоичных чисел пре- вышает один бит. То, что полусумматор не может сделать, так это прибавить возможный бит переноса, получившийся в результате предыдущей операции сложения. Представьте, что складываем два двоичных числа. 1111 + 1111 11110 Мы можем использовать полусумматор только для сложения цифр в правом крайнем столбце: 1 плюс 1 равно 0, 1 переносится. В случае со вторым столбцом справа нам, по сути, нужно сложить три двоичные цифры из-за переноса. И это касается всех остальных столбцов. Каждая последующая операция сложения двух двоичных цифр может включать бит переноса из предыдущего столбца. Для сложения трех двоичных цифр понадобятся два полусумматора и вен- тиль ИЛИ, соединенные следующим образом. Выход суммы Вход переноса Выход переноса Вход А Вход В A B S CO A B S CO Полусумматор Полусумматор Чтобы разобраться в этой схеме, начнем со входов A и B первого полусум- матора слева. Результат — бит суммы и бит переноса. Эта сумма должна быть добавлена к переносу из предыдущего столбца, поэтому они являются входа- ми для второго полусумматора. Сумма, полученная от второго полусуммато- ра, — окончательная. Два переноса из полусумматоров — входы для вентиля ИЛИ. Может показаться, что здесь нужен второй полусумматор, и такая схема, безусловно, сработала бы. Однако если вы проанализируете все возможности, то обнаружите, что оба переноса из двух полусумматоров никогда не равны 1. Вентиля ИЛИ достаточно для их сложения, поскольку он действует так же, как вентиль Искл-ИЛИ, если оба входных сигнала одновременно не равны 1. Глава 12. Двоичный сумматор 155 Вместо многократного перерисовывания этой схемы можем просто на- звать ее полным сумматором. A B S CO CI Вход переноса (carry input, 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 реле. Вот как я это понял: для каждого вентиля И, ИЛИ и И-НЕ требуются по два реле. Таким образом, вентиль Искл-ИЛИ состоит из шести реле. Полу- сумматор — это вентиль Искл-ИЛИ и вентиль И, поэтому для его создания необходимы восемь реле. Каждый полный сумматор — два полусумматора и вентиль ИЛИ, то есть 18 реле. Нам нужны восемь полных сумматоров для создания 8-битной машины, или 144 реле. Вспомните наш исходный пульт управления с переключателями и лам- почками. 156 Код Теперь мы можем начать присоединять переключатели и лампочки к пол- ному сумматору. Сначала подключим два крайних правых переключателя и крайнюю пра- вую лампочку к полному сумматору. V V A B S CO CI Выход переноса Полный сумматор Когда вы начинаете складывать два двоичных числа, первый столбец цифр отличается от остальных тем, что не может содержать бит переноса из преды- дущего столбца. В первом столбце нет бита переноса, поэтому вход для пере- носа полного сумматора соединяется с землей, то есть его значением является 0 бит. Разумеется, в результате сложения первой пары двоичных цифр может получиться бит переноса. Этот выход переноса — вход для следующего столбца. Для следующих двух цифр и лампочки вы используете полный сумматор, подключенный так. V V A B S CO CI Выход переноса Вход переноса Полный сумматор Выход переноса, полученный от первого полного сумматора, является входом для второго полного сумматора. Каждый последующий столбец цифр складывается по той же схеме. Каждый разряд переноса из одного столбца по- дается на вход для переноса следующего столбца. Наконец, восьмая и последняя пара переключателей подключена к по- следнему полному сумматору. Глава 12. Двоичный сумматор 157 V V A B S CO CI Вход переноса Полный сумматор Здесь последний выход для переноса подключен к девятой лампочке. Вот еще один способ изобразить схему из восьми полных сумматоров (full adder, FA), в которой каждый выход для переноса (CO) подключен к следую- щему входу для переноса (CI). FA FA FA FA FA FA FA FA Выход для переноса 8-битная сумма Вход для переноса A B CI A B CI A B CI A B CI A B CI A B CI A B CI A B CI CO S C O S CO S C O S CO S C O S CO S C O S Представим единое обозначение 8-битного сумматора, входы обозначим бук- вами от A 0 до A 7 и от B 0 до B 7 , выходы — буквами от S 0 до S 7 (от sum — «сумма»). Вход для переноса 8-битный сумматор Выход для переноса Вход для числа А Вход для числа В A 7 ... A 0 B 7 ... B 0 S 7 ... S 0 Выход для суммы CO CI Это распространенный способ обозначения отдельных битов многобит- ного числа. Биты A 0 , B 0 и S 0 являются младшими, а биты A 7 , B 7 и S 7 — стар- шими. Например, вот как с помощью этих букв с индексами можно было бы представить двоичное число 0110 1001. 158 Код А 7 А 6 А 5 А 4 А 3 А 2 А 1 А 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 Если вы умножите каждую степень двойки на цифру, расположенную под ней, и сложите результаты, получите десятичный эквивалент числа 0110 1001, который равен 64 + 32 + 8 + 1, или 105. По-другому 8-битный сумматор можно изобразить так. S 7 ... S 0 8 A 7 ... A 0 8 B 7 ... B 0 8 CO CI Выход для переноса Вход для переноса Вход А Вход В 8-битный сумматор Восьмерки внутри стрелок указывают на то, что каждая из них — это группа из восьми отдельных сигналов. Индексы символов A 7 … A 0 , B 7 … B 0 и S 7 … S 0 также обозначают восьмиразрядность числа. Как только соберете один 8-битный сумматор, вы сможете создать второй. Их легко расположить каскадом, чтобы сложить два 16-битных числа. 8-битный сумматор Вход А (старшие 8 бит) 8 8 S 15 ... S 8 8 S 7 ... S 0 8 A 7 ... A 0 B 7 ... B 0 A 15 ... A 8 B 15 ... B 8 Вход В (старшие 8 бит) Выход А (младшие 8 бит) 8 8 Выход В (младшие 8 бит) CO CI CO CI 16-битная сумма Вход для переноса Вход для переноса Выход для переноса Выход для переноса 8-битный сумматор Выход для переноса правого сумматора связан со входом для переноса ле- вого. Левый сумматор в качестве входных значений принимает самые старшие Глава 12. Двоичный сумматор восемь цифр двух слагаемых и в качестве выходного значения выдает самые старшие восемь цифр. Теперь вы можете спросить: «Неужели компьютеры действительно скла- дывают числаименно так?» В принципе да. Но не совсем. Во-первых, сумматоры могут быть быстрее тех, которые мы описали. Если вы посмотрите на то, как работает эта схема, то поймете, что выход переноса от младшей пары цифр необходим для сложения со следующей парой, выход переноса от второй пары цифр — для сложения с третьей парой и т. д. Общая скорость сумматора равна количеству битов, умноженному на скорость одного полного сумматора. Это называется сквозным переносом. Быстрые сумматоры используют дополнительные схемы ускоренного переноса. Во-вторых (и это самое главное), компьютерам больше не нужно реле! Однако первые цифровые компьютеры, созданные в начале 1930-х годов, ис- пользовали реле, позднее — вакуумные лампы. Современные компьютеры создаются на основе транзисторов. Транзисторы в основном функционируют так же, как и реле, однако (как мы увидим далее) они намного быстрее, ком- пактнее, тише, дешевле и потребляют гораздо меньше энергии. Для построе- ния 8-битного сумматора по-прежнему требуются 144 транзистора (или боль- ше, если вы хотите заменить сквозной перенос схемой ускоренного переноса), однако при этом размер схемы микроскопический. 160 Глава 13 А как насчет вычитания? Убедившись в том, что реле действительно можно соединить для сложения двоичных чисел, зададимся вопросом: «А как насчет вычитания?» Не бойтесь показаться смешным, задавая его. На самом деле вы довольно проницатель- ны. Сложение и вычитание в некотором смысле дополняют друг друга, однако механика у этих операций разная. Сложение предполагает последовательное продвижение от крайнего правого столбца цифр до крайнего левого. Каждое значение, перенесенное из одного столбца, прибавляется к следующему. При вычитании мы ничего не переносим; мы заимствуем, а это действие предпо- лагает использование довольно запутанного механизма. Давайте рассмотрим типичную задачу на вычитание с заимствованием. 253 − 176 ??? Начнем решение с крайнего правого столбца. Сначала мы замечаем, что 6 больше 3, поэтому нам нужно занять 1 у 5, а затем вычесть 6 из 13, в резуль- тате чего получается 7. Мы помним, что заняли 1 у 5, поэтому вместо 5 име- ем 4, что меньше 7, поэтому занимаем 1 у 2, вычитаем 7 из 14 и получаем 7. Мы заняли 1 у 2, поэтому у нас есть только единица, из которой вычитаем 1 и получаем 0. Наш ответ — 77. 253 − 176 77 Как же заставить группу логических вентилей следовать такой странной логике? Глава 13. А как насчет вычитания? 161 Не будем даже пытаться. Вместо этого используем небольшой трюк, по- зволяющий вычитать без заимствования. Это порадовало бы Полония («Не за- нимай и не ссужай») и всех остальных. Кроме того, подробное рассмотрение процесса вычитания полезно, поскольку напрямую связано с использованием двоичных кодов для хранения в компьютерах отрицательных чисел. Числа, участвующие в операции вычитания, называются уменьшаемым и вычитаемым. Вычитаемое вычитается из уменьшаемого, результатом явля- ется разность. Уменьшаемое − Вычитаемое Разность Чтобы произвести вычитание без заимствования, сначала нужно вычесть вычитаемое из 999, а не из уменьшаемого. 999 − 176 823 В данном случае используем число 999, поскольку числа, участвующие в операции, состоят из трех цифр. Если бы они были четырехзначными, мы бы использовали число 9999. При вычитании числа из строки девяток получа- ем число, называемое дополнением до девяти. Дополнение числа 176 до девя- ти — 823. Это работает и в обратную сторону: дополнение числа 823 до девя- ти — 176. Вся прелесть в том, что вне зависимости от значения вычитаемого вычисление его дополнения до девяти никогда не требует заимствования. После вычисления дополнения вычитаемого до девяти нужно прибавить к нему исходное уменьшаемое. 253 + 823 1076 Наконец, прибавить 1 и вычесть 1000. 1076 + 1 − 1000 77 162 Код Вот и всё. Мы получили такой же результат, как и раньше, ни разу не при- бегнув к заимствованию. Почему это работает? Исходная задача на вычитание такова: 253 – 176. Если к этому выражению прибавить и вычесть любое число, результат останется прежним. Так что давайте прибавим и вычтем 1000: 253 – 176 + 1000 – 1000. Выражение эквивалентно следующему: 253 – 176 + 999 + 1 – 1000. Теперь числа можно перегруппировать: 253 + (999 – 176) + 1 – 1000. Это соответствует вычислению, которое я продемонстрировал с исполь- зованием дополнения до девяти. Мы заменили одно вычитание двумя вычи- таниями и двумя сложениями, избавившись при этом от всех нежелательных заимствований. А если вычитаемое больше уменьшаемого? Рассмотрим такой пример. 176 − 253 ??? Обычно вы смотрите на подобную задачу и думаете: «Хм, вычитаемое больше уменьшаемого, поэтому придется поменять числа местами, выпол- нить вычитание и не забыть о том, что результат будет отрицательным». Вы можете произвести перестановку чисел в голове и записать ответ сле- дующим образом. 176 − 253 –77 Глава 13. А как насчет вычитания? 163 Процесс выполнения данного расчета без заимствований несколько от- личается от предыдущего примера. Как и раньше, мы начинаем с вычитания вычитаемого (253) из 999 для получения дополнения до девяти. 999 − 253 746 Теперь прибавим дополнение до девяти к исходному уменьшаемому. 176 + 746 922 На этом этапе в более раннем примере для получения окончательного ре- зультата мы могли прибавить 1 и вычесть 1000. Однако в данном случае эта стратегия не сработала бы, поскольку нам пришлось бы вычесть 1000 из 923, что в действительности потребовало бы вычесть 923 из 1000, и без заимство- ваний мы бы не обошлись. Вместо этого, по аналогии с прибавлением 999, вычтем 999. 922 − 999 ? ? ? Сразу становится очевидным, что наш ответ будет отрицательным, поэто- му следует поменять числа местами и вычесть 922 из 999. Это опять же не тре- бует заимствований, а ответ совпадает с ожидаемым. 922 − 999 −77 Этот метод применим и к двоичным числам, работать с которыми ока- зывается проще, чем с десятичными. Давайте посмотрим, как это работает. Вот исходная задача на вычитание. 164 Код 253 − 176 ??? После преобразования чисел в двоичные получаем следующую задачу. 11111101 − 10110000 ???????? Шаг 1. Вычесть вычитаемое из 11111111 (что соответствует 255). 11111111 − 10110000 01001111 При работе с десятичными числами вычитаемое вычиталось из строки де- вяток, а результат назывался дополнением до девяти. При работе с двоичными числами вычитаемое вычитается из строки единиц, результат — дополнение до единицы. Заметьте, что нам на самом деле не нужно выполнять вычитание, чтобы вычислить дополнение до единицы, поскольку каждый 0 в исходном числе превращается в 1 в дополнении до единицы, а каждая 1 превращается в 0. По этой причине дополнение до единицы иногда также называется отри- цанием или инверсией. (Сейчас вы, вероятно, вспомнили о том, что в главе 11 мы конструировали устройство, называемое инвертором, которое меняло 0 на 1, а 1 на 0.) Шаг 2. Прибавить дополнение вычитаемого до единицы к уменьшаемому. 11111101 + 01001111 101001100 Шаг 3. Прибавить к результату 1. 101001100 + 1 101001101 Шаг 4. Вычесть 100000000 (что соответствует 256). Глава 13. А как насчет вычитания? 165 101001101 − 100000000 1001101 Результат эквивалентен десятичному числу 77. Давайте попробуем еще раз, поменяв числа местами. В десятичной систе- ме счисления задача на вычитание выглядит так. 176 − 253 ??? В двоичной системе — так. 10110000 − 11111101 ???????? Шаг 1. Вычесть вычитаемое из 11111111, чтобы получить дополнение до единицы. 11111111 − 11111101 00000010 Шаг 2. Прибавить дополнение вычитаемого до единицы к уменьшаемому. 10110000 + 00000010 10110010 Теперь нужно как-то вычесть из результата число 11111111. Когда исходное вычитаемое меньше уменьшаемого, для этого достаточно прибавить 1 и вы- честь 100000000. Однако эту операцию нельзя выполнить без заимствования. Вместо этого мы вычитаем результат из числа 11111111. 11111111 − 10110010 01001101 166 Код Опять же, такая стратегия на самом деле означает, что для получения результата мы выполняем простое инвертирование. Ответ снова равен 77, а на самом деле −77. Теперь у нас есть необходимые знания для оснащения собранного в пре- дыдущей главе сумматора функцией вычитания. Чтобы не слишком усложнять эту счетную машину, сделаем так, чтобы она выполняла вычитание только тог да, когда вычитаемое меньше уменьшаемого, когда в результате получает- ся положительное число. Основой этой счетной машины являлся 8-разрядный сумматор, собран- ный из логических вентилей. Выход для переноса 8-битный сумматор Вход для переноса Вход А Вход В A 7 ... A 0 B 7 ... B 0 S 7 ... S 0 Выход суммы CO CI Вероятно, вы помните, что входы с A 0 по A 7 и с B 0 по B 7 были подклю- чены к переключателям, с помощью которых вводились два 8-битных числа, подлежащие сложению. Вход для переноса соединялся с землей, выходы с S 0 по S 7 — с восемью лампочками, отображающими результат сложения. Посколь- ку в итоге могло получиться 9-битное значение, выход для переноса был под- ключен к девятой лампочке. Пульт управления выглядел так. 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 Глава 13. А как насчет вычитания? 167 Положения переключателей на этом изображении соответствуют сложе- нию чисел 183 (10110111) и 22 (00010110), в результате которого получается 205, или 11001101, что и отражено рядом лампочек. Новый пульт управления для сложения и вычитания двух 8-битных чисел имеет несколько иной вид. Он предусматривает дополнительный переключа- тель, позволяющий выбрать между сложением и вычитанием. 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 Вычитание Сложение Переполнение/ Исчезновение Подписи подсказывают, что размыкание этого переключателя соответствует сложению, а замыкание — вычитанию. Кроме того, для отображения результа- тов используются только восемь крайних лампочек справа. Девятая лампочка обозначена словами «Переполнение/Исчезновение». Она загорается, когда по- лученное число не может быть представлено восемью лампочками. Так проис- ходит, если в результате сложения получается число, превышающее 255 (это называется переполнением), или если результат вычитания — отрицательное число — исчезновение порядка, то есть если вычитаемое больше уменьшаемого. Главное нововведение в счетной машине — схема, которая вычисляет до- полнение до единицы для 8-битного числа. Напомним, что вычисление дополне- ния до единицы эквивалентно инвертированию битов, поэтому устройство для произведения этой операции могло бы состоять просто из восьми инверторов. Входы Выходы Проблема этой схемы заключается в том, что она всегда инвертирует по- ступающие в нее биты. Наша цель — создать машину, которая выполняет как 168 Код сложение, так и вычитание, поэтому эта схема должна инвертировать биты только при выполнении вычитания. Вот более подходящая схема. Выходы Входы Инверсия Сигнал «Инверсия» поступает на каждый из восьми вентилей Искл-ИЛИ (исключающее ИЛИ). Напомним, вентиль Искл-ИЛИ работает так. |