Булевы выражения. Глава 2

Логическая схема состоит из:
Входов
Выходов
Функциональной спецификации
Временной спецификации
Введение

Узлы
Входы: A, B, C
Выходы: Y, Z
Внутренний узел: n1
Элементы схемы
E1, E2, E3
Каждый их них, в свою очередь, является схемой
Схемы

Комбинационные цифровые схемы
Не имеют памяти
Выход определяется текущим состоянием входов
Последовательностные цифровые схемы
Имеют память
Выход определяется текущим и предыдущим состоянием входов
Типы цифровых схем

Каждый элемент сам является комбинационным
Каждое узел схемы является или входом, или подсоединен к одному-единственному выходу другого элемента
Схема не содержит циклических путей
Пример:
Правила комбинационной композиции

Функциональная спецификация выходов по значениям входов
Пример: S = F(A, B, Cin)
Cout = F(A, B, Cin)
Булевы выражения

Дополнение: переменная с чертой над именем
A, B, C
Литерал: переменная или ее дополнение
A, A, B, B, C, C
Импликанта: произведение литералов
ABC, AC, BC
Минтерм: произведение, в которое входят литералы всех входных переменных
ABC, ABC, ABC
Макстерм: сумма, в которую входят литералы всех входных переменных
(A+B+C), (A+B+C), (A+B+C)
Некоторые определения

Y = F(A, B) =
Все выражения могут быть записаны в дизъюнктивной форме
Каждой строке соответствует минтерм
Минтерм является произведением (И, AND) литералов
Каждый минтерм становится ИСТИННЫМ только для своей строки
Функция записывается путем суммирования минтермов тех строк, для которых выход равен ИСТИНЕ
Таким образом, формируется сумма (ИЛИ, OR) произведений (И, AND)
Дизъюнктивная форма

Y = F(A, B) =
Дизъюнктивная форма
Все выражения могут быть записаны в дизъюнктивной форме
Каждой строке соответствует минтерм
Минтерм является произведением (AND) литералов
Каждый минтерм становится ИСТИННЫМ только для своей строки
Функция является суммой минтермов тех строк, для которых выход равен ИСТИНЕ
Таким образом, формируется сумма (ИЛИ, OR) произведений (И, AND)

Y = F(A, B) = AB + AB = Σ(1, 3)
Дизъюнктивная форма
Все выражения могут быть записаны в дизъюнктивной форме
Каждой строке соответствует минтерм
Минтерм является произведением (И, AND) литералов
Каждый минтерм становится ИСТИННЫМ только для своей строки
Функция записывается путем суммирования минтермов тех строк, для которых выход равен ИСТИНЕ
Таким образом, формируется сумма (ИЛИ, OR) произведений (И, AND)

Y = F(A, B) = (A + B)(A + B) = Π(0, 2)
Все булевы выражения могут быть записаны в конъюнктивной форме
Каждой строке соответствует макстерм
Макстерм является суммой (ИЛИ, OR) литералов
Каждый макстерм становится ЛОЖНЫМ только для своей строки
Функция является произведением макстермов тех строк, для которых выход равен ЛОЖЬ
Таким образом, формируется произведение (И, AND) сумм (ИЛИ, OR)
Конъюнктивная форма

Вы собираетесь в кафетерий пообедать
Вы не пообедаете (E)
Там закрыто (не открыто, O) или
Они предлагают только корн-доги (C)
Запишите таблицу истинности, по которой можно определить пообедаете ли вы (E)
Примеры булевых выражений

Вы собираетесь в кафетерий пообедать
Вы не пообедаете (E)
Там закрыто (не открыто, O) или
Они предлагают только корн-доги (C)
Запишите таблицу истинности, по которой можно определить пообедаете ли вы (E)
Примеры булевых выражений

Дизъюнктивная форма (SOP, sum-of-products) сумма (ИЛИ) произведений (И)
Конъюнктивная форма (POS, product-of-sums) - произведение (И) сумм (ИЛИ)
Дизъюнктивная и конъюнктивная формы

Дизъюнктивная форма (SOP, sum-of-products) сумма (ИЛИ) произведений (И)
Конъюнктивная форма (POS, product-of-sums) - произведение (И) сумм (ИЛИ)
Y = (O + C)(O + C)(O + C)
= Π(0, 1, 3)
Y = OC
= Σ(2)
Дизъюнктивная и конъюнктивная формы

Аксиомы и теоремы позволяют упрощать булевы выражения
Подобно обычной алгебре, но проще: переменные принимают только два значения (0 или 1)
Двойственность аксиом и теорем:
Можно взаимно заменить И и ИЛИ, 0 и 1
Булева алгебра

Булевы аксиомы

B 1 = B
B + 0 = B
T1: Теорема идентичности

B 1 = B
B + 0 = B
T1: Теорема идентичности

B 0 = 0
B + 1 = 1
T2: Теорема о нулевом элементе

B 0 = 0
B + 1 = 1
T2: Теорема о нулевом элементе

B B = B
B + B = B
T3: Теорема об идемпотентности

B B = B
B + B = B
T3: Теорема об идемпотентности

B = B
T4: Теорема идентичности

B = B
T4: Теорема идентичности

B B = 0
B + B = 1
T5: Теорема о дополнительности

B B = 0
B + B = 1
T5: Теорема о дополнительности

Булевы теоремы, обзор

Булевы теоремы нескольких переменных

Y = AB + AB
Упрощение булевых выражений
Пример 1:

Y = AB + AB
= B(A + A) T8
= B(1) T5’
= B T1
Упрощение булевых выражений
Пример 1:

Y = A(AB + ABC)
Пример 2:
Упрощение булевых выражений

Y = A(AB + ABC)
= A(AB(1 + C)) T8
= A(AB(1)) T2’
= A(AB) T1
= (AA)B T7
= AB T3
Пример 2:
Упрощение булевых выражений

Y = AB = A + B
Y = A + B = A B
Теорема де Моргана

Назад:
Изменить тип элемента
Добавить инверсию на входы
Вперед:
Изменить тип элемента
Добавить инверсию на выход
Перемещение инверсии

Запишите булево выражение для этой схемы
Перемещение инверсии

Запишите булево выражение для этой схемы
Y = AB + CD
Перемещение инверсии

Начать с выхода и двигаться в направлении входов
Перемещать инверсию от выходов ко входам
Нарисовать элементы так, чтобы увидеть, что инверсии взаимно уничтожаются
Правила перемещения инверсии

Пример перемещения инверсии

Пример перемещения инверсии

Пример перемещения инверсии

Пример перемещения инверсии

Двухуровневая цифровая схема Сначала элементы И, затем ИЛИ
Пример: Y = ABC + ABC + ABC
От логики к логическим элементам

Входы слева (или сверху)
Выходы справа (или внизу)
Информация передается от элементов, расположенных слева, к элементам, расположенным справа
Для проводников стараться использовать прямые линии
Правила изображения принципиальных схем

Проводники всегда должны соединяться в виде буквы Т
Точка в месте пересечения проводников обозначает их соединение
Проводники, пересекающиеся без точки, не имеют соединения друг с другом
Правила изображения принципиальных схем (продолжение)

Пример: Схема приоритета
Выход устанавливается
в соответствии
со старшим разрядом
который равен ИСТИНЕ
Схемы с несколькими выходами

Пример: Схема приоритета
Выход устанавливается
в соответствии
со старшим входом
который равен ИСТИНЕ
Схемы с несколькими выходами

Реализация схемы приоритета

Безразличное значение

Конфликтом: схема пытается установить на выходе одновременно 0 и 1
Действительное значение находится где-то между
Может быть 0, 1 или в запрещенной диапазоне
Может зависеть от напряжения, температуры, времени, шума
Часто вызывает большое энергопотребление
Предупреждение:
Конфликт обычно является ошибкой
В зависимости от контекста X обозначает безразличное значение или конфликт
Конфликт: X

Третье состояние, состояние высокого импеданса, неподключенная или плавающая цепь
Состояние неподключенного выхода может быть 0, 1 или быть промежуточным
Вольтметр не показывает что узел находится в плавающем состоянии
Буфер с тремя состояниями
Третье состояние: Z

Состояние высокого импеданса используется для создания шин
Несколько микросхем подключены к шине
Но активной в некоторый момент может быть одна и только одна
Шины с тремя состояниями

Булевы выражения можно упростить путем комбинирования термов
Карты Карно позволяют наглядно минимизировать выражение
PA + PA = P
Карты Карно

Обведите овалом 1 в соседних квадратах
В булево выражение включаются только те литералы, прямая и инверсная форма которых не попадает в овал
Y = AB
Карты Карно

Карты Карно - три входа

Y = AB + BC
Карты Карно - три входа

Дополнение: переменная с чертой над именем
A, B, C
Литерал: Литерал: переменная или ее дополнение
A, A, B, B, C, C
Импликанта: произведение литералов
ABC, AC, BC
Первичная импликанта: импликанта, соответствующая наибольшему овалу на карте Карно
Построение карты Карно

Каждая 1 должна входить хотя бы в один овал
Каждый овал должен охватывать блок, число клеток которого в каждом направлении равно степени двойки (то есть 1, 2 или 4)
Каждый овал должен настолько большим, насколько это возможно
Овал может связывать края карты Карно
Безразличные значения (X) могут входить в овал, если это помогает минимизировать выражение
Правила карт Карно

Карты Карно - четыре входа

Карты Карно - четыре входа

Карты Карно - четыре входа

Карты Карно и безразличные значения

Карты Карно и безразличные значения

Карты Карно и безразличные значения

Мультиплексоры
Дешифраторы
Базовые комбинационные блоки

Выбирает один из N входов и соединяет его с выходом
log2N-бит для выбора входа – вход управления (выбора)
Пример: 2:1 Mux
Мультиплексор (Mux)

2-<>
Используя логические элементы
Дизъюнктивная форма
Используя буферы с тремя состояниями
Для N-входового мультиплексора используется N буферов с тремя состояниями
Один и только один их них включается для выбора соответствующего входа
Реализация мультиплексоров

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

Уменьшение размера мультиплексора
Цифровые схемы на основе мультиплексоров

N входов, 2N выходов
Прямой унитарный код: только один выход принимает значение ИСТИНА
Дешифраторы

Реализация дешифраторов

Функция ИЛИ от минтермов
Цифровые схемы на основе дешифраторов

Задержка между изменением входа и соответствующим изменением выхода
Как проектировать быстрые схемы?
Временные характеристик

Задержка распространения tpd = максимальная задержка тракта вход-выход
Задержка реакции tcd = минимальная задержка тракта вход-выход
Задержки распространения и реакции

Задержки обусловлены
Емкостями и сопротивлениями в цепях
Конечностью скорости света
Причины, по которым tpd и tcd могут различаться
Разные задержки нарастания и спада сигнала
Несколько входов и выходов, одни из которых быстрее, чем другие
Замедление работы схемы при повышении температуры и ускорение при охлаждении
Задержки распространения и реакции

Критический (длинный) путь tpd = 2tpd_AND + tpd_OR
Кратчайший путь tcd = tcd_AND
Критический (длинный) и кратчайший пути

Одиночное изменение на входного сигнала вызывает несколько изменений сигнала на выходе
Импульсные помехи

Что происходит когда A = 0, C = 1, а B изменяется с 1 до 0?
Пример импульсной помехи

Пример импульсной помехи (продолжение)

Борьба с импульсными помехами