Булева логика и логические вентили: из чего собран процессор

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

Ответ обескураживающе прост. Внутри процессора нет ни арифметики, ни чисел, ни «понимания». Есть только миллиарды крошечных электрических ключей, соединённых так, что если на входы подать напряжения, изображающие два числа, то на выходах само собой возникнет напряжение, изображающее их сумму. Мостик между «ключ включён/выключен» и «2 + 2 = 4» — это булева алгебра. Она — та математика, которую физика умеет исполнять даром.

Эта статья ведёт снизу вверх: две величины и три операции → вентили → сумматор (арифметика из чистой логики) → защёлка (память из петли обратной связи) → и понимание того, что весь процессор — это большая, но принципиально понятная комбинация тех же элементов.

Булева алгебра: вся математика на двух значениях

В 1854 году Джордж Буль в книге «An Investigation of the Laws of Thought» предложил алгебру, где переменные принимают лишь два значения — «истина» и «ложь». Почти сто лет это считалось чистой логикой, философской забавой. В 1937-м студент MIT Клод Шеннон в магистерской диссертации «A Symbolic Analysis of Relay and Switching Circuits» заметил: если «истину» назвать замкнутым реле, а «ложь» — разомкнутым, то законы Буля буквально описывают, как ведут себя электрические схемы. Эту работу часто называют самой важной магистерской диссертацией XX века — она и есть фундамент всей цифровой техники.

Договоримся о величинах: 1 («истина», есть напряжение) и 0 («ложь», нет напряжения). Над ними определены три базовые операции — этого набора достаточно, чтобы выразить любую логическую функцию.

Полное поведение функции от булевых входов задаётся таблицей истинности — перечислением выхода для каждой комбинации входов. Для двух входов комбинаций всего четыре:

Здесь же появляется важнейшая производная операция — исключающее ИЛИ (XOR, ⊕): «1, когда входы различны». XOR — это одновременно «сложение по модулю 2» и «управляемый инвертор», и мы увидим его в самом сердце сумматора.

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

• Коммутативность: A ∧ B = B ∧ A, A ∨ B = B ∨ A
• Идемпотентность: A ∧ A = A, A ∨ A = A
• Поглощение: A ∨ (A ∧ B) = A
• Законы де Моргана: ¬(A ∧ B) = ¬A ∨ ¬B и ¬(A ∨ B) = ¬A ∧ ¬B

Законы де Моргана — не абстракция: именно они позволяют переделать схему из «И» в схему из «ИЛИ» с инверторами, а это часто дешевле в кремнии. Их же вы каждый день применяете в коде, переписывая !(a && b) в !a || !b. Формальные корни этих законов — в математической логике и теории множеств; систематический обзор — в треке математики.

Вентиль: операция, отлитая в железо

Логический вентиль (gate) — это физическая схема, вычисляющая одну булеву операцию: на входах напряжения-биты, на выходе — напряжение-результат. У каждой операции свой общепринятый (ANSI/IEEE) символ; кружок на выходе всегда означает инверсию.

Кроме трёх базовых на схемах постоянно встречаются их инверсии: NAND (¬(A∧B)), NOR (¬(A∨B)) и XNOR (¬(A⊕B), «1, когда входы равны»). Причина не в удобстве записи, а в физике: как мы увидим ниже, транзистор естественно строит именно инвертирующий вентиль, поэтому NAND и NOR в кремнии дешевле и быстрее, чем «чистые» AND и OR.

Функциональная полнота: одного вентиля достаточно

Замечательный факт: NAND сам по себе функционально полон — из одних только NAND-вентилей можно собрать любую булеву функцию, а значит, и любой процессор. То же верно и для NOR. Проверяется конструктивно — выразим через NAND все три базовые операции:

NOT A      = A NAND A                      (оба входа = A)
A AND B    = NOT (A NAND B)                = (A NAND B) NAND (A NAND B)
A OR  B    = (NOT A) NAND (NOT B)          = (A NAND A) NAND (B NAND B)

Практический смысл огромен: заводу-изготовителю достаточно уметь безупречно печатать один тип вентиля и тиражировать его миллиардами — вся сложность переносится в то, как эти одинаковые элементы соединены. Это первый по-настоящему мощный пример принципа, который пронизывает всю информатику: сложное поведение = простой элемент × правильная композиция.

От транзистора к вентилю: где логика встречается с физикой

Вентиль — всё ещё абстракция. Физически его строят из транзисторов — управляемых напряжением ключей. В доминирующей технологии КМОП (CMOS) используют пары комплементарных транзисторов: nMOS проводит ток, когда на его затворе логическая 1, а pMOS — наоборот, когда на затворе 0. Простейшая схема — инвертор (вентиль NOT) — это ровно два транзистора.

Логика схемы: вход 0 открывает верхний (pMOS) ключ — выход подтягивается к «1»; вход 1 открывает нижний (nMOS) — выход садится на «0». Ровно инверсия. Красота КМОП в том, что в любом устойчивом состоянии открыт только один ключ, и сквозного тока от питания к земле практически нет — энергия тратится в основном на переключения. Отсюда, забегая вперёд, и берётся связь «выше тактовая частота → больше переключений в секунду → больше тепла».

NAND и NOR в КМОП строятся из четырёх транзисторов, а вот AND и OR приходится делать как NAND+инвертор — то есть дороже. Поэтому синтезаторы схем охотнее раскладывают логику на NAND/NOR. Как из вентилей вырастает целый исполнитель команд — тема следующей статьи «Как работает процессор»; здесь нам важно лишь, что уровень «транзистор → вентиль» замкнут и надёжен.

Слои, по которым мы поднимаемся, удобно окинуть одной картой:

Комбинационная логика: как из вентилей рождается арифметика

Схема, выход которой зависит только от текущих входов (без памяти о прошлом), называется комбинационной. Самый показательный пример — сложение. Покажем, что «2 + 2 = 4» — это не магия, а две таблицы истинности.

Полусумматор: сложение двух битов

Сложим два бита A и B. Результат — два бита: младший S (сумма) и перенос C в следующий разряд.

Вглядитесь в столбцы. Столбец S — это в точности таблица XOR. Столбец C — таблица AND. То есть:

S = A ⊕ B
C = A ∧ B

Два вентиля — и вот уже железо «умеет» складывать биты. Это и есть полусумматор.

Полный сумматор и перенос по цепочке

Чтобы складывать многоразрядные числа, каждому разряду нужно принимать ещё и перенос Cin из младшего разряда. Такой блок — полный сумматор (три входа: A, B, Cin; два выхода: сумма S и перенос Cout). Его собирают из двух полусумматоров и одного вентиля OR:

Соответствующие булевы выражения:

S    = A ⊕ B ⊕ Cin
Cout = (A ∧ B) ∨ ((A ⊕ B) ∧ Cin)

Теперь соединим Cout каждого разряда со входом Cin следующего — и получим сумматор со сквозным переносом (ripple-carry adder), который складывает целые 32- или 64-битные числа. Ровно этот блок стоит в арифметико-логическом устройстве (ALU) процессора. Логическое вычитание получается тем же сумматором через дополнительный код (прибавить отрицание +1), а из сложения и сдвигов вырастает умножение. Так вся целочисленная арифметика сводится к комбинациям шести вентилей.

Здесь же прячется первая утечка абстракции: ripple-carry «ждёт», пока перенос доползёт через все разряды, — задержка растёт линейно с разрядностью. Поэтому реальные ALU используют схемы ускоренного переноса (carry-lookahead) — платят лишними вентилями за скорость. Классический trade-off «площадь против задержки», который вы ещё много раз встретите в алгоритмах как «память против времени».

Мультиплексор и дешифратор: логика выбора

Арифметика — не единственное, что делают из вентилей. Два строительных блока управления встречаются повсюду:

• Мультиплексор (MUX) — «переключатель»: по управляющему биту S пропускает на выход либо вход D0, либо D1. Выражение: Q = (¬S ∧ D0) ∨ (S ∧ D1). Это аппаратный if.
• Дешифратор (decoder) — из n-битного адреса зажигает ровно одну из 2ⁿ линий. Именно так процессор по номеру регистра выбирает нужный регистр, а память — нужную ячейку (подробнее — в статье об иерархии памяти).

Из мультиплексоров, кстати, тоже можно собрать что угодно: MUX 2-в-1 с константами на входах реализует любую булеву функцию — ещё один взгляд на функциональную полноту.

Секвенциальная логика: как из петли рождается память

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

Простейший элемент памяти — SR-защёлка из двух перекрёстно соединённых вентилей NOR. Вход S (set) ставит 1, вход R (reset) ставит 0, а когда оба равны 0 — защёлка удерживает последнее значение. Один бит, который остаётся собой, пока его не перезапишут:

У «сырой» защёлки есть изъян: S=1, R=1 — запрещённое состояние, а реагирует она на входы в любой момент, что порождает гонки. Поэтому на практике используют D-триггер (flip-flop): у него один вход данных D и вход тактового сигнала clock. Правило простое — «по фронту такта запомни то, что сейчас на D, и держи до следующего фронта». Именно D-триггер — атом хранения в процессоре: 64 таких элемента в ряд образуют один регистр, а тактовый сигнал синхронно защёлкивает в них новое состояние на каждом такте.

Вот здесь и смыкаются слои. Комбинационная логика (сумматоры, MUX) вычисляет следующее состояние; регистры на D-триггерах хранят текущее; тактовый генератор командует «шаг!». Этот цикл «вычислили → защёлкнули → снова вычислили» и есть физическая основа цикла fetch-decode-execute, а долговременное хранение, переживающее выключение питания, — уже тема памяти и персистентности.

Где эта абстракция протекает

По правилам трека — честно о трещинах. «Вентиль — это булева функция» верно как модель, но в кремнии он остаётся физическим устройством, и физика иногда проступает:

• Задержка распространения (propagation delay). Сигнал идёт через вентиль не мгновенно — десятки-сотни пикосекунд. Длина самой длинной цепочки вентилей между двумя триггерами («критический путь») задаёт максимальную тактовую частоту. Отсюда фундаментальный предел: чем глубже логика между тактами, тем ниже частота. Это причина, по которой процессор нельзя просто «разогнать до бесконечности».
• Глитчи (hazards). Из-за разных задержек по путям выход может кратковременно «дёрнуться» в неверное значение, прежде чем устаканиться. Комбинационную логику это не портит (ждём, пока успокоится), но защёлкивать её нужно только после стабилизации — за этим и следит такт.
• Метастабильность. Если данные на D-триггере меняются ровно в момент фронта такта (типично для сигналов из другого тактового домена), триггер может застрять в неопределённом состоянии на непредсказуемое время. Реальная головная боль при передаче данных между асинхронными частями чипа; лечится синхронизаторами, но полностью не устраняется — вероятность лишь снижают.
• Fan-out и уровни напряжения. Один выход не может питать бесконечно много входов; «0» и «1» — это диапазоны напряжений с зоной неопределённости между ними, а помехи и просадки питания способны эту границу разрушить.

Для написания прикладного кода эти детали не нужны — в том и ценность абстракции. Но когда вы читаете про «частоту 5 ГГц», «тайминги памяти» или разгон — вы смотрите ровно на эти протечки цифровой логики.

Как вы встречаете булеву логику в коде

Даже вдали от кремния булева логика — ваш ежедневный инструмент. Два разных её проявления стоит различать чётко.

1. Логические (булевы) операторы работают с истиной/ложью и часто «ленивы» (short-circuit): вычисляют второй операнд, только если он влияет на результат.

# Короткое замыкание: если user is None, user.is_admin даже не вычисляется —
# это защищает от ошибки обращения к атрибуту None.
if user is not None and user.is_admin:
    grant_access()

# Закон де Моргана в рефакторинге читаемости:
# not (a and b)  эквивалентно  (not a) or (not b)

2. Побитовые операторы применяют вентили AND (&), OR (|), XOR (^), NOT (~) одновременно ко всем битам машинного слова — это буквально ряд вентилей из этой статьи, работающий над 64 битами за один такт. Отсюда классические приёмы «битовых масок»:

READ    = 0b001   # флаги-права как отдельные биты
WRITE   = 0b010
EXECUTE = 0b100

perms = READ | WRITE          # включить биты чтения и записи  -> 0b011
can_write = perms & WRITE      # проверить бит: != 0, значит есть  -> 0b010
perms = perms & ~WRITE         # снять бит записи (AND с инверсией) -> 0b001
perms = perms ^ EXECUTE        # переключить бит исполнения (XOR)   -> 0b101

# XOR обратим: x ^ k ^ k == x. Отсюда — простейшее (не криптостойкое!)
# «шифрование» и трюк обмена двух чисел без временной переменной:
a, b = 5, 9
a ^= b; b ^= a; a ^= b         # теперь a == 9, b == 5

Побитовые операции — это способ «спуститься» из языка высокого уровня прямо к вентилям: флаги в одном целом, быстрые проверки чётности (n & 1), умножение и деление на степени двойки сдвигами (n << 3 == n * 8), хеши и контрольные суммы. Тот факт, что XOR обратим и складывает по модулю 2, лежит в основе и сумматора, и контроля чётности, и потоковых шифров — подробнее в статье об основах безопасности.

А когда логики становится слишком много, её проектируют, а не паяют: инженеры описывают схему на языках HDL (Verilog, VHDL), а САПР-синтезатор сам раскладывает булевы выражения на вентили и оптимизирует их — минимизацией (карты Карно, алгоритм Квайна—Мак-Класки) добиваясь меньшего числа элементов и короче критического пути. На FPGA такую схему можно «прошить» и запустить, не изготавливая чип, — прямой практический выход всего, о чём шла речь.

Мини-итог

• 0 и 1 плюс три операции (И, ИЛИ, НЕ) — этого достаточно, чтобы выразить любую логическую функцию; поведение задаётся таблицей истинности.
• Вентиль — операция, отлитая в железо. NAND (или NOR) функционально полон: из одного типа вентиля строится всё остальное.
• Транзистор — управляемый ключ; пара КМОП даёт инвертор, из инверторов и ключей — все вентили. Так физика начинает исполнять булеву алгебру.
• Комбинационная логика без памяти даёт арифметику: XOR + AND = полусумматор, цепочка полных сумматоров = сложение целых чисел, а с ним — вся арифметика ALU.
• Секвенциальная логика через обратную связь даёт память: SR-защёлка → D-триггер → регистр. Такт синхронизирует цикл «вычислили → запомнили».
• Абстракция вентиля протекает задержками, глитчами и метастабильностью — и именно это вы видите за словами «тактовая частота» и «разгон».
• В коде та же логика живёт в ленивых булевых и побитовых операторах — прямом мостике от языка к вентилям.

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

Что дальше

Как работает процессор: фон Нейман, регистры, ALU, fetch-decode-execute — соберём из вентилей, сумматоров и регистров этой статьи полноценную машину, которая читает и исполняет программу.