Построение схем логических элементов
В предыдущей лекции мы изучили четыре основных логических элемента. В этой лекции мы соединим их вместе, чтобы построить схемы, решающие реальные задачи.
Один логический элемент подобен винту — его функция ограничена сама по себе. Но соедините их, и вы сможете построить сколь угодно сложные функции.
Бытовая аналогия: строительство замка из кубиков Lego
Представьте, что перед вами четыре цвета кирпичиков LEGO:
- Зелёный блок = элемент И: Ток течёт только тогда, когда оба конца соединены
- Оранжевый блок = элемент ИЛИ: Ток течёт, когда подключён хотя бы один конец
- Красный блок = элемент НЕ: Включённое становится выключенным, выключенное становится включённым
- Фиолетовый блок = элемент исключающее ИЛИ: Ток течёт, когда два конца находятся в разных состояниях
Что можно построить из этих кирпичиков?
устройство для голосованияТри человека голосуют, и решает большинство. Это типичная комбинационная логическая схема — просто соедините элементы И/ИЛИ, чтобы реализовать её.
кодовый замокПравильные клавиши должны быть нажаты одновременно, чтобы разблокировать. По сути, это каскад элементов И — каждая клавиша соответствует входу, и только когда все входы равны 1, выход становится равным 1.
сигнализацияЕсли срабатывает любой датчик, звучит сигнал тревоги. По сути, это применение элементов ИЛИ — пока хотя бы один датчик выдаёт 1, сигнализация звучит.
Комбинационная логика против последовательностной логики
Прежде чем мы углубимся в построение схем, давайте разграничим два важных понятия:
| Type | Особенности | Выход зависит от | Есть ли у неё память? | Примеры |
|---|---|---|---|---|
| Комбинационная логика | Выход определяется только текущим входом | значение текущего входа | нет | Сумматор, мажоритарный элемент, дешифратор |
| Последовательностная логика | Выход определяется текущими входами + историческим состоянием | Текущий вход + ранее сохранённые значения | Да | Счётчик, регистр, конечный автомат |
Эта лекция посвящена комбинационной логике.Последовательностная логика будет подробно рассмотрена в лекции 9.
Простой способ их различать: комбинационная логика — это «что подашь на вход, то и получишь на выходе» (как математическая функция); последовательностная логика — это «я всё ещё помню, что ты подавал раньше» (как человеческая память).
Методология построения схемы: трёхшаговый метод
Существует универсальный трёхшаговый процесс построения любой комбинационной логической схемы с помощью логических элементов:
- Составьте таблицу истинностиШаг 1: Перечислите все комбинации входов и запишите ожидаемый выход для каждого случая.
- Запишите логическое выражениеШаг 2: Для каждой строки, где выход равен 1, запишите соответствующий «член-произведение» (комбинацию входов через AND), затем соедините все члены-произведения операцией OR. Это называется формой «сумма произведений».
- Нарисуйте схему / Напишите кодШаг 3: Преобразуйте логическое выражение в соединение логических элементов.
Давайте отработаем этот метод на трёх примерах, от простого к сложному.
Случай 1: Кодовый замок с двумя входами
ТребованияСлучай 1: Спроектируйте простую схему проверки пароля. Есть два входа A и B. Только когда A=1 и B=1, выход становится 1 (разблокировка); в противном случае выход равен 0 (заблокировано).
Это требование на самом деле представляет собой просто элемент AND. Но мы можем использовать его, чтобы продемонстрировать трёхшаговый метод:
Шаг 1: Таблица истинности
| A | B | Ожидаемый выход Y |
|---|---|---|
| 0 | 0 | 0 (заблокировано) |
| 0 | 1 | 0 (заблокировано) |
| 1 | 0 | 0 (заблокировано) |
| 1 | 1 | 1 (разблокировано) |
Шаг 2: Логическое выражение
Только последняя строка имеет выход 1. Соответствующий член произведения: A И B.
Итак: Y = A И B
Шаг 3: Реализация схемы
Вам нужен только один элемент И, с входами A и B и выходом Y.
Слишком просто? Давайте рассмотрим более практичный пример.
Случай 2: Мажоритарный элемент (основной случай)
ТребованияТри человека (A, B, C) голосуют по предложению (1 означает одобрение, 0 — отклонение). Предложение принимается, когда как минимум два человека одобряют (выход 1).
Это классический мажоритарный элемент с тремя входами и обязательный для изучения случай в учебниках по цифровым схемам.
Шаг 1: Составьте таблицу истинности
Три входа дают в сумме 23= 8 комбинаций:
| A | B | C | Число голосов за | Пройдено/не пройдено: Y | Описание |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | Никто не одобряет |
| 0 | 0 | 1 | 1 | 0 | Только C одобряет |
| 0 | 1 | 0 | 1 | 0 | Только B одобряет |
| 0 | 1 | 1 | 2 | 1 | B и C одобряют |
| 1 | 0 | 0 | 1 | 0 | Только A одобряет |
| 1 | 0 | 1 | 2 | 1 | A и C одобряют |
| 1 | 1 | 0 | 2 | 1 | A и B одобряют |
| 1 | 1 | 1 | 3 | 1 | Принято единогласно |
Шаг 2: Запишите логическое выражение
Найдите строки, в которых выход равен 1 (строки 4, 6, 7, 8), и запишите по одному члену произведения для каждой строки:
- Строка 4: NOT(A) AND B AND C
- Строка 6: A AND NOT(B) AND C
- Строка 7: A AND B AND NOT(C)
- Строка 8: A AND B AND C
используйте OR-соединение:Y = (NOT(A) AND B AND C) OR (A AND NOT(B) AND C) OR (A AND B AND NOT(C)) OR (A AND B AND C)
Это выражение может показаться немного длинным, но логически оно очень ясно:Y равно 1 тогда и только тогда, когда любые два или три входа равны 1。
Шаг 3: Нарисуйте схему цепи с помощью SVG
Три элемента AND проверяют, является ли каждая из трёх пар "AB", "BC" и "AC" равной 11, затем элемент OR объединяет результаты.
Интерактивная демонстрация: реализация мажоритарного элемента на Python
Пример
# Требование: голосуют три человека; решение проходит (выход 1), только когда как минимум два одобряют (1).
# ----- Повторное использование базовых логических элементов из лекции 6 -----
def AND(a, b):
return 1 if a == 1 and b == 1 else 0
def OR(a, b):
return 1 if a == 1 or b == 1 else 0
def NOT(a):
return 1 if a == 0 else 0
# ----- Метод 1: стандартная форма суммы произведений (SOP) -----
def majority_voter_sop(a, b, c):
"""
Реализация мажоритарного элемента через сумму произведений.
Непосредственно выведите из таблицы истинности: найдите все строки, в которых выход равен 1,
Запишите по одному терму AND на строку, затем соедините их с помощью OR.
"""
term1 = AND(AND(NOT(a), b), c) # ~A·B·C
term2 = AND(AND(a, NOT(b)), c) # A·~B·C
term3 = AND(AND(a, b), NOT(c)) # A·B·~C
term4 = AND(AND(a, b), c) # A·B·C
return OR(OR(term1, term2), OR(term, term4))
# ----- Метод 2: оптимизированная упрощённая форма -----
def majority_voter_optimized(a, b, c):
"""
Оптимизированная реализация мажоритарного элемента: Y = AB + BC + AC.
Эта форма требует меньше вентилей, но логически эквивалентна первому методу.
Почему это эквивалентно?
После раскрытия SOP-формы метода 1 её можно упростить, используя закон поглощения булевой алгебры:
~A·B·C + A·~B·C + A·B·~C + A·B·C
= (~A·B·C + A·B·C) + (A·~B·C + A·B·C) + (A·B·~C + A·B·C)
= B·C·(~A+A) + A·C·(~B+B) + A·B·(~C+C)
= B·C + A·C + A·B
"""
return OR(OR(AND(a, b), AND(b, c)), AND(a, c))
# ============================================
# Вывести полную таблицу истинности и сравнить два метода
# ============================================
print("=" * 60)
print(Таблица истинности мажоритарного голосования с тремя входами (ПРИМЕР демонстрации))
print("=" * 60)
print()
print("┌───┬───┬───┬────────┬──────────┬──────────┐")
print(│ A │ B │ C │ Пройдено? │ Метод SOP │ Метод оптимизации │)
print("├───┼───┼───┼────────┼──────────┼──────────┤")
for a in [0, 1]:
for b in [0, 1]:
for c in [0, 1]:
count = a + b + c
passed = "Пройдено" if count >= 2 else "Не пройдено"
sop = majority_voter_sop(a, b, c)
opt = majority_voter_optimized(a, b, c)
print(f"│ {a} │ {b} │ {c} │ {passed} │ {sop} │ {opt} │")
print("└───┴───┴───┴────────┴──────────┴──────────┘")
# ============================================
# Статистика использования логических элементов
# ============================================
print("\n" + "=" * 60)
print(" Сравнение количества логических элементов, используемых двумя методами")
print("=" * 60)
print()
print(Метод 1 (полная форма SOP):)
print(Элементы НЕ: 3 (~A, ~B, ~C))
print(Элементы И: 4 (четыре терма И, каждый требует 2 двухвходовых элемента И))
print(Элемент ИЛИ: 3 (объединение четырёх произведений))
print(Итого: примерно 14 вызовов базовых логических элементов)
print()
print("Метод 2 (оптимизированная форма Y = AB + BC + AC):")
print(Элементы И: 3 (AB, BC, AC))
print(Элемент ИЛИ: 2 (объединение трёх произведений))
print(" Итого: 5 вызовов базовых логических элементов")
print()
print(После оптимизации число вентилей сокращается примерно на 65%!)
print("В этом заключается инженерная ценность упрощения булевой алгебры.")
Обратите внимание на процесс преобразования таблицы истинности в логическое выражение. Это один из ключевых навыков в проектировании цифровых схем: увидев таблицу истинности, можно записать выражение; увидев выражение, можно нарисовать схему. Эти три представления взаимно однозначно соответствуют друг другу.
Пример 3: одноразрядный компаратор
ТребованияСравнить два 1-битных двоичных числа A и B. Вывести три сигнала: A>B, A=B, A<B
Это очень важная базовая схема — многобитные компараторы и условные проверки в процессорах развились отсюда.
Шаг 1: Таблица истинности
| A | B | A > B | A = B | A < B |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
Шаг 2: Логическое выражение
Посмотрите на таблицу истинности:
- A > B равно 1 тогда и только тогда, когда: A=1 AND B=0. Следовательно: Greater = A AND NOT(B)
- A = B равно 1 тогда и только тогда, когда: A и B одинаковы. Поэтому: Equal = NOT(A XOR B), или, иначе говоря, Equal = (A AND B) OR (NOT(A) AND NOT(B))
- A < B равно 1 тогда и только тогда, когда: A=0 AND B=1. Следовательно: Less = NOT(A) AND B
Обратите внимание, что определение A = B тесно связано с элементом XOR. Выход XOR, равный 1, означает "различны"; взятие NOT от него даёт "равны".
Шаг 3: реализация в коде
Пример
# Сравнение двух 1-битных двоичных чисел A и B
def AND(a, b):
return 1 if a == 1 and b == 1 else 0
def OR(a, b):
return 1 if a == 1 or b == 1 else 0
def NOT(a):
return 1 if a == 0 else 0
def one_bit_comparator(a, b):
"""
Однобитный компаратор: сравнивает A и B.
Возвращает кортеж (Greater, Equal, Less).
"""
greater = AND(a, NOT(b)) # A > B: A=1 и B=0
less = AND(NOT(a), b) # A < B: A=0 и B=1
# A = B: ни больше, ни меньше
# Эквивалентно NOT(A XOR B), здесь используется другая реализация
equal = AND(NOT(greater), NOT(less))
return (greater, equal, less)
# Вывести таблицу истинности
print("=" * 50)
print(Таблица истинности одноразрядного компаратора (ПРИМЕР демонстрации))
print("=" * 50)
print()
print("┌───┬───┬────────┬────────┬────────┐")
print("│ A │ B │ A > B │ A = B │ A < B │")
print("├───┼───┼────────┼────────┼────────┤")
for a in [0, 1]:
for b in [0, 1]:
gt, eq, lt = one_bit_comparator(a, b)
print(f"│ {a} │ {b} │ {gt} │ {eq} │ {lt} │")
print("└───┴───┴────────┴────────┴────────┘")
# Проверка некоторых полезных сценариев
print("\nТестовый сценарий: ")
a_test, b_test = 1, 0
gt, eq, lt = one_bit_comparator(a_test, b_test)
print(f"A={a_test}, B={b_test}: A>B={gt}, A=B={eq}, A<B={lt}")
print(f"Интерпретация: A больше B" if gt else ("A равно B" if eq else "A меньше B"))
Случай 4: дешифратор 2-в-4
ТребованияПодайте на вход 2-битное двоичное число (00, 01, 10, 11) и сделайте так, чтобы ровно одна из соответствующих 4 выходных линий была равна 1, а остальные — 0.
Дешифратор — ключевой компонент в CPU — когда CPU хочет выбрать регистр, он по сути использует дешифратор.
Таблица истинности
| A1 | A0 | Y0 | Y1 | Y2 | Y3 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
логическое выражение
- Y0 = NOT(A1) AND NOT(A0)
- Y1 = NOT(A1) AND A0
- Y2 = A1 AND NOT(A0)
- Y3 = A1 AND A0
Пример
# Вход: 2-битное двоичное число A1 A0
# Выход: ровно одна из 4 линий равна 1
def AND(a, b):
return 1 if a == 1 and b == 1 else 0
def NOT(a):
return 1 if a == 0 else 0
def decoder_2to4(a1, a0):
"""
Линейный дешифратор 2-в-4.
Верните список [Y0, Y1, Y2, Y3],
Ровно один из них равен 1, остальные равны 0.
"""
Y0 = AND(NOT(a1), NOT(a0)) # 00 → Y0
Y1 = AND(NOT(a1), a0) # 01 → Y1
Y2 = AND(a1, NOT(a0)) # 10 → Y2
Y3 = AND(a1, a0) # 11 → Y3
return [Y0, Y1, Y2, Y3]
# Вывести таблицу истинности
print("=" * 50)
print(Таблица истинности дешифратора 2-4 (ПРИМЕР Демо))
print("=" * 50)
print()
print("┌────┬────┬────┬────┬────┬────┐")
print("│ A1 │ A0 │ Y0 │ Y1 │ Y2 │ Y3 │")
print("├────┼────┼────┼────┼────┼────┤")
for a1 in [0, 1]:
for a0 in [0, 1]:
Y = decoder_2to4(a1, a0)
print(f"│ {a1} │ {a0} │ {Y[0]} │ {Y[1]} │ {Y[2]} │ {Y[3]} │")
print("└────┴────┴────┴────┴────┴────┘")
# Показать реальный сценарий использования
print("\nПрактический сценарий применения: использование дешифратора для выбора регистров)
registers = ["R0", "R1", "R2", "R3"]
for a1 in [0, 1]:
for a0 in [0, 1]:
Y = decoder_2to4(a1, a0)
idx = Y.index(1) # Найти, какая выходная линия равна 1
print(fАдрес A1A0={a1}{a0} → выбирает регистр {registers[idx]})
Дешифратор — это классическая схема «один-ко-многим». Его аналог — мультиплексор (MUX), который работает по принципу «многие-к-одному». Оба очень часто используются при проектировании тракта данных CPU. Дешифратор используется для «выбора цели» (например, в какой регистр выполнять запись), а мультиплексор — для «выбора источника» (например, из какого регистра АЛУ считывает данные).
Универсальные логические элементы: чем особенны NAND и NOR
В реальном производстве микросхем элементы NAND и NOR более «низкоуровневые», чем элементы AND и OR.
Элемент NAND = AND + NOTТо есть сначала выполняется AND, затем инверсия. NAND и NOR называют «универсальными логическими элементами», потому что каждый из них по отдельности может реализовать все булевы функции.
Почему микросхемы предпочитают NAND/NOR? Потому что в КМОП-технологии:
- Элемент NAND требует всего 4 транзистора, а элемент AND — 6 (AND = NAND + NOT).
- У элементов NAND выше скорость переключения
- Поэтому функция AND в реальных микросхемах реализуется на низком уровне с помощью NAND + NOT.
Далее проверим «универсальность» элемента NAND:
Пример
# Один элемент NAND может реализовать три основные функции: NOT, AND, OR
def NAND(a, b):
"""Элемент NAND: результат AND инвертируется.
Y = 0 тогда и только тогда, когда a=1 и b=1"""
return 0 if a == 1 and b == 1 else 1
Реализуйте NOT с помощью NAND: NOT(A) = NAND(A, A)
def NOT_from_NAND(a):
return NAND(a, a)
# используйте NAND для реализации AND:AND(A,B) = NOT(NAND(A,B)) = NAND(NAND(A,B), NAND(A,B))
def AND_from_NAND(a, b):
nand_ab = NAND(a, b)
return NAND(nand_ab, nand_ab)
# Реализуйте OR с помощью NAND: OR(A,B) = NAND(NOT(A), NOT(B))
def OR_from_NAND(a, b):
return NAND(NOT_from_NAND(a), NOT_from_NAND(b))
# ============================================
# Проверка
# ============================================
print("=" * 60)
print(Демонстрация универсальности вентилей NAND (пример демонстрации).)
print("=" * 60)
print("\n[Проверка: NOT реализовано с помощью NAND]")
for a in [0, 1]:
expected = 1 if a == 0 else 0
actual = NOT_from_NAND(a)
print(f" A={a}: NOT_from_NAND = {actual}, ожидаемое = {expected}, {'Успех' if actual == expected else 'Провал'}")
print("\n[Проверка: AND реализовано с помощью NAND]")
for a in [0, 1]:
for b in [0, 1]:
expected = 1 if a == 1 and b == 1 else 0
actual = AND_from_NAND(a, b)
print(f" A={a}, B={b}: AND_from_NAND = {actual}, ожидаемое = {expected}, {'Успех' if actual == expected else 'Провал'}")
print("\n[Проверка: OR реализовано с помощью NAND])
for a in [0, 1]:
for b in [0, 1]:
expected = 1 if a == 1 or b == 1 else 0
actual = OR_from_NAND(a, b)
print(f" A={a}, B={b}: OR_from_NAND = {actual}, period望 = {expected}, {'Through' if actual == expected else 'failure'}")
print("\nВывод: для построения ЛЮБОЙ булевой функции нужны только вентили NAND.)
print(Вот почему в курсе nand2tetris можно построить целый компьютер, начиная с вентилей NAND.)
nand2tetris (From NAND to Tetris) — известный курс по информатике. Он предлагает вам шаг за шагом построить процессор, память и операционную систему, используя только вентили NAND, а затем запустить игру «Тетрис». Если вам интересны низкоуровневые детали компьютеров, очень рекомендую.
Интерактивная демонстрация: конструктор схемы мажоритарного голосования (пример демонстрации vis-network)
Используйте нижеvis-networkОна визуализирует схему мажоритарного голосования с тремя входами (Y = AB + BC + AC).Щёлкните входные узлы A, B, C, чтобы переключать 0/1, схема автоматически вычислит и обновит цвета всех проводов —Красныйозначает, что сигнал равен 1,серыйозначает, что сигнал равен 0.