Логические элементы и схемы: И, ИЛИ, НЕ

Ночью на стоянке сработала сирена. Реакция машины честная: сирена включается, когда сработал датчик движения И охрана поставлена на сигналку, ИЛИ когда кто-то нажал тревожную кнопку. Это готовое логическое выражение (A И B) ИЛИ C — но вычисляет его не охранник и не таблица истинности на бумаге, а железо: схема из логических элементов, у которой на входах нули и единицы, а на выходе — команда «включить сирену». Таблицы истинности ты уже умеешь строить, операции И, ИЛИ, НЕ знаешь по именам. Сейчас спустимся на уровень ниже: каждый вентиль — физическая деталь, по проводам бежит сигнал, и любую схему можно прочитать как текст — слева направо. Схема — это способ записать рассуждение железом: рассуждение нельзя потерять, забыть или устать от него. А вентили живут не только на стоянке: дверной замок «откроет, если есть ключ И нажата ручка», стиральная машина нальёт воду, «если дверца закрыта И программа запущена» — те же конъюнкции и дизъюнкции, только в быту.

История вопроса: Буль, Шеннон и транзистор

Алгебра, на которой стоят вентили, старше электроники на век с лишним: в 1854 году англичанин Джордж Буль описал логику числами, где единица — «истина», ноль — «ложь». Железо подтянулось в 1937-м: Клод Шеннон в дипломной работе показал, что цепочки электрических реле вычисляют те же «И» и «ИЛИ», что и булева алгебра, — с этой работы начинается вся цифровая техника. В 1947 году в лаборатории Bell Labs собрали первый транзистор, и логические элементы уместились в кристалл: сегодня на процессорной пластине площадью с ноготь живут миллиарды вентилей. Получается, урока логики девятнадцатого века хватает, чтобы описать телефон двадцать первого.

Вентиль: логическая операция в железе

Логический элемент (его ещё называют вентиль) — миниатюрная схема из транзисторов, которая принимает на входах сигналы 0 и 1 и выдаёт на выходе тоже 0 или 1. Сигнал — это напряжение: нет напряжения — ноль, есть — единица; никаких «наполовину приоткрытых дверей» у машины нет. Вентиль НЕ (инвертор) имеет один вход и один выход и переворачивает сигнал: на входе 0 — на выходе 1. Вентиль И (конъюнктор) и вентиль ИЛИ (дизъюнктор) берут два входа и работают ровно как операции из алгебры логики: конъюнктор выдаёт единицу только при единицах на всех входах, дизъюнктор — при единице хотя бы на одном. На схемах в российских учебниках элементы рисуют прямоугольниками: внутри символа & сидит вентиль И, внутри символа 1 — вентиль ИЛИ, а инвертор отличается кружком на выходе. Кружок всегда означает инверсию: встретишь его у любого прямоугольника — знай, сигнал перед выходом переворачивается. В англоязычных книгах вместо прямоугольников рисуют фигуры со скруглённой спинкой — обозначение другое, а таблица истинности та же самая. Сведём три элемента в шпаргалку: И — два входа, единица только при двух единицах сразу; ИЛИ — два входа, единица при любой единице; НЕ — один вход, выход всегда противоположен входу. Эти три детали — полный конструктор: из них, как из кубиков, собирают всё остальное — от ячейки памяти до схемы, складывающей числа.

Читаем схему: сигнал слева направо

Схема читается как дорога: входы слева, выход справа, сигнал течёт в одну сторону. У каждого провода в конкретный момент есть своё значение — 0 или 1, — и оно одно и то же у всех вентилей, к которым провод подключён. Чтение простое: подписываешь значения на входах, идёшь от вентиля к вентилю и дописываешь значения на проводах, пока не дойдёшь до выхода. Такие пометки называются трассировкой. Вторая задача встречается в контрольных постоянно: по готовой схеме записать выражение. Ход обратный: смотришь на выход, видишь последний вентиль и оборачиваешь его операцией вокруг подвыражений входов. Например, схема с двумя датчиками движения: датчик у двери A и датчик у окна B заходят в вентиль ИЛИ, а его выход — в инвертор. Записываем от выхода: НЕ поверх ИЛИ даёт $F=\neg (A\vee B)$. Логика схемы понятна и по-житейски: «комната пуста», если ни дверь, ни окно не потревожены. Прогоним трассировку на двух наборах. Пусть A = 0 и B = 0: дизъюнктор складывает два нуля и отдаёт 0, инвертор переворачивает — на выходе F = 1, комната пуста. Пусть A = 1 и B = 0: ИЛИ даёт 1, инвертор — 0, F = 0: движение зафиксировано, пустой комнату не назовёшь. Два прогона — и поведение схемы понятно без единой строки таблицы. Чем больше входов у схемы, тем важнее подписи: на бумаге легко спутать провода, а подпись на каждом проводе превращает чтение схемы в аккуратное заполнение пропусков.

И-НЕ и ИЛИ-НЕ: универсальные вентили

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

Синтез: собираем схему по выражению

Таблица подтвердила сборку: единицы стоят в пяти строках, и каждая обошлась без чудес — только честная работа трёх вентилей. Обрати внимание на строку A = 1, B = 0, C = 1: оба входа дизъюнктора получили нули, и F рухнула в ноль, хотя по отдельности условия почти сошлись. Именно так схемы проверяют в задачах: подставили строку — прошли по вентилям — сравнили с ответом. Дальше по этой же тропе стоит сумматор: перенос в старший разряд при сложении двух бит выдаёт вентиль И — перенос случается, только когда оба слагаемых равны единице. Добавь к нему схему для разряда суммы — получится полусумматор, первый кирпич арифметики процессора. В реальном процессоре таких вентилей миллиарды: транзисторы собраны в элементы, элементы — в узлы, узлы — в то, что складывает числа, пока ты печатаешь сообщение. На экзаменах тему спрашивают в двух формах: по схеме записать выражение и по выражению сосчитать вентили — обе решаются тем же ходом от выхода.

У вентилей есть свойство, которого не видно на бумаге, — скорость. Сигнал проходит через элемент не мгновенно: задержка измеряется наносекундами и меньше, но цепочка вентилей складывает их по очереди. Отсюда «тикает» процессор: тактовая частота — это договорённость «за один такт сигнал успевает пройти самую длинную цепочку схемы». При частоте в три миллиарда тактов в секунду на такт приходится меньше трети наносекунды — значит, проектировщики обязаны укладывать вычисление в крошечное число вентилей подряд. Это ограничение живёт на другом конце той же темы: чем глубже логическая схема, тем дольше идёт сигнал.

Подсказка: клавиши J — следующая тема, K — предыдущая, на телефоне: свайп влево/вправо — соседняя тема