- •И. В. Потапов элементы прикладной теории цифровых автоматов
- •Оглавление
- •Введение
- •1. Представление чисел в эвм
- •1.1. Позиционные системы счисления
- •1.2. Обоснование применения в эвм двоичной системы счисления
- •1.3. Представление двоичных чисел с фиксированной и плавающей запятой
- •1.4. Прямой и инверсные коды чисел
- •1.5. Двоично-десятичные коды чисел
- •Вопросы для самоконтроля
- •2. Арифметические операции в двоичных кодах
- •2.1. Сложение двоичных кодов
- •2.2. Вычитание двоичных кодов
- •2.3. Выполнение операции округления чисел
- •2.3.1. Округление прямых кодов
- •2.3.2. Округление инверсных кодов
- •2.4. Умножение двоичных кодов
- •2.4.1. Умножение прямых кодов чисел
- •2.4.2. Ускоренное выполнение операции умножения
- •2.4.3. Умножение инверсных кодов чисел
- •2.5. Деление двоичных кодов
- •2.5.1. Деление прямых кодов чисел
- •2.5.2. Ускоренное выполнение операции деления
- •2.5.3. Деление дополнительных кодов чисел
- •2.6. Извлечение квадратного корня
- •2.7. Выполнение арифметических операций в d-кодах
- •2.7.1. Сложение в d-кодах
- •2.7.2. Умножение в d-кодах
- •2.7.3. Деление в d-кодах
- •Вопросы для самоконтроля
- •3. Переключательные функции
- •3.1. Основные определения и способы задания пф
- •3.2. Элементарные логические функции
- •3.3. Основные законы алгебры логики
- •3.4. Полные системы переключательных функций
- •3.5. Канонические формы аналитического представления пф
- •3.6. Кубическое представление пф
- •3.7. Синтез комбинационных схем
- •3.7.1. Синтез кс на логических элементах
- •3.7.2. Синтез кс на дешифраторах
- •3.7.3. Синтез кс на мультиплексорах
- •3.7.4. Синтез многовыходных схем
- •3.8. Риски сбоя в комбинационных схемах
- •Вопросы для самоконтроля
- •4. Минимизация переключательных функций
- •4.1. Минимизация пф с помощью карт Карно
- •4.2. Минимизация пф методом Квайна
- •4.3. Минимизация методом Квайна – Мак-Класки
- •4.4. Минимизация пф методом Блейка – Порецкого
- •4.5. Минимизация пф, заданных в конъюнктивной форме
- •4.6. Минимизация не полностью определенных пф
- •4.7. Минимизация систем пф
- •4.8. Минимизация пф в универсальных базисах и-не, или-не
- •Вопросы для самоконтроля
- •5. Моделирование работы и синтез автоматов с памятью
- •5.1. Основные модели, понятия и определения
- •5.1.1. Общее понятие цифрового автомата с памятью
- •5.1.2. Основные модели цифровых автоматов
- •5.1.3. Описание функционирования цифровых автоматов
- •5.1.4. Задание цифровых автоматов
- •5.1.5. Правила перехода между моделями Мили и Мура
- •5.2. Минимизация числа состояний цифровых автоматов
- •5.2.1. Минимизация числа состояний синхронного автомата методом Полла-Ангера
- •5.2.2. Минимизация числа состояний автомата Мура методом l-эквивалентных разбиений
- •5.2.3. Минимизация числа состояний автомата Мили методом l-эквивалентных разбиений
- •5.3. Структурный синтез цифровых автоматов
- •5.3.1. Типы элементарных автоматов, обладающие полной системой переходов-выходов
- •5.3.2. Основные этапы структурного синтеза
- •5.4. Рациональный выбор варианта кодирования состояний синхронных автоматов
- •Вопросы для самоконтроля
- •Библиографический список
- •Задания для выполнения самостоятельных работ
- •Илья Викторович потапов, канд. Техн. Наук, доцент элементы прикладной теории цифровых автоматов
4.1. Минимизация пф с помощью карт Карно
Карта Карно (диаграмма Вейча) для функции представляет собой прямоугольную таблицу, состоящую из 2n клеток, где каждой строке (столбцу) или группе строк (столбцов) соответствует прямое или инверсное значение одной из переменных. Каждой клетке такой таблицы ставится в соответствие набор аргументов функции. В клетке карты Карно записывается единица, если функция на соответствующем этой клетке наборе принимает значение 1, в противном случае в соответствующую клетку записывается 0. Таким образом, карта Карно является разновидностью таблицы истинности булевой функции.
В табл. 4.2–4.5 приведены карты Карно в общем виде для функций двух, трех, четырех и пяти аргументов. В ячейках этих карт Карно записаны соответствующие им наборы аргументов.
Таблица 4.2
Таблица 4.3
Таблица 4.4
Карты Карно для функций большего числа аргументов строятся аналогичным образом. При этом в любой карте Карно соседние наборы, отличающиеся значением только одной переменной, находятся в соседних клетках. Крайние столбцы и строки карты Карно также содержат соседние наборы.
Метод минимизации ПФ с помощью карт Карно основан на так называемой операции полного склеивания: . При этом говорят, что два дизъюнктивных члена склеиваются по переменной . Таким образом, соседние наборы склеиваются по одной из переменных.
Общее правило склеивания на картах Карно можно сформулировать следующим образом: склеиванию подлежат совокупности соседних ячеек, содержащих одинаковые значения заданной ПФ, общее число которых кратно , . Результатом такого склеивания является элементарное произведение переменных, значения которых не изменялись на всех склеиваемых наборах.
Для получения минимальной ДНФ по карте Карно необходимо выполнить следующие действия.
Определить совокупности соседних ячеек с единичным значением функции. Необходимо стремиться объединить в одну совокупность как можно большее количество соседних ячеек карты, а общее число совокупностей должно быть минимальным. При этом некоторые единицы уже выделенных совокупностей могут участвовать в формировании других совокупностей соседних ячеек.
Определить элементарные произведения, получающиеся путем склеивания соседних ячеек, определенных на предыдущем шаге.
Записать минимальную ДНФ функции как дизъюнкцию полученных элементарных конъюнкций.
Рассмотрим несколько примеров минимизации по картам Карно.
Пример 1. Минимизировать с помощью карты Карно ПФ, заданную следующим выражением:
Карта Карно для этой функции имеет вид, представленный в табл. 4.6.
Таблица 4.6
|
x2
|
|
|
|
x1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
|
|
|
x3 |
|
Прямоугольниками обозначены совокупности соседних ячеек, выделяемых для операции склеивания. Единица в ячейке (крайний правый столбец) может объединяться с единицей , поскольку эти две ячейки являются соседними.
Для определения результатов склеивания достаточно записать элементарные произведения переменных, которые накрывают выделенные совокупности ячеек. Из табл. 4.5 следует, что совокупность из четырех единиц (наборы , , , ) может быть накрыта только переменной , а остальные две переменные накрывают только часть этой совокупности, поэтому первым элементарным произведением будет . Вторая выделенная совокупность соседних ячеек (наборы , ) может быть накрыта элементарным произведением , поскольку эти две ячейки расположены в строке, отмеченной переменной , и столбцы, соответствующие этой совокупности ячеек, отмечены инверсным значением переменной .
Таким образом, минимальная ДНФ для заданной функции имеет вид
Рассмотрим еще несколько примеров получения минимальной ДНФ по карте Карно. При этом будем задавать исходные ПФ в виде карт Карно, так как процедура перехода от СДНФ к карте и наоборот выполняется элементарно. Также для простоты будем записывать в ячейки только единичные значения функции, а ячейки с нулевыми значениями будем оставлять незаполненными.
Пусть минимизируемая функция задана картой Карно (табл. 4.7).
Таблица 4.7
|
x2
|
|
|
|
|
x1 |
1 |
1 |
1 |
|
|
1 |
|
|
1 |
x3 |
|
|
1 |
|
|
|
|
|
1 |
1 |
1 |
|
|
|
|
x4 |
|
|
Поскольку минимальное число совокупностей соседних ячеек, объединяющих все единицы исходной функции, равно трем, минимальная ДНФ для функции, заданной табл. 4.6, включает в себя три слагаемых:
.
Пусть минимизируемая функция задана картой Карно (табл. 4.8).
Таблица 4.8
|
x2
|
|
|
|
|
x1 |
|
|
|
1 |
|
1 |
1 |
1 |
|
x3 |
|
|
1 |
1 |
1 |
|
|
|
|
|
1 |
|
|
|
|
x4 |
|
|
Поскольку единица в ячейке не имеет подходящих для склеивания соседей, она входит в минимальную ДНФ в виде элементарного произведения всех четырех аргументов:
.