Базовый CS с нуля
Логические вентили
В предыдущем уроке ты изучил И, ИЛИ и НЕ как абстрактные операции над значениями
истинности. Каждый оператор if, каждая проверка прав доступа, каждое правило
инвалидации кеша сводится к некоторой комбинации этих трёх операций. Но где они
физически существуют?
Они существуют в аппаратуре — в виде физических компонентов, называемых логическими вентилями. Вентиль — это небольшая схема из транзисторов: на входе провода, на выходе провод. Ты подаёшь напряжение (1) или отсутствие напряжения (0) на входы, и вентиль выдаёт правильный результат согласно реализуемой операции. Вентиль И выдаёт 1 только когда оба входа равны 1. Вентиль ИЛИ выдаёт 1, когда хотя бы один вход равен 1. Вентиль НЕ инвертирует свой единственный вход.
Это и есть мост: булева логика, которую можно рассматривать на бумаге с единицами и нулями, превращается в аппаратуру, которую можно физически построить и соединить. И как только вентили соединяются, можно собрать всё что угодно, включая арифметику.
После этого урока ты сможешь объяснить, что такое логический вентиль и как он связан с булевой операцией, описать поведение вентилей И, ИЛИ и НЕ по входам и выходу, читать простую схему из вентилей, объяснить, как вентили соединяются в схемы, и описать на концептуальном уровне, как вентили И и XOR образуют полусумматор, складывающий два бита.
Что такое вентиль. Логический вентиль — это аппаратный компонент с одним или несколькими входными проводами и одним выходным. Он собран из транзисторов — переключателей, которые открываются или закрываются в зависимости от напряжения. Конкретная схема из транзисторов различается для разных типов вентилей, но поведение всегда одно: булева функция. При входах 0 или 1 вентиль выдаёт 0 или 1 согласно своей таблице истинности.
Снаружи внутренние транзисторы не важны. Важен контракт: вентиль И — таблица истинности И, вентиль ИЛИ — таблица ИЛИ, вентиль НЕ — таблица НЕ. Вентиль — это чёрный ящик, который надёжно вычисляет одну операцию миллиарды раз в секунду по входам и выходу.
Вентили физичны: они потребляют ничтожно малую мощность, выделяют ничтожно малое количество тепла и тратят ничтожно малое время (наносекунды), чтобы выходное напряжение установилось после изменения входов. Но на уровне логики их считают мгновенными и абстрактными — так же, как таблицы истинности из предыдущего урока.
Три основных вентиля. Те же три операции, которые функционально полны в булевой логике, напрямую соответствуют трём типам вентилей.
Вентиль НЕ (инвертор): один вход, один выход. Выход противоположен входу.
| Вход A | Выход |
|---|---|
| 0 | 1 |
| 1 | 0 |
Вентиль И: два входа, один выход. Выход равен 1 только когда оба входа равны 1.
| Вход A | Вход B | Выход |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Вентиль ИЛИ: два входа, один выход. Выход равен 1, когда хотя бы один вход равен 1.
| Вход A | Вход B | Выход |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Это те же таблицы истинности, что и в предыдущем уроке, — теперь понимаемые как точные спецификации физических компонентов, которые можно изготовить и соединить.
Соединение вентилей в схемы. Настоящая сила вентилей в том, что они компонуются. Выход одного вентиля можно соединить со входом другого. Совокупность соединённых вентилей называется схемой. Схема в целом вычисляет некоторую функцию: по входным битам она производит выходные биты. Функция определяется только тем, какие вентили используются и как они соединены.
Возьмём построение XOR из И, ИЛИ и НЕ. В предыдущем уроке была показана таблица истинности XOR (истинно, когда входы различаются). В терминах вентилей:
- Подаём A и B на вентиль И. Его выход —
A И B. - Подаём A и B на вентиль ИЛИ. Его выход —
A ИЛИ B. - Подаём
A И Bна вентиль НЕ. Его выход —НЕ(A И B). - Подаём
A ИЛИ BиНЕ(A И B)на финальный вентиль И.
Финальный выход — (A ИЛИ B) И НЕ(A И B) — что в точности является XOR.
Вот как функциональная полнота И, ИЛИ, НЕ воплощается в аппаратуру: любую таблицу истинности можно реализовать в виде схемы, соединив нужные вентили.
Почему это работает
Почему вентили вообще можно каскадировать. Выход вентиля — это 0 или 1, того же типа, что и его входы. Это значит, что выход одного вентиля непосредственно совместим со входом следующего. Никаких шагов преобразования, никаких переговоров о протоколе. Уровень напряжения, означающий «1» на выходе одного вентиля, — ровно тот уровень напряжения, который означает «1» на входе следующего. Эта однородность и делает схемы компонуемыми: из существующих вентилей можно собрать новый вентиль, который снаружи ведёт себя точно как примитивный.
Схемы строят арифметику: полусумматор. Поскольку вентили свободно соединяются, из них можно строить схемы, выполняющие арифметику. Простейший пример — полусумматор, складывающий два одиночных бита.
При сложении двух битов A и B вручную:
- 0 + 0 = 0, перенос отсутствует
- 0 + 1 = 1, перенос отсутствует
- 1 + 0 = 1, перенос отсутствует
- 1 + 1 = 10 в двоичной записи (десятичное 2): бит суммы равен 0, бит переноса равен 1
Полусумматор имеет два выхода: бит суммы и бит переноса. Рассмотрим закономерность:
- Сумма = 1 ровно тогда, когда входы различаются (0+1 или 1+0). Это XOR.
- Перенос = 1 ровно тогда, когда оба входа равны 1 (1+1). Это И.
Таким образом, полусумматор — это просто вентиль И (для переноса) и схема XOR (для суммы), подключённые к одним и тем же двум входам. Новые примитивы не нужны — уже определённых вентилей достаточно.
Полный сумматор расширяет это, добавляя обработку входного переноса от предыдущего разряда, что позволяет каскадировать сумматоры для сложения многоразрядных чисел. Полный сумматор строится из двух полусумматоров и одного вентиля ИЛИ. Цепочка полных сумматоров образует арифметико-логическое устройство (АЛУ) внутри реального процессора — и там тоже только вентили.
Граничные случаи
И-НЕ: один вентиль на всё. В уроке 4 ты узнал, что И, ИЛИ, НЕ функционально полны. Существует более сильный результат: вентиль И-НЕ (NAND — выход равен 0 только когда оба входа равны 1, в остальных случаях — 1) сам по себе функционально полон. Из одних только вентилей И-НЕ можно построить НЕ, И и ИЛИ. Это значит, что весь компьютер можно собрать из единственного типа вентилей. Курс nand2tetris делает именно это, стартуя только от И-НЕ. На практике проектировщики микросхем используют другие типы вентилей для эффективности, но теоретическая полнота И-НЕ — фундаментальный результат.
Прослеживаем работу полусумматора для входов A=1, B=1.
Полусумматор имеет две части, подключённые к одним входам A и B:
- Вентиль И для выходного переноса.
- Схема XOR для выходной суммы. Напомним: XOR =
(A ИЛИ B) И НЕ(A И B).
При A=1, B=1:
Перенос (вентиль И):
- A И B = 1 И 1 = 1
Сумма (схема XOR):
- A ИЛИ B = 1 ИЛИ 1 = 1
- A И B = 1 И 1 = 1
- НЕ(A И B) = НЕ 1 = 0
- (A ИЛИ B) И НЕ(A И B) = 1 И 0 = 0
Результат: сумма = 0, перенос = 1. Это правильно: 1 + 1 = 10 в двоичной записи, то есть «бит суммы 0, бит переноса 1». Перенос распространится в следующий разряд при каскадировании с полным сумматором.
Вентиль И имеет входы A=1 и B=1. Каков его выход?
Вентиль ИЛИ имеет входы A=0 и B=0. Каков его выход?
Вентиль НЕ имеет вход A=1. Каков его выход?
В полусумматоре какой вентиль формирует бит переноса?
Полусумматор с A=1, B=0: каков бит суммы?
Полусумматор с A=1, B=0: каков бит переноса?
Полусумматор вычисляет сумму и перенос двух одиночных битов. Какой вентиль формирует бит суммы, а какой — бит переноса?
Логический вентиль — это физический аппаратный компонент, вычисляющий одну булеву операцию: И, ИЛИ или НЕ. Его входы и выход — биты (0 или 1), а поведение определяется точно его таблицей истинности. Вентили собраны из транзисторов, но используются как абстракции-чёрные ящики. Соединение вентилей образует схему, вычисляющую более сложную булеву функцию — любую таблицу истинности можно реализовать в виде схемы. Полусумматор — простая схема из вентиля И (выход переноса) и схемы XOR (выход суммы), правильно складывающая два одиночных бита. Каскадирование полных сумматоров расширяет это до многоразрядного сложения, образуя арифметико-логическое устройство внутри любого процессора. Путь от битов до арифметики целиком сделан из вентилей.