Производные вентили: NAND, NOR, XOR
Урок знакомит с составными вентилями — NAND, NOR и особенно полезным XOR.
NAND = NOT(AND), NOR = NOT(OR), XOR (исключающее ИЛИ) = 1, когда входы различны. NAND и NOR функционально полны: из любого одного строится вся логика.
Зачем нужны производные вентили
В железе NAND и NOR проще и быстрее, чем AND и OR (требуют меньше транзисторов, потому что инверсия в CMOS «естественна»). Поэтому реальные схемы часто строят из NAND. А XOR — рабочая лошадка арифметики: именно он даёт бит суммы в сумматоре, проверяет равенство и лежит в основе простейшего шифрования и контрольных сумм.
Таблицы истинности
NAND NOR XOR a b | y a b | y a b | y -----+--- -----+--- -----+--- 0 0 | 1 0 0 | 1 0 0 | 0 0 1 | 1 0 1 | 0 0 1 | 1 1 0 | 1 1 0 | 0 1 0 | 1 1 1 | 0 1 1 | 0 1 1 | 0
XOR читается как «ровно один из двух»: выход 1, если входы разные. Отсюда мнемоника: XOR — это «детектор различия».
Функциональная полнота NAND
Удивительный факт: имея только вентили NAND, можно собрать NOT, AND, OR — а значит, и весь процессор. Покажем это конструктивно:
def NAND(a, b): return 1 - (a & b)
def NOT_(a): return NAND(a, a) # NOT из NAND
def AND_(a, b): return NOT_(NAND(a, b)) # AND из NAND
def OR_(a, b): return NAND(NOT_(a), NOT_(b))# OR из NAND (закон де Моргана)
print("Проверяем сборку из одного NAND:")
print(" NOT 0 =", NOT_(0), "| NOT 1 =", NOT_(1))
for a in (0,1):
for b in (0,1):
print(f" a={a} b={b}: AND={AND_(a,b)} OR={OR_(a,b)}")Вывод:
Проверяем сборку из одного NAND: NOT 0 = 1 | NOT 1 = 0 a=0 b=0: AND=0 OR=0 a=0 b=1: AND=0 OR=1 a=1 b=0: AND=0 OR=1 a=1 b=1: AND=1 OR=1
XOR на практике: обмен без буфера и шифр
XOR обратим: a ^ b ^ b = a. Это даёт два классических трюка — обмен значений без временной переменной и простейший потоковый шифр (xor с ключом дважды восстанавливает данные).
# XOR-шифр: шифруем и расшифровываем тем же ключом
def xor_cipher(data, key):
return bytes(b ^ key for b in data)
msg = b"HELLO"
key = 0x5A
enc = xor_cipher(msg, key)
dec = xor_cipher(enc, key)
print("исходник: ", list(msg))
print("шифр: ", list(enc))
print("расшифровка:", dec.decode())
# обмен через XOR без третьей переменной
x, y = 12, 7
x ^= y; y ^= x; x ^= y
print("после обмена: x =", x, "y =", y)Вывод:
исходник: [72, 69, 76, 76, 79] шифр: [18, 31, 22, 22, 21] расшифровка: HELLO после обмена: x = 7 y = 12
Как работает под капотом
XOR выражается через базовые вентили: a XOR b = (a AND NOT b) OR (NOT a AND b). В кремнии XOR требует около 8–12 транзисторов — недёшево, поэтому в схемах его берегут. Зато один XOR заменяет цепочку проверок «равны ли биты».
Глубже: почему именно NAND стал «атомом» микросхем
Функциональная полнота NAND — это красивая математика, но у его повсеместности есть и сугубо физическая причина. В технологии CMOS инверсия достаётся почти даром: естественное поведение пары транзисторов — переворачивать сигнал. Поэтому «инвертированные» вентили NAND и NOR строятся из меньшего числа транзисторов, чем «прямые» AND и OR, которым нужен ещё дополнительный инвертор на выходе. NAND в CMOS — это всего четыре транзистора, а полноценный AND — шесть. Когда вы штампуете миллиарды вентилей, экономия двух транзисторов на каждом превращается в огромную разницу по площади, скорости и теплу. Так теоретическая полнота и практическая дешевизна сошлись в одном элементе, и NAND стал базовым «кирпичом» целых семейств логики и флеш-памяти (которую так и зовут — NAND-память).
Из этого вырастает важный для инженера навык — мыслить схему сразу в терминах NAND или NOR, а не AND/OR/NOT. Закон де Моргана здесь рабочий инструмент: он позволяет механически переписать любое выражение в форму, использующую только один тип вентиля, что прямо отображается на технологический процесс изготовления чипа.
Зачем XOR в арифметике: связь со следующими главами
XOR назван «детектором различия» не зря, и эта роль делает его сердцем сложения. Когда складываешь два бита, бит результата равен 1 ровно тогда, когда биты различны (0+1 или 1+0), а при двух единицах даёт 0 и перенос — это в точности таблица XOR для суммы и AND для переноса. Именно так устроен полусумматор, с которого начнётся глава о комбинационных схемах: сумма = a XOR b, перенос = a AND b. То есть скромный вентиль «ровно один из двух» — это половина любого сумматора, а значит, и любой арифметики процессора. Когда вы видите XOR, вы смотрите на будущий строительный блок калькулятора внутри чипа.
Та же роль детектора различия делает XOR идеальным для сравнения на равенство: если a XOR b даёт ноль во всех битах, значения совпадают. Процессоры используют это, чтобы проверять равенство чисел за одну операцию. А связь «XOR обнуляет одинаковое» объясняет популярную идиому x ^ x = 0, которой обнуляют регистр быстрее, чем присваиванием.
Глубже: обратимость XOR и где она действительно работает
Свойство a ^ b ^ b = a кажется забавным фокусом, но именно на нём держатся серьёзные технологии. Массивы RAID хранят на отдельном диске XOR всех остальных дисков: если один диск выходит из строя, его содержимое восстанавливают, проксорив уцелевшие, — та же обратимость, что в обмене переменных. Контрольные суммы и коды коррекции ошибок используют XOR, чтобы по «лишним» битам обнаруживать и чинить искажения при передаче. И хотя учебный однобайтовый XOR-шифр ломается мгновенно, его старший брат — потоковый шифр, складывающий данные по XOR с длинной непредсказуемой псевдослучайной последовательностью — лежит в основе реальной криптографии. Принцип всюду один: XOR обратим и идеально «перемешивает», не теряя информации, — а это драгоценное свойство и для надёжности, и для секретности.
Частые ошибки
- Считать XOR «обычным ИЛИ». При двух единицах XOR даёт 0, а OR — 1.
- Думать, что XOR-шифр стойкий. Однобайтовый ключ ломается за секунды; XOR-шифр — учебный пример, не защита.
- Забывать про де Моргана. OR через NAND получают именно по закону де Моргана:
a OR b = NOT(NOT a AND NOT b).
Итог
- NAND/NOR — инвертированные AND/OR; каждый функционально полон.
- XOR — «детектор различия»: 1 при разных входах; основа суммы и сравнения.
- XOR обратим: даёт обмен без буфера и простейший (нестойкий) шифр.