- •Часть 2
- •8.091501–«Компьютерные системы и сети» и
- •7.091503–«Специализированные компьютерные системы»
- •Содержание
- •Введение
- •1 Основные понятия и определения алгебры логики и цифрового конечного автомата
- •1.1 Основные определения алгебры логики
- •1.2 Конечный автомат
- •1.3 Основные логические операции
- •1.3.1 Операция отрицания
- •1.3.2 Операция логического умножения
- •1.3.3 Операция логического сложения
- •1.3.4 Операция эквиваленция
- •1.3.5 Операция импликация
- •1.3.6 Сумма по модулю 2
- •1.3.7 Штрих Шеффера
- •1.3.8 Стрелка Пирса
- •2 Зависимость состава функций от числа переменных
- •2.1 Состав функций при отсутствии входных переменных
- •2 .2 Функции одной переменной
- •2.3 Функции двух переменных
- •2.4 Действительные и фиктивные функции
- •2.5 Определение общего числа функций
- •3 Суперпозиция функций
- •3.1 Методы суперпозиции
- •3.2 Выражение одних элементарных функций через другие
- •4 Свойства законов и правила алгебры логики
- •4.1 Свойства операций конъюнкции, дизъюнкции и отрицания
- •4.2 Свойства суммы по модулю 2, импликации, функции Шеффера и Пирса
- •5.1.1 Представление лф в совершенной дизъюнктивной нормальной форме
- •5.1.2 Дизъюнктивная нормальная форма лф
- •5.1.3 Представление лф в совершенной конъюнктивной нормальной форме
- •5.2 Основные свойства и алгоритм получения сднф, скнф
- •5.2.1 Общие свойства сднф
- •5.2.2 Алгоритм записи сднф
- •5.2.3 Свойства скнф
- •5.2.4 Алгоритм записи скнф
- •5.3 Способы преобразования днф и кнф в сднф и скнф
- •6 Полные системы функций
- •6.1 Функционально полные базисы
- •6.2 Теорема Поста
- •7 Методы минимизации функций алгебры логики
- •7.1 Аналитический метод минимизации фл
- •7.2 Числовое и геометрическое представление фл
- •7.3 Минимизация фл с помощью комплекса кубов
- •7.3.1 Построение комплекса кубов и его минимального покрытия
- •7.3.2 Цена покрытия кубов
- •7.4 Метод неопределенных коэффициентов
- •8 Метод квайна-мак-класки
- •9 Метод минимизации фл с помощью карт карно
- •9.1 Правила минимизации по картам Карно
- •9.1.1 Соседние клетки
- •9.1.2 Правило объединения соседних клеток
- •9.1.3 Определение простых импликант
- •9 .2 Не полностью определенные логические функции в картах Карно
- •10 Анализ и структурный синтез цифровых автоматов
- •10.1 Задачи анализа и синтеза
- •10.2 Синтез элементов логических схем
- •10.3 Особенности схем логических элементов
- •10.3.1 Базовый логический элемент
- •10.3.2 Элемент с открытым коллектором
- •10.3.3 Элементы и - или – не и расширители
- •10.3.4 Трисабильные элементы
- •10.4 Временные параметры логических микросхем
- •10.5 Переходные процессы в логических схемах микросхем
- •11 Комбинационные схемы
- •11.1 Построение преобразователя кодов
- •11.2 Сумматоры
- •11.3 Временные логические функции
- •12 Способы задания цифровых конечных автоматов
- •12.1 Математические модели ца
- •12.2 Табличный способ задания ца
- •12.3 Задание цифрового автомата графом
- •12.4 Минимизация абстрактных автоматов
- •13 Методы структурного синтеза автоматов
- •13.1 Канонический метод синтеза автомата
- •13.1.1 Пример синтеза ца каноническим методом
- •13.2 Структурный синтез ца по методу графа автомата
- •13.3 Метод синтеза ца по граф–схеме алгоритма
- •13.4 Синтез автомата с жесткой логикой управления
- •13.4.1 Принцип работы микропрограммного автомата с жесткой логикой управления
- •13.4.2 Проектирование микропрограммного автомата с жесткой логикой управления
- •14 Язык задания поведения цу - vhdl и синтезатор leonardo
- •15 Программируемые логические матрицы
- •16 Схемы основных логических устройств
- •16.1 Элементы памяти последовательностных логических схем
- •16.1.1 Триггер
- •16.1.1.1 Асинхронный rs - триггер
- •16.1.1.2 Синхронный rs - триггер
- •16.1.2 Универсальный jk-триггер
- •16.2 Регистры
- •16.2.1 Параллельные и последовательные регистры
- •16.2.2 Реверсивный регистр сдвига
- •Список литературы
9.1.3 Определение простых импликант
Каждый отдельный контур объединения соответствует минтерму, который иначе называют простой импликантой. Для определения и записи простой импликанты, прямо по карте Карно, проводится анализ переменных по тем строчкам и столбцам карты, которые пересекают контур объединенных 1 (вершин куба). Начинают анализ с первой переменной Х1.
Если переменная Х1 в любой строчке(столбце), проходящей через контур, не изменяет значения своей координаты (т.е. во всех строчках контура ее значение либо 0, либо 1), то в минтерм объединения записывается ее значение (либо 0, либо1).
Если переменная Х1 в строчках (столбцах), проходящих через контур, изменяет значение своей координаты (т.е. в одной строчке контура ее значение 0, а в другой 1, либо наоборот), то в минтерм объединения записывается, так называемая, неопределенная переменная Х на том месте, где должно записываться значение переменной Х1 (рисунок 9.1д,е,ж). Аналогичный анализ проводится последовательно для всех переменных, в результате чего получаем минтерм объединения. На рисунке 9.1д,е,ж они расположены на выносках.
Это первый этап записи минимальной логической функции прямо с карты Карно. На втором этапе меняем значения переменных на соответствующие им переменные по правилу: если значение переменной 0 – то пишем , если 1 – то пишем Хі. На месте неопределенной переменной Х не пишем ничего, т. е. это место опускаем. Тепер соединив все минтермы знаком дизъюнкции, получим минимальную дизъюнктивную нормальную форму логической функции (МДНФ).
При построении минимальной формы для конъюнкции, карты Карно заполняются 0, т.е. минтермами тех наборов, на которых функция равна нулю. Объединение нулей и запись МДНФ для не функции, т.е. выполняют по тем же правилам. Затем, применив к левой и правой части равенства правило де-Моргана и преобразовав дизъюнкцию правой части в конъюнкцию, получим минимальную конъюнктивную нормальную форму (МКНФ) логической функции. Таким образом, минимальное покрытие выбирается интуитивным путем на основе анализа различных вариантов покрытий (контуров объединений) минимизируемой функции.
Покрытие с минимальной ценой формируется, если каждая существенная вершина будет покрыта кубом с наибольшим числом независимых переменных, а для покрытия всех существенных вершин будет использовано наименьшее число кубов.
Наилучшим считается такое покрытие, где минимум контуров объединения. Если вариантов много, то выбирается тот, который дает максимальную суммарную площадь контуров (прямоугольников). Качество минимизации оценивается по коэффициенту покрытия
k = m / s,
где m - количество прямоугольников, s - их площадь. Покрытие лучше, чем меньше k.
В качестве примера использования карт Карно для определения минимальных ДНФ и КНФ рассмотрим функцию, представленную на рисунке 9.2.
Данной ДНФ (рисунок 9.2 а) соответствует минимальная форма вида:
f= +x1 x4+x2x3.
Нулевые значения этой функции представлены на рисунке 9.2б. Отмеченные на карте клетки определяют функцию , обратную f.
При минимизации функции , получаем
= x2 +x1 + x3.
Используя правило де Моргана, преобразуем в КНФ:
f= =(x1+ +x3)( +x3+x4)(x2+ ). При пяти и более переменных строят комбинированную карту, состоящую из совокупности простых, например четырехмерных. Тогда сначала находят минимальные формы внутри четырехмерных карт, а затем, расширяя понятие соседних клеток, отыскивают минимальные термы для совокупности карт. На рисунке 9.3 показаны карты для 5 и 6 переменных.