3.12.2.2 Минимизация ПФ с помощью карт Карно
На рисунке 3.5 показан пример карты Карно для ПФ четырех переменных (n=4).
Рисунок 3.5
Каждая клетка в картах Карно так же, как и в диаграммах Вейча соответствует определенному набору переменных. Соседние клетки соответствуют наборам, отличающимся значением одной из переменных. Каждая строка и столбец обозначаются значением конкретной переменной или комбинацией (произведением) переменных в прямой или инверсной форме.
Клетки, помеченные переменными в прямой форме, соответствуют наборам, где эти переменные принимают единичные значения, а клетки, обозначенные переменными в инверсной форме - наборам, где эти переменные равны нулям.
Карты Карно удобно использовать, если ПФ задана в виде булевого выражения в СДНФ.
Например,
(3.14)
Правила минимизации с помощью карт Карно в основном аналогичны правилам, изложенным при рассмотрении диаграмм Вейча. Отличие состоит в заполнении карты Карно единицами. Если диаграмма Вейча заполняется единицами в соответствии с номерами наборов, на которых исходная ПФ принимает единичное значение, то в карте Карно единицы ставят в клетки, лежащие на пересечении строк и столбцов карты, помеченных комбинациями переменных, которые при их перемножении дают запись соответствующей конституенты единицы (конъюнкции) в булевом выражении минимизируемой функции (3.14). На рисунке 3.5 показан пример заполнения карты Карно по выражению (3.14), содержащему шесть конституент единиц.
Булево выражение минимизированной ПФ имеет вид
.(3.15)
Другие примеры использования диаграмм Вейча и карт Карно показаны в [3, 18].
- 1. ВВЕДЕНИЕ
- 2. ДИСКРЕТИЗАЦИЯ АНАЛОГОВЫХ СИГНАЛОВ
- 2.1 Квантование по уровню
- 2.2 Квантование по времени
- 2.3 Квантование по уровню и по времени
- 2.3.1 Расчет погрешности АЦП
- 2.3.2 Выбор величины шага квантования по времени
- 3. ПРИМЕНЕНИЕ АЛГЕБРЫ ЛОГИКИ (БУЛЕВОЙ АЛГЕБРЫ) ПРИ АНАЛИЗЕ И СИНТЕЗЕ ЦИФРОВЫХ ЭЛЕКТРОННЫХ УСТРОЙСТВ
- 3.1 Определение и способы задания переключательных функций
- 3.2 Переключательные функции одной переменной (n=1)
- 3.3 Переключательные функции двух переменных (n=2)
- 3.4 Базисные логические функции
- 3.5 Принцип двойственности булевой алгебры
- 3.6 Основные тождества булевой алгебры
- 3.7 Основные законы и теоремы булевой алгебры
- 3.7.1 Законы
- 3.7.2 Теоремы
- 3.8 Совершенная дизъюнктивная нормальная форма (СДНФ) записи булевых выражений
- 3.10 Совершенная конъюнктивная нормальная форма (СКНФ) записи булевых выражений
- 3.11 Конъюнктивная нормальная форма (КНФ)
- 3.12 Минимизация логических функций
- 3.12.1 Алгебраический способ минимизации ПФ
- 3.12.2 Минимизация ПФ с использованием диаграмм Вейча (карт Карно)
- 3.12.2.1 Минимизация ПФ с помощью диаграмм Вейча
- 3.12.2.1.1 Общие правила минимизации
- 3.12.2.1.2 Примеры минимизации ПФ с помощью диаграмм Вейча
- 3.12.2.2 Минимизация ПФ с помощью карт Карно
- 4. ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ
- 4.1 Инвертор (логический элемент НЕ)
- 4.2 Конъюнктор (логический элемент И)
- 4.3 Дизъюнктор (логический элемент ИЛИ)
- 4.4 Повторитель
- 4.5 И-НЕ
- 4.6 ИЛИ-НЕ
- 4.7 Исключающее ИЛИ
- 4.8 Сложение по модулю два (нечетность)
- 4.9 Сложение по модулю два с отрицанием (четность)
- 4.10 Эквивалентность
- 4.11 Неэквивалентность
- 4.12 И-ИЛИ-НЕ