Цифровая схемотехника. Синтез произвольных комбинаторных схем

Произвольная таблица истинности
Как построить схему?

ДНФ
Дизъюнктивная Нормальная Форма
Событие 1
Событие 2
Событие 4
Событие 5
Событие 7
События приводящие к 1 на выходе
ИЛИ

ДНФ
События приводящие к 1 на выходе
Что делать, если на вход поступят другие слова то же приводящие к 1?

ДНФ
Надо их превратить в 111
События, приводящие к 1 на выходе

ДНФ
Дизъюнктивная Нормальная Форма
Bus
Wire
Input Ports
Output Port

КНФ
Конъюнктивная Нормальная Форма
Событие 0
Событие 3
Событие 6
События приводящие к 0 на выходе
И

КНФ
Конъюнктивная Нормальная Форма
Событие 0
Событие 3
Событие 6
События приводящие к 0 на выходе

ДНФ vs КНФ
Множество решений!
В нашем случае ДНФ короче чем КНФ.
Но всегда будем выбирать ДНФ.
К555ЛР13 (74LS54)
(с точностью до инверсии выхода)
Древняя микросхема
КНФ

ДНФ vs КНФ
ДНФ
КНФ
Но КНФ у нас короче и схема проще.
Нулей меньше чем единиц.
ДНФ по 0
Можно вполне обойтись только ДНФ
Нули всегда можно превратить в единицы инверсией.

Карты Карно
Можно ли еще сократить?
Морис Карно
Maurice Karnaugh
1953 Bell Labs
Можно как и задачи по алгебре

Карты Карно. 2 переменные.
Представление функции
Таблица
Алгебраическое выражение
График
Карты Карно

Карты Карно. 2 переменные.
Для логических переменных все проще.

Карты Карно. 2 переменные.
Выходное значение не зависит от входных переменных

Карты Карно. 2 переменные.
Координата группы
Если I1=0, то Q=1 независимо от I0

Карты Карно. 2 переменные.
Координата группы
Если I1=0, то Q=1 независимо от I0
Координата группы
(2NAND)
Если I0=0, то Q=1 независимо от I1

Карты Карно. 2 переменные.
(XOR)
Это НЕ группа.
Координату записать невозможно!
Не упрощается.

Карты Карно. 3 переменные.
Соседние клеточки отличаются только одной переменной

Карты Карно. 3 переменные.

Карты Карно. 3 переменные.
В группе должно быть 2n клеточек
Группа должна быть компактной

Карты Карно. 3 переменные.

Карты Карно. 4 переменные.
Соседние клеточки отличаются только одной переменной

Карты Карно. 4 переменные.

Карты Карно. 5 переменных.

Карты Карно. 5 переменных.
Программы

Недоопределенные таблицы истинности.
Пример: на комбинаторный преобразователь подается двоично-десятичный код
Двоично-десятичный код
Таких входных слов быть не может
Здесь 0 и 1 в зависимости от задачи
Что написать здесь?

Недоопределенные таблицы истинности.
Пример: на комбинаторный преобразователь подается двоично-десятичный код
Здесь 0 и 1 в зависимости от задачи
X – безразличное состояние

Недоопределенные таблицы истинности.
X
X
X
X
X
X
0
1
1
1
1
0
0
0
0
Пример:
Что делать с X?
0