Методы минимизации логических функций
Любая логическая функция может быть записана в различной форме. Различные форм логической функции могут иметь различную сложность, т.е. для их реализации в виде комбинационной схемы может требоваться различное количество логических элементов. Поэтому перед реализацией логической функции должна быть предпринята попытка минимизировать (упростить) эту функцию. Для минимизации могут быть использованы различные методы.
По форме представления логической функции различают следующие методы минимизации:
аналитические методы;
графические методы.
В аналитических методах минимизации логическая функция представляется обычно в СДНФ.
В графических методах логическая функция задается в виде графа или в виде специальной диаграммы. Наиболее известным из графических методов является метод Карно.
Аналитический метод
При аналитическом методе весь процесс минимизации сводится к понижению рангов конъюнкций и уменьшению их числа в функции применением свойств и законов алгебры логики. Выбранный путь минимизации может привести к тупиковому выражению. Тогда выполняют минимизацию другим путем. Затем сравнивают оба результата и выбирается лучший.
Метод Карно
Сущность метода Карно заключается в построении специальных диаграмм, представляющих собой прямоугольные таблицы. Каждой конъюнкции исходной логической функции соответствует одна из клеток таблицы. Главная особенность диаграмм Карно заключается в том, что конъюнкциям, которые могут быть склеены соответствуют соседние по строке или по столбцу клетки.
Диаграмма Карно по каждой переменной делится на две половины. Половина диаграммы, отмеченная соответствующей буквой, содержит все конъюнкции, в которых эта буква записана в прямой форме (без отрицания).
Заполнение диаграмм Карно упрощается при использовании эталонных диаграмм. На эталонной диаграмме клетки помечены номерами соответствующих конъюнкций исходной логической функции. Номера конъюнкций соответствуют двоичным комбинациям входных сигналов в таблице истинности логической функции.
При использовании метода Карно идея заключается в том, что отмеченные клетки диаграммы объединяются в группы по 2, 4 и 8 клеток. Каждая отмеченная клетка должна входить по крайней мере в одну группу. Каждая группа должна содержать только отмеченные клетки. Группы клеток должны образовывать квадраты или прямоугольники. При этом число групп должно быть минимальным.
При объединении двух клеток в одну группу получается одна конъюнкция, ранг которой на одну единицу меньше ранга исходной конъюнкции. При этом полученная конъюнкция не содержит той логической переменной, которая различным образом входит в исходные конъюнкции (без инверсии и с инверсией).
Метод Карно практически можно использовать лишь для минимизации логических функций не более, чем четырех переменных.
- Раздел 1. Теория автоматического управления
- Частотные характеристики систем управления и связь между ними
- Временные характеристики систем управления
- Типовые звенья систем управления
- Интегрирующее звено
- Консервативное звено
- Запаздывающее звено
- Частотные методы оценки устойчивости систем
- Методы построения логариф частотных хар-к
- Законы распределения и числовые характеристики случайных сигналов
- Оценка качества регулир. Показатели качества
- Передаточные функции дискретных су
- Алгебраический критерий устойчивости дискретных систем
- Частотный критерий устойчивости дискретных систем
- Метод гармонич линеариз нелин систем
- Раздел 2. Локальные системы управления
- Особенности математического описания объектов управления. Входные и выходные переменные. Векторы состояния, управления и возмущения. Оператор и переходная функция
- Д атчики систем автоматики
- Устойчивость датчиков к действию высокочастотных помех
- Двигатель постоянного тока как элемент автоматики. Принципиальная схема, основные уравнения движения
- Асинхронный двигатель как элемент автоматики. Структурная схема, передаточная функция, переходные характеристики
- Дискретные законы управления. Математическая модель дискретного управляющего устройства. Импульсные передаточные функции каналов дискретного уу
- Раздел 3. Вычислительные машины, системы
- Принципы построения вычислител машин
- Понятие логической функции. Полностью и неполностью определенные логические функции. Способы задания логических функций
- Комбинационные автоматы. Синтез комбинационных конечных автоматов
- Методы минимизации логических функций
- Модели вычислений. Многоуровневая организация вычислительных процессов
- Прерывания. Шина современных пк
- Типы и основные принципы построения периферийных устройств
- Многомашинные комплексы и многопроцессорные системы
- Управляющие вычислительные комплексы
- Раздел 4. Технические средства обработки текста и изображений
- Методика светоэнергетического расчета лазерного фотовыводного устройства
- Методика расчета параметров лазерных выводных устройств, определ скорость сканирования
- Структура, назначение и принцип работы проявочных машин. Основные системы автоматизации процессов обработки фотоматериалов
- Технические средства анализа и ввода изображения в систему допечатной обработки
- Основные виды, параметры и принцип работы источников и модуляторов лазерного излучения
- Структурная схема, назначение и принцип работы формовыводного устройства (рекордера)
- Основные этапы и характеристики электрофотографического процесса цветной электрофотографии. Структурная схема, назначение устройств и принцип работы аппарата цветной электрографии
- Принцип работы, назначение и разновидности струйных принтеров
- Структурная схема, назначение устройств и принцип работы лазерного принтера (одноцветный вариант)
- Структурная схема, назначение устройств и принцип работы лазерного фотонаборного автомата
- Цифровые печатные машины (цпм). Основные типы цпм и принцип работы
- Раздел 5. Автоматизированное управление полиграфическим производством
- Задачи управления дискретным производством: планирование ассортимента выпуска продукции, транспортная задача
- Симплекс-метод решения задачи линейного программирования. Табличная реализация симплекс-метода в задаче об ассортименте выпускаемой продукции. Алгоритм поиска оптимального плана
- Табличный метод решения транспортной задачи. Использование циклов пересчетов и метода потенциалов при поиске оптимального плана перевозок. Достаточное условие оптимальности
- Информационное обеспечение систем управления. Фактографические базы данных. Типы субд и их характеристики
- Документальные информационные системы, их характеристики. Информационный поиск в документальных системах, оценка полноты и релевантности. Модели поисковых образов
- Методы защиты информации в информационно-управляющих системах. Алгоритмы шифрования данных. Метод открытого ключа. Средства анализа защищенности компьютерных сетей