- •Аналоговые и цифровые устройства
- •Устройства аналоговые и цифровые
- •1. История развития электроники и классификация электронных устройств
- •1.1 Арифметические основы эвм
- •1.2 Логические основы эвм
- •1.2.1 Основные положения алгебры логики
- •1.2.2 Логические элементы
- •1.2.3 Законы и тождества алгебры логики
- •3.1 Основные параметры логических элементов
- •3.2 Транзисторно-транзисторная логика
- •3.2.1 Ттл элемент и-не с простым инвертором
- •3.2.2 Ттл элемент со сложным инвертором
- •3.2.3 Элементы ттлш
- •3.2.4 Элементы ттл с тремя выходными состояниями —
- •3.3 Эмиттерно-связанная логика
- •3.4 Транзисторная логика с непосредственными связями (тлнс)
- •3.5 Интегральная инжекционная логика
- •3.6 Логические элементы на моп-транзисторах
- •3.6.1 Логические элементы на ключах с динамической нагрузкой
- •3.6.2 Логические элементы на комплементарных ключах
- •1. Минимизация булевых функций
- •2. Методы минимизации булевых функций
- •2.1 Метод неопределенных коэффициентов
- •2.2. Метод Квайна - Мак - Класки
- •2.3. Метод Петрика
- •2.4. Метод Блека - Порецкого
- •Минимизация логических функций
- •Основы синтеза цифровых устройств
- •2.1 Последовательность операций при синтезе цифровых устройств комбинационного типа
- •2.2 Аналитическая запись логической формулы кцу
- •2.3 Понятие базиса
- •2.4 Минимизация логических формул
- •2.4.1 Расчётный метод минимизации
- •2.4.2 Минимизация неопределённых логических функций
- •2.5 Запись структурных формул в универсальных базисах
- •4 Цифровые устройства комбинационного типа
- •4.1 Двоичные сумматоры
- •4.1.1 Одноразрядные сумматоры
- •4.1.2 Многоразрядные сумматоры
- •4.1.3 Арифметико-логические устройства
- •4.2 Кодирующие и декодирующие устройства
- •4.2.1 Шифраторы
- •4.2.2 Дешифраторы (декодеры)
- •4.3 Коммутаторы цифровых сигналов
- •4.3.1 Мультиплексоры
- •4.3.2 Дешифраторы-демультиплексоры
- •4.4 Устройства сравнения кодов. Цифровые компараторы
- •4.5 Преобразователи кодов. Индикаторы
- •5 Цифровые устройства последовательностного типа
- •5.1 Триггеры
- •5.1.1 Rs-триггеры
- •5.1.2 D-триггеры (триггеры задержки)
- •5.1.3 Триггер т-типа (Счётный триггер)
- •5.1.4 Jk-триггеры
- •5.1.5 Несимметричные триггеры
- •5.2 Регистры
- •5.2.1 Параллельные регистры (регистры памяти)
- •5.2.2 Регистры сдвига
- •5.2.3 Реверсивные регистры сдвига
- •5.2.4. Интегральные микросхемы регистров (примеры)
- •5.3 Счётчики импульсов
- •5.3.1 Требования, предъявляемые к счётчикам
- •5.3.2 Суммирующие счётчики
- •5.3.3 Вычитающие и реверсивные счётчики
- •5.3.4 Счётчики с произвольным коэффициентом счёта
- •5.3.5 Счётчики с последовательно-параллельным переносом
- •5.3.6 Универсальные счётчики в интегральном исполнении (Примеры)
2. Методы минимизации булевых функций
2.1 Метод неопределенных коэффициентов
Метод применим для функций от любого числа переменных, но мы рассмотрим его для функций от 3-х переменных.
Представим в виде ДНФ с неопределенными коэффициентамиk:
(**)
В этой ДНФ представлены все возможные элементарные коньюнкции, которые могут входить в функцию, а коэффициенты kмогут принимать значения 0 или 1. Значения коэффициентов нужно выбрать так, чтобы данная ДНФ была минимальной.
Будем рассматривать данную нам функцию на всех наборах и приравнивать выражение (**) на каждом из наборов (отбрасывая нулевые конъюнкции) соответствующему значению функции. Получим систему изуравнений вида:
Если в каком-то из этих уравнений правая часть равна 0, то все слагаемые левой части тоже равны 0. Эти коэффициенты можно исключить из всех уравнений, правые части которых равны 1. В этих уравнениях значение 1 следует присвоить тому коэффициенту, который соответствует коньюнкции наименьшего ранга. Эти коэффициенты и определят МДНФ.
Пример
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Составляем систему, используя выражение (**).
После исключения нулевых слагаемых получаем
Полагаем остальные коэффициенты считаем нулевыми. Получаем МДНФ:
2.2. Метод Квайна - Мак - Класки
Рассмотренный метод неопределенных коэффициентов эффективен, если число аргументов функции не больше, чем 5 – 6. Это связано с тем, что число уравнений равно 2n. Более эффективным является выписывание не всех возможных конъюнкций для функции, а только тех, которые могут присутствовать в ДНФ данной функции. На этом основан метод Квайна. При этом предполагается, что функция задана в виде СДНФ. В данном методе элементарные конъюнкции рангаn, входящие в ДНф, называются минитермами рангаn. Метод Квайна состоит из последовательного выполнения следующих этапов.
1. Нахождение первичных импликант
Просматриваем последовательно каждый минитерм функции и производим склеивание его со всеми минитермами, с которыми это возможно. В результате склеивания минитермов n-го ранга, мы получим минитермы (n-1)-га ранга. Минитермыn-го ранга, которые участвовали в операции склеивания, помечаем. Затем рассматриваем минитермы (n-1)-го ранга и операцию склеивания применяем к ним. Помечаем склеивающиеся минитермы (n-1)-го ранга и записываем получившиеся в результате склеивания минитермы (n-2)-го ранга и т. д. Этап заканчивается, если вновь полученные минитермыl-го ранга уже не склеиваются между собой. Все неотмеченные минитермы называются первичными импликантами. Их дизъюнкция представляет собой Сокр. ДНФ функции.
Склеиваем минитермы 4-го ранга и помечаем склеивающиеся минитермы звездочками
Образуем минитермы 2-го ранга:
Первичными ( простыми ) импликантами являются:
2. Расстановка меток
Для данной функции Сокр. ДНФ имеет вид:
Для построения тупиковых ДНФ и Сокр. ДНФ нужно выбросить лишние интервалы. Строим таблицу, строки которой соответствуют первичным импликантам, а столбцы – минитермам СДНФ. Если в некоторый из минитерм входит какой-то из импликант, то на пересечении соответствующей строки и столбца ставится метка, например, 1.
Продолжение примера
|
|
|
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
1 |
|
|
|
|
|
1 |
1 |
|
|
|
|
|
|
|
|
|
1 |
1 |
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
1 |
1 |
|
|
|
1 |
1 |
3. Нахождение существенных импликант
Если в каком-либо столбце содержится только одна единица, то первичная импликанта, определяющая эту строку, называется существенной. Например, существенной импликантой является . Существенная импликанта не может быть удалена из Сокр. ДНФ, т. к. только она способна покрыть некоторые минитермы СДНФ. Поэтому из таблицы исключаем строки, соответствующие этим импликантам, и столбцы, имеющие единицы в этих строках.
В рассматриваемом примере исключаем строку и столбцы.
В результате получаем таблицу
|
|
|
|
|
|
1 |
1 |
|
|
|
1 |
|
|
1 |
|
|
1 |
|
|
|
|
|
1 |
1 |
|
|
|
1 |
|
4. Вычеркивание лишних столбцов и строк
Если в полученной таблице есть одинаковые столбцы, то вычеркиваем все, кроме одного. Если после этого в таблице появятся пустые строки, то их вычеркиваем.
5. Выбор минимального покрытия максимальными интервалами
В полученной таблице выбираем такую совокупность строк, которая содержит единицы во всех столбцах. При нескольких возможных вариантах такого выбора, предпочтение отдается варианту с минимальным числом букв в строках, образующих покрытие.
Продолжение примера
Минимальное покрытие таблицы образуют строки, соответствующие импликантам . Тогда МДНФ имеет вид:
В методе Квайна есть одно существенное неудобство, связанное с необходимостью полного по парного сравнивания минитермов на этапе построения Сокр. ДНФ. В 1956 г. Мак - Класки предположил модернизацию первого этапа метода Квайна, дающую существенное уменьшение количества сравнений минитермов.
Идея метода Мак - Класки заключается в следующем. Все минитермы записываются в виде двоичных номеров, например, как 1010. Эти номера разбиваются на группы по числу единиц в номере, т. е. вi-ю группу попадают номера, имеющие в своей записиiединиц. По парное сравнение производится только между соседними по номеру группами, т. к. минитермы, пригодные для склеивания, отличаются друг от друга только в одном разряде. При образовании минитермов с ранга выше нулевого, в разряды, соответствующие исключенным переменным, ставится тире.
Пример
Найдем МДНФ для функции:
Минитермы 4-го ранга по группам
Минитермы 3-го ранга
Минитермы 2-го ранга
Непомеченные минитермы или простые импликанты
Строим таблицу меток
|
1000 |
1001 |
1010 |
1110 |
1011 |
1111 |
10-- |
1 |
1 |
1 |
|
1 |
|
1-1- |
|
|
1 |
1 |
|
1 |
Обе первичные импликанты существенны и определяют минимальное покрытие, т. е. МДНФ имеет вид: