Текст книги "Код. Тайный язык информатики"

Глава 11. Логические вентили

В далеком будущем, когда история примитивных вычислений XX века превратится в предания, кто-то, вероятно, предположит, что логические вентили были названы в честь одноименного сантехнического устройства. Это не совсем так. Мы вскоре увидим, что логические вентили действительно напоминают обычные вентили, через которые проходит вода, и выполняют элементарные логические задачи, блокируя или пропуская электрический ток.

В предыдущей главе мы рассматривали сценарий, когда вы вошли в зоомагазин и сказали продавцу: «Мне нужен белый или рыжий стерилизованный кот или стерилизованная кошка любого цвета, кроме белого, или любой кот или кошка черного цвета». Эти критерии можно объединить в следующее логическое выражение, а также выразить с помощью схемы из переключателей и лампочки:

(М × С × (Б + Р)) + (Ж × С × (1 − Б)) + Ч.

Такая схема иногда называется сетью, хотя в настоящее время это слово гораздо чаще используется для обозначения соединенных между собой компьютеров, а не набора простых переключателей.

Несмотря на то что все обозначенные на схеме элементы были изобретены в XIX веке, тогда никто не представлял, что логические выражения можно реализовать непосредственно в виде электрических цепей. Эта возможность была осознана только в 1930-х годах Клодом Шенноном (1916–2001), который в 1938 году защитил знаменитую магистерскую диссертацию под названием «Символьный анализ реле и коммутаторов». Спустя десять лет впервые была опубликована его статья «Математическая теория связи», в которой слово «бит» (bit) использовалось для обозначения двоичной цифры.

Разумеется, задолго до 1938 года было известно, что для протекания тока при последовательном соединении двух переключателей оба должны быть замкнуты, а при параллельном соединении – лишь один из них. Однако никто так ясно и убедительно, как Шеннон, не показал, что для проектирования схем с переключателями инженеры-электрики могут использовать все инструменты булевой алгебры. В частности, если вы можете упростить логическое выражение, описывающее схему, то можете упростить и саму схему.

Например, выражение, содержащее ваши критерии выбора кошки, выглядит так:

(М × С × (Б + Р)) + (Ж × С × (1 − Б)) + Ч.

Используя сочетательный закон, мы можем изменить порядок переменных, объединенных знаком И («×»), и переписать выражение:

(С × М × (Б + Р)) + (С × Ж × (1 − Б)) + Ч.

Для ясности введу два дополнительных символа X и Y:

X = М × (Б + Р);

Y = Ж × (1 − Б).

Теперь выражение с критериями выбора кошки можно записать так:

(С × X) + (С × Y) + Ч.

Наконец, мы можем вернуть значения выражений, соответствующих символам X и Y.

Обратите внимание: переменная С встречается в выражении дважды. Используя распределительный закон, это выражение можно переписать только с одной переменной С:

(С × (X + Y)) + Ч.

Теперь подставим в выражение значения X и Y:

(С × ((M × (Б + Р)) + (Ж × (1 − Б)))) + Ч.

Из-за множества скобок это выражение не выглядит упрощенным. Однако оно содержит на одну переменную меньше, а значит, в схеме меньше переключателей. Вот ее пересмотренная версия.

Действительно, увидеть, что эта схема эквивалентна предыдущей, легче, чем заметить тождество выражений.

На самом деле в этой цепи по-прежнему на три переключателя больше, чем нужно. Теоретически для выбора идеальной кошки должно быть достаточно четырех переключателей. Почему четырех? Каждый переключатель – это бит. Одного переключателя хватит для указания пола (разомкнутый – соответствует коту, замкнутый – кошке), еще один будет указывать на стерилизованную кошку в замкнутом состоянии и нестерилизованную – в разомкнутом, еще два позволят распознать цвет. Существуют четыре возможных цвета: белый, черный, рыжий и «другой». И мы знаем, что четыре варианта можно определить с помощью двух битов, поэтому для указания цвета нужно всего два переключателя. Например, белому цвету могут соответствовать два разомкнутых переключателя, черному – один замкнутый, рыжему – второй замкнутый, а «другим» – два замкнутых.

Теперь давайте построим пульт управления для выбора кошки, который будет состоять из лампочки и четырех переключателей (похожих на те, с помощью которых вы включаете и выключаете свет).

Переключатель замкнут, когда находится в положении вверх, разомкнут – когда находится в положении вниз. Боюсь, что обозначения двух переключателей для выбора цвета кошки могут показаться немного непонятными, однако это следствие попытки обойтись при создании пульта управления минимумом средств. Левый переключатель в этой паре обозначен буквой Ч; замыкание только левого переключателя (как показано на рисунке) соответствует черному цвету. Правый переключатель в этой паре обозначен буквой Р; замыкание только правого переключателя соответствует рыжему цвету, замыкание обоих – «другому» цвету (этот вариант обозначен буквой Д). Размыкание обоих переключателей соответствует белому цвету и обозначается буквой Б внизу.

Если пользоваться компьютерной терминологией, набор переключателей – это устройство ввода информации, управляющей поведением цепи. В данном случае переключатели соответствуют четырем битам, позволяющим описать кошку. Устройством вывода является лампочка, которая загорается, если положение переключателей согласуется с описанием подходящей кошки. Переключатели, изображенные на предыдущем рисунке, описывают нестерилизованную черную кошку. Ее характеристики удовлетворяют вашим критериям, поэтому лампочка загорается.

Теперь нам нужно лишь сконструировать схему, которая оживит этот пульт управления.

Как вы помните, диссертация Клода Шеннона называлась «Символьный анализ реле и коммутаторов». Описанные им реле были очень похожи на телеграфные, о которых мы говорили в главе 6. Однако к моменту публикации работы Шеннона реле использовались для других целей, в частности в телефонной сети.

Подобно переключателям, реле можно соединять последовательно и параллельно для решения простых логических задач. Эти комбинации называются логическими вентилями. Когда я говорю, что эти логические вентили решают простые логические задачи, я имею в виду максимально простые задачи. Преимущество реле по сравнению с переключателями заключается в том, что их можно включать и выключать автоматически (с помощью других реле), а не вручную. Таким образом, логические вентили можно комбинировать для решения более сложных задач, например для выполнения простых арифметических операций. В следующей главе будет показано, как из переключателей, лампочек, источника питания и телеграфных реле можно собрать счетную машину (пусть и работающую исключительно с двоичными числами).

Как известно, реле играли ключевую роль в работе телеграфной системы. Из-за больших расстояний провода, соединяющие телеграфные станции, имели очень высокое сопротивление. Нужно было устройство, способное принимать слабый сигнал и передавать идентичный, но более мощный. Реле решало это задачу, используя электромагнит для управления переключателем. По сути, реле усиливало слабый сигнал для получения более мощного.

В наши планы не входит использование реле для усиления слабого сигнала. Нас интересует только то, что реле является переключателем, которым можно управлять не вручную, а с помощью электричества. Мы можем соединить реле с переключателем, лампочкой и парой батареек.

Обратите внимание: переключатель слева разомкнут, а лампочка не горит. Когда вы замкнете переключатель, ток из батарейки слева от него потечет по виткам катушки, намотанной на железный сердечник, который приобретет магнитные свойства и притянет гибкую металлическую полоску, что, в свою очередь, приведет к замыканию цепи и включению лампочки.

Когда электромагнит притягивает металлическую полоску, реле считается активированным. После размыкания выключателя железный сердечник теряет магнитные свойства, а металлическая полоска возвращается в исходное положение.

Такой способ зажечь лампочку кажется довольно мудреным, и это действительно так. Если бы мы хотели ограничиться только включением лампочки, мы могли бы обойтись и без реле. Однако перед нами стоит более сложная задача.

В этой главе мы будем часто использовать реле (а после сборки логических вентилей полностью от них откажемся), поэтому хочу упростить схему. Мы можем избавиться от некоторых проводов с помощью земли. В данном примере «земля» – просто общий провод; к реальной земле ничего подключать не нужно.

Понимаю, это не похоже на упрощение, однако мы еще не закончили. Важно: отрицательные контакты обеих батарей подключены к земле.

Так что везде, где нам встретится подобное изображение, заменим его заглавной буквой V (которая означает voltage – «напряжение»), как сделали это в главе 5 и главе 6. Теперь реле выглядит так.

Когда переключатель замкнут, ток между источником питания (V) и землей течет через катушку электромагнита. Это заставляет электромагнит притянуть гибкую металлическую полоску, которая замыкает цепь между источником питания, лампочкой и землей, и лампочка загорается.

На этих схемах присутствуют два источника питания и две земли, однако все источники питания, как и все земли, на приведенных в этой главе схемах могут быть соединены друг с другом. Все схемы, состоящие из реле и логических вентилей, изображенные в этой и следующей главах, допускают использование только одной (хотя и мощной) батарейки. Например, предыдущую схему можно перерисовать только с одним источником питания.

Учитывая то, что мы собираемся делать с реле, эта схема не является достаточно понятной. Лучше избегать замкнутых цепей и рассматривать работу реле, как и в случае с описанным ранее пультом управления, с точки зрения входного и выходного сигналов.

Если напряжение поступает на вход (например, если он соединен с источником питания с помощью переключателя), то активируется электромагнит, и на выходе появляется напряжение.

Ко входу реле не обязательно подключать переключатель, а к выходу – лампочку. Выход одного реле может быть подключен ко входу другого.

Замыкание переключателя активирует первое реле, которое затем подает напряжение на второе. Срабатывание второго реле приведет к включению лампочки.

Соединяя несколько реле, можно конструировать логические вентили.

На самом деле лампочку можно подключить к реле двумя способами. Обратите внимание на гибкую металлическую деталь, которую притягивает электромагнит. В состоянии покоя она касается одного контакта. Когда электромагнит притягивает ее, она касается другого контакта. Мы использовали нижний контакт в качестве выхода реле, однако могли бы применить и верхний. В этом случае выход реле меняется на противоположный, и лампочка загорается при размыкании входного переключателя. При замыкании входного переключателя лампочка гаснет.

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

Как и в случае с переключателями, два реле могут быть соединены последовательно.

Выход верхнего реле подает напряжение на нижнее. Как видите, когда оба переключателя разомкнуты, лампочка не горит. Попробуем замкнуть верхний переключатель.

Лампочка не загорается, поскольку нижний переключатель все еще разомкнут, и второе реле не срабатывает. Попробуем разомкнуть верхний переключатель и замкнуть нижний.

Лампочка по-прежнему не горит. Ток до нее не доходит, потому что не сработало первое реле. Единственным способом зажечь лампочку является замыкание обоих переключателей.

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

Подобно двум соединенным последовательно переключателям, эти два реле решают небольшую логическую задачу. Лампа загорается только в случае срабатывания обоих реле. Такая схема последовательного соединения двух реле называется вентилем И. Для его обозначения на схемах инженеры-электрики используют специальный символ, который выглядит так.

Это первый из четырех основных логических вентилей. Вентиль И имеет два входа (слева на приведенной выше схеме) и один выход (справа). Вам часто будет встречаться именно такое изображение вентиля И – со входами слева и выходом справа. Дело в том, что людям, привыкшим читать слева направо, удобнее изучать электрические схемы также слева направо. Однако входы логического вентиля И можно было бы изобразить вверху, справа или внизу.

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

С использованием символа вентиля И эта же схема принимает следующий вид.

Обратите внимание: символ вентиля И не только используется вместо двух соединенных последовательно реле, но также подразумевает, что верхнее реле подключено к источнику питания и оба реле соединены с землей. Опять же, лампочка загорается только в случае замыкания верхнего и нижнего переключателей. Вот почему эта схема называется вентилем И.

Входы вентиля И не обязательно должны быть соединены с переключателями, а выход – подключен к лампочке. В данном случае мы имеем дело просто с напряжением на входах и выходе. Например, выход одного вентиля И может быть входом второго вентиля И.

Эта лампочка загорится лишь в случае замыкания всех трех переключателей. Только если будут замкнуты верхние два переключателя, выход первого вентиля И активирует первое реле во втором вентиле И. Нижний переключатель активирует второе реле во втором вентиле И.

Если мы выразим отсутствие напряжения в виде 0, а его наличие – в виде 1, то зависимость выходного сигнала вентиля И от входных сигналов будет следующей.

Как и в случае с двумя последовательно соединенными переключателями, работу вентиля И можно описать с помощью небольшой таблицы.

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

Лампочка загорится при замыкании всех трех переключателей. Подобная конфигурация обозначается таким символом.

Такая схема называется трехвходовым вентилем И.

Следующий логический вентиль состоит из двух реле, соединенных параллельно.

Важно: выходы двух реле соединены друг с другом. Этот объединенный выход подает питание на лампочку. Для того чтобы лампочка загорелась, достаточно активировать одно из двух реле. Например, если мы замкнем верхний переключатель, лампочка загорится, поскольку получает питание от левого реле.

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

Лампочка также загорится при замыкании обоих переключателей.

В данном случае мы находимся в ситуации, когда лампочка загорается при замыкании верхнего или нижнего переключателя. Ключевым здесь является слово или, поэтому данная схема называется вентилем ИЛИ. Для его обозначения инженеры-электрики используют такой символ.

Он несколько похож на символ вентиля И, за исключением закругления стороны входов. На выходе вентиля ИЛИ есть напряжение, если оно подается на один из двух его входов. Если мы обозначим отсутствие напряжения 0, а его наличие – 1, то вентиль ИЛИ сможет находиться в четырех возможных состояниях.

Результаты работы вентиля ИЛИ можно представить в виде таблицы.

Вентиль ИЛИ также может иметь более двух входов. Выход такого вентиля равен 1, если любой из его входов равен 1; выход вентиля равен 0, если все его входы равны 0.

Ранее я объяснил, что используемые нами реле называются двухпозиционными, потому что их выходы могут быть подключены двумя разными способами. Как правило, при разомкнутом переключателе лампочка не горит.

При замыкании переключателя лампочка загорается.

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

В этом случае лампочка будет гаснуть при замыкании переключателя. Подключенное таким способом одиночное реле называется инвертором. Инвертор не является логическим вентилем (логические вентили всегда имеют два или более входов), однако он часто оказывается очень полезным и изображается с помощью специального символа.

Данная схема называется инвертором, потому что она инвертирует 0 (отсутствие напряжения) в 1 (наличие напряжения) и наоборот.

Теперь, когда у нас есть инвертор, вентиль И и вентиль ИЛИ, мы можем приступить к созданию пульта управления, который позволит автоматизировать выбор идеальной кошки. Начнем с переключателей. Первый переключатель в замкнутом состоянии соответствует кошке, в разомкнутом – коту. Так мы сможем генерировать два сигнала, которые обозначим Ж и М.

Ж равно 1, М равно 0, и наоборот. Аналогично второй переключатель соответствует стерилизованной кошке в замкнутом состоянии, нестерилизованной – в разомкнутом.

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

Когда оба переключателя разомкнуты (как показано на рисунке), они соответствуют белому цвету. Вот как можно использовать два инвертора и один вентиль И для того, чтобы сгенерировать сигнал, обозначенный буквой Б, который будет равен 1 (наличие напряжения), если вы выбрали белую кошку, и 0 (отсутствие напряжения), если не выбрали.

Когда переключатели разомкнуты, входы обоих инверторов равны 0. Таким образом, оба выходных сигнала инверторов (которые подаются на входы вентиля И) равны 1. Это означает, что выход вентиля И равен 1. При замыкании любого из переключателей выход вентиля И будет равен 0.

Чтобы выбрать черную кошку, мы замыкаем первый переключатель. Это можно сделать, используя один инвертор и вентиль И.

Выход вентиля И будет равен 1 только в том случае, если первый переключатель замкнут, а второй – разомкнут.

Аналогично замыкание второго переключателя будет означать выбор рыжей кошки.

Замыкание обоих переключателей означает, что нам нужна кошка «другого» цвета.

Теперь давайте объединим описанные выше четыре небольшие схемы в одну. (Как обычно, черными точками обозначаются соединения проводов; провода, на пересечениях которых черных точек нет, не соединены.)

Понимаю, в этих хитросплетениях проводов сложно разобраться. Однако если вы внимательно проследите, откуда подаются сигналы на входы каждого из вентилей И, и проигнорируете то, куда еще они идут, то увидите, что схема работает. Если оба переключателя разомкнуты, выход Б будет равен 1, а остальные – 0. Если первый переключатель замкнут, выход Ч будет равен 1, а остальные – 0 и т. д.

Для соединения вентилей и инверторов существует несколько простых правил: выход одного вентиля (или инвертора) может являться входом одного или нескольких других вентилей (инверторов). Однако выходы двух или более вентилей (инверторов) никогда не соединяются друг с другом.

Эта схема, состоящая из четырех вентилей И и двух инверторов, называется дешифратором двух линий на четыре. На его вход подается два бита, которые в различных комбинациях могут представлять четыре разных значения. На его выходе образуются четыре сигнала, лишь один из которых равен 1 в любой момент времени (какой конкретно, зависит от входных значений). По аналогичному принципу вы можете создать дешифратор трех линий на восемь или дешифратор четырех линий на шестнадцать и т. д.

Еще раз приведу упрощенное логическое выражение для выбора кошки:

(С × ((М × (Б + Р)) + (Ж × (1 − Б)))) + Ч.

Каждому знаку «+» в этом выражении должен соответствовать вентиль ИЛИ, а каждому знаку «×» – вентиль И.

Порядок символов слева от схемы соответствует их порядку в выражении. Эти сигналы поступают от переключателей, соединенных с инверторами и дешифратором «2 на 4». Обратите внимание на использование инвертора для реализации части выражения 1 − Б.

Вы можете подумать, что в схеме используется слишком много реле, и это действительно так. В ней присутствуют два реле для каждого вентиля И и ИЛИ и одно реле для каждого инвертора. Могу лишь посоветовать привыкнуть к такому положению дел. В следующих главах мы будем использовать гораздо больше реле. Просто радуйтесь, что вам не придется покупать реле и собирать эти схемы дома.

Сейчас мы рассмотрим еще два логических вентиля. Оба используют выход реле, на котором присутствует напряжение, когда реле не активировано (выход, используемый в инверторе). Например, в следующей конфигурации выход одного реле подает питание на вход второго. Когда оба входа отключены от источника питания, лампочка горит.

При замыкании верхнего выключателя лампочка гаснет.

Лампочка гаснет из-за того, что на второе реле не подается питание. Точно так же лампочка гаснет при замыкании нижнего выключателя.

Когда замкнуты оба переключателя, лампочка тоже не горит.

Это поведение прямо противоположно поведению вентиля ИЛИ. Такая схема называется вентилем ИЛИ-НЕ.

Его символ аналогичен символу вентиля ИЛИ, за исключением того, что на выходе изображен небольшой кружок, означающий инвертировать. Вентиль ИЛИ-НЕ соответствует следующей схеме.

Результаты работы вентиля ИЛИ-НЕ представлены в таблице.

Они противоположны результатам работы вентиля ИЛИ, выход которого равен 1, если один из двух его входов равен 1, а 0 – только если оба входа равны 0.

Далее показан еще один способ соединения двух реле.

В данном случае два выхода соединены. Это похоже на конфигурацию вентиля ИЛИ, только здесь используются другие контакты. Лампочка горит, когда оба переключателя разомкнуты.

Лампочка продолжает гореть при замыкании верхнего переключателя.

Точно так же лампочка продолжает гореть и при замыкании нижнего переключателя.

Только при замыкании обоих переключателей лампочка гаснет.

Это поведение прямо противоположно поведению вентиля И. Такая схема называется вентилем И-НЕ. Вентиль И-НЕ изображается так же, как и вентиль И, но с кружком на выходе, который означает, что выходной сигнал противоположен выходному сигналу вентиля И.

Вентиль И-НЕ демонстрирует следующее поведение.

Обратите внимание: выход вентиля И-НЕ противоположен выходу вентиля И. Выход вентиля И равен 1, только если оба входа равны 1; в противном случае выход равен 0.

Итак, мы рассмотрели четыре различных способа подключения реле, которые имеют два входа и один выход. Каждая конфигурация дает несколько различающиеся результаты. Для экономии сил и времени мы назвали эти конфигурации логическими вентилями и решили обозначать их с помощью символов, используемых инженерами-электриками. Выходной сигнал конкретного логического вентиля зависит от входного сигнала, как показано в следующих таблицах.

Теперь у нас есть четыре логических вентиля и инвертор. Осталось дополнить инструментарий обычным реле, которое называется буфером.

Буфер изображается так.

Этот символ аналогичен символу инвертора, но без маленького кружка. Буфер примечателен тем, что он почти ничего не делает. Выходной сигнал буфера совпадает с его входным сигналом.

Однако вы можете использовать буфер при наличии слабого входного сигнала. Как вы помните, именно по этой причине реле использовались в телеграфной системе много лет назад. Кроме того, буфер можно применять для небольшой задержки сигнала. Дело в том, что для срабатывания реле требуется немного времени – небольшая доля секунды.

Отныне в книге редко будут встречаться изображения реле. Вместо этого следующие схемы будут состоять из буферов, инверторов, четырех основных логических вентилей и более сложных схем (дешифратора «2 на 4», например), собранных из этих вентилей. Разумеется, все эти компоненты состоят из реле, однако нам нет необходимости их рассматривать.

Ранее, когда мы конструировали дешифратор «2 на 4», нам встретилась небольшая схема следующего типа.

Два инвертированных входа стали входами вентиля И. Иногда такая конфигурация изображается без инверторов.

Обратите внимание на маленькие кружки на входе вентиля И, которые указывают, что сигналы в этой точке инвертируются: 0 (отсутствие напряжения) становится 1 (наличие напряжения), и наоборот.

Вентиль И с двумя инвертированными входами ведет себя точно так же, как вентиль ИЛИ-НЕ.

Выход равен 1, только если оба входа равны 0.

Аналогично вентиль ИЛИ с двумя инвертированными входами эквивалентен вентилю И-НЕ.

Выход равен 0, только если оба входа равны 1.

Эти две пары эквивалентных схем представляют электрическое воплощение законов Огастеса де Моргана, еще одного математика викторианской эпохи, который был на девять лет старше Буля. Его книга «Формальная логика» была опубликована в 1847 году, согласно преданию, в один день с книгой Буля «Математический анализ логики». На самом деле на занятия логикой Буля подвигла открытая вражда между де Морганом и другим британским математиком, связанная с обвинениями в плагиате (история оправдала де Моргана). С самого начала де Морган осознал важность прозрений Буля. Он бескорыстно поощрял Буля и помогал ему в исследованиях, однако сегодня он, к сожалению, почти забыт, а в памяти потомков остались только его знаменитые законы.

Законы де Моргана проще всего выразить следующим образом.

A и B – два булевых операнда. В первом выражении они инвертируются, а затем объединяются с помощью булева оператора И. Это эквивалентно объединению двух операндов с помощью булева оператора ИЛИ и последующему инвертированию результата (соответствует оператору ИЛИ-НЕ). Во втором выражении два оператора инвертируются, а затем объединяются с помощью булева оператора ИЛИ. Это эквивалентно объединению двух операндов с помощью булева оператора И и последующему инвертированию результата (соответствует оператору И-НЕ).

Законы де Моргана – важный инструмент для упрощения булевых выражений, а значит, для упрощения схем. История показала, что именно в этом заключалось значение работы Клода Шеннона для инженеров-электриков. Однако чрезмерное упрощение схем не является целью этой книги. Нам важно собрать работающую схему, а не сделать так, чтобы она работала как можно проще. Этим мы и займемся в следующей главе – соберем работающую счетную машину.