Логические вентили: Атомы вычислений

Цели урока

• Понимать принцип работы транзистора как переключателя
• Знать таблицы истинности AND, OR, NOT, XOR, NAND, NOR
• Применять законы булевой алгебры и де Моргана
• Понимать, как из вентилей строятся сумматоры и мультиплексоры

Предварительные знания

• Двоичная система счисления
• Понятие бита

• Двоичная система

В 1937 году 21-летний Клод Шеннон написал магистерскую диссертацию: электрические переключатели могут реализовывать булеву алгебру. До него компьютеров не существовало. После - стали возможны. Apple M3 с 25 миллиардами транзисторов, SHA-256 в Bitcoin, AES в TLS обычного браузера - всё это AND, OR, NOT в разных комбинациях.

• **AES-NI инструкции** в x86: XOR и S-box операции на уровне вентилей, 1 AES-раунд за 1 clock cycle. Это то, что делает TLS в 1000x быстрее программного шифрования
• **FPGA в AWS F1 инстансах**: программируемые вентили для ускорения видеотранскодинга, геномики, финансовых вычислений. Настраиваются на уровне AND/OR схем
• **Побитовые операции в Python/JS/C**: `&`, `|`, `^`, `~`, `<<`, `>>` - это прямой доступ к AND/OR/XOR/NOT/SHIFT вентилям ALU
• **Bitcoin mining**: SHA-256 хэш - это 64 раунда XOR, AND, OR, NOT и арифметических операций. ASIC-майнеры содержат миллиарды специализированных вентилей только для SHA-256
• **Redis BITCOUNT**: `BITCOUNT key` считает установленные биты через POPCNT инструкцию - аппаратная реализация подсчёта единиц через вентили

Клод Шеннон и магистерская работа, изменившая мир

1937 год. MIT. 21-летний аспирант Клод Шеннон работает на механическом дифференциальном анализаторе Вэнивара Буша и замечает: электрические реле можно организовать так же, как переменные в булевой алгебре Джорджа Буля. Его магистерская диссертация 'A Symbolic Analysis of Relay and Switching Circuits' связала математическую логику с электрическими схемами. Говард Гарднер назвал её «возможно, наиболее важной магистерской работой века». Через 10 лет Шеннон создаст теорию информации - и снова изменит всё.

Транзистор как выключатель

**Парадокс:** Процессор Apple M3 содержит 25 миллиардов транзисторов. Каждый из них умеет только одно - открываться или закрываться, как кран с водой. Никакой математики, никакой логики. Просто электронный выключатель. Как из 25 миллиардов выключателей возникает устройство, которое запускает Large Language Model?

**Транзистор** - электронный переключатель. Подаём напряжение на «затвор» - транзистор пропускает ток от источника к стоку. Убираем напряжение - блокирует. Два состояния: ток есть (1) или тока нет (0). Это и есть бит на уровне физики.

**Масштаб:** Транзистор в Apple M3 - 3 нанометра. Это примерно 15 атомов кремния в ширину. Для сравнения: толщина человеческого волоса - 70 000 нанометров. Физический предел квантового туннелирования близко.

NOT (инвертор)

**NOT** - простейший вентиль. Один вход, один выход. Инвертирует сигнал: 0 становится 1, 1 становится 0. В CMOS-схемах реализуется двумя транзисторами: PMOS (p-type) и NMOS (n-type). Они всегда работают в противофазе - когда один открыт, другой закрыт.

NOT(NOT(A)) = A. Двойная инверсия - тождество. Это используется в схемотехнике: иногда добавляют буфер из двух инверторов подряд чтобы усилить сигнал и убрать задержку, не меняя логику.

AND (И)

**AND** - выход = 1 только когда ОБА входа = 1. Реализуется как два NMOS-транзистора последовательно. Оба должны открыться чтобы ток прошёл. Это принципиальное свойство AND: один ноль на входе - всегда ноль на выходе. Поэтому AND-маскирование работает: `value & mask` обнуляет все биты где mask=0, независимо от value.

OR и XOR

**OR** - выход = 1 если ХОТЯ БЫ ОДИН вход = 1. Два NMOS-транзистора параллельно: достаточно одного чтобы ток прошёл. OR применяется для установки флагов: `flags | NEW_FLAG` гарантирует, что NEW_FLAG установлен, остальные биты не трогая.

**XOR (exclusive OR)** - выход = 1 если входы РАЗЛИЧАЮТСЯ. Это «или одно, или другое, но не оба». XOR обладает уникальными свойствами: A XOR A = 0, A XOR 0 = A. Из этого вытекает whole класс применений в криптографии и алгоритмах. В SHA-256 и AES XOR - одна из основных операций. В half-adder (полусумматор) XOR вычисляет бит суммы.

**Суперсила XOR:** A XOR A = 0. A XOR 0 = A. Swap без временной переменной: a ^= b; b ^= a; a ^= b. Проверка равенства: если (a XOR b) == 0, то a == b. AES использует XOR в MixColumns и AddRoundKey на каждом раунде.

NAND и NOR - универсальные вентили

**NAND** = NOT(AND). **NOR** = NOT(OR). На первый взгляд - просто ещё два вентиля. Но они **функционально полны**: из одного NAND можно построить любой другой вентиль. Intel, AMD, ARM - реальные чипы внутри состоят преимущественно из NAND-цепочек. Один тип ячейки на весь чип упрощает производство и верификацию.

**Практика:** FPGA (Field-Programmable Gate Array) - программируемые чипы, используемые в сетевых устройствах Cisco, ускорителях AWS FPGA и прототипировании ASIC. Программируются на уровне вентилей через HDL (Verilog, VHDL). Google использует FPGA в дата-центрах для ускорения поиска.

Булева алгебра и комбинационные схемы

Логические вентили подчиняются **булевой алгебре** - математике Джорджа Буля 1854 года с двумя значениями (0 и 1). Клод Шеннон в 1937 году показал, что булева алгебра напрямую описывает электрические схемы. Это стало теоретическим фундаментом всей цифровой электроники.

Из базовых вентилей строятся **комбинационные схемы** - где выход зависит только от текущих входов. **Мультиплексор (MUX)** выбирает один из входов по селектору. **Полусумматор** складывает 2 бита. Цепочка полных сумматоров - 64-битный ALU. Каждая операция `a + b` в Python компилируется в ~400 транзисторов на уровне железа.

Ключевые идеи

• **Транзистор** - электронный выключатель 3 нм в ширину. 25 миллиардов в Apple M3 - каждый делает одно: открыт или закрыт
• **AND**: выход = 1 только когда ВСЕ входы = 1. Применение: маскирование битов (`value & mask`), проверка флагов
• **OR**: выход = 1 если ХОТЯ БЫ ОДИН вход = 1. Применение: установка флагов (`flags | NEW_FLAG`)
• **XOR**: выход = 1 если входы РАЗЛИЧАЮТСЯ. Суперсилы: A XOR A = 0, используется в AES, SHA-256, swap без tmp
• **NAND/NOR** - функционально полные: из одного NAND строится любая логическая схема. Реальные чипы используют преимущественно NAND
• **Булева алгебра** Шеннона 1937 года: законы де Моргана, дистрибутивность - основа компиляторной оптимизации и верификации схем
• **Полусумматор (XOR + AND)** = вычисление одного бита сложения. Цепочка полных сумматоров = 64-битный ALU процессора

Связанные темы

Логические вентили - строительные блоки всего hardware. Следующий шаг - схемы из вентилей:

• АЛУ (Arithmetic Logic Unit) — Сумматоры и компараторы из вентилей - выполняют все арифметические операции CPU
• CPU: архитектура — Как из вентилей через АЛУ и регистры получается процессор
• Побитовые операции — AND, OR, XOR в коде - прямой доступ к вентилям ALU

Вопросы для размышления

• Ты разрабатываешь протокол для IoT-устройств с жёсткими ограничениями: один байт на флаги состояния (8 бит). Нужно хранить: признак питания от батареи, два бита для уровня заряда (00/01/10/11), флаг ошибки датчика, флаг режима сна, флаг обновления прошивки. Как бы ты распределил биты - и какие именно операции AND, OR, XOR использовал бы для чтения и записи каждого флага?

Связанные уроки

• arch-01-binary — Двоичная система - язык которым говорят вентили
• arch-03-alu — ALU - сумматоры и компараторы из вентилей
• arch-04-cpu — CPU строится из комбинационных и последовательностных схем
• alg-35-bit-manipulation — Битовые операции в коде - прямое отражение AND/OR/XOR
• bc-06-digital-signatures — XOR - основа симметричного шифрования и hash-функций
• dm-01