Цифровая логика: вентили, карты Карно и триггеры: задачи с пошаговыми решениями
Бесплатные задачи по теме Цифровая логика: вентили, карты Карно и триггеры с рисунками, подсказками и подробными решениями. Каждый раз новые значения, трёх уровней: вентили, таблицы истинности и задержки, булева алгебра, карты Карно и мультиплексоры, безразличные состояния, триггеры и счётчики.
Бесплатная задачаЛёгкая
NAND и NOR — универсальные вентили: любую логическую функцию можно построить только из одного из них. Каково минимальное число N двухвходовых вентилей NAND, нужных для построения показанной функции NOT?
Средняябулева алгебра, карты Карно и мультиплексоры
Сложнаябезразличные состояния, триггеры и счётчики
Как решать задачи по теме «Цифровая логика: вентили, карты Карно и триггеры»
Для схемы идите от входов к выходу вентиль за вентилем и записывайте значение на каждом проводе или запишите её выражение и заполните таблицу истинности.
Для упрощения поставьте единицы (и безразличные состояния как X) на карту Карно со строками и столбцами в коде Грея: 00, 01, 11, 10.
Покройте единицы как можно меньшим числом как можно больших групп по 1, 2, 4, 8 или 16 клеток, с переходом через края; каждая группа — один член-произведение из переменных, которые остаются постоянными. Для формы POS группируйте нули.
Для триггеров и счётчиков считывайте входы на каждом активном фронте тактового сигнала, записывайте состояние после каждого фронта и помните, что n-разрядный счётчик возвращается к началу после 2ⁿ состояний.
Типичные ошибки
Располагать столбцы карты Карно как 00, 01, 10, 11 вместо кода Грея 00, 01, 11, 10.
Забывать, что группы могут переходить через края, или рисовать группы из 3 или 6 клеток.
Покрывать безразличные состояния, которые не увеличивают группу.
Забывать о возврате счётчика к началу или читать Q₃Q₂Q₁Q₀ в неверном порядке.
Основные формулы
Основные вентили
A·B, A + B, A′, (A·B)′, (A + B)′, A ⊕ B
Правила булевой алгебры
X + X′ = 1, X·X′ = 0, X + XY = X, XY + XY′ = X
Законы де Моргана
(X·Y)′ = X′ + Y′, (X + Y)′ = X′·Y′
Порядок на карте Карно
00, 01, 11, 10 (Gray code)
Группа из 2ᵏ клеток
теряет k переменных
Мультиплексор 4 в 1
F = A′B′I0 + A′BI1 + AB′I2 + ABI3
Триггеры
D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
Счётчики
n-разрядный: 2ⁿ состояний; по модулю N: наименьшее n, при котором 2ⁿ ≥ N; fout = fclk/N
Асинхронный счётчик
fmax = 1/(n·tpd)
Кольцевой счётчик и счётчик Джонсона
n и 2n состояний
Изучите тему «Цифровая логика: вентили, карты Карно и триггеры» с нуля
Цифровые схемы работают с двумя значениями: 0 (низкое напряжение, ложь) и 1 (высокое напряжение, истина). Логический вентиль принимает один или несколько входов и выдаёт один выход.
AND даёт 1 только тогда, когда все входы равны 1. Записывается A·B или AB.
OR даёт 1, когда хотя бы один вход равен 1. Записывается A + B.
NOT инвертирует: 0 становится 1, а 1 становится 0. Записывается A′ (или с чертой над A).
NAND и NOR — это AND и OR, за которыми следует NOT; маленький кружок на обозначении означает «инвертировано».
XOR (A ⊕ B) даёт 1, когда входы различаются.
Таблица истинности перечисляет выход для каждой комбинации входов: 2ⁿ строк для n входов. Строка ABC = 101 имеет номер 5 и называется минтермом m₅.
Самопроверка A = 1 и B = 0. Что выдаёт вентиль NAND?
0
1
Зависит от предыдущего выхода
Ничего: NAND требует, чтобы оба входа были равны 1
Ответ: 1. AND от 1 и 0 равно 0, и NAND инвертирует его в 1. NAND равен 0 только тогда, когда все его входы равны 1.
2Булева алгебра
Логические выражения подчиняются правилам, как обычная алгебра, плюс нескольким собственным. Самые полезные из них:
X + X′ = 1 X·X′ = 0 X + X = X X + X·Y = X
X·Y + X·Y′ = X де Морган: (X·Y)′ = X′ + Y′, (X + Y)′ = X′·Y′
Правило склеивания X·Y + X·Y′ = X лежит в основе упрощения: два члена, различающиеся одной переменной, объединяются, и эта переменная исчезает.
Сумма произведений (SOP) — это OR из членов AND, например F = AB′ + C. Произведение сумм (POS) — это AND из членов OR, например F = (A + B)(B′ + C). Каждый член-произведение состоит из литералов: переменных с штрихом или без него.
3Карты Карно
Карта Карно — это таблица истинности, нарисованная в виде сетки, в которой соседние клетки отличаются ровно одной переменной. Поэтому строки и столбцы идут в порядке 00, 01, 11, 10 (код Грея), а не в двоичном порядке.
Запишите 1 в клетку каждого минтерма; маленькое число в каждой клетке — это номер минтерма.
Обведите прямоугольниками по 1, 2, 4, 8 или 16 клеток единицы. Группы могут переходить через края: левый и правый столбцы соседние, как и верхняя и нижняя строки.
Делайте каждую группу как можно больше и используйте как можно меньше групп, пока не будет покрыта каждая единица.
Читайте каждую группу как член-произведение: оставляйте только переменные, которые внутри неё не меняются. Группа из 2ᵏ клеток теряет k переменных.
На карте выше четыре единицы образуют одну группу. Внутри неё меняются A и C, остаётся постоянным только B = 1, поэтому F = B.
Клетки с X — это безразличные состояния (don’t-care): комбинации входов, которые никогда не встречаются. Используйте X как 1, если это увеличивает группу, а иначе игнорируйте. Если группировать нули, получится минимальная форма POS.
Самопроверка Сколько литералов даёт группа из 4 клеток на карте с 4 переменными?
1
2
3
4
Ответ: 2. Четыре клетки — это 2², поэтому две переменные внутри группы меняются и выпадают. Из четырёх переменных остаются две.
4Разобранный пример
Пройдите каждый шаг. Попробуйте предсказать следующий, прежде чем открыть его.
Разобранный пример
Найдите минимальную форму SOP функции F(A, B, C) = Σm(0, 2, 4, 5, 6) и посчитайте её литералы.
1
Заполните карту
Строки A = 0, 1; столбцы BC = 00, 01, 11, 10. Единицы стоят в m0, m2 (строка 0, столбцы 00 и 10) и в m4, m5, m6 (строка 1, столбцы 00, 01 и 10).
2
Самая большая группа
Столбцы BC = 00 и BC = 10 соседние через край. Вместе они содержат m0, m2, m4 и m6: группу из четырёх. Постоянна только C = 0, поэтому эта группа даёт C′.
3
Покройте последнюю единицу
m5 (A = 1, BC = 01) всё ещё не покрыта. Объедините её с соседней m4: в этой паре постоянны A = 1 и B = 0, поэтому член равен AB′.
4
Прочитайте ответ
F = C′ + AB′
Три литерала в двух членах. Группировка одной m5 дала бы AB′C — более длинный член: всегда делайте группы как можно больше, даже если они пересекаются.
Ответ
F = C′ + AB′, 3 литерала.
5Триггеры и счётчики
Вентили реагируют на свои входы сразу. Триггер (flip-flop) хранит один бит и меняется только по активному фронту тактового сигнала (обычно по переднему).
D-триггер: Q становится равным D по каждому фронту тактового сигнала (Q⁺ = D).
T-триггер: переключается при T = 1, сохраняет состояние при T = 0.
JK-триггер: JK = 00 сохраняет, 01 сбрасывает в 0, 10 устанавливает в 1, 11 переключает.
Переключающийся триггер меняется по каждому переднему фронту, поэтому частота его выхода вдвое ниже тактовой. Цепочка из n таких триггеров образует n-разрядный двоичный счётчик с 2ⁿ состояниями. Счётчик по модулю N считает 0, 1, …, N − 1 и возвращается к 0; ему нужно наименьшее n, при котором 2ⁿ ≥ N, а его последний выход работает на частоте fclk/N.
В асинхронном счётчике каждый разряд тактируется предыдущим, поэтому задержки складываются: период тактового сигнала должен быть не меньше n·tpd. Счётчики на сдвиговых регистрах используют меньше состояний: кольцевой счётчик из n триггеров имеет n состояний, счётчик Джонсона — 2n.
Самопроверка 4-разрядный двоичный суммирующий счётчик показывает 13. Какое значение он покажет после ещё 5 тактовых импульсов?
18
2
3
8
Ответ: 2. У 4-разрядного счётчика 16 состояний, и после 15 он переходит к 0: 13 + 5 = 18, а 18 mod 16 = 2. Ответ 18 забывает о переходе через конец счёта.
6Типичные ошибки
Записывать столбцы карты Карно как 00, 01, 10, 11. Порядок — код Грея: 00, 01, 11, 10.
Забывать, что группы переходят через края карты.
Делать группы из 3 или 6 клеток. В группах бывает 1, 2, 4, 8 или 16 клеток.
Покрывать безразличное состояние, которое ничем не помогает: X покрывать необязательно.
Читать группу, оставляя переменные, которые меняются. Оставляйте только те, что остаются постоянными.
Забывать, что счётчик возвращается к началу: n-разрядный счётчик считает по модулю 2ⁿ.
7Как выглядят экзаменационные задачи
Лёгкий: вычислить выход схемы из вентилей для заданных входов, посчитать единицы в её таблице истинности, поставить минтерм на карту Карно, найти число вентилей NAND для функции или наихудшую задержку распространения.
Средний: упростить выражение, найти минимальную форму SOP или POS по карте Карно, функцию на мультиплексоре или изолированную единицу карты.
Сложный: карты с безразличными состояниями, существенные простые импликанты, временные диаграммы триггеров, счётчики после многих импульсов, число триггеров или частоту выхода, а также сдвиговые регистры.
Проверьте упрощённое выражение, подставив одну-две строки таблицы истинности: исходная и упрощённая формы должны давать один и тот же выход.
NAND и NOR — универсальные вентили: любую логическую функцию можно построить только из одного из них. Каково минимальное число N двухвходовых вентилей NAND, нужных для построения показанной функции AND?
F = A·B
Найти: N
Показать подсказки
Вентиль NAND с соединёнными входами — это инвертор.
AND = NAND с последующим инвертором; OR = NAND от инвертированных входов (закон де Моргана).
Считайте каждый вентиль, включая те, что используются как инверторы.
Показать ответ и пошаговое решение
Логические вентили: каждый вход и выход равен 0 или 1. AND даёт 1 только тогда, когда все входы равны 1; OR даёт 1, когда хотя бы один вход равен 1; NOT инвертирует. NAND и NOR — это AND и OR, за которыми следует NOT, а XOR даёт 1, когда входы различаются. Проходите схему от входов к выходу, вентиль за вентилем. Таблица истинности перечисляет выход для всех 2ⁿ комбинаций входов; номер строки — двоичное значение входов, поэтому строка ABC = 101 — это минтерм m₅.
Постройте её из вентилей NAND
Закон де Моргана: A + B = (A′·B′)′, поэтому OR — это NAND от инвертированных входов.
F = A·B = NOT(NAND(A, B))
Посчитайте вентили
N = 2
Ответ
N = 2
Пример 2Средняя
На этой карте Карно ровно у одной единицы нет соседней единицы, поэтому в минимальной форме SOP она остаётся группой из одной клетки (полным минтермом из четырёх литералов). Соседи через края карты учитываются. Нажмите на эту клетку.
F = Σm(0, 3, 4, 10, 13, 14, 15)
1AB = 00, CD = 00
2AB = 00, CD = 01
3AB = 00, CD = 11
4AB = 00, CD = 10
5AB = 01, CD = 00
6AB = 01, CD = 01
7AB = 01, CD = 11
8AB = 01, CD = 10
9AB = 11, CD = 00
10AB = 11, CD = 01
11AB = 11, CD = 11
12AB = 11, CD = 10
13AB = 10, CD = 00
14AB = 10, CD = 01
15AB = 10, CD = 11
16AB = 10, CD = 10
Показать подсказки
Соседние клетки отличаются ровно одной переменной.
Самый левый и самый правый столбцы соседние, как и верхняя и нижняя строки.
Проверьте четырёх соседей (сверху, снизу, слева, справа, с переходом через край) каждой единицы.
Показать ответ и объяснение
Карты Карно: клетки упорядочены по коду Грея (00, 01, 11, 10), поэтому соседние клетки, включая те, что через края, отличаются ровно одной переменной. Группируйте единицы в прямоугольники по 1, 2, 4, 8 или 16 клеток, как можно большие и в как можно меньшем числе, пока не будет покрыта каждая единица. Каждая группа — один член-произведение: переменные, которые внутри неё остаются постоянными. Группа из 2ᵏ клеток теряет k переменных. Безразличные состояния (X) можно использовать, чтобы увеличить группы, но покрывать их не обязательно. Если группировать нули, получится минимальная форма POS.
Соседи каждой единицы
Единица с соседней единицей может войти в группу из двух или более.
m3: m2, m1, m7, m11 → 0
Изолированная единица
m3 = A′B′CD → AB = 00, CD = 11
Ответ
AB = 00, CD = 11
Пример 3Сложная
Синхронный счётчик по модулю 12 считает 0, 1, …, 11, а затем возвращается к 0. Он начинает с 8. Какое значение Q (в десятичном виде) он покажет после 36 тактовых импульсов?
Q0 = 836N = 12
Найти: Q
Показать подсказки
У счётчика 12 состояний, и он повторяется через 12 импульсов.
После k импульсов значение равно (8 + k) mod 12.
36 mod 12 = 0.
Показать ответ и пошаговое решение
Триггеры и счётчики: триггер меняется только по активному фронту тактового сигнала. D копирует свой вход (Q⁺ = D); T переключается при T = 1; JK сохраняет состояние при 00, сбрасывает при 01, устанавливает при 10 и переключает при 11. n-разрядный двоичный счётчик имеет 2ⁿ состояний и считает по модулю 2ⁿ; счётчик по модулю N считает 0, 1, …, N − 1 и возвращается к 0, и ему нужно наименьшее число триггеров n, при котором 2ⁿ ≥ N. Каждый разряд асинхронного счётчика делит частоту пополам, поэтому последний выход счётчика по модулю N работает на частоте fclk/N. У счётчика Джонсона из n триггеров 2n состояний, у кольцевого счётчика n.
Полные циклы
Каждые 12 импульсов возвращают счётчик в то же состояние.
36 = 3·12 + 0
Значение после оставшихся импульсов
Q = (8 + 0) mod 12 = 8
Q = 1000₂
Ответ
Q = 8
Вопросы и ответы
Цифровая логика: вентили, карты Карно и триггеры: что это?
Цифровые схемы работают с двумя значениями: 0 (низкое напряжение, ложь) и 1 (высокое напряжение, истина). Логический вентиль принимает один или несколько входов и выдаёт один выход.
Цифровая логика: вентили, карты Карно и триггеры: как решать задачи шаг за шагом?
Для схемы идите от входов к выходу вентиль за вентилем и записывайте значение на каждом проводе или запишите её выражение и заполните таблицу истинности.
Для упрощения поставьте единицы (и безразличные состояния как X) на карту Карно со строками и столбцами в коде Грея: 00, 01, 11, 10.
Покройте единицы как можно меньшим числом как можно больших групп по 1, 2, 4, 8 или 16 клеток, с переходом через края; каждая группа — один член-произведение из переменных, которые остаются постоянными. Для формы POS группируйте нули.
Для триггеров и счётчиков считывайте входы на каждом активном фронте тактового сигнала, записывайте состояние после каждого фронта и помните, что n-разрядный счётчик возвращается к началу после 2ⁿ состояний.
Цифровая логика: вентили, карты Карно и триггеры: какие ошибки самые частые?
Располагать столбцы карты Карно как 00, 01, 10, 11 вместо кода Грея 00, 01, 11, 10.
Забывать, что группы могут переходить через края, или рисовать группы из 3 или 6 клеток.
Покрывать безразличные состояния, которые не увеличивают группу.
Забывать о возврате счётчика к началу или читать Q₃Q₂Q₁Q₀ в неверном порядке.
Цифровая логика: вентили, карты Карно и триггеры: что вы тренируете?
Лёгкая: вентили, таблицы истинности и задержки
Средняя: булева алгебра, карты Карно и мультиплексоры
Сложная: безразличные состояния, триггеры и счётчики
В каждой задаче новые значения, поэтому вы учите метод, а не ответ. Застряли? Сначала откройте небольшую подсказку, а полное объяснение — только когда оно понадобится.
Как проходят занятия
В каждой задаче новые значения, поэтому вы учите метод, а не ответ.
Застряли? Сначала откройте небольшую подсказку, а полное объяснение — только когда оно понадобится.
Ваш прогресс, ошибки и сохранённые задачи остаются, поэтому перед экзаменом вы сможете всё повторить.