6 / 63 · Теория

Универсальные элементы: схема только из NAND

Покажите функциональную полноту NAND и NOR конструктивно и проверьте промежуточные сигналы XOR.

Что означает «любая схема»

Из одних NAND можно построить NOT, AND и OR; этими операциями выражается любая комбинационная логическая функция с конечным числом входов. В этом смысле NAND — универсальный элемент^{Универсальный вентиль позволяет реализовать любую булеву функцию, используя только многократные экземпляры этого типа вентиля. Типичные примеры — NAND и NOR.}. Это не означает, что один NAND решает также задачи хранения, тактирования, проводников и питания.

\overline a=\operatorname{NAND}(a,a)

ab=\operatorname{NAND}(n,n),\quad n=\operatorname{NAND}(a,b)

a+b=\operatorname{NAND}(\operatorname{NAND}(a,a),\operatorname{NAND}(b,b))

Если подать один сигнал на оба входа NAND, получится NOT. Для AND результат NAND инвертируют^{Инверсия — операция NOT, меняющая 0 на 1 и 1 на 0. Черта над формулой означает применение NOT ко всему выражению под ней. Подробнее} ещё раз; для OR используют закон де Моргана^{Законы де Моргана: инверсия результата AND равна OR инвертированных входов; инверсия результата OR равна AND инвертированных входов. Подробнее}. У NOR тоже можно объединить входы, получив NOT, и аналогично показать универсальность.

XOR из четырёх NAND

Определим промежуточные сигналы в таком порядке:

n_0=\overline{ab},\quad n_1=\overline{a n_0},\quad n_2=\overline{b n_0},\quad y=\overline{n_1n_2}

a	b	n0	n1	n2	y
0	0	1	1	1	0
0	1	1	1	0	1
1	0	1	0	1	1
1	1	0	1	1	0

Постройте XOR с общим промежуточным сигналом

Первый NAND: n0 = NAND(a, b)
Два промежуточных NAND: n1 = NAND(a, n0); n2 = NAND(b, n0)
Последний NAND: y = NAND(n1, n2)

Два NAND второго уровня работают параллельно. Всего элементов 4, но самый длинный логический путь содержит 3 уровня. В простой модели с максимальной задержкой каждого элемента 2 ns максимальная сумма равна 6 ns. Влияние реальной нагрузки и проводников учитывают отдельно.

Сравните результат четырёх NAND с XOR

XOR · Таблица истинности
a	b	y
0	0	0
0	1	1
1	0	1
1	1	0

Самостоятельно заполните четыре строки таблицы и сравните с XOR выше. Функциональная эквивалентность утверждает совпадение выходов для всех входов, а не равенство числа элементов или задержки распространения^{Задержка распространения — время от изменения входа до установления правильного выхода. Логическая эквивалентность выражений и их временные характеристики — разные вопросы. Подробнее}.

Попробуйте сами

Запишите NOT и AND только через NOR. Сколько элементов и уровней на самом длинном пути содержит ваша реализация AND?

Прочитать объяснение

NOT a=NOR(a,a). AND=NOR(NOR(a,a), NOR(b,b)). Два инвертора входов и последний NOR дают всего 3 элемента; самый длинный путь содержит 2 уровня.